Why does UndirectedGraph sometimes relabel vertices?

Normally, UndirectedGraph preserves the vertex names and the vertex ordering.

UndirectedGraph[Graph[{"a" -> "b"}], VertexLabels -> Automatic]


But sometimes it does not:

g = Graph[{1 <-> 0, 0 <-> 2}, VertexLabels -> Automatic]


dg = DirectedGraph[g, "Acyclic", VertexLabels -> Automatic]


ug = UndirectedGraph[%, VertexLabels -> Automatic]


EdgeList[g]
(* {1 \[UndirectedEdge] 0, 0 \[UndirectedEdge] 2} *)

EdgeList[ug]
(* {1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3} *)


Is this inconsistency a bug? What is different between the first directed graph and the above example and dg that causes UndirectedGraph to process them differently?

• you should contact tech support for this. – halmir Apr 23 '18 at 13:38
• @halmir Thanks for the comment. I sent the report to support. – Szabolcs Apr 23 '18 at 14:46
• @halmir Thanks for fixing this one! – Szabolcs Oct 26 '18 at 19:05

Starting with a graph with strings as vertex names leads to the same output:

g = Graph[{"b" <-> "a", "a" <-> "c"}, VertexLabels -> Automatic];
dg = DirectedGraph[g, "Acyclic", VertexLabels -> Automatic]
ug = UndirectedGraph[%, VertexLabels -> Automatic]


It appeared to me that the vertex ordering is not changed but that vertices are merely replaced by their position within VertexList[dg]:

EdgeList[ug] == (UndirectedEdge @@@ EdgeList[dg] /.


True

The problem seems to occur (only?) when the internal graph representation of the graph handed over to UndirectedGraph is by a SparseArray which is the case for dg but not for hand-woven graphs such as g or UndirectedGraph[Graph[{"a" -> "b"}], VertexLabels -> Automatic]

GraphComputationGraphRepresentation[g]
GraphComputationGraphRepresentation[ug]


"Incidence"

"Simple"

I observe a similar behavior also for graphs that have Sparse as result of GraphComputationGraphRepresentation.

Another evidence is that we can use conversion of the internal graph representation as a workaround:

UndirectedGraph[
GraphComputationToGraphRepresentation[dg, "Incidence"],
VertexLabels -> Automatic
]


Summed up, I cannot imagine that this inconsistency were intentional. I vote for the bug tag.