What I'm trying to do is to get each element's level.
I'm currently using this code:
re = {0: [b.keys()[0]]}
n = 1
for a in b:
l = []
for e in s[a]:
l.append(e)
if l != []:
re.update({n: l})
n += 1
print re
That is giving me the following output:
{"0": ["a"], "1": ["b"], "2": ["i"], "3": ["c", "d"], "4": ["f", "g", "h"], "5": ["e", "l"]}
What I'm doing wrong here?
There are some problems here:
[s.keys()[0]] as a way to find the "root" of the tree. Note however that dictionaries are unordered (yes in the CPython-3.6 dictionaries use insertion order, but this is seen as an implementation detail), so there is no guarantee that [s.keys()[0]] is actually the root; andSo we need to solve the two problems. The first one can be solved by looking for nodes that are no child of another element. So we can write it as:
nonroots = {c for cs in s.values() for c in cs}
these are all nodes that are children, so that means that all keys in the dictionary that are not in children, are roots:
roots = [k for k in s if k not in nonroots]
The roots are on level 0, so we can set it to:
levels[0] = roots
now for each iteration, we construct the next generation, by looking up the values corresponding to the previous iteration.
next_gen = [c for k in prev_gen for c in s.get(k,())]
So now we can turn this into a loop: we keep constructing a new generation as long as the previous generation contains at least one elemen. So a complete implementation is:
nonroots = {c for cs in s.values() for c in cs}
level = [k for k in s if k not in nonroots]
generation = 0
result = {}
while level:
result[generation] = level
generation += 1
level = [c for k in level for c in s.get(k,())]
at the end, result is a dictionary that maps all levels to a list of children.
Note that we better use a list instead of a dictionary, since generations start with index 0, and we know that if there is a generation i, then there is also a generation i-1 (for i > 0). So we can turn it into a list like:
nonroots = {c for cs in s.values() for c in cs}
level = [k for k in s if k not in nonroots]
result = []
while level:
result.append(level)
level = [c for k in level for c in s.get(k,())]
This gives us:
>>> result
[['a'], ['b'], ['c', 'd'], ['i', 'e', 'l'], ['f', 'g', 'h']]
We can also use an approach where the caller provides the root(s), in which case we thus generate a tree. We can alter the existing approach, for instance:
def get_levels(tree, roots):
result = []
roots = list(roots)
while roots:
result.append(roots)
roots = [c for k in roots for c in tree.get(k,())]
return result
Now we can thus call it with a given list of roots. In case the roots are not the real roots, we will get an ordering for the subtree(s) under the given tree:
>>> get_levels(s, ['a'])
[['a'], ['b'], ['c', 'd'], ['i', 'e', 'l'], ['f', 'g', 'h']]
>>> get_levels(s, ['c'])
[['c'], ['i']]
>>> get_levels(s, ['i','l'])
[['i', 'l']]
>>> get_levels(s, ['i','e'])
[['i', 'e'], ['f', 'g', 'h']]
You can use recursion:
from collections import defaultdict
listing1 = defaultdict(list)
s = {"a": ["b"], "b": ["c", "d"], "c": ["i"], "d": ["e", "l"], "e": ["f", "g", "h"], "f": [], "g": [], "h": [], "i": [], "l": []}
def get_listing(current_node, count):
global listing1
listing1[count].append(current_node)
for i in s[current_node]:
get_listing(i, count+1)
get_listing('a', 0)
print(dict(listing1))
Output:
{0: ['a'], 1: ['b'], 2: ['c', 'd'], 3: ['i', 'e', 'l'], 4: ['f', 'g', 'h']}
Note that as pointed out in the comments by @WillemVanOnsem and @quamrana, dict.keys() will return an unsorted list, thus making {0: [s.keys()[0]]} unreliable as the root start.
Let's assume you have a dictionary 'd' like that.
d = {"a": ["b"], "b": ["c", "d"], "c": ["i"], "d": ["e", "l"], "e": ["f", "g", "h"], "f": [], "g": [], "h": [], "i": [], "l": []}
keys=d.keys()
keys.sort()
def getKey(l):
for key,value in d.items():
if l == value:
return key
val=dict()# to store level of each node
val['a']=0
for l in keys:
for v in d.values():
if l in v:
key = getKey(v)
val[l]=int(val.get(key,0))+1
print(l,val[l])
sa string?s.keys()produces:AttributeError: 'str' object has no attribute 'keys'[s.keys()[0]]can lead to non-determinstic behavior.