longest path

[irinag]

Hello,

Is there a method to find the longest path? I want to find the longest
path from a node without coming back to it. So if you start at a node
and check out all possible directions branching off, pick the longest
one.

Thank you very much,
Irina.

[Aric Hagberg]

On Wed, Jul 14, 2010 at 10:59 AM, irinag <irina.n...@gmail.com> wrote:
> Hello,
>
> Is there a method to find the longest path? I want to find the longest
> path from a node without coming back to it. So if you start at a node
> and check out all possible directions branching off, pick the longest
> one.

Do you mean the longest of the shortest paths from a node to every
other node? Or the longest of all paths? I'm not familiar with that
problem but Wikipedia suggests that some versions of it are hard:

http://en.wikipedia.org/wiki/Longest_path_problem

Aric

[irinag]

Yes, I mean the longest path from a node, not the shortest longest. So
if you start at a node, how far in the network can you go? Of course
this means also exploring all the options along the paths branching
off.

I also want to confirm about graph creation. Originally I had a
dictionary where a key:[]. The key is a reactant and the list has all
the products, so the key has an edge to each item in the list. So this
is how I made the graph:

G = nx.Graph()
for key in keys:
l = Nodes[key]
for i in range(0,len(l)):
p = l[i]
G.add_edge(key, p)
print len(G)
An=nx.to_agraph(G)

I could also just do G = nx.Graph(Nodes), right?

And as an ex, G[key] = {p:{},e:{}}. But it could it show the items in
p also, because it is also a key itself and has a list of nodes. If I
want to go to its list, I need to do G[p] first, I can just look
further inside G[key]?

And I have another question - if finding the longest path proves too
difficult, I will need to consider the eccintricities (longest
shortest path). Is there a way to print out not just the value of
eccentricity, but the nodes that were passed?

Thanks very much!!!
Irina.


On Jul 14, 7:09 pm, Aric Hagberg <ahagb...@gmail.com> wrote: