package kapitel_10

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 10, Verbindungen finden
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_10_02_ShortestPathsWithPath_App extends App {

  def boarderEdges(V: List[String], E: List[(String, String)]): List[(String,String)] =
    for ( v <- V;
          (x, y) <- E
          if x == v && !V.contains(y)
          ) yield (v, y)


  /*
   * Der Algorithmus, der neben der Länge des kürzesten Pfads auch diesen selbst berechnet,
   * kann als Erweiterung der Variante ohne Pfade realisiert werden:
   */

  def ShortestPaths(
                     s: String,     // start
                     V: List[String], // all vertices
                     E: List[(String, String)], // all edges
                     w: Map[(String, String), Int] // all weights
                   ): Map[String, (Int, List[String])] = {

    var S: List[String] = s :: Nil
    var U: List[String] = V.filter( _ != s)
    var SP: Map[String, (Int, List[String])] = Map(s -> (0, List(s)))

    while ( U.nonEmpty ) {
      val outNodesWithDist =
        for ((inNode, outNode) <- boarderEdges(S, E))
          yield (outNode, (SP(inNode)._1 + w((inNode, outNode)), SP(inNode)._2 ++ List(outNode) ))
      val (u, (d, p)) = outNodesWithDist.minBy {
        case (_, (distance, _)) => distance
      }
      S = u :: S
      U = U.filter( _ != u)
      SP = SP + (u -> (d, p))
    }
    SP
  }

  val V = List("a", "b", "c", "d", "e")

  val w = Map[(String, String), Int](
    ("d", "b") -> 2,
    ("b", "a") -> 3,
    ("b", "c") -> 4,
    ("e", "d") -> 4,
    ("d", "c") -> 5,
    ("c", "e") -> 6,
    ("a", "d") -> 7
  )

  val E = w.keySet.toList

  ShortestPaths("a", V, E, w).foreach {
    case (dest, (len, path)) => println(s"a -> $dest = $len, path = ${path.mkString(",")}")
  }

}