6
$\begingroup$

Given a graph, I want to find the shortest distance between each pair of vertices:

g = Graph[{4 <-> 5, 2 <-> 3, 4 <-> 6, 2 <-> 4, 3 <-> 4, 1 <-> 2}, 
        VertexLabels -> "Name"];

This is what the graph looks like:

Graph g

It is obvious that the distance of shortest path from 1 to 6 is 3. However, when I compute the shortest distance in this way:

m = GraphDistanceMatrix[g];
m[[1, 6]]

The output is

2

It tells that the distance from 1 to 6 is 2. This is incorrect. I noticed from its documentation that "the vertices are assumed to be in the order given by VertexList[g]".

So, I called VertexList[g]:

VertexList[g]

And this is the vertex order:

{4, 5, 2, 3, 6, 1}

This actually gives troubles to my application. Is there a way to get the shortest distance according to the numerical order rather than vertex order?

$\endgroup$
5
$\begingroup$
GraphDistance[g, 1, 6]

returns 3.

I've had this problem in the past, and if you want to fix your original method, you can use Sjoerd C. de Vries's answer there. It's one of the few really annoying behaviours of Mathematica I've come across.

Example with a shuffled list of vertices, eleven vertices and ten edges:

edges = UndirectedEdge @@@ RandomInteger[10, {10, 2}];
g = Graph[RandomSample[Range[10], 10], edges, VertexLabels -> "Name"];

ClearAll[state, label]
MapIndexed[(state[#1] = #2[[1]]) &, VertexList[g]];
MapIndexed[(label[#2[[1]]] = #1) &, VertexList[g]];

mat = GraphDistanceMatrix[g];

mat[[state[4], state[6]]]

This is still lightning-fast for ten thousand edges on a hundred vertices for me.

Alternatively, you may ensure the vertex list is ordered when you create the graph, by using the Graph[vertexlist, edgelist] construction. If the vertex list is Range[n] for some n, the following will work to find the distance between vertices of name 4 and 10 (but might forget any metadata you've stored in the graph):

orderedg = Graph[Sort@VertexList[g], EdgeList[g]]
GraphDistanceMatrix[orderedg][[4, 10]]
$\endgroup$
  • $\begingroup$ This is okay for computing a pair, but too slow for all pairs shortest distance. $\endgroup$ – Purboo Aug 23 '15 at 9:02
  • $\begingroup$ @Purboo, how big is your graph? $\endgroup$ – Patrick Stevens Aug 23 '15 at 9:03
  • $\begingroup$ about 100 vertices and 10000 undirected edges. $\endgroup$ – Purboo Aug 23 '15 at 9:05
  • $\begingroup$ Does Sjoerd C de Vries's answer not work quickly? I'll edit into this post. $\endgroup$ – Patrick Stevens Aug 23 '15 at 9:08
  • $\begingroup$ @Purboo Added to post. $\endgroup$ – Patrick Stevens Aug 23 '15 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.