package kapitel_06

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 6, Graphen: Jeder mit jedem
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_06_02_DepthFirstTraversalFunc_App extends App {

  type Graph[V] = List[(V, V)]

  // alle von einem Knoten aus erreichbaren anderen Knoten
  def Reachable[V](start: V, graph: Graph[V]): List[V] = {

    def successors(node: V, g: Graph[V]): List[V] = g match {
      case Nil => Nil
      case (n1, n2) :: gRest if node == n1 =>
        n2 :: successors(node, gRest)
      case _ :: gRest =>
        successors(node, gRest)
    }

    def trav(from: List[V], visited: List[V]) : List[V] = from match {
      case Nil => visited
      case node :: rest if visited.contains(node) => trav(rest, visited)
      case node :: rest => trav(successors(node, graph) ++ rest, node :: visited)
    }

    trav(start :: Nil, Nil).reverse
  }

  val g: Graph[String] = List(
    ("a","b"), ("a","d"), ("b","c"),
    ("b","d"), ("c","b"), ("d","c"),
    ("d","e"), ("d","f"), ("e","c"), ("f","c") )

  println(Reachable("a", g))

}