[networkx-discuss] How to find edges along the shortest path when there are parallel edges

[Marc]

I am considering NetworkX for use with solving routing problems in
networks. I need a K-shortest paths algorithm which I intend to write
myself as it doesn't appear to be part of this graph package. But in
analyzing this package I am confused at how I would adapt it for my
purposes. I have a multi di-graph and want to find shortest paths. But
I need to know the edges traversed to get from the start to the
finish. While the shortest path algorithms in this library seem to
return a list of nodes. This gives no indication about what edges
where actually used. Of course, if you had the edges instead you can
easily get the nodes.

Perhaps I am missing something which would allow this in the library.
Can anyone make any recommendations?

If this isn't possible in this library then perhaps I can just adapt
it to keep a predecessor list of edges instead of nodes and then
return the paths as a list of edges instead.

Thanks.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[Richard Careaga]

If you're not using the Multigraph class (see
http://networkx.lanl.gov/reference/classes.multigraph.html#iterating-over-nodes-and-edges),
you'll only see nodes because each node has only one edge, which was a
big revelation for my learning curve. Not that I can tell you which of
the class methods might be available for your problem.

[Aric Hagberg]

On Thu, Apr 29, 2010 at 3:17 PM, Marc <mdb...@gmail.com> wrote:
> I am considering NetworkX for use with solving routing problems in
> networks. I need a K-shortest paths algorithm which I intend to write
> myself as it doesn't appear to be part of this graph package. But in
> analyzing this package I am confused at how I would adapt it for my
> purposes. I have a multi di-graph and want to find shortest paths. But
> I need to know the edges traversed to get from the start to the
> finish. While the shortest path algorithms in this library seem to
> return a list of nodes. This gives no indication about what edges
> where actually used. Of course, if you had the edges instead you can
> easily get the nodes.
>
> Perhaps I am missing something which would allow this in the library.
> Can anyone make any recommendations?
>
> If this isn't possible in this library then perhaps I can just adapt
> it to keep a predecessor list of edges instead of nodes and then
> return the paths as a list of edges instead.
>

There isn't an algorithm to do exactly what you want but there
is some similar code you can look at and possibly adapt.

The predecessor algorithm (uses a BFS) will give you the info you need to
find the edges in the shortest paths.

As it is currently written though it looks like it won't keep track of
multiple edges.
https://networkx.lanl.gov/trac/browser/networkx/trunk/networkx/algorithms/shortest_paths/unweighted.py#L425

e.g. from a previous thread on this list

For example

In [28]: G=networkx.Graph()

In [29]: G.add_cycle([0,1,2,3])

In [30]: p=networkx.predecessor(G,0) # shortest path starting at 0

In [31]: p
Out[31]: {0: [], 1: [0], 2: [1, 3], 3: [0]}

Then you just need to identify your target (say 2) and follow the
paths back:

In [32]: p[2]
Out[32]: [1, 3] # both one and 3 are on the shortest path

In [33]: p[1] # predecessor of 1 is the source so we are done
Out[33]: [0]

Aric

[Dan Schult]

If I recall correctly, the shortest paths algorithms were not written
with
multigraphs in mind because keeping track of all the extra edges
slows down the algorithm too much. Since only one of the edges from
u to v will ever be used (the shortest edge), it might be worthwhile
converting your MultiDiGraph to a DiGraph. For each node pair with
at least one edge, fill the DiGraph with the shortest edge.

When the shortest_path routines return a list of nodes from u to v
you can turn that into a list of edges pretty efficiently with

zip(path[1:],path[:-1])

to get a list of edge tuples. It's actually more efficient to store the
list of nodes rather than pack and unpack all the edge tuples.
So while there are cases where you really need the edges, you
might think about whether using the list of nodes would be more
effective in your case--it often is.
Dan

> To post to this group, send email to networkx-
> dis...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discuss
> +unsub...@googlegroups.com.

[Aric Hagberg]

On Thu, Apr 29, 2010 at 8:06 PM, Dan Schult <dsc...@colgate.edu> wrote:
> If I recall correctly, the shortest paths algorithms were not written with
> multigraphs in mind because keeping track of all the extra edges
> slows down the algorithm too much.  Since only one of the edges from
> u to v will ever be used (the shortest edge), it might be worthwhile
> converting your MultiDiGraph to a DiGraph.  For each node pair with
> at least one edge, fill the DiGraph with the shortest edge.
>
> When the shortest_path routines return a list of nodes from u to v
> you can turn that into a list of edges pretty efficiently with
>
> zip(path[1:],path[:-1])
>
> to get a list of edge tuples.  It's actually more efficient to store the
> list of nodes rather than pack and unpack all the edge tuples.
> So while there are cases where you really need the edges, you
> might think about whether using the list of nodes would be more
> effective in your case--it often is.

