TopologicalSort.scala

/**
 * 위상정렬 구현
 * @tparam T  노드의 ID 가 될 타입
 */
class TopologicalSort[T] {

  class CycleFoundException extends RuntimeException("At least one cycle found in the graph")

  /** edge 목록에서 incoming edges가 없는 vertex 를 찾는다. */
  def roots(vertices: Set[T], edges: Seq[(T, T)]): Set[T] = {
    val targets = edges.map(_._2).toSet
    vertices -- targets
  }

  /** edge 목록에서 모든 vertex의 집합을 구한다 */
  def vertices(edges: Seq[(T, T)]): Set[T] = {
    val sources = edges.map(_._1).toSet
    val targets = edges.map(_._2).toSet
    sources ++ targets
  }

  /** 위상정렬 */
  def apply(edges: Seq[(T, T)]): Seq[T] = apply(vertices(edges), edges)

  /** 위상정렬 */
  def apply(vertices: Set[T], edges: Seq[(T, T)]): Seq[T] = {
    if (vertices.isEmpty) return Nil

    val roots = this.roots(vertices, edges)
    if (roots.isEmpty) throw new CycleFoundException

    val remaining = edges.filterNot {
      case (source, target) => roots.contains(source)
    }

    roots.toSeq ++ apply(vertices -- roots, remaining)
  }

}

object TopologicalSort {
  def apply[T](edges: Seq[(T, T)]): Seq[T] = new TopologicalSort[T].apply(edges)
  def apply[T](vertices: Set[T], edges: Seq[(T, T)]): Seq[T] = new TopologicalSort[T].apply(vertices, edges)
}