tree data structure

[Duncan Booth]

Padraig Brady <Padraig at Linux.ie> wrote in 
news:FM0e9.2860$cP3.6165 at news.iol.ie:

> Hi,
> 
> I've a graph like stucture represented
> by a list of tuples:
> 
> [(L0,S2), (S2,S0), (S2,S1), (S1,Q2), (S0,Q1), (S2,S3)]
> 
> And would like to convert it to
> a tree structure like:
> 
>            S0 - Q1
>          /
> L0 - S2 - S3
>          \
>            S1 - Q2
> 
> Any tips appreciated.
> 
Does this help?

data = [('L0', 'S2'), ('S2', 'S0'), ('S2', 'S1'), ('S1', 'Q2'), ('S0', 
'Q1'), ('S2', 'S3')]

# Produce a tuple where each node contains its name
# and a list of its child nodes:
#  (node, [child1, ...])
nodes = {}
for parent, child in data:
    nodes.setdefault(parent, (parent, 
[]))[1].append(nodes.setdefault(child, (child, [])))

result = nodes[data[0][0]]

assert result==('L0', [('S2', [('S0', [('Q1', [])]), ('S1', [('Q2', [])]), 
('S3', [])])])


-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?