If I understand correctly Marc wants k shortest paths. And it sounds
like a two-terminal problem - k-shortest paths between s and t.
So there are specialized algorithms for that (not implemented in NetworkX).
E.g. see Eppstein's paper: www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
I'm not sure if those algorithms can be used with multigraphs or not.

Aric

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

[Marc]

Richard,

I understand what you are saying. I am using MultiGraph or more
correctly I am using MultiDiGraph. As in my scenario it is possible to
have numerous parallel links which can have equal or different
weights.

On Apr 29, 8:59 pm, Richard Careaga <leuc...@gmail.com> wrote:
> If you're not using the Multigraph class (seehttp://networkx.lanl.gov/reference/classes.multigraph.html#iterating-...),

[Richard Careaga]

OK, just wanted to make sure you had run across the documentation section for MG; I always have trouble remembering where it is.

[Marc]

Thanks to everyone for their answers. I perhaps should not have
complicated the post by mentioning the K-shortest paths algorithm.
Aric actually pointed out the exact algorithm I have used in the past
(i.e. the one from David Eppstein). The basis for this algorithm is to
find the first shortest path and then based on this find the next
shortest path. I have implemented it in the past in C++ and made use
of Dijkstra's shortest path algorithm as the basis. My Dijkstra
algorithm implementation supported returning the edge list for the
path instead of the node list. And of course, since you know the end
points of the edges, you can easily produce the node list too.

I had a look at the single_source_dijkstra() function and with quite
an easy adaptation I can get what I want. Instead of storing nodes in
the path I would just store edges. Then I would return the list of
edges. Then I would just implement David Eppstein's k-shortest paths
algorithm. I didn't understand the comment about the algorithm not
being implemented multigraphs because it slows down the algorithm too
much. As if you look at the special case where a Multigraph is equal
to Graph (i.e. only one edge) the two implementations perform the
same. I agree that having Multigraph requires more work to find the
shortest path as you then have more neighbors to investigate.

I also may investigate the Boost Graph Library and its Python
bindings. As I think that all the BGL algorithms are adapted for
Multigraphs. But I will have to validate this.

[Dan Schult]

My comment about finding shortest path using multigraph
refers to the following:

For shortest path, when considering crossing an edge from node u to node v you have to consider which of the edges to traverse, but you will always traverse the shortest edge between u and v. So you are repeatedly checking the same set of edges (between u and v) for which is shortest. Switching to a DiGraph removes all edges that you won't be using anyway up front. Thats the savings I was refering to. But... This doesn't apply for k-shortest_paths because you have to be able to fall back on a slightly longer edge between u and v to find the next-to-shortest path.

There is also a minor timing issue that multidigraph is slightly slower than digraph to check edge weights for any given edge because there is one more dict lookup -- but I don't think this is much of an issue unless you have many edges between u and v.

Sounds like you have a reasonable approach in mind.
Dan

[franck kalala]

In the attached file I have a graph for which the output format is of this form:


graph output format :
each line is <vertex> <neighbour 1> <neighbour 2> ...

is there any routine in Networkx that can read this file and represent this graph as a Networkx graph object?

Cheers

Franck

[Richard Careaga]

Under 'crude but effective'

f = open("/Users/YOU/corr.dot", 'r')
G = nx.read_dot(f)
f.close()

All you'd need to do is to put your data in graphviz form

corr.dot:

digraph moo {
vertex -> neighbor1
vertex -> neighbor2
neighbor1 -> neighbor2

[franck kalala]

I don't know graphviz

How do you create corr.dot from mygraph?




----- Message d'origine ----
De : Richard Careaga <leu...@gmail.com>
À : networkx...@googlegroups.com
Envoyé le : Sam 8 mai 2010, 23h 18min 14s
Objet : Re: [networkx-discuss] read graph from a file

[Moritz Beber]

Isn't that an adjacency list format which could be read by the following
function:

http://networkx.lanl.gov/reference/generated/networkx.read_adjlist.html#networkx.read_adjlist

[Richard Careaga]

I wasn't sure what your attachment was, so I didn't open it. If it is a spreadsheet, for example, you could save it as a comma separated file, read it in as before, then parse each line, but I'd first try the later suggestion by M. Beber.

franck kalala wrote:

I don't know graphviz

How do you create corr.dot from mygraph



----- Message d'origine ----
De : Richard Careaga <leu...@gmail.com>

[Mehrdad Moradi]

Hi Marc,

I know a long time has passed from your posts. I wonder if you have the code

for k-shortest paths algorithm on a multi-graph available somewhere. This

is exactly what I need as a building block for a traffic engineering algorithm

of one of my papers. If you could provide me with your code, I can save

lots of time.

Thanks a lot!

---Mehrdad Moradi

PhD student University

of Michigan