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

  /*
   * Die Mengen und Mengen-Operationen im Pseudocode stehen dabei für irgendwelche (noch) nicht näher spezifizierte
   * Datenstrukturen und die Operationen auf diesen Strukturen. Wir nehmen als konkrete Datenstruktur Liste.
   */

  // find all external direct neighbors elements of V
  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)


  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] = {

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

    while ( Ui.nonEmpty ) {
      val (u, d) = boarderEdges(Vi, E).map {
        case (inNode, outNode) =>
          (outNode, SP(inNode) + w((inNode, outNode)))
      }.minBy {
        case (_, distance) => distance
      }
      Vi = u :: Vi
      Ui = Ui.filter( _ != u)
      SP = SP + (u -> d)
    }
    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) => println(s"a -> $dest = $len")
  }


}