Velocity Reviews > Representing a Tree in Python

# Representing a Tree in Python

godshorse
Guest
Posts: n/a

 05-13-2009
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,

CTO
Guest
Posts: n/a

 05-13-2009
On May 13, 12:10*am, godshorse <(E-Mail Removed)> 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):

....

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

godshorse
Guest
Posts: n/a

 05-13-2009
On May 13, 11:54*am, CTO <(E-Mail Removed)> wrote:
> On May 13, 12:10*am, godshorse <(E-Mail Removed)> 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):

>
> ...
>

>
> 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

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.

CTO
Guest
Posts: n/a

 05-13-2009
> 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.

A tree is just a connected acyclic rooted graph, so however you're
representing graphs should be a perfectly natural representation for
your shortest paths tree. In effect, you just treat the shortest
paths operation as an subgraph operation which only preserves the
edges that are part of a shortest path.

Geremy Condra

Jaime Fernandez del Rio
Guest
Posts: n/a

 05-13-2009
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 <(E-Mail Removed)> wrote:
> On May 13, 11:54*am, CTO <(E-Mail Removed)> wrote:
>> On May 13, 12:10*am, godshorse <(E-Mail Removed)> 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):

>>
>> ...
>>

>>
>> 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.

godshorse
Guest
Posts: n/a

 05-13-2009
On May 13, 3:19*pm, Jaime Fernandez del Rio <(E-Mail Removed)>
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 <(E-Mail Removed)> wrote:
> > On May 13, 11:54*am, CTO <(E-Mail Removed)> wrote:
> >> On May 13, 12:10*am, godshorse <(E-Mail Removed)> 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)
> >> ...

>

>
> >> 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,

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

bearophileHUGS@lycos.com
Guest
Posts: n/a

 05-13-2009
godshorse, you may use the "shortestPaths" method of this graph class
of mine:
http://sourceforge.net/projects/pynetwork/

(It uses the same Dijkstra code by Eppstein).
(Once you have all distances from a node to the other ones, it's not
too much difficult to find the tree you talk about).

Also see the Minimum spanning tree:
http://en.wikipedia.org/wiki/Minimum_spanning_tree

Bye,
bearophile

Piet van Oostrum
Guest
Posts: n/a

 05-13-2009
>>>>> godshorse <(E-Mail Removed)> (g) wrote:

>g> Hello,
>g> I want to find out the shortest path tree from a root to several nodes
>g> in a graph data structure. I found a Dijkstra code from internet that
>g> finds shortest path between only two nodes. How can i extend it to a
>g> tree?. And what is the best way to represent a tree in Python?.

http://networkx.lanl.gov/ has all kinds of Dijkstra's algorithms.
--
Piet van Oostrum <(E-Mail Removed)>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: http://www.velocityreviews.com/forums/(E-Mail Removed)

CTO
Guest
Posts: n/a

 05-13-2009
On May 13, 8:19*am, (E-Mail Removed) wrote:
> godshorse, you may use the "shortestPaths" method of this graph class
> of mine:http://sourceforge.net/projects/pynetwork/
>
> (It uses the same Dijkstra code by Eppstein).
> (Once you have all distances from a node to the other ones, it's not
> too much difficult to find the tree you talk about).
>
> Also see the Minimum spanning tree:http://en.wikipedia.org/wiki/Minimum_spanning_tree
>
> Bye,
> bearophile

Let me add a caution to what bearophile says here- a minimum spanning
tree minimizes
the weight of the *whole tree*, not the individual paths in that tree,
which seems
to be what you're going after. Those can be pretty different things.

Geremy Condra

Benjamin Edwards
Guest
Posts: n/a

 05-14-2009
On May 13, 8:27*pm, CTO <(E-Mail Removed)> wrote:
> On May 13, 8:19*am, (E-Mail Removed) wrote:
>
> > godshorse, you may use the "shortestPaths" method of this graph class
> > of mine:http://sourceforge.net/projects/pynetwork/

>
> > (It uses the same Dijkstra code by Eppstein).
> > (Once you have all distances from a node to the other ones, it's not
> > too much difficult to find the tree you talk about).

>
> > Also see the Minimum spanning tree:http://en.wikipedia.org/wiki/Minimum_spanning_tree

>
> > Bye,
> > bearophile

>
> Let me add a caution to what bearophile says here- a minimum spanning
> tree minimizes
> the weight of the *whole tree*, not the individual paths in that tree,
> which seems
> to be what you're going after. Those can be pretty different things.
>
> Geremy Condra

no love for floyds algorithm. so simple

http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Paul Johnson VHDL 6 01-30-2006 09:09 PM Kingsley Oteng VHDL 0 05-04-2004 02:00 AM ALuPin VHDL 3 02-25-2004 08:41 PM Melkor Ainur C Programming 6 01-02-2004 08:44 AM Stub C Programming 3 11-12-2003 01:51 PM