|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?
|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
with the weights set to 1.
|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
|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
|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.
|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.
|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
nx.shortest_path(G, source=b, 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.
|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-----
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,