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_01_DepthFirstTraversalImp_App extends App {

  import scala.collection.mutable.{TreeMap => MTreeMap, Map => MMap}

  trait Graph[V] {
    val vertices: List[V]
    val edge:     Map[V, List[V]]
    val mark:     MMap[V, Int]
  }

  def DFS[V](G: Graph[V]): Unit = {
    var count = 0
    G.vertices.foreach( G.mark(_) = 0 )
    G.vertices.foreach( v =>
      if (G.mark(v) == 0)
        dfs(v)
    )

    def dfs(v: V): Unit = {
      G.mark(v) = count
      count = count+1
      neighbors(v) foreach( w =>
        if (G.mark(w) == 0)
          dfs(w)
        )
    }

    def neighbors(w: V): List[V] = G.edge(w)

  }

  val graph: Graph[String] = new Graph[String] {
    override val vertices = List("a", "b", "c", "d", "e", "f")
    override val edge = Map(
      "a" -> List("b", "d"),
      "b" -> List("c","d"),
      "c" -> List("b"),
      "d" -> List("c", "e", "f"),
      "e" -> List("c"),
      "f" -> List("c"))
    override val mark = new MTreeMap()
  }

  DFS(graph)

  println(graph.mark)

}