DAG

Graph.scala

// Implementation of DAGs based on:
// Jeremy Gibbons, An Initial-Algebra Approach to Directed Acyclic Graphs, 1995
// https://www.researchgate.net/publication/2423982_An_Initial-Algebra_Approach_to_Directed_Acyclic_Graphs
//
// Good:
// ✅ Immutable, compositional representation that supports structural sharing
// ✅ Correct by construction: no way to create cyclic graphs, so no need to check
// ✅ Some graph operations are easy: topological sort, certain replacement graph transformations
// ✅ Cool underlying theory: graphs are arrows in a symmetric monoidal category
// ⚠️ Extensions to the default idea of a DAG: supports multiple edges between the same vertices, ordered ports, and
// (optional) global graph ports
// ❌ Not trivial to construct from other representations, e.g. adjacency lists
// ❌ No idea how you'd do even basic traversal like "get me all vertices adjacent to this vertex"

sealed trait Graph[+T] {
  val inDegree: Int
  val outDegree: Int

  def x(n: Int): Graph[T] = if (n == 0) Empty else Seq.fill(n)(this).reduce(Beside(_, _))

  def ⨾[U >: T](that: Graph[U]): Graph[U] = Before(this, that)

  def ║[U >: T](that: Graph[U]): Graph[U] = Beside(this, that)

  def order: Int

  def reverse: Graph[T]

  def topologicalSort: Seq[T]

  def map[U](f: T => U): Graph[U]
}

object Vertex {

  def source[T](label: T, outDegree: Int): Graph[T] = Vertex(label, inDegree = 0, outDegree = outDegree)

  def sink[T](label: T, inDegree: Int): Graph[T] = Vertex(label, inDegree = inDegree, outDegree = 0)
}

case class Vertex[+T](label: T, inDegree: Int, outDegree: Int) extends Graph[T] {
  override def order: Int = 1

  override def reverse: Graph[T] = copy(outDegree = inDegree, inDegree = outDegree)

  override def topologicalSort: Seq[T] = Seq(this.label)

  override def map[U](f: T => U): Graph[U] = copy(f(label))
}

case object Edge extends Graph[Nothing] {
  override val inDegree: Int = 1
  override val outDegree: Int = 1

  override def order: Int = 0

  override def reverse: Graph[Nothing] = this

  override def topologicalSort: Seq[Nothing] = Seq.empty

  override def map[U](f: Nothing => U): Graph[U] = this
}

case class Beside[+T](first: Graph[T], second: Graph[T]) extends Graph[T] {
  override val inDegree: Int = first.inDegree + second.inDegree
  override val outDegree: Int = first.outDegree + second.outDegree

  override def order: Int = first.order + second.order

  override def reverse: Graph[T] = first.reverse ║ second.reverse

  override def topologicalSort: Seq[T] = first.topologicalSort ++ second.topologicalSort

  override def map[U](f: T => U): Beside[U] = Beside(first map f, second map f)
}

case class Before[+T](first: Graph[T], second: Graph[T]) extends Graph[T] {
  assert(first.outDegree == second.inDegree, s"Incompatible graphs $first and $second")
  override val inDegree: Int = first.inDegree
  override val outDegree: Int = second.outDegree

  override def order: Int = first.order + second.order

  override def reverse: Graph[T] = Before(second.reverse, first.reverse)

  override def topologicalSort: Seq[T] = first.topologicalSort ++ second.topologicalSort

  override def map[U](f: T => U): Before[U] = Before(first map f, second map f)
}

case object Empty extends Graph[Nothing] {
  override val inDegree: Int = 0
  override val outDegree: Int = 0

  override def order: Int = 0

  override def reverse: Graph[Nothing] = this

  override def topologicalSort: Seq[Nothing] = Seq.empty

  override def map[U](f: Nothing => U): Graph[U] = this
}

object Rotate {

  val swap: Rotate = Rotate(1, 2)

}

import Rotate._

case class Rotate(numberToShift: Int, total: Int) extends Graph[Nothing] {
  override val inDegree: Int = total
  override val outDegree: Int = total

  override def order: Int = 0

  override def reverse: Graph[Nothing] = Rotate(total - numberToShift, total)

  override def topologicalSort: Seq[Nothing] = Seq.empty

  override def map[U](f: Nothing => U): Graph[U] = this
}

object Main extends App {


  //   ╱------------------------╲
  // A                           ╲
  //   ╲-------╲ ╱--------------> D
  //            ╳                ╱
  //   ╱-------╱ ╲-----╲ ╱------╱
  // B                  ╳
  //   ╲-------╲ ╱-----╱ ╲------╲
  //            ╳                ╲
  //   ╱-------╱ ╲--------------> E
  // C                           ╱
  //   ╲------------------------╱
  val abc: Graph[String] =
  Vertex.source("A", 2) ║
    Vertex.source("B", 2) ║
    Vertex.source("C", 2)

  val wiring: Graph[String] =
    Edge ║
      ((swap x 2) ⨾ (Edge ║ swap ║ Edge)) ║
      Edge

  val de: Graph[String] =
    Vertex.sink("D", 3) ║
      Vertex.sink("E", 3)

  val graph: Graph[String] = abc ⨾ wiring ⨾ de

  println(graph.order)
  println(graph.topologicalSort)
  println(graph.reverse.topologicalSort)

  println(graph.map(_.toLowerCase).topologicalSort)
}