Representing a Tree in Python

godshorse chinthakawk at gmail.com
Wed May 13 08:31:07 CEST 2009


On May 13, 11:54 am, CTO <debat... at gmail.com> wrote:
> On May 13, 12:10 am, godshorse <chinthak... at gmail.com> wrote:
>
> > Hello,
>
> > I want to find out the shortest path tree from a root to several nodes
> > in a graph data structure. I found a Dijkstra code from internet that
> > finds shortest path between only two nodes. How can i extend it to a
> > tree?. And what is the best way to represent a tree in Python?.
>
> > Thank you,
>
> Well, I'm biased, but I like <URL:http://graphine.org>.
> As an example, to build a five node tree:
>
> >>> from graph.base import Graph
> >>> g = Graph()
> >>> for i in range(5):
>
> ...     g.add_node(i)
> ...
>
> >>> g.add_edge(0, 1)
> >>> g.add_edge(0, 2)
> >>> g.add_edge(1, 3)
> >>> g.add_edge(1, 4)
>
> And to find the shortest path between, say, node 0 and node 4:
>
> >>> start = g[0]
> >>> end = g[4]
> >>> distance, edges = g.get_shortest_paths(start)[end]
> >>> distance
> 2
> >>> edges
>
> [Edge(name=(0,1)), Edge(name=(1,4))]
>
> Let me know what you think if you decide to use it- I'm looking for
> feedback.
>
> Geremy Condra

Thanks very much for your reply Geremy. That site was interesting.

Actually the Graph building part is already completed now. I used a
dictionary for that and it works fine. for Dijkstra shortest path
problem your suggestion can be used.

But let me clear the my problem again. I have a graph. and I want to
find 'shortest path tree' from a root node to several nodes. as a
example if we have a graph of 5 nodes from 1 to 5, I need to build the
shortest path tree from node 1 to nodes 2,3,5. So my question is
instead of keeping separate lists for each destination node's shortest
path. How can I represent and store them in a tree structure using
python. Then I can easily find out what are the common nodes in the
path to each destination.

Thanks once again.



More information about the Python-list mailing list