Representing a Tree in Python

[godshorse]

On May 13, 3:19 pm, Jaime Fernandez del Rio <jaime.f... at gmail.com>
wrote:
> Dijkstra's algorithm computes shortest paths between a node and _ALL_
> other nodes in the graph. It is usually stopped once computing the
> shortest path to the target node is done, but that's simply for
> efficiency, not a limitation of the algorithm. So you should be able
> to tweak the code you are using so that it provides you with all you
> are looking for. I'd be surprised if graphine (which, by the way,
> looks great, CTO) or any other graph package didn't implement it, so
> switching to that may be the most efficient thing to do.
>
> On the other hand, if you want to post your code and links to the
> Dijkstra code you are using it may be possible to help you with the
> tweaking...
>
> Jaime
>
>
>
> On Wed, May 13, 2009 at 8:31 AM, godshorse <chinthak... at gmail.com> wrote:
> > 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.
> > --
> >http://mail.python.org/mailman/listinfo/python-list
>
> --
> (\__/)
> ( O.o)
> ( > <) Este es Conejo. Copia a Conejo en tu firma y ayúdale en sus
> planes de dominación mundial.

Hello Jaime,

Thanks for the reply.

This is the link to the code that I am using. http://code.activestate.com/recipes/119466/
What I do in my code is just looping through the destination nodes and
find the shortest path to each node.

Thanks