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

  val V = List("Vlad", "Brunhilde", "Olga", "Rudiger", "Hildegard", "Anna")
  val E = List(
    ("Vlad", "Olga" :: "Hildegard" :: Nil),
    ("Brunhilde", "Rudiger" :: Nil ),
    ("Olga", "Hildegard" :: "Anna" :: Nil),
    ("Rudiger", Nil),
    ("Hildegard", Nil),
    ("Anna", "Rudiger" :: "Hildegard" :: Nil)
  )

  def MaxReachable(E: List[(String, List[String])]): String = {

    def R(v: String): List[String] = {
      var M: List[String] = Nil

      def Reach(E: List[(String, List[String])], v: String): List[String] = {
        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(E, v)
    }

    E . map ( _._1 ) // vertices
      . map( R(_))   // R of vertices
      . maxBy( _.length)  // get longest list
      . head // take head of list
  }

  println(MaxReachable(E))

}