Directed Cycle Algorithm
The Directed Cycle Algorithm is a graph traversal technique used to detect cycles in a directed graph. This algorithm is essentially an extension of the Depth-First Search (DFS) algorithm, which operates by exploring the graph in a depthward motion, visiting a vertex's adjacent vertices before backtracking. The primary objective of the Directed Cycle Algorithm is to identify the presence of any directed cycles in a given graph, which are sequences of vertices with directed edges such that the initial and final vertices are the same. Identifying directed cycles is essential in various real-world applications, including deadlock detection in operating systems, identifying circular dependencies in software systems, and analyzing feedback loops in biological networks.
To implement the Directed Cycle Algorithm, one needs to maintain three sets of vertices - visited, on-stack, and completed. Initially, all vertices are unmarked and belong to the visited set. During the DFS traversal, when a vertex is encountered, it is moved from the visited set to the on-stack set. The algorithm then recursively explores the adjacent vertices of the current vertex. If it encounters a vertex that is already in the on-stack set, this indicates the presence of a directed cycle. At this point, the algorithm can terminate as the primary goal of detecting a cycle is achieved. If the DFS traversal completes without encountering any cycles, the graph is deemed to be acyclic. Throughout the traversal, when a vertex's neighbors have been fully explored, it is moved from the on-stack set to the completed set, signifying that the vertex and its descendants have been processed.
package org.gs.digraph
import scala.annotation.tailrec
/** Find any directed cycles in digraph using depth first search
*
* @constructor creates a new DirectedCycle with a digraph and number of vertices
* @param g Digraph
* @see [[https://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class DirectedCycle(g: Digraph) extends BaseDirectedCycle[Int](g.numV) {
protected def dfs(v: Int) {
onStack(v) = true
marked(v) = true
def recurOnNewVertex(w: Int): Boolean = if (!marked(w)) {
edgeTo(w) = v
dfs(w)
true
} else false
def traceBack(w: Int): Boolean = {
if (onStack(w)) {
_cycle = Some(List[Int]())
@tailrec
def loop(x: Int): Unit = {
if (x != w) {
_cycle = Some(x :: _cycle.get)
loop(edgeTo(x))
}
}
loop(v)
_cycle = Some(v :: w :: _cycle.get)
true
} else false
}
@tailrec
def loopW(w: Int, xs: List[Int]): Unit = {
if (!hasCycle) {
if (!recurOnNewVertex(w)) traceBack(w)
xs match {
case x :: xs => loopW(x, xs)
case Nil =>
}
}
}
if (!hasCycle) {
g.adj(v) match {
case x :: xs => loopW(x, xs)
case Nil =>
}
onStack(v) = false
}
}
}
