3
$\begingroup$

I define a graph:

g = Graph[{1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 
3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5, 
4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6}, 
VertexLabels -> "Name"]

The output looks correct in how the vertices are connected, but the AdjacencyMatrix[g] and VertexDegree[g] put the vertices out of order with my labels.

Why is that, and what is the order Mathematica uses?

$\endgroup$
  • 1
    $\begingroup$ Vertex ordering is completely unrelated to the names of the vertices. Vertices can be any expression, not just numbers. Never assume that numerical vertices are ordered from smallest to greatest. Use VertexIndex and VertexList to relate the index of a vertex to the vertex itself. In practice, Mathematica puts the vertices in the order you first specify them (as they appear in the edge list in your example), but never count on this as there's no guarantee and I won't be surprised if future versions change this. $\endgroup$ – Szabolcs May 25 '15 at 8:52
  • 1
    $\begingroup$ I removed the implementation-details tag because the question is more about what the function returns than about how the function works internally. $\endgroup$ – Szabolcs Aug 3 '15 at 15:21
6
$\begingroup$

AdjacencyMatrix >> Details:

enter image description here

VertexList >> Details:

enter image description here

So, unless you provide a vertex list as the first argument of Graph, VertexList[g] is populated with vertices in the order they appear in the edge list, i.e., {1, 3, 2, 4, 5, 6}. Using Range[6] as the first argument in Graph:

g1 = Graph[Range[6], {1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 
   3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5, 
   4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6}, 
  VertexLabels -> "Name", ImagePadding -> 10]

Mathematica graphics

versus

g2 = Graph[{1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 
   3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5, 
   4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6}, 
  VertexLabels -> "Name", ImagePadding -> 10]

Mathematica graphics

Their VertexLists and VertexDegrees:

Column[Labeled[TableForm[{VertexList@#, VertexDegree@#}, 
     TableHeadings -> {{"VertexList", "VertexDegree"}, None}], #2, 
    Top] & @@@ {{g1, "g1"}, {g2, "g2"}}, Spacings -> 2]

enter image description here

and AdjacencyMatrixs:

Row[Labeled[TableForm[Normal@AdjacencyMatrix@#, 
            TableHeadings -> {VertexList@#, VertexList@#}], 
      #2, Top] & @@@ {{g1, "g1"}, {g2, "g2"}}, Spacer[15]]

enter image description here

$\endgroup$

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.