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

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

  def R[V](G: Graph[V], v: V): List[V] = {

    var M: List[V] = Nil // marks

    def Reach(E: Map[V, List[V]], v: V) : List[V] = {
      M = v :: M
      var result = v :: Nil
      for ((x, ww) <- E) {
        if (x == v) {
          for (w <- ww) {
            if (!M.contains(w)) {
              result = result ++ Reach(E, w)
            }
          }
          return result
        }
      }
      Nil
    }
    Reach(G.edge, v)
  }

  def MaxReach[V](G: Graph[V]): V =
    (for(v <- G.vertices )
        yield R(G, v)
      ).maxBy( _.length ).head


  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"))
  }

  println(MaxReach(graph))
}