I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as first $n$ natural numbers. (Note that once created, the graph $G$ may have more topological orderings apart from the ones given.)
The following constraints should be met:
- The maximum outdegree of every node should be 1
- The number of nodes having indegree 0 should be minimum.
There can be multiple solutions, any of them should work.
What I have tried. (Approach 1 which is wrong as it fails one example given in the answer. Please scroll to the second approach, which still I'm not able to find a mistake.)
From all the given orderings, first, create a directed graph by creating a directed edge from every node to its next node. This means if the orderings are:
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$
I will create a directed graph with a directed edge from $1$ to $3, 3$ to $2, 2$ to $5$ and so forth.
This ensures that the number of nodes with indegree 0 remains minimum. Now, I'll remove all the cycles and make sure all the orderings are valid and finally, eliminate all the extra edges any node has. WHile doing so, I'll make sure that if there are two nodes whose edge is coming from the same node, I'll remove the edge from the node having a higher indegree, so that condition 2 is met. The graph constructed then, should look like:
This DAG created, follows both the constraints, and IMO has the minimum number of nodes of indegree as 0, although, it's not proven.
I have coded the approach and it is giving expected results for the use cases I supply, but I know that it is wrong. What am I missing here? Can anyone provide an alternative use case, which fails the above approach?
I create a directed graph $G$ by creating an edge from $a_i $ to $ a_j$ for all $ j > i$ in all the orderings given. So, for the orderings:
$$ 1, 2, 3, 4, 5$$ $$ 2, 4, 1, 5, 3$$
I will create the following graph:
The first step after this is to validate all the orderings. Removing cycles separately is not required as they will be removed by this step itself.
For any ordering $$ a_1, a_2, a_3, a_4, ... a_n $$ I will check if there exists any edge from $a_j$ to $a_i$ where $ j > i$, I'll remove that edge.
Doing so, will give the following graph:
The last step is to remove extra edges from all nodes as maximum outdegree of any node can be $1$ max. I'll remove the outgoing edges such that the number of nodes having indegree $0$ is minimum. First I calculate the indegree of each node. Then for each node which has more than 1 outgoing edges, I'll remove all the edges except the one with the minimum indegree.
This graph satisfies both the constraints. But I know this approach is wrong! Can anyone help to find why is this wrong?