Edge Weighted Directed Cycle Algorithm
The Edge Weighted Directed Cycle Algorithm is a graph theory algorithm used to detect and find the weighted directed cycle with the minimum total weight in a directed weighted graph. A directed weighted graph is a collection of vertices (nodes) and edges, where each edge has an associated weight (cost) and a direction. The algorithm is particularly useful in solving various real-world problems, such as finding the shortest route for a delivery vehicle or determining the optimal order of tasks in a project with precedence constraints and task durations. It is an extension of the standard cycle detection algorithms, such as Depth-First Search (DFS) or Breadth-First Search (BFS), and takes into account the weights of the edges in the graph.
To implement the Edge Weighted Directed Cycle Algorithm, we perform a modified DFS traversal on the given directed weighted graph. During the traversal, we maintain a stack to keep track of the vertices in the current path and an array to store the edgeTo information (the edge that connects a vertex to its parent in the traversal tree). When a back edge (an edge that connects the current vertex to an ancestor in the traversal tree) is encountered, we have found a cycle, and we can compute the total weight of this cycle by summing up the weights of its constituent edges. To find the minimum weighted directed cycle, we compare the weight of the newly found cycle with the previously found cycles and update the minimum weight cycle accordingly. Once the traversal is complete, we will have the minimum weighted directed cycle in the given graph. If there is no cycle in the graph, the algorithm will indicate that as well.
package org.gs.digraph
import scala.annotation.tailrec
/** Find if an edge weighted digraph has a directed cycle, return it if it does
*
* @constructor creates a new EdgeWeightedDirectedCycle with an EdgeWeightedDigraph
* @param g acyclic digraph, edges have direction and weight
* @see [[https://algs4.cs.princeton.edu/44sp/EdgeWeightedDirectedCycle.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class EdgeWeightedDirectedCycle(g: EdgeWeightedDigraph) extends BaseDirectedCycle[DirectedEdge](g.numV) {
protected def dfs(v: Int): Unit = {
onStack(v) = true
marked(v) = true
@tailrec
def loopEdges(es: List[DirectedEdge]): Unit = es match {
case e :: xs => {
search(e)
loopEdges(xs)
}
case _ =>
}
def search(e: DirectedEdge): Unit = {
if (!hasCycle) {
val w = e.to
val newV = !marked(w)
if (newV) {
edgeTo(w) = e
dfs(w)
} else if (onStack(w)) {
def traceBack(): Option[List[DirectedEdge]] = {
_cycle = Some(List[DirectedEdge]())
@tailrec
def loop(x: DirectedEdge): Unit =
if (x.from != w) {
_cycle = Some(x :: _cycle.get)
loop(edgeTo(x.from))
} else _cycle = Some(x :: _cycle.get)
loop(e)
_cycle
}
val c = traceBack()
}
}
}
val es = g.adj(v)
loopEdges(es)
if (!hasCycle) onStack(v) = false
}
}
