Adding edges to an acyclic graph

2
votes

I have a graph with directed and undirected edges, now I want to get rid of the undirected edges by replacing them with directed edges (each undirected edge becomes one directed edge). There are two possibilies for each undirected edge (replace it with a directed edge in one direction or the other direction).

How to determine the direction of the undirected edges so that my graph stays acyclic (a DAG)?

My approach:

Do a topological sort on the graph without the undirected edges, add the undirected edges one by one (make them point from smaller topo-vlalue to larger).

This doesn't seem to work since topological sort creates a partial order (not all vertices are comparable to each other), what I need is a total order (all vertices are comparable). How to extend the partial order to a total order?

An example graph where my approach fails:

  • n = 8 (number of vertices, numbered from 1 to n)
  • m = 5 (number of directed edges)
  • l = 6 (number of undirected edges)

Directed edges:

  1. 2 -> 1
  2. 3 -> 2
  3. 2 -> 6
  4. 4 -> 5
  5. 5 -> 8

Undirected edges:

  1. 1 <-> 4
  2. 2 <-> 5
  3. 3 <-> 7
  4. 4 <-> 8
  5. 6 <-> 7
  6. 6 <-> 8

The graph with only directed edges and topological order values beside the vertices:enter image description here

Now as I start adding undirected edges (and directing them according to the topological order values) I get a cycle after adding the edge 8 -> 4:enter image description here

https://en.wikipedia.org/wiki/Directed_acyclic_graph

2
javaalgorithmgraphtopological-sort
Topological sort by definition is a total order. – Saeed Amiri
Then I don't understand why my approach doesn't work, I added an example where my approach fails. What am I doing wrong? – PlsWork
You implement it wrongly, I think in your topological order definition if there is an edge from a to b then b is smaller than a. But in your second graph, you break the rule and add an edge from 4 to 6, you mixed the identifier of vertices (8,4) with their topological order (4,6). I turn these two comments to an answer – Saeed Amiri

2 Answers

2
votes

Topological sort by definition is a linear order and every linear order is a total order, so in theory, your approach is quite fine. However, your implementation is wrong.

I.e. in your topological order definition if there is an edge from a to b then b < a. But in your second graph, you break the rule and add an edge from 4 to 6 (6>4!), you mixed the identifier of vertices (8 and 4) with their topological order (4 and 6).

1
votes

To me, your approach seems valid. Take any ordering of the vertices; the existing edges should be oriented in such a way that they point 'right', i.e. from a vertex with lower position to a vertex with higher position. This is always possible and results in an acyclic directed graph.

In the next step, you can perhaps use Dedekind–MacNeille completion to generate a total ordering containing the initial ordering as a subset.