How to create multidimensional dictionary of unknown depth based on lookup dictionary? (python)

Question

I have this "lookup" dictionary, which represents nodes:

# Original "lookup" dictionary

{
  0 : [1, 2],
  2 : [3],
  4 : [5]
}

...and I wish to create a new dictionary based on this, like so:

# New multidimensional dictionary

{
  0 : {
        1 : {},
        2 : {
              3 : {}
            }
      }
  4 : {
        5 : {}
      }
  }
}

How can this be achieved using recursion?

The original "lookup" dictionary's keys represent parent nodes and the values represent children nodes in one or more node trees.

The original "lookup" dictionary contains an unknown amount of keys/values and the depth is unknown.

To express the purpose of the original dict: it describes parent-child relationships with the keys being the parents and the values being the children?! — deceze, Dec 09 '15 at 14:47
This sounds (reads) like a recursion problem. Use a function that calls itself. Have you tried that? — tglaria, Dec 09 '15 at 14:51
There are several implementations here - http://stackoverflow.com/questions/3229419/pretty-printing-nested-dictionaries-in-python — Tom Ron, Dec 09 '15 at 14:56
@tglaria yes but I don't understand how to recursively add a new key at a given depth. — fredrik, Dec 09 '15 at 15:02
@fredrik, well it's just `new_dict[some_key] = some_value`. So if the present value is a list, you add its value to the dictionnary, if not, then you add a new dictionnary. — tglaria, Dec 09 '15 at 15:24
Is this supposed to result in a tree, or something else? Your sample data appears to have two roots: `0` and `4`, implying it's a "forest" (several trees), or that the tree has an assumed "invisible root" that's a parent of all roots, or that you're actually trying to create a DAG, or... — Kevin J. Chase, Dec 10 '15 at 12:15
@KevinJ.Chase It's supposed to result in a "forest", which is how the accepted answer deals with it. — fredrik, Dec 12 '15 at 19:50
Thanks fredrik, that cleared it up. I couldn't figure out why you'd accepted an answer that started off by assuming you wanted a tree, when your example output clearly _wasn't_ a tree. Or at least, wasn't _one_ tree. — Kevin J. Chase, Dec 12 '15 at 21:44

alexis · Accepted Answer · 2015-12-09T15:29:05.497

I will assume that this data structure represents a tree, and that nodes are numbered so that the parent always has a lower index than the children. Then, you can build the tree you want without recursion, with the help of a helper index (nodeindex) that lets you find each node in one step:

tree = dict()
nodeindex = dict()
for node, vals in sorted(lookup.items()):
    if node not in nodeindex:
        nodeindex[node] = tree[node] = dict()  # insert at the top level

    position = nodeindex[node]
    for val in vals:
        if val in nodeindex:
            raise ValueError("Value (%d, %d) would create a loop!" %(node, val))
        nodeindex[val] = position[val] = dict()

If a non-tree graph is legal, the last part of the loop would assign to position[val] the value it found, instead of raising an error:

    ...
    for val in vals:
        if val in nodeindex:
            position[val] = nodeindex[val]
        else:
            nodeindex[val] = position[val] = dict()

I know you're not supposed to comment to say "thanks" etc... but that was an awesome solution. Thank you! — fredrik, Dec 09 '15 at 15:20
You're welcome! In my experience it's tolerated in comments-- just leave the thanks out of the questions and answers :-) — alexis, Dec 09 '15 at 15:21

How to create multidimensional dictionary of unknown depth based on lookup dictionary? (python)

1 Answers1