# Retain Edge Ordering in DAG Conversion

I would like to convert an undirected graph into a directed graph such that for each tuple, the first value is a head and the second is a tail in a directed edge.

Initially I thought using DirectedGraph[G, "Acyclic"] would straightforwardly solve this, but considering an example with edges E={{1,2},{2,3},{5,3},{3,4},{4,6}}, the {5,3} edge connects from 3 to 5. I could convert the graph into something like E={{1,2},{2,4},{3,4},{4,5},{5,6}}, and imagine an algorithm exists that detects edges with a larger head and relabels the vertices. For example I could locate a bad pair, swap labels to get {{1,2},{2,5},{3,5},{5,4},{4,6}} while swapping the vertex coordinates in-step, iterating until a result like {{1,2},{2,4},{3,4},{4,5},{5,6}}. But I wonder what simpler and/or alternative methods you might think of.

• Can you show a complete example of what you did? The vertex ordering in your graph probably doesn't correspond to vertex names (as integers). Jun 15, 2021 at 8:42
• To produce the graph above, I used something along the lines of Graph[E, VertexLabels -> {1,...,6}]. Generally what I do is create a graph Graph[E, VertexCoordinates->V] where V is a list of coordinates, and Mathematica treats the i'th coordinate as vertex i. Jun 16, 2021 at 18:01

If you have an undirected graph, there is no concept of edge direction. This is what "undirected" means. While Mathematica appears to preserve the ordering of edge endpoints in many cases, I would definitely not rely on this. The internal graph representation may change at some point, which may not preserve the endpoint order of undirected edges. Example:

In:= g = Graph[{1, 2, 3}, {3 <-> 2, 1 <-> 2}];

In:= EdgeList[g]
Out= {3 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 2}

In:= EdgeList@GraphComputationToGraphRepresentation[g, "Sparse"]
Out= {1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3}


If you have not a graph object, but a list of ordered pairs, convert them to a directed graph directly:

pairs = {{3, 2}, {1, 2}};

Graph[DirectedEdge @@@ pairs]


What does DirectedGraph[..., "Acyclic"] do? It orients the edges from vertices that appear earlier in the vertex list to vertices which appear later. For example:

In:=
g = Graph[{1, 2, 3}, {3 <-> 2, 1 <-> 2}];
EdgeList@DirectedGraph[g, "Acyclic"]

Out= {1 \[DirectedEdge] 2, 2 \[DirectedEdge] 3}

In:=
g = Graph[{1, 3, 2}, {3 <-> 2, 1 <-> 2}];
EdgeList@DirectedGraph[g, "Acyclic"]

Out= {1 \[DirectedEdge] 2, 3 \[DirectedEdge] 2}


Notice that the only difference between the two inputs above is the vertex ordering.

You may be interested in my IGraph/M package, which has IGReorderVertices to easily reorder vertices without losing any edge/vertex attributes.

You need to use: "DirectedEdge":

e = {{1, 2}, {2, 3}, {5, 3}, {3, 4}, {4, 6}, {6, 3}};
l = DirectedEdge @@@ e
Graph[l, VertexLabels -> All]
` 