Graph.scala

/** A fancy, functional graph encoding taken from here:
  * https://github.com/snowleopard/alga-paper
  */
sealed trait Graph[+A] { self =>
  import Graph._

  def toStandardGraph[A1 >: A]: StandardGraph[A1] =
    fold[StandardGraph[A1]](
      empty = StandardGraph(Set.empty, Set.empty),
      vertex = value => StandardGraph(Set(value), Set.empty),
      overlay = (v1, v2) =>
        StandardGraph(
          v1.vertices ++ v2.vertices,
          v1.edges ++ v2.edges
        ),
      connect = (v1, v2) =>
        StandardGraph(
          v1.vertices ++ v2.vertices,
          v1.edges ++ v2.edges ++ cartesianProduct(v1.vertices, v2.vertices)
        )
    )

  private def cartesianProduct[X](s1: Set[X], s2: Set[X]): Set[(X, X)] =
    for {
      x <- s1
      y <- s2
    } yield (x, y)

  def fold[B](empty: B, vertex: A => B, overlay: (B, B) => B, connect: (B, B) => B): B =
    self match {
      case Graph.Empty          => empty
      case Vertex(value)        => vertex(value)
      case Overlay(left, right) =>
        overlay(
          left.fold(empty, vertex, overlay, connect),
          right.fold(empty, vertex, overlay, connect)
        )
      case Connect(left, right) =>
        connect(
          left.fold(empty, vertex, overlay, connect),
          right.fold(empty, vertex, overlay, connect)
        )
    }

  def >>>[A1 >: A](that: Graph[A1]): Graph[A1] = combineNonEmpty(that)(Connect(_, _))

  def ++[A1 >: A](that: Graph[A1]): Graph[A1] = combineNonEmpty(that)(Overlay(_, _))

  def map[B](f: A => B): Graph[B] = flatMap(a => Vertex(f(a)))

  def filter(p: A => Boolean): Graph[A] =
    flatMap { a => if (p(a)) Graph(a) else Graph.empty }

  def flatMap[B](f: A => Graph[B]): Graph[B] =
    self match {
      case Empty                => Graph.Empty
      case Vertex(value)        => f(value)
      case Overlay(left, right) => Overlay(left.flatMap(f), right.flatMap(f))
      case Connect(left, right) => Connect(left.flatMap(f), right.flatMap(f))
    }

  /** Remove all redundant Empty nodes in the Graph.
    */
  def normalizeEmpty: Graph[A] = self match {
    case Graph.Empty           => Graph.Empty
    case Vertex(value)         => Vertex(value)
    case Overlay(left, Empty)  => left.normalizeEmpty
    case Overlay(Empty, right) => right.normalizeEmpty
    case Connect(left, Empty)  => left.normalizeEmpty
    case Connect(Empty, right) => right.normalizeEmpty
    case Overlay(left, right)  => Overlay(left.normalizeEmpty, right.normalizeEmpty)
    case Connect(left, right)  => Overlay(left.normalizeEmpty, right.normalizeEmpty)
  }

  private def combineNonEmpty[A1 >: A](that: Graph[A1])(f: (Graph[A1], Graph[A1]) => Graph[A1]): Graph[A1] = {
    (self, that) match {
      case (Empty, that) => that
      case (self, Empty) => self
      case (self, that)  => f(self, that)
    }
  }
}

object Graph {
  def apply[A](v: A): Graph[A]         = Vertex(v)
  def apply[A](v: A, vs: A*): Graph[A] = Graph.vertices(v +: vs: _*)
  def empty: Graph[Nothing]            = Empty

  def vertices[A](list: A*): Graph[A] = list.foldRight[Graph[A]](empty)(Graph(_) ++ _)

  case object Empty                                             extends Graph[Nothing]
  final case class Vertex[+A](value: A)                         extends Graph[A]
  final case class Overlay[+A](left: Graph[A], right: Graph[A]) extends Graph[A]
  final case class Connect[+A](left: Graph[A], right: Graph[A]) extends Graph[A]

}

/** Your standard issue graph: Sets of vertices and edges.
  */
final case class StandardGraph[A](vertices: Set[A], edges: Set[(A, A)])

object Examples extends App {
  val int: Graph[Int] = Graph(1) >>> Graph(2, 3)
  println(int.toStandardGraph)
}