# Difference between vertex names and indices in a directed graph

A simple digraph g:

ClearAll[g];
g = Graph[{
1 -> 2, 1 -> 4, 1 -> 5, 2 -> 3, 2 -> 5,
3 -> 1, 3 -> 5, 3 -> 9, 4 -> 2, 4 -> 7,
5 -> 6, 6 -> 2, 6 -> 8, 7 -> 5, 8 -> 1,
8 -> 9, 9 -> 4, 9 -> 7
}, DirectedEdges -> True, VertexLabels -> "Name"];


This results in an apparently incorrect Adjacency Matrix:

AdjacencyMatrix[g]//MatrixForm

{
{0, 1, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0},
{1, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 1, 0, 0, 0}
}


This adjacency matrix is not what I expected: it seems that many edges are not correctly identified in the adjacency matrix. For instance, in my graph there is no edge from vertex 1 to 3, but I see a $$1$$ in the (1,3) element of the adjacency matrix. There are several other edges that appear incorrectly mapped in the matrix.

I suspect that the vertices are labeled in a way I do not understand. What am I misinterpreting?

• Not correct how? Can you point out where you think it is incorrect, and what you would expect as the correct result? Mar 19, 2021 at 16:51
• @MarcoB: I give a specific set of directed edges and looking at the adjacency matrix, I clearly see that many edges are not correctly given in the adjacency matrix. Just look at my digraph in which there is no edge from vertex 1 to 3, but I see there is 1 in the element (1,3) of the matrix. There are several other edges not correctly mapped in the matrix. Mar 19, 2021 at 16:56
• Look at VertexList[g] and remember that in general, vertex 4 is not the 4th vertex. Vertex name != vertex index. Mar 19, 2021 at 16:57
• Indeed, if you do AdjacencyGraph[ the matrix you find ] you'll see a picture indistinguishable from your original g. Mar 19, 2021 at 17:00
• Long-standing gotcha. I get bitten by it from time to time. Mar 19, 2021 at 20:47

• The vertices $$v_i$$ are assumed to be in the order given by VertexList[$$g$$].

If an explicit vertex list is not provided in the first argument of Graph:

• VertexList returns the list of vertices in the order used by the graph $$g$$.

Vertices are taken in the order they appear in the list of edges:

So... if you provide a vertex list vlist in the first argument of Graph then AdjacencyMatrix rows/columns correspond to the vertices in vlist.

ClearAll[g1, g2];

g1 = Graph[{1 \[DirectedEdge] 2, 1 \[DirectedEdge] 4,
1 \[DirectedEdge] 5, 2 \[DirectedEdge] 3, 2 \[DirectedEdge] 5,
3 \[DirectedEdge] 1, 3 \[DirectedEdge] 5, 3 \[DirectedEdge] 9,
4 \[DirectedEdge] 2, 4 \[DirectedEdge] 7, 5 \[DirectedEdge] 6,
6 \[DirectedEdge] 2, 6 \[DirectedEdge] 8, 7 \[DirectedEdge] 5,
8 \[DirectedEdge] 1, 8 \[DirectedEdge] 9, 9 \[DirectedEdge] 4,
9 \[DirectedEdge] 7}, DirectedEdges -> True,
VertexLabels -> "Name", ImageSize -> Medium];



g2 = Graph[
Range[9], {1 \[DirectedEdge] 2, 1 \[DirectedEdge] 4,
1 \[DirectedEdge] 5, 2 \[DirectedEdge] 3, 2 \[DirectedEdge] 5,
3 \[DirectedEdge] 1, 3 \[DirectedEdge] 5, 3 \[DirectedEdge] 9,
4 \[DirectedEdge] 2, 4 \[DirectedEdge] 7, 5 \[DirectedEdge] 6,
6 \[DirectedEdge] 2, 6 \[DirectedEdge] 8, 7 \[DirectedEdge] 5,
8 \[DirectedEdge] 1, 8 \[DirectedEdge] 9, 9 \[DirectedEdge] 4,
9 \[DirectedEdge] 7}, DirectedEdges -> True,
VertexLabels -> "Name", ImageSize -> Medium];



You can get am2 from am1 (and vice versa) using VertexList + Part:

am2 == am1[[Ordering @ VertexList[g1], Ordering @ VertexList[g1]]]

 True

am1 == am2[[VertexList[g1], VertexList[g1]]]

 True

• The list of vertex labels Range[] was missing from my graph. Thanks very much. Mar 19, 2021 at 17:40

If your demand is to have an adjacency matrix whose row/column orders are determined by the labels you give, rather than Mathematica's internal representation (given by the order of VertexList[g]) you can do

o = Ordering[VertexList[g]]
m = AdjacencyMatrix[g] (* Mathematica's ordering *)
y = m[[o,o]] (* your ordering *)


The resulting y is

{
{0, 1, 0, 1, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 1, 0, 0}
}


which may be what you're looking for?

I just picked Ordering because of the 'natural' ordering of your labels as integers. But you could pick any other ordering o and get a correct adjacency matrix.

• (But, you may be better off just working with Mathematica's ordering for both the labels, VertexList[g], and the AdjacencyMatrix[g].) Mar 19, 2021 at 17:36
• That is right. This is what I wanted. However, I still think that, for given numerical vertex names, the adjacency matrix should include the correct indices automatically. Unfortunately, it is not the case because vertex names are not always numeric. Therefore, setting the vertex names within Graph[VertexList[g], directed edges] solves the problem. Thanks for your time and effort. Mar 19, 2021 at 20:58