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 <bjedwa...@gmail.com> 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 <irina.n...@gmail.com> 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 use
Dijkstra'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 <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:
> 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 with
print 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: SHA1

Le 2010-07-19 à 08:37, Tyler Kahn a écrit :

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)
for u, v in H.edges():
    H[u][v]['weight'] *= -1

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


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (Darwin)

iEYEARECAAYFAkxXEVoACgkQLKWiTxa2C80T2wCgrgXr4nlKOIhPVPBeGcJvUqzx
wZ4AoLcF6l8SVvGwNXWSMPI41X6LiOj+
=PUYe
-----END PGP SIGNATURE-----