need to find child element from python list

Question

i have a python list as below

[(u'1', u'0'), (u'2', u'1'), (u'3', u'2'), (u'4', u'3'), (u'5', u'4'), (u'6', u'4'), (u'7', u'4'), (u'8', u'4'), (u'9', u'4'), (u'10', u'4'), (u'11', u'4'), (u'11.5', u'2'), (u'12', u'11.5'), (u'13', u'11.5'), (u'14', u'11.5'), (u'15', u'11.5'), (u'16', u'11.5'), (u'17', u'11.5'), (u'18', u'11.5'), (u'19', u'11.5'), (u'20', u'11.5'), (u'21', u'11.5'), (u'22', u'11.5'), (u'23', u'11.5'), (u'24', u'11.5'), (u'25', u'11.5'), (u'26', u'11.5'), (u'27', u'11.5'), (u'28', u'11.5'), (u'30', u'11.5'), (u'29', u'11.5')]

here each tuple's 1st place is its own id while 2nd position is its parent id.

i want to get all child of specific id. Example, if i want to get the list of all ownids who are child(or child of child... to n depth) of own id "3". so answer list will be [u'4', u'5', u'6', u'7', u'8', u'9', u'10', u'11']

any way to do this??

Answer 1

You can use the networkx library...

import networkx as nx
g = nx.DiGraph()
g.add_edges_from( (y,x) for x,y in your_list )
print list(nx.dfs_postorder_nodes(g, '3'))
[u'11', u'10', u'5', u'7', u'6', u'9', u'8', u'4', '3']

Answer 2

If you have no defined number of levels…

With your list li:

d = {}
for o, p in li:
    d.setdefault(p, []).append(o)
todo = d[u'3'][:]
descendants = []
while todo:
    node = todo.pop(0)
    todo.extend(d.get(node, []))
    descendants.append(node)

descendants contains the sought list.