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

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

  def TopoSortImp[V](G: Graph[V]): List[V] = {
    val adjMatrix = Array.fill[Boolean](G.Vertices.length,G.Vertices.length)( false)

    for ( v <- G.Vertices;
          (x, y) <- G.Edges) {
          if (x == v) {
        adjMatrix(G.Vertices.indexOf(x))(G.Vertices.indexOf(y)) = true
      }
    }

    val Vremaining: Array[Boolean] = Array.fill[Boolean](G.Vertices.length)(true)

    var result = List[V]()

    while (Vremaining.contains(true)) {

      // print adjacency matrix
      println(adjMatrix.map( _.map(if(_) "1" else "0")).map( _.mkString(",\t")).mkString("\n"))
      println()

      for (v <- 0 until G.Vertices.length) {
        if (Vremaining(v)) { // v ist noch aktiv
          if (!adjMatrix.exists( _(v) == true)) { // es zeigt nichts auf v
            Vremaining(v) = false // remove v form V
            result = G.Vertices(v) :: result // store v
            for (j <- 0 until G.Vertices.length) {
              adjMatrix(v)(j) = false
            }
          }
        }
      }
    }

    result.reverse
  }

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

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

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

  println(TopoSortImp(partialOrder).mkString(","))
}