Difference between vertex names and indices in a directed graph

Question

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?

Answer 1

AdjacencyMatrix >> Details:

• 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 >> Details:

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

VertexList >> Properties and Relations:

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

Row[{g1, MatrixForm[am1 = AdjacencyMatrix[g1]]}]

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

Row[{g2, MatrixForm[am2 = AdjacencyMatrix[g2]]}]

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

Answer 2

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.