Directed

Algorithms

Operation	Complexity
Breadth First Search	$O(v + e)$
Depth First Search	$O(v + e)$
Topological Sort	$O(v + e)$
Kosaraju's Strongly Connected Components	$O(v + e)$

sealed abstract class DirectedGraph[A](m: Map[A, Set[A]]) {

  /** Return first cycle detected, if one exists */
  def cycle(start: A): (List[A], Option[List[A]]) = {

    def dfs(
      stack: Chain[A],
      stackContains: Set[A],
      visited: LinkedHashSet[A]
    ): (List[A], Option[List[A]]) = 
      stack.headOption.fold(
        visited.toList -> (None: Option[List[A]])
      ) { top =>
        val (visited1, notVisited) =
          m.get(top)
            .fold(Set.empty[A] -> Set.empty[A])(_.partition(visited.contains))
        visited1
          .find(stackContains.contains)
          .fold(
            notVisited.foldLeft(List.empty[A] -> (None: Option[List[A]])) {
              (_, elem) =>
                dfs(
                  stack.prepend(elem),
                  stackContains + elem,
                  visited + elem
                )
            }
          )(cycleEnd =>
            visited.toList -> Some(stack.prepend(cycleEnd).toList))

      }

    dfs(Chain.one(start), Set.empty[A], mutable.LinkedHashSet.empty)

  }

  /** Post, reverse post (topological sort), pre traversals.
   *  Not stack safe
   * */
  def dfsTraversalsUnsafe[A](start: A): (LinkedHashSet[A], List[A], LinkedHashSet[A]) = {

    def dfs(
        curr: A,
        post: LinkedHashSet[A],
        reversePost: List[A],
        pre: LinkedHashSet[A]
    ): (LinkedHashSet[A], List[A], LinkedHashSet[A]) = {
      val preWithCurr = pre + curr
      val (post1, reversePost1, pre1) = m
        .get(curr)
        .fold((post, reversePost, preWithCurr))(nexts =>
          nexts.foldLeft((post, reversePost, preWithCur)) {
            case ((post, postStack, pre), next) =>
              if (pre.contains(next)) (post, postStack, pre)
              else dfs(next, post, postStack, pre)
        })
      (post1 + curr,
       if (post.contains(curr)) reversePost1 else curr :: reversePost1,
       pre1)
    }
  
    dfs(start, LinkedHashSet.empty, List.empty, LinkedHashSet.empty)
  
  }

  /** Kosaraju's algorithm for determining strongly connected
    * components in a directed graph. A graph is strongly connected if 
    * every vertex is reachable from every other vertex
    * */
  def stronglyConnectedComponents(start: A): Set[Set[A]] = {

    def dfs(
      stack: Chain[A],
      visited: LinkedHashSet[A],
      m: Map[A, Set[A]]
    ): LinkedHashSet[A] =
      stack.uncons.fold(
        visited
      ) {
        case (top, tail) =>
          val notVisited =
            m.get(top)
              .fold(Chain.empty[A])(nexts =>
                Chain.fromSeq(nexts.filterNot(visited.contains).toList))

          dfs(
            notVisited ++ tail,
            visited + top,
            m
          )
      }

    val stack = Chain.fromSeq(
      dfs(
        Chain.one(start),
        LinkedHashSet.empty,
        m
      ).toList)

    val complimentGraph =
      m.foldLeft(Map.empty[A, Set[A]]) {
        case (m, (k, vs)) =>
          vs.foldLeft(m) { (m, v) =>
            m.get(v).fold(m + (v -> Set(k)))(ks => m.updated(v, ks + k))
          }
      }

    stack
      .foldLeft(Set.empty[Set[A]] -> LinkedHashSet.empty[A]) {
        case ((out, visited), k) =>
          if (visited.contains(k)) out -> visited
          else {
            val res = dfs(
              Chain.one(k),
              visited,
              complimentGraph
            )
            (out + (res.toSet -- visited.toSet)) -> (visited ++ res)
          }
      }
      ._1

  }

}