How to use recursion to get all children when each parent has an array of children?-CodePudding

I have a dictionary d of parent:list(children) as so:

d = \
{'accounts': ['nodate'],
 'retfile': ['bb', 'aa'],
 'snaps': [],
 'raw': ['pview', 'status'],
 'nodate': ['tainlog', 'retfile'],
 'mview': ['status', 'nodate'],
 'pview': [],
 'retlog': [],
 'aa': ['payfile'],
 'remfile': ['retlog'],
 'tainlog': ['remfile'],
 'payfile': [],
 'bb': ['payfile'],
 'balance': [],
 'status': ['accounts', 'snaps', 'nodate'],
 'charges': ['mview', 'raw', 'balance']}

For each key parent I want to get all decedents, so I was thinking of a recursion, so far I have this:

def get_all_descendants(t, l):
    l.extend(list(d[t]))
    if not d[t]:
        return set(l)
    for t1 in d[t]:
        return get_all_descendants(t1, l)

but this is not good as the for loop never really iterates over all the elements in the list rather the recursion starts over for the the first element.

For instance consider 'charges', my function is returning 11 elements:

{'accounts',
 'balance',
 'mview',
 'nodate',
 'raw',
 'remfile',
 'retfile',
 'retlog',
 'snaps',
 'status',
 'tainlog'}

While I want 15 elements (all the keys in d except 'charges') for instance missing 'pview' (which is the child of 'raw').

Any ideas?

CodePudding user response：

You can do a depth first search. Just keep track of which items you've seen in a set. Then yield each one you haven't seen and yield from the result of recursive call:

def get_all_descendants(t, d, seen=None):
    if seen is None:
        seen = set([t])
    for item in d[t]:
        if item not in seen:
            seen.add(item)
            yield item
            yield from get_all_descendants(item, d, seen)

list(get_all_descendants('charges', d))

This will give you this list:

['mview',
 'status',
 'accounts',
 'nodate',
 'tainlog',
 'remfile',
 'retlog',
 'retfile',
 'bb',
 'payfile',
 'aa',
 'snaps',
 'raw',
 'pview',
 'balance']

CodePudding user response：

I think @Mark's answer can be improved. Moving the if outside of the for loop means you can skip many unnecessary checks on child nodes when the parent node has already been seen -

def dfs(t, d, seen = None):
  if not seen: 
    seen = set()
  if t not in seen:
    seen.add(t)
    for item in d[t]:
      yield item
      yield from dfs(item, d, seen)

The output is identical -

for node in dfs("charges", d):
  print(node)

mview
status
accounts
nodate
tainlog
remfile
retlog
retfile
bb
payfile
aa
payfile
snaps
nodate
nodate
raw
pview
status
balance