Depth First Directed Paths Algorithm

The Depth First Directed Paths (DFDP) Algorithm is an essential graph traversal technique that explores all the vertices and edges of a directed graph. This algorithm follows the depth-first search (DFS) pattern, which means it traverses the graph by visiting a vertex and exploring its adjacent vertices as deeply as possible before backtracking. In other words, it dives into the graph visiting the unvisited vertices along a path, and once it reaches a dead-end, it backtracks to explore other branches until all vertices are visited. DFDP can be used to find directed paths and cycles in a graph, as well as to determine if a given directed graph is acyclic. The implementation of the DFDP algorithm typically involves using recursion or an explicit stack data structure for backtracking purposes. It starts from a given source vertex and marks it as visited, then recursively explores its adjacent and unvisited vertices. During the exploration, the algorithm keeps track of the edge that connects each vertex to its predecessor in the path, which can be later used to reconstruct the directed path between the source vertex and any other reachable vertex. Once the algorithm completes its traversal, one can determine whether a directed path exists between the source vertex and any other vertex in the graph, as well as retrieve the corresponding path by following the chain of predecessor edges.
package org.gs.digraph

import scala.annotation.tailrec

/** Find paths from single source vertex
  *
  * @constructor createa a new DepthFirstDirectedPaths with a digraph and a source vertex
  * @param g Digraph
  * @param s a single source vertex
  * @see [[https://algs4.cs.princeton.edu/42directed/DepthFirstDirectedPaths.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
class DepthFirstDirectedPaths(g: Digraph, s: Int) {
  private val marked = new Array[Boolean](g.numV)
  private val edgeTo = new Array[Int](g.numV)

  private def dfs(v: Int) {
    marked(v) = true
    g.adj(v) foreach (w => if (!marked(w)) {
      edgeTo(w) = v
      dfs(w)
    })
  }
  dfs(s)

  /** returns if there is a path from s to v */
  def hasPathTo(v: Int): Boolean = marked(v)

  /** returns the path from s to v */
  def pathTo(v: Int): List[Int] = {

    @tailrec
    def loop(x: Int, xs: List[Int]): List[Int] = if (x == s) x :: xs else loop(edgeTo(x), x :: xs)

    loop(v, List[Int]())
  }
}

LANGUAGE:

DARK MODE: