1

I have a dictionary of the following, of unknown hierarchical depth:

dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}}

I found the following useful for learning how to recurse this, but I have had trouble modifying the code to get what I want, which is a list of all the paths from the top hierarchal level to the dead ends.

The desired output is:

list = ['a,b,c', 'a,b,d', 'a,b,e', 'f,g']

To start approaching this, I used a DFS approach:

hierarchy = []
for parent in dict_of_dicts:
    recurse_dicts(concepts, parent, hierarchy)

def recurse_dicts(concepts, parent, hierarchy):
    hierarchy.append(parent)
    for child in concepts[parents]:
        if len(recurse[node][child].keys()) > 0:
            recurse_dicts(recurse[node], child, hierarchy)
        else:
            return

This resulted in:

hierarchy = ['a', 'b', 'c', 'd', 'e']

which is something, but not quite what I wanted.

Community
  • 1
  • 1
knewson
  • 13
  • 3

2 Answers2

0

Assuming your values are always dictionaries, you could use:

def paths(d, path=(), res=None):
    if res is None:
        res = []
    for key, value in d.iteritems():
        if not value:
            # end of the line, produce path
            res.append(','.join(path + (key,)))
        else:
            # recurse down to find the end of this path
            paths(value, path + (key,), res)
    return res

This uses a shared list (produced on first call) to pass the resulting generated paths back to the caller, and builds a path for each recursion step, to add it to the result list whenever an empty value is encountered.

Demo:

>>> dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}}
>>> paths(dict_of_dicts)
['a,b,c', 'a,b,e', 'a,b,d', 'f,g']

The paths are not sorted, because dictionaries have no order; you can still sort on the keys if desired:

for key in sorted(d):
    value = d[key]

instead of the for key, value in d.iteritems() loop.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
0

Here's a recursive DFS procedure that keeps track of the path of each branch:

dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}}

def dfs(path, d):
    if d == {}:
        print path;
    for item in d:
        dfs(path+[item],d[item])

dfs([],dict_of_dicts)

Output:

['a', 'b', 'c']
['a', 'b', 'e']
['a', 'b', 'd']
['f', 'g']
keyser
  • 18,829
  • 16
  • 59
  • 101