3
\$\begingroup\$

How can I re-factorise this circular nesting dictionary function?

The challenge:

I recently received a data extract with a list of folder names and associated subfolders. The challenge was to produce a reusable function that could provide a summary of the unique folder names and all the nested subfolders.

The data source was an excel spreadsheet containing 2 columns:

Parent: Folder name

Child: Subfolder name

Note: I have recreated spreadsheet data using pandas so the code can be easily tested.

Create table:

import pandas as pd

data = {'Parent': ['A', 'B', 'C', 'D', 'E', 'F', 'C', 'C'],
        'Child': ['B', 'C', 'E', 'E', 'Z', 'Z', 'B', 'A']}

df = pd.DataFrame(data)

print(df):

Parent  Child
0   A   B
1   B   C
2   C   E
3   D   E
4   E   Z
5   F   Z
6   C   B
7   C   A

My solution:

def relationship_dictionary(dataframe, key_column_name, values_column_name):
    """
    The key_column_name is the primary data source that should be considered the 
    start of the nested relationship.

    The values_column_name is the subfolder

    Creates a dictionary of unique relationships to each key.
    """

    parent = key_column_name
    child = values_column_name
​
    d = {}
    for i, row in dataframe.iterrows():
        key = row[parent]
        value = row[child]
        if key in d.keys():
            d[key].append(value)
        else:
            d[key] = [value]

    for k, values in d.items():
        for v in values:
            if v in d.keys():
                for each in d[v]:
                    if (each not in d[k]) and (each != k):
                        d[k].extend([each])
    return d

Result:

relationship_dictionary(df, "Parent", "Child")
{'A': ['B', 'C', 'E', 'Z'],
 'B': ['C', 'E', 'A', 'Z'],
 'C': ['E', 'B', 'A', 'Z'],
 'D': ['E', 'Z'],
 'E': ['Z'],
 'F': ['Z']}

Feedback

I'm happy to say it works after mitigating the circular nesting issue but I can't help thinking there is a far simpler way of doing this so I thought I'd put it out there for critique so feedback would be welcome... :)

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

You could create a graph, and use graph theory algorithms to find all nodes (children) you can visit from your current node (parent). The graph would be a directed, acyclic graph due to the nature of the file system.

In fact, this sounds like a great example of how to use graph theory in practice, so I will implement it given slightly more time.

I am including a simplified version of your code without using graphs (still had to use a nested loop, but only of depth 2!):

def relationship_dictionary(dataframe, key_column_name, values_column_name):
    """
    The key_column_name is the primary data source that should be considered the
    start of the nested relationship.

    The values_column_name is the subfolder

    Creates a dictionary of unique relationships to each key.
    """
    # ['A', 'B', 'C', 'D', 'E', 'F', 'C', 'C']
    parents = dataframe[key_column_name].to_list()

    # ['B', 'C', 'E', 'E', 'Z', 'Z', 'B', 'A']
    children = dataframe[values_column_name].to_list()

    # [('A', 'B'), ('B', 'C'), ('C', 'E'), ('D', 'E'), ('E', 'Z'), ('F', 'Z'), ('C', 'B'), ('C', 'A')]
    queue = tuple(zip(parents, children))

    # Create a parent -> empty set mapping to avoid using "if parent in mapping then ..., else ..."
    mapping = {parent: set() for parent in parents}

    # Iterate over each parent, child pair
    for parent, child in queue:

        # Always register a new pair has been processed
        mapping[parent].add(child)

        # Need to iterate over current pairs to make sure situations such as
        # 1. Pair A -> {B} added
        # 2. Pair B -> {C} added
        # result in A -> {B, C} instead of A -> {B}
        #
        # This essentially checks that if the parent in the current pair has been a child somewhere, the child in
        # current pair should also be added to wherever the parent was a child (if confusing follow sample above),
        # excluding cases (such as the last C -> {A} pair being included into A -> {'C', 'B', 'E', 'Z'} mapping)
        # in which the child is also the parent
        for current_parent, current_children in mapping.items():
            if parent in current_children and child != current_parent:
                current_children.add(child)

    return mapping


for k, v in relationship_dictionary(df, "Parent", "Child").items():
    print(k, v)

Result:

A {'E', 'B', 'Z', 'C'}
B {'E', 'A', 'Z', 'C'}
C {'A', 'B', 'Z', 'E'}
D {'Z', 'E'}
E {'Z'}
F {'Z'}

I have only tested it with your example but you might want to verify the code works with some more samples!

Hope it helps!

\$\endgroup\$
1
  • \$\begingroup\$ I really like this! This problem was a real life one with basically finding out all the user and computer objects in an Active Directory.I had no idea what graph theory was so I've just spent 4 hours reading up on it and it is awesome! \$\endgroup\$ Feb 19, 2020 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.