digraph.ts

(async () => {
  // -- Generic collection helpers

  // get the (arbitrary) first element of an (unordered) set
  function carSet<T>(set: Set<T>): T | undefined {
    return set.entries().next().value[0]
  }

  // a Hash Set is a mapping from keys to sets
  function consHSet<K, V>(hset: Map<K, Set<V>>, k: K, v: V): void {
    let set = hset.get(k)
    if (!set) {
      set = new Set<V>()
      hset.set(k, set)
    }
    set.add(v)
  }

  // a double Hash set is a mapping from keys to hash sets
  function consHHSet<K1, K2, V>(
    hhset: Map<K1, Map<K2, Set<V>>>,
    k1: K1,
    k2: K2,
    v: V,
  ): void {
    let hset = hhset.get(k1)
    if (!hset) {
      hset = new Map<K2, Set<V>>()
      hhset.set(k1, hset)
    }
    consHSet(hset, k2, v)
  }

  // get or create a value in a dictionary
  function getOrCreateHValue<T>(
    map: Map<ID, T>,
    id: ID,
    factory: (id: ID) => T,
  ): T {
    let x = map.get(id)
    if (!x) {
      x = factory(id)
      map.set(id, x)
    }
    return x
  }

  // -- Basic directed graph

  // dog ate cookie
  //
  // e:ate
  //   sources:
  //     v:dog: [v:cookie]
  //   targets:
  //     v:cookie: [v:dog]
  //
  // v:dog
  //   out:
  //     e:ate:[v:cookie]
  //
  // v:cookie
  //   in:
  //     e:ate:[v:dog]

  // ---

  type ID = string
  type EdgeRef = ID
  type VertexRef = ID

  class Vertex {
    public id: ID
    public out: Map<EdgeRef, Set<VertexRef>>
    public in: Map<EdgeRef, Set<VertexRef>>

    constructor(id: ID) {
      this.id = id
      this.out = new Map<EdgeRef, Set<VertexRef>>()
      this.in = new Map<EdgeRef, Set<VertexRef>>()
    }
  }

  class Edge {
    public id: ID
    public sources: Map<VertexRef, Set<VertexRef>>
    public targets: Map<VertexRef, Set<VertexRef>>

    constructor(id: ID) {
      this.id = id
      this.sources = new Map<VertexRef, Set<VertexRef>>()
      this.targets = new Map<VertexRef, Set<VertexRef>>()
    }
  }

  class Digraph {
    public id: ID
    public vertices: Map<VertexRef, Vertex>
    public edges: Map<EdgeRef, Edge>

    // ---

    constructor(id: ID) {
      this.id = id
      this.vertices = new Map<VertexRef, Vertex>()
      this.edges = new Map<EdgeRef, Edge>()
    }

    // -- Mutations

    public getOrCreateEdge = (id: ID): Edge =>
      getOrCreateHValue(this.edges, id, (iid: ID) => new Edge(iid))

    public getOrCreateVertex = (id: ID): Vertex =>
      getOrCreateHValue(this.vertices, id, (iid: ID) => new Vertex(iid))

    // ate(dog, cookie)
    public addEdge = (e: EdgeRef, source: VertexRef, target: VertexRef): void => {
      const edge = this.getOrCreateEdge(e)

      // forward: (ate, dog, cookie)
      consHSet(edge.sources, source, target)

      // inverse: (ate, cookie, dog)
      consHSet(edge.targets, target, source)

      // vertex out: (dog, ate, cookie)
      const vertexX = this.getOrCreateVertex(source)
      consHSet(vertexX.out, e, target)

      // vertex in: (cookie, ate, dog)
      const vertexY = this.getOrCreateVertex(target)
      consHSet(vertexY.in, e, source)
    }

    // -- Queries

    // (?x, e, _)
    public edgeSources = (
      e: EdgeRef,
    ): IterableIterator<VertexRef> | undefined => {
      const edge = this.edges.get(e)
      return edge ? edge.sources.keys() : undefined
    }

    // (_, e, ?y)
    public edgeTargets = (
      e: EdgeRef,
    ): IterableIterator<VertexRef> | undefined => {
      const edge = this.edges.get(e)
      return edge ? edge.targets.keys() : undefined
    }

    // (x, ?e, _)
    public outEdges = (x: VertexRef): IterableIterator<EdgeRef> | undefined => {
      const vertex = this.vertices.get(x)
      return vertex ? vertex.out.keys() : undefined
    }

    // (_, ?e, y)
    public inEdges = (y: VertexRef): IterableIterator<EdgeRef> | undefined => {
      const vertex = this.vertices.get(y)
      return vertex ? vertex.in.keys() : undefined
    }

    // (x, e, ?y)
    public targets = (x: VertexRef, e: EdgeRef): Set<VertexRef> | undefined => {
      const vertex = this.vertices.get(x)
      return vertex ? vertex.out.get(e) : undefined
    }

    // (?x, e, y)
    public sources = (y: VertexRef, e: EdgeRef): Set<VertexRef> | undefined => {
      const vertex = this.vertices.get(y)
      return vertex ? vertex.in.get(e) : undefined
    }
  }
})()