CODEWITHSUNDEEP
c++algorithmgraphdirected-acyclic-graphs
Rohit Ratnesh
Rohit Ratnesh

Reputation: 51

Is it possible to create back DAG from given all possible topological sort?

Is it possible to create back original DAG from given all possible topological sort of a DAG? And what if some n number(less than total possible topological sorts) of topological sorts given, can a DAG be constructed such that it satisfies given n topological orderings ?

Upvotes: 0

Views: 383

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58201

Given the vertices of your DAG, construct a new relation a->b defined by a->b if and only if a appears before b in all the given topological sorts.

This new graph is acyclic, transitive, and compatible with the given topological sorts.

Even given all topological orderings, it's not possible to uniquely determine the DAG, since the following two three-vertex DAGs have the same topological orderings.

a -> b -> c

a -> b -> c
 \________^

However, the above procedure produces the transitive closure of the original DAG, if you're given all possible topological orderings. Because if there's a path from a to b in the original DAG, then necessarily a appears before b in every topological ordering. Conversely, if a appears before b in every topological ordering, then there must be a path between a and b in the original DAG. For if not, add an edge between b and a in the original DAG (this can't form a cycle, since there's no path from a to b), and topologically sort the DAG. This gives a valid topological sort of the original DAG where b necessarily appears before a, giving a contradiction.

Upvotes: 3

Related Questions