AlgaSketch.swift

/*
 struct G<A> {
  let vertices : [A]
  let edges: [(A, A)]
}

let gex = G(vertices: [1, 2, 3], edges: [(1, 2), (2, 3)])
let gbad = G(vertices: [1], edges: [(1, 2)])
*/

protocol Graph {
  associatedtype Vertex

  static var empty : Self { get }
  static func vertex(_ : Vertex) -> Self
  static func overlay(_ : Self, _ : Self) -> Self
  static func connect(_ : Self, _ : Self) -> Self
}

extension Graph {
  static func edge(_ l : Self.Vertex, _ r : Self.Vertex) -> Self {
    return Self.connect(Self.vertex(l), Self.vertex(r))
  }

  static func vertices(_ vs : [Self.Vertex]) -> Self {
    return vs.map(Self.vertex).reduce(Self.empty, Self.overlay)
  }

  static func clique(_ vs : [Self.Vertex]) -> Self {
    return vs.map(Self.vertex).reduce(Self.empty, Self.connect)
  }

  static func graph(_ vs : [Self.Vertex], _ es : [(Self.Vertex, Self.Vertex)]) -> Self {
    return Self.overlay(Self.vertices(vs), Self.edges(es))
  }

  static func edges(_ es : [(Self.Vertex, Self.Vertex)]) -> Self {
    return es.map(Self.edge).reduce(Self.empty, Self.overlay)
  }
}

extension Graph where Self : Equatable {
  func isSubgraph(of other: Self) -> Bool {
    return Self.overlay(self, other) == other
  }
}

struct PairOf<A : Hashable> : Hashable {
  let v : (A, A)

  static func == (lhs : PairOf<A>, rhs : PairOf<A>) -> Bool {
    return lhs.v == rhs.v && lhs.v == rhs.v
  }

  var hashValue : Int {
    return v.0.hashValue ^ v.1.hashValue
  }
}

struct Relation<A: Comparable & Hashable> : Graph, Equatable {
  let domain : Set<A>
  let relation : Set<PairOf<A>>

  typealias Vertex = A

  static var empty : Relation {
    return Relation(domain: [], relation: [])
  }
  static func vertex(_ x : Vertex) -> Relation {
    return Relation(domain: [x], relation: [])
  }
  static func overlay(_ lhs : Relation, _ rhs : Relation) -> Relation {
    return Relation(domain: lhs.domain.union(rhs.domain), relation: lhs.relation.union(rhs.relation))
  }
  static func connect(_ lhs : Relation, _ rhs : Relation) -> Relation {
    return Relation(
      domain: lhs.domain.union(rhs.domain),
      relation: lhs.relation.union(rhs.relation).union(lhs.domain.flatMap { ls in return rhs.domain.flatMap { rs in PairOf<A>(v: (ls, rs)) } }))
  }

  static func == (lhs : Relation<A>, rhs : Relation<A>) -> Bool {
    return lhs.domain == rhs.domain && lhs.relation == rhs.relation
  }
}

extension Relation where A: Numeric {
  static func + (lhs : Relation, rhs : Relation) -> Relation {
    return Relation.overlay(lhs, rhs)
  }

  static func * (lhs : Relation, rhs : Relation) -> Relation {
    return self.connect(lhs, rhs)
  }

  prefix static func -(operand: Relation) -> Relation { return operand }

  var signum: Relation { return Relation.empty }
  var magnitude: Relation { return self }
}

indirect enum ShallowGraph<A> {
  case Empty
  case Vertex(A)
  case Overlay(ShallowGraph<A>, ShallowGraph<A>)
  case Connect(ShallowGraph<A>, ShallowGraph<A>)
}

extension ShallowGraph where A : Comparable & Hashable {
  static func == (lhs : ShallowGraph<A>, rhs : ShallowGraph<A>) -> Bool {
    return fold(lhs) == (fold(rhs) as Relation<A>)
  }
}

func fold<G : Graph>(_ sg : ShallowGraph<G.Vertex>) -> G {
  switch sg {
  case .Empty: return G.empty
  case let .Vertex(x): return G.vertex(x)
  case let .Overlay(x, y): return G.overlay(fold(x), fold(y))
  case let .Connect(x, y): return G.connect(fold(x), fold(y))
  }
}

struct Symmetric<A : Comparable & Hashable> : Graph {
  let unSym : Relation<A>

  typealias Vertex = Relation<A>.Vertex

  static var empty : Symmetric<A> {
    return Symmetric(unSym: Relation<A>.empty)
  }
  static func vertex(_ x : Vertex) -> Symmetric<A> {
    return Symmetric(unSym: Relation<A>.vertex(x))
  }
  static func overlay(_ lhs : Symmetric<A>, _ rhs : Symmetric<A>) -> Symmetric<A> {
    return Symmetric(unSym: Relation<A>.overlay(lhs.unSym, rhs.unSym))
  }
  static func connect(_ lhs : Symmetric<A>, _ rhs : Symmetric<A>) -> Symmetric<A> {
    return Symmetric(unSym: Relation<A>.connect(lhs.unSym, rhs.unSym))
  }

//  static func == (lhs : Symmetric<A>, rhs : Symmetric<A>) -> Bool {
//    return lhs.symmetricClosure == rhs.symmetricClosure
//  }
}

//struct Transpose<G : Graph> : Graph {
//
//}

/*
struct GraphFunctor<A> : Graph {
  let map : Any
  let fingerprint : ObjectIdentifier

  init<G : Graph>(_ map : @escaping ((A) -> G.Vertex) -> G) {
    self.map = map
    self.fingerprint = ObjectIdentifier(A.self)
  }

  typealias Vertex = A

  static var empty : GraphFunctor<A> {
    return GraphFunctor<A>({ _ in .empty })
  }
  static func vertex(_ x : Vertex) -> GraphFunctor<A> {
    return GraphFunctor<A>({ f in return .vertex(f(x)) })
  }
  static func overlay(_ lhs : GraphFunctor<A>, _ rhs : GraphFunctor<A>) -> GraphFunctor<A> {
    return Symmetric(unSym: Relation<A>.overlay(lhs.unSym, rhs.unSym))
  }
  static func connect(_ lhs : GraphFunctor<A>, _ rhs : GraphFunctor<A>) -> GraphFunctor<A> {
    return Symmetric(unSym: Relation<A>.connect(lhs.unSym, rhs.unSym))
  }
}
*/