Why does UndirectedGraph sometimes relabel vertices?

Question

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?

Answer 1

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] /. 
   AssociationThread[VertexList[dg], Range[VertexCount[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]

GraphComputation`GraphRepresentation[g]
GraphComputation`GraphRepresentation[ug]

"Incidence"

"Simple"

I observe a similar behavior also for graphs that have Sparse as result of GraphComputation`GraphRepresentation.

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

UndirectedGraph[
 GraphComputation`ToGraphRepresentation[dg, "Incidence"],
 VertexLabels -> Automatic
 ]

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