longest path
irinag
is there a method to find the longest path between 2 specified nodes?
this would be a simple acyclic path.
if not, is there a way to get the longest shortest path between them?
thank you very much,
Irina.
Sudarshan Iyengar
> hello,
>
> is there a method to find the longest path between 2 specified nodes?
> this would be a simple acyclic path.
>
> if not, is there a way to get the longest shortest path between them?
>
Hi,
I don't think there is a way in networkx to find the longest path,
this is an NP-Complete problem.
There isn't a longest of shortest paths :-) did you mean shortest of
all possible paths? if that is the question then nx.shortest_path()
does the needful.
best,
sudarshan
irinag
I thought it's NPcomp if there're cycles? But why shouldn't you be
able to simply find the longest straight path between nodes? No, if I
can't have the simple longest, I need the longest shortest, not the
shortest...
thanks a lot for your reply!
Irina.
On Aug 24, 2:57 pm, Sudarshan Iyengar <sudarshani...@gmail.com> wrote:
Loïc Séguin-Charbonneau
http://groups.google.com/group/networkx-discuss/browse_thread/thread/76240f7f256644f2
http://groups.google.com/group/networkx-discuss/browse_thread/thread/d9269113a95a7cd7
>> > is there a method to find the longest path between 2 specified nodes?
>> > this would be a simple acyclic path.
If your graph is acyclic, you can mutliply edge weights by -1 (if you
don't have edge weights, assign each edge a weight of -1) and run
nx.ford_bellman (available in NetworkX 1.3rc1) with one of your nodes
as the source. The function returns a dict keyed by node containing
the predecessors of each node on the shortest path from your source.
This path is actually a longest path in the original graph since you
multiplied the weights by -1.
>> > if not, is there a way to get the longest shortest path between them?
>> There isn't a longest of shortest paths :-) did you mean shortest of
>> all possible paths? if that is the question then nx.shortest_path()
>> does the needful.
As Sudarshan said, there is no such thing as a longest shortest path
between two given nodes.
--
Loïc Séguin-Charbonneau
devio.us/~loicseguin/
irinag
On Aug 24, 3:49 pm, Loïc Séguin-Charbonneau <loicseg...@gmail.com>
wrote:
>
>
> http://groups.google.com/group/networkx-discuss/browse_thread/thread/...
> >> > is there a method to find the longest path between 2 specified nodes?
> >> > this would be a simple acyclic path.
>
> If your graph is acyclic, you can mutliply edge weights by -1 (if you
> don't have edge weights, assign each edge a weight of -1) and run
> nx.ford_bellman (available in NetworkX 1.3rc1) with one of your nodes
Thanks a lot for your help. So I tried the bellman ford on my original
graph and on a copy with edges multiplied by -1.
But I get the same nodes and lenght of path in both cases - can this
be correct? Does this mean there is only one path? Because there
definitely more that 1 path from most nodes...
Thanks very much!
Irina.
Loïc Séguin-Charbonneau
Sorry, my first email was not quite accurate. Here is a more detailed answer.
2010/8/26 irinag <irina.n...@gmail.com>:
> On Aug 24, 3:49 pm, Loïc Séguin-Charbonneau <loicseg...@gmail.com>
> wrote:
>> If your graph is acyclic, you can mutliply edge weights by -1 (if you
>> don't have edge weights, assign each edge a weight of -1) and run
>> nx.ford_bellman (available in NetworkX 1.3rc1) with one of your nodes
This is obviously true since if the graph is acyclic, there is only a
single path between to given nodes. What I meant to say is that if
your graph does not contain a cycle of positive weight, then you can
run bellman_ford on the graph with weights multiplied by -1 to find a
longest path.
> Thanks a lot for your help. So I tried the bellman ford on my original
> graph and on a copy with edges multiplied by -1.
>
> But I get the same nodes and lenght of path in both cases - can this
> be correct? Does this mean there is only one path? Because there
> definitely more that 1 path from most nodes...
If you get the same path in both cases, it is because you only have
one path between your two nodes.
Here is an example.
"""Example of how to find a longest path.
This finds a longest path between node 0 and all other nodes.
(py2.7)Micron:trunk loic$ python longest_path.py
({0: None, 1: 0, 2: 1, 3: 2, 4: 0}, {0: 0, 1: 1, 2: 2, 3: 3, 4: 2})
({0: None, 1: 0, 2: 1, 3: 4, 4: 0}, {0: 0, 1: -1, 2: -2, 3: -4, 4: -2})
"""
import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(0, 1, {'weight': 1}),
(1, 2, {'weight': 1}),
(2, 3, {'weight': 1}),
(0, 4, {'weight': 2}),
(4, 3, {'weight': 2})])
H = nx.DiGraph(G)
for u, v in H.edges_iter():
H[u][v]['weight'] *= -1
print nx.bellman_ford(G, 0)
print nx.bellman_ford(H, 0)
--
Loïc Séguin-Charbonneau
devio.us/~loicseguin/
irinag
Thank you so much! This is very helpful!
Irina.
On Aug 27, 10:11 am, Loïc Séguin-Charbonneau <loicseg...@gmail.com>
wrote:
>
> Sorry, my first email was not quite accurate. Here is a more detailed answer.
>