## longest path between two nodes for directed acyclic graph?

Showing 1-10 of 10 messages
 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! On Jul 21, 5:41 pm, Ben Edwards wrote: > 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_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 wrote:> but is there a bellman-ford implementation in networkx? I couldn't> find... thanks!There isn't.  But if your weights are non-negative you can useDijkstra's algorithm:  use shortest_path(G,source).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 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 wrote:> Hmmm. I'm getting>>> TypeError: shortest_path() got an unexpected keyword argument> 'weighted'You probably have an older version of NetworkX.You can find the version withprint networkx.__version__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: SHA1I 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 suchH = nx.Graph(G)for u, v in H.edges():    H[u][v]['weight'] *= -1Then 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-----BEGIN PGP SIGNATURE-----Version: GnuPG v1.4.10 (Darwin)iEYEARECAAYFAkxXEVoACgkQLKWiTxa2C80T2wCgrgXr4nlKOIhPVPBeGcJvUqzxwZ4AoLcF6l8SVvGwNXWSMPI41X6LiOj+=PUYe-----END PGP SIGNATURE-----