Undirected

Algorithm

Operation	Complexity
Breadth First Search	$O(v + e)$
Depth First Search	$O(v + e)$

import scala.collection.immutable.Queue
import scala.collection.mutable.{LinkedHashSet, LinkedHashMap}
import cats.data.Chain

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

  /**
    * @param start  what vertex to search from
    * @param endOpt what vertex to end at. if None, will visit all vertices connected to `start`
    *
    *
    * @return (vertexes visited in order,
    *
    *         if `endOpt` was found (if Some),
    * 
    *         a map of each vertex visited to what
    *         vertex it was visited from. Can
    *         be used to find a path back from one vertex
    *         to another
    *         )
    * 
    * */
  def depthFirst(
    start: A,
    endOpt: Option[A] = None
  ): (List[A], Boolean, Map[A, A]) = {

    def go(
      stack: Chain[A],
      visited: LinkedHashSet[A],
      edgeTo: Map[A, A]): (List[A], Boolean, Map[A, A]) =
      stack.uncons.fold((visited.iterator.toList, false, edgeTo)) {
        case (head, tail) =>
          if (Some(head) == endOpt)
            ((visited + head).iterator.toList, true, edgeTo)
          else {
            val nexts = m
              .get(head)
              .fold(Chain.empty[A])(next =>
                Chain(next.filterNot(visited.contains).toList: _*))
            go(
              nexts ++ tail,
              visited + head,
              nexts.map(_ -> head).toList.toMap ++ edgeTo
            )
          }
      }

    go(Chain.one(start), new LinkedHashSet[A], Map.empty)
  }
  
  /** We're using the call stack as our dfs stack instead
      * of a maintaining a stack data structure. This will blow
      * stack with sufficiently large graphs */
  def depthFirstUnsafe(
      start: A,
      endOpt: Option[A] = None
  ): List[A] = {

    def dfs(
        curr: A,
        visited: LinkedHashSet[A]
    ): LinkedHashSet[A] =
      m.get(curr)
        .fold(
          visited
        ) { nexts =>
          nexts.foldLeft(visited) { (visited, next) =>
            if (visited.contains(next)) visited
            else if (Some(next) == endOpt) visited + next
            else visited ++ dfs(next, visited + next)
          }

        }

    dfs(start, LinkedHashSet(start)).toList

  }

  def breadthFirst(
    start: A,
    end: Option[A] = None
  ): (List[A], Boolean, Map[A, A]) = {

    def go(
      queue: Queue[A],
      visited: LinkedHashSet[A],
      edgeTo: Map[A, A]
    ): (List[A], Boolean, Map[A, A]) =
      queue.dequeueOption.fold(
        (visited.toList, false, edgeTo)
      ) {
        case (a, rest) =>
          if (Some(a) == end)
            ((visited + a).toList, true, edgeTo)
          else {
            val nexts = m
              .get(a)
              .fold(Queue.empty[A])(next =>
                Queue(next.filterNot(visited.contains).toList: _*))
            go(
              rest ++ nexts,
              visited + a,
              nexts.map(_ -> a).toMap ++ edgeTo
            )
          }
      }

    go(Queue(start), LinkedHashSet.empty, Map.empty)

  }

  /** Is there a cycle in the undirected graph? */
  def cycle(start: A): Boolean = {

    def go(
      stack: Chain[A],
      visited: LinkedHashSet[A],
      previous: A
    ): Boolean =
      stack.uncons.fold(false) {
        case (top, tail) =>
          m.get(top)
            .fold(false) { next =>
              next.foldLeft(false) { (bool, a) =>
                if (!visited.contains(a))
                  go(
                    tail.prepend(a),
                    visited + top,
                    top
                  )
                else
                  (a != previous) || bool
              }
            }
      }

    go(Chain.one(start), LinkedHashSet.empty, start)
  }

  /** Each vertex is assigned !boolean of the 
    * boolean assigned to the vertex from which it was visited.
    * If it so happens that there is a neighboring vertex
    * that is neighborBoolean == currentBoolean, then this
    * is not a bipartite graph
    * */
  def bipartite(start: A): Boolean = {

    def go(
      stack: Chain[(A, Boolean)],
      visited: mutable.LinkedHashMap[A, Boolean]
    ): Boolean =
      stack.uncons.fold(true) {
        case ((top, bool), tail) =>
          val (visited1, notVisited) = m
            .get(top)
            .fold(Set.empty[A] -> Set.empty[A])(_.partition(visited.contains))
          if (visited1.forall(visited(_) != bool))
            go(
              Chain(notVisited.map(_ -> !bool).toList: _*) ++ tail,
              visited += (top -> bool)
            )
          else false
      }

    go(Chain.one(start -> true), mutable.LinkedHashMap.empty[A, Boolean])
  }
  
  /** Uses dfs to find the connected components */
  def connectedComponents: Set[Set[A]] = {

    def dfs(
      stack: Chain[A],
      visited: LinkedHashSet[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.keys
      .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),
              LinkedHashSet.empty[A]
            )
            (out + res.toSet) -> (visited ++ res)
          }
      }
      ._1
  }
  
}