longest path between two nodes for directed acyclic graph? | Tyler Kahn | 7/19/10 5:37 AM | I've seen it suggested that one could use the Bellman-Ford algorithm
with 'inverted weights'. I don't exactly know what this means or know how to do this with networkx. Can anyone help me out? Thanks!! |

Re: longest path between two nodes for directed acyclic graph? | Ben Edwards | 7/21/10 2:41 PM | So if you have a Graph G with nodes N and edged E and if each edge has
a weight w, you can instead set that weight to 1/w, and use the Bellman Ford algorithm for shortest path, or one of the other algorithms for shortest path in the networkx package. If it is a directed-acyclic graph with no weights you should be able to use the algorithm here: http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs with the weights set to 1. Ben |

Re: longest path between two nodes for directed acyclic graph? | irinag | 7/22/10 10:40 AM | but is there a bellman-ford implementation in networkx? I couldn't
find... thanks! > http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_a... |

Re: [networkx-discuss] Re: longest path between two nodes for directed acyclic graph? | Aric Hagberg | 7/22/10 10:58 AM | On Thu, Jul 22, 2010 at 11:40 AM, irinag <irina.n...@gmail.com> wrote: There isn't. But if your weights are non-negative you can use Aric |

Re: longest path between two nodes for directed acyclic graph? | Ben Edwards | 7/22/10 11:03 AM | Bellman-ford is advantageous because it works on graphs with negative
weight edges, which now that I think about it might have been the notion of inversion that was suggested to you at first, additive inversion as opposed to mutliplicative inversion. There is no Bellman-ford currently in networkx. Dijkstra's algorithm works if your graph has no negative weights. The floyd-warshall algorithm will work if you choose to give the graph edges negative weights, but be warned it seems to give odd answers when a negative cycle exists. Both Dijkstra's and the Floyd-Warshall algorithm are implemented in networkx. http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Ben |

Re: longest path between two nodes for directed acyclic graph? | irinag | 7/22/10 12:23 PM | Thank you very much for your replies! But do these methods work only
for DAG, not if you have cycles? |

Re: longest path between two nodes for directed acyclic graph? | Ben Edwards | 7/22/10 12:55 PM | Correct. If you had a cycle in a graph, the longest path wouldn't be
well defined, because you could keep going round and round the cycle making the path longer. Ben |

Re: longest path between two nodes for directed acyclic graph? | Tyler Kahn | 7/23/10 4:40 PM | Hmmm. I'm getting
TypeError: shortest_path() got an unexpected keyword argument 'weighted' for nx.shortest_path(G, source=b[0], target=b[-1], weighted=True) On Jul 22, 1:58 pm, Aric Hagberg <ahagb...@gmail.com> wrote: |

Re: [networkx-discuss] Re: longest path between two nodes for directed acyclic graph? | Aric Hagberg | 7/23/10 5:34 PM | On Fri, Jul 23, 2010 at 5:40 PM, Tyler Kahn <tka...@gmail.com> wrote: You probably have an older version of NetworkX. Aric |

Re: [networkx-discuss] longest path between two nodes for directed acyclic graph? | L.S.C. | 8/2/10 11:41 AM | -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I just added the Bellman-Ford algorithm to the development trunk of NetworkX. You can check it out right now or wait until NetworkX 1.3 is released. For your specific problem, suppose you have a graph G with some arbitrary weights (positive or negative). Build another graph H as such H = nx.Graph(G) Then run the Bellman-Ford algorithm on H. It will return a shortest path on H which corresponds to a longest simple path on G. This works for DiGraph as well. If you graph G has a cycle with positive weight, i.e., if you sum the sum the weights of all the edges while going around the cycle and get a positive result, you'll have a negative weight cycle in H. Bellman-Ford will raise an exception indicating the presence of that negative weight cycle. This means that your graph G does not have a longest path, more precisely, you can find a path of length arbitrary long if you go around the cycle again and again. Hope this helps, Loïc
iEYEARECAAYFAkxXEVoACgkQLKWiTxa2C80T2wCgrgXr4nlKOIhPVPBeGcJvUqzx |