A little kooky DAG class

case class cycleException(es: String) extends Exception(es)

case class Edge(a: Int, b: Int) {
  def t = Edge(b, a)
}

object KookyDAG {
  def empty = KookyDAG(Vector(), Vector())
}

/** A DAG with a list of all the paths, that allows you to find out the successors and ancestors from each node, and to
  * easily check for cycles -- and for paths.
  *
  * @param edges a `Vector` with tuples representing each edge, origin -> destiny.
  * @param paths a list of all paths, calculated via `append` or `remove`.
  */
case class KookyDAG(edges: Vector[Edge], paths: Vector[Edge]) {

  def append(ed: Edge) = {
    if (paths contains ed.t) throw cycleException("This edge would close a cycle in the DAG")
    if (edges contains ed) this
    else KookyDAG(edges :+ ed, paths ++ find_paths(ed))
  }

  def remove(ed: Edge) =
    if (edges contains ed) KookyDAG(edges diff Vector(ed), paths diff find_paths(ed))
    else this

  /** @param ab input edge.
    * @return list of paths that (might) contain the given edge.
    */
  def find_paths(ab: Edge) = for (o <- origins(ab.a); d <- destinies(ab.b)) yield Edge(o, d)

  /** @param from input node
    * @return list of nodes with paths to the given edge
    */
  def origins(from: Int): Vector[Int] = from +: (paths filter (_.b == from) map (_.a))

  /** @param from input node
    * @return list of nodes with paths starting from the given node
    */
  def destinies(from: Int): Vector[Int] = from +: (paths filter (_.a == from) map (_.b))
}

case class SpartanKookyDAG(edges: Vector[Edge], paths: Vector[Edge]) {

  def append(ed: Edge) = {
    if (paths contains ed.t) throw cycleException("This edge would close a cycle in the DAG")
    else if (edges contains ed) this
    else KookyDAG(edges union Vector(ed), paths union find_paths(ed))
  }

  def remove(ed: Edge) =
    if (!(edges contains ed)) this
    else KookyDAG(edges diff Vector(ed), paths diff find_paths(ed))

  def find_paths(ab: Edge) =
    for {
      o <- ab.a +: (paths filter (_.b == ab.a) map (_.a))
      d <- ab.b +: (paths filter (_.a == ab.b) map (_.b))
    } yield Edge(o, d)
}

object MyMain extends App {

  var kd = KookyDAG.empty

  for (ed <- Seq(Edge(1, 2), Edge(2, 3), Edge(4, 5), Edge(1, 5), Edge(3, 4), Edge(2, 4))) {
    kd = kd.append(ed)
    println(kd)
  }

  for (ed <- Seq(Edge(2, 3), Edge(4, 5), Edge(1, 5), Edge(3, 4), Edge(1, 2), Edge(2, 4))) {
    kd = kd.remove(ed)
    println(kd)
  }

  kd = KookyDAG.empty.append(Edge(1, 2)).append(Edge(2, 3)).append(Edge(1, 3))
  println(kd)
  try {
    kd = KookyDAG.empty.append(Edge(1, 2)).append(Edge(2, 3)).append(Edge(3, 1))
    println(kd)
  }
  catch {
    case cycleException(es) => println(es)
  }
}



/*
/usr/lib/jvm/java-7-openjdk-amd64/bin/java (...) com.intellij.rt.execution.application.AppMain MyMain
KookyDAG(Vector(Edge(1,2)),Vector(Edge(1,2)))
KookyDAG(Vector(Edge(1,2), Edge(2,3)),Vector(Edge(1,2), Edge(2,3), Edge(1,3)))
KookyDAG(Vector(Edge(1,2), Edge(2,3), Edge(4,5)),Vector(Edge(1,2), Edge(2,3), Edge(1,3), Edge(4,5)))
KookyDAG(Vector(Edge(1,2), Edge(2,3), Edge(4,5), Edge(1,5)),Vector(Edge(1,2), Edge(2,3), Edge(1,3), Edge(4,5), Edge(1,5)))
KookyDAG(Vector(Edge(1,2), Edge(2,3), Edge(4,5), Edge(1,5), Edge(3,4)),Vector(Edge(1,2), Edge(2,3), Edge(1,3), Edge(4,5), Edge(1,5), Edge(3,4), Edge(3,5), Edge(2,4), Edge(2,5), Edge(1,4), Edge(1,5)))
KookyDAG(Vector(Edge(1,2), Edge(2,3), Edge(4,5), Edge(1,5), Edge(3,4), Edge(2,4)),Vector(Edge(1,2), Edge(2,3), Edge(1,3), Edge(4,5), Edge(1,5), Edge(3,4), Edge(3,5), Edge(2,4), Edge(2,5), Edge(1,4), Edge(1,5), Edge(2,4), Edge(2,5), Edge(1,4), Edge(1,5)))
KookyDAG(Vector(Edge(1,2), Edge(4,5), Edge(1,5), Edge(3,4), Edge(2,4)),Vector(Edge(1,2), Edge(4,5), Edge(3,4), Edge(3,5), Edge(1,5), Edge(2,4), Edge(2,5), Edge(1,4), Edge(1,5)))
KookyDAG(Vector(Edge(1,2), Edge(1,5), Edge(3,4), Edge(2,4)),Vector(Edge(1,2), Edge(3,4), Edge(2,4), Edge(1,4), Edge(1,5)))
KookyDAG(Vector(Edge(1,2), Edge(3,4), Edge(2,4)),Vector(Edge(1,2), Edge(3,4), Edge(2,4), Edge(1,4)))
KookyDAG(Vector(Edge(1,2), Edge(2,4)),Vector(Edge(1,2), Edge(2,4), Edge(1,4)))
KookyDAG(Vector(Edge(2,4)),Vector(Edge(2,4)))
KookyDAG(Vector(),Vector())
KookyDAG(Vector(Edge(1,2), Edge(2,3), Edge(1,3)),Vector(Edge(1,2), Edge(2,3), Edge(1,3), Edge(1,3)))
This edge would close a cycle in the DAG

Process finished with exit code 0
*/