1
$\begingroup$

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.

enter image description here

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Szabolcs
    Jun 15, 2021 at 8:42
  • $\begingroup$ 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. $\endgroup$
    – JJJJJJJJJJJJJJJJ
    Jun 16, 2021 at 18:01

2 Answers 2

Reset to default
4
$\begingroup$

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[190]:= g = Graph[{1, 2, 3}, {3 <-> 2, 1 <-> 2}];

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

In[192]:= EdgeList@GraphComputation`ToGraphRepresentation[g, "Sparse"]
Out[192]= {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[199]:= 
g = Graph[{1, 2, 3}, {3 <-> 2, 1 <-> 2}];
EdgeList@DirectedGraph[g, "Acyclic"]

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

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

Out[202]= {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.

Improve this answer
$\endgroup$
3
$\begingroup$

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]

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.