Representing a Tree in Python

Discussion in 'Python' started by godshorse, May 13, 2009.

  1. godshorse

    godshorse Guest

    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,
    godshorse, May 13, 2009
    #1
    1. Advertising

  2. godshorse

    CTO Guest

    On May 13, 12:10 am, godshorse <> 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
    CTO, May 13, 2009
    #2
    1. Advertising

  3. godshorse

    godshorse Guest

    On May 13, 11:54 am, CTO <> wrote:
    > On May 13, 12:10 am, godshorse <> 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.
    godshorse, May 13, 2009
    #3
  4. godshorse

    CTO Guest

    > 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
    CTO, May 13, 2009
    #4
  5. 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 <> wrote:
    > On May 13, 11:54 am, CTO <> wrote:
    >> On May 13, 12:10 am, godshorse <> 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.
    Jaime Fernandez del Rio, May 13, 2009
    #5
  6. godshorse

    godshorse Guest

    On May 13, 3:19 pm, Jaime Fernandez del Rio <>
    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 <> wrote:
    > > On May 13, 11:54 am, CTO <> wrote:
    > >> On May 13, 12:10 am, godshorse <> 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
    godshorse, May 13, 2009
    #6
  7. godshorse

    Guest

    , May 13, 2009
    #7
  8. >>>>> godshorse <> (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 <>
    URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
    Private email:
    Piet van Oostrum, May 13, 2009
    #8
  9. godshorse

    CTO Guest

    On May 13, 8:19 am, 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
    CTO, May 13, 2009
    #9
  10. On May 13, 8:27 pm, CTO <> wrote:
    > On May 13, 8:19 am, 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 :D

    http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm
    Benjamin Edwards, May 15, 2009
    #10
  11. If you run Dijkstra without a third argument, i.e. without an end
    node, the it will compute the shortest paths from your start node to
    all nodes in the tree. So by doing something like:

    start_node = 1
    end_nodes = [2,3,5]

    D, P = Dijkstra(G, start_node)

    You will then have in D a dictionary with distances to all nodes, and
    in P a dictionary of preceding nodes along the shortest path for each
    node. You could tweak the Dijkstra function so that it stops when the
    minimum distances to all elements of end_nodes have been calculated,
    without having to solve for the whole graph...

    Apart from that, how you want to store the shortest path information
    is up to you, but if you stick to the "graph as a dictionary of
    dictionaries" you can construct the subgraph that contains only the
    nodes in the shortest paths between the start and the end nodes with
    code like this one:

    shortest_tree = {}
    current_layer = end_nodes
    while current_layer != [start_node] :
    new_layer = set()
    for node in current_layer :
    new_node = P[node]
    if new_node in shortest_tree :
    if node not in shortest_tree[new_node] :
    shortest_tree[new_node][node] = G[new_node][node]
    else :
    shodtest_tree[new_node] = {}
    shortest_tree[new_node][node] = G[new_node][node]
    new_layer.add(new_node)
    current_layer = [j for j in new_layer]

    I haven't tested the code, and there may be more efficient ways of
    achieving the same, though...

    Jaime

    On Wed, May 13, 2009 at 10:49 AM, godshorse <> wrote:
    > On May 13, 3:19 pm, Jaime Fernandez del Rio <>
    > 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 <> wrote:
    >> > On May 13, 11:54 am, CTO <> wrote:
    >> >> On May 13, 12:10 am, godshorse <> 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
    > --
    > 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.
    Jaime Fernandez del Rio, May 15, 2009
    #11
  12. In article <>,
    godshorse <> wrote:
    >On May 13, 11:54=A0am, CTO <> wrote:
    >> On May 13, 12:10=A0am, godshorse <> 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?.


    <SNIP>

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


    If I understand correctly, you want to know the path given
    the end-node. Common sense dictates that you use back links
    if that has to be done with decent efficiency.
    The back links can be added as part of the algorithm.

    >
    >Thanks once again.


    Groetjes Albert

    --
    --
    Albert van der Horst, UTRECHT,THE NETHERLANDS
    Economic growth -- like all pyramid schemes -- ultimately falters.
    albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
    Albert van der Horst, May 23, 2009
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ALuPin
    Replies:
    3
    Views:
    3,427
    Egbert Molenkamp
    Feb 25, 2004
  2. Kingsley Oteng

    Representing signed numbers in VHDL

    Kingsley Oteng, May 4, 2004, in forum: VHDL
    Replies:
    0
    Views:
    745
    Kingsley Oteng
    May 4, 2004
  3. Paul Johnson

    Representing INF in a real?

    Paul Johnson, Jan 27, 2006, in forum: VHDL
    Replies:
    6
    Views:
    1,743
  4. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,108
  5. Melkor Ainur
    Replies:
    6
    Views:
    440
    Uli Kusterer
    Jan 2, 2004
Loading...

Share This Page