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

  trait Graph[V] {
    val Vertices: List[V]
    val Edges: List[(V, V)]
  }

  def TopoSortFunc[V](G: Graph[V]): List[V] = G.Vertices match {
    case Nil => Nil
    case _ =>
      val sources = // find sources (no ingoing edge)
        for (v <- G.Vertices
             if G.Edges.count {
               case (_, y) if y == v => true
               case _ => false
             } == 0
        ) yield v
      val n = sources.head // take first source
      n :: TopoSortFunc(
        new Graph[V] { // graph without first source
          override val Vertices: List[V] = G.Vertices.filter(_ != n)
          override val Edges: List[(V, V)] = G.Edges.filter {
            case (x, _) if x != n => true
            case _ => false
          }
        }
      )
  }

  val partialOrder: Graph[String] = new Graph[String] {

    override val Vertices: List[String] = List(
      "Socken", "Schuhe", "Uhr", "Unterhose", "Jackett",
      "Hemd", "Hose", "Guertel", "Krawatte", "Unterhemd")

    override val Edges: List[(String, String)] = List(
      ("Unterhemd", "Hemd"),
      ("Krawatte", "Jackett"),
      ("Hose", "Schuhe"),
      ("Hose", "Guertel"),
      ("Socken", "Schuhe"),
      ("Unterhose", "Hose"),
      ("Unterhose", "Schuhe"),
      ("Guertel", "Jackett"),
      ("Hemd", "Guertel"),
      ("Hose", "Schuhe"),
      ("Socken", "Hose"),
      ("Hemd", "Krawatte")
    )
  }

  println(TopoSortFunc(partialOrder).mkString(","))

}