tree data structure
Padraig Brady
Padraig at Linux.ie
Fri Sep 6 08:46:44 EDT 2002
Duncan Booth wrote:
> 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', [])])])
>
>
It certainly does!
Just one thing...Why use lists instead of tuples?
thanks,
Pádraig.
p.s. I am completely amazed by Python. What is it now.. 4 hours
and 43 minutes and I've learnt Python enough (from the web docs)
to be able to parse a "graph format" text file and outputting XML
(albeit with a little help :-)). Fantastic!
More information about the Python-list
mailing list