6
$\begingroup$

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?

$\endgroup$
10
  • 1
    $\begingroup$ Not correct how? Can you point out where you think it is incorrect, and what you would expect as the correct result? $\endgroup$
    – MarcoB
    Mar 19, 2021 at 16:51
  • $\begingroup$ @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. $\endgroup$ Mar 19, 2021 at 16:56
  • 4
    $\begingroup$ Look at VertexList[g] and remember that in general, vertex 4 is not the 4th vertex. Vertex name != vertex index. $\endgroup$
    – Szabolcs
    Mar 19, 2021 at 16:57
  • 1
    $\begingroup$ Indeed, if you do AdjacencyGraph[ the matrix you find ] you'll see a picture indistinguishable from your original g. $\endgroup$
    – evanb
    Mar 19, 2021 at 17:00
  • 3
    $\begingroup$ Long-standing gotcha. I get bitten by it from time to time. $\endgroup$ Mar 19, 2021 at 20:47

2 Answers 2

4
$\begingroup$

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

enter image description here

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

enter image description here

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
$\endgroup$
1
  • $\begingroup$ The list of vertex labels Range[] was missing from my graph. Thanks very much. $\endgroup$ Mar 19, 2021 at 17:40
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ (But, you may be better off just working with Mathematica's ordering for both the labels, VertexList[g], and the AdjacencyMatrix[g].) $\endgroup$
    – evanb
    Mar 19, 2021 at 17:36
  • $\begingroup$ 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. $\endgroup$ Mar 19, 2021 at 20:58

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.