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$

1 Answer 1

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$
10
  • $\begingroup$ This is okay for computing a pair, but too slow for all pairs shortest distance. $\endgroup$
    – Purboo
    Aug 23, 2015 at 9:02
  • $\begingroup$ @Purboo, how big is your graph? $\endgroup$ Aug 23, 2015 at 9:03
  • $\begingroup$ about 100 vertices and 10000 undirected edges. $\endgroup$
    – Purboo
    Aug 23, 2015 at 9:05
  • $\begingroup$ Does Sjoerd C de Vries's answer not work quickly? I'll edit into this post. $\endgroup$ Aug 23, 2015 at 9:08
  • $\begingroup$ @Purboo Added to post. $\endgroup$ Aug 23, 2015 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.