Is it possible to use Warshall's algorithm (calculating the transitive closure) to determine if a directed graph is acyclic or not?
I'm trying to achieve this but getting stuck on the reflexive property of the transitive closure!
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I'm not intending to change Warshall's algorithm but I'm wondering if by just taking the resulting matrix it's even possible to conclude anything about this property, especially because of the reflexive property. I think it's not. $\endgroup$ – Azz Jan 16 '13 at 22:14
Add a comment
|
$\begingroup$
$\endgroup$
After running Warshall's algorithm (let's call the input graph $G$ and the resulting graph $G'$), we can reason that if there were a cycle $c_1\rightarrow c_2\rightarrow\ldots\rightarrow c_n\rightarrow c_1$ in $G$, then for every old edge of this cycle $c_i\rightarrow c_{i+1}$ there has to be a new, antisense edge $c_{i+1}\rightarrow c_i$, because it's a part of the closure of the path $c_{i+1}\rightarrow c_{i+2}\rightarrow\ldots\rightarrow c_{i-1}\rightarrow c_i$.
Also, for every 2-cycle ($c_1\rightarrow c_2\rightarrow c_1$) in $G'$ we know from the semantics of the algorithm that any of the two edges stands for some oriented path in $G$: $c_1=p_{1_1}\rightarrow p_{1_2} \rightarrow\ldots p_{1_n}=c_2$ and $c_2=p_{2_1}\rightarrow p_{2_2} \rightarrow\ldots p_{2_n}=c_1$. It's easy to think about gluing these two together to get at least one original cycle.
So, we estabilished an equivalency between "there is a cycle in $G$" and "there is a 2-cycle in $G'$".
$\begingroup$
$\endgroup$
It is possible to use Warshall's algorithm for that also. If there is is a negative entry on the diagonal, then the graph contains a negative cycle. If both the shortest path from i to j and the shortest path from j to i is not infinite, then the graph contains a cycle. If there are no i and j with this property, then the graph is acyclic. (This takes only $O(|V|^2)$ steps to check, while Warshall's algorithm itself takes $O(|V|^3)$ steps.)
However, it's faster to use depth first search and check that there are no backward edges in the depth first search tree. Also note that there exists an algorithm for computing the transitive closure (including the transitive reduction) in $O(|V|\cdot|E|)$ steps. (I think it uses a topological order as a starting point.)
