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

  def findSetOf(v: String, setSet: Set[Set[String]]): Set[String] =
    setSet.find( set => set.contains(v)).getOrElse(throw new Exception("must be partition"))

  def unite(regions: Set[Set[String]], region1: Set[String], region2: Set[String]): Set[Set[String]] = {
    val unitedRegion = region1 ++ region2
    val reducedRegions = (regions - region1) - region2
    reducedRegions + unitedRegion
  }

  def connectedComp(V: List[String], E: List[(String, String)]): Set[Set[String]] = {
    var regions: Set[Set[String]] = V.map( v => Set(v)) . toSet

    for ((x, y) <- E) {
      val regionOfx = findSetOf(x, regions)
      val regionOfy = findSetOf(y, regions)
      if ( regionOfx != regionOfy ) {
        regions = unite(regions, regionOfx, regionOfy)
      }
    }
    regions
  }

  val V = List("a", "b", "c", "d", "e", "f", "g", "h", "i", "j")
  val E = List(
    ("a", "b"), ("a", "f"),
    ("b", "h"), ("h", "f"),
    ("c", "d"), ("d", "e"),
    ("g", "i"), ("i", "j"), ("g", "j")
  )

  connectedComp(V, E).foreach( comp =>
    println( s"{${comp.mkString(",")}}" )
  )

}