Base Directed Cycle Algorithm
The Base Directed Cycle Algorithm is an advanced graph theory algorithm designed to identify cycles within directed graphs. Directed graphs, also known as digraphs, are a collection of vertices (nodes) and directed edges (arrows), where each edge has an initial vertex, known as the tail, and a terminal vertex, known as the head. The Base Directed Cycle Algorithm aims to detect the presence of cycles, which are a sequence of vertices and edges that starts and ends at the same vertex, in these directed graphs. Detecting cycles in directed graphs is a critical component in various applications, including deadlock detection in distributed systems, resource allocation, and circuit analysis.
The Base Directed Cycle Algorithm works by performing a depth-first search (DFS) traversal on the directed graph, visiting each vertex and its corresponding edges. During the traversal, the algorithm maintains a stack of visited vertices and keeps track of the vertices' status, such as unvisited, visited, and completed. When the algorithm encounters an edge whose head is already in the visited stack, it indicates the presence of a cycle. The algorithm then returns the cycle, which consists of the path from the head of the detected edge to the current vertex. If the entire graph has been traversed without finding any cycles, the algorithm concludes that the directed graph is acyclic. The Base Directed Cycle Algorithm is efficient and effective in detecting cycles, making it a popular choice for solving a variety of problems in computer science and engineering.
package org.gs.digraph
import scala.reflect.ClassTag
/** Superclass of directed cycles
*
* @constructor called by subclass with number of vertices
* @tparam A use Int for DirectedCycle or use DirectedEdge for EdgeWeightedDirectedCycle
* @param v number of vertices in a Digraph or EdgeWeightedDigraph
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
abstract class BaseDirectedCycle[A: ClassTag](v: Int) {
protected val marked = Array.fill[Boolean](v)(false)
protected val onStack = Array.fill[Boolean](v)(false)
protected val edgeTo = new Array[A](v)
protected var _cycle: Option[List[A]] = None
for {
v <- 0 until v
if (!marked(v))
} dfs(v)
protected def dfs(v: Int): Unit
/** @return directed cycle as a List if a cycle exists */
def cycle(): Option[List[A]] = _cycle
/** returns if digraph has a directed cycle */
def hasCycle(): Boolean = _cycle != None
}
