Vertex Order of Graph

Question

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:

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?

Answer 1

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]]