5
$\begingroup$

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

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

Mathematica graphics

But sometimes it does not:

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

Mathematica graphics

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

Mathematica graphics

ug = UndirectedGraph[%, VertexLabels -> Automatic]

Mathematica graphics

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?

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

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]

enter image description here

enter image description here

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
 ]

enter image description here

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

$\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.