Circular nesting dictionary function

Question

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... :)

Answer 1

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!