Directed Graph Execution Order

digraph.ts

type VertexResolvable = string | Vertex;

class Vertex {
    public edges = { from: new Set<Edge>(), to: new Set<Edge>() };
    public name: string | undefined = undefined;
}

class Edge {
    public constructor(public from: Vertex, public to: Vertex) {

    }
}

class Digraph {
    public verticies = new Set<Vertex>();
    public edges = new Set<Edge>();

    private cache: Record<string, Vertex> = {};

    public vertex(v: VertexResolvable): Vertex {
        if (typeof v === 'string') {
            const cached = this.cache[v];

            if (!cached) {
                const created = new Vertex();
                created.name = v;
    
                this.cache[v] = created;
                this.verticies.add(created);
            }

            return this.cache[v];
        } else {
            if (v.name !== undefined) {
                const cached = this.cache[v.name];
    
                if (!cached) {
                    this.cache[v.name] = v;
                    this.verticies.add(v);
                }
            } else {
                if (!this.verticies.has(v)) {
                    this.verticies.add(v);
                }
            }

            return v;
        }
    }

    public edge(v: VertexResolvable, u: VertexResolvable): Edge {
        const { from } = this.vertex(v).edges;
        const { to } = this.vertex(u).edges;

        for (const e of to) {
            if (e.from === this.vertex(v)) {
                return e;
            }
        }

        const edge = new Edge(this.vertex(v), this.vertex(u));

        to.add(edge);
        from.add(edge);

        this.edges.add(edge);

        return edge;
    }

    public remove(v: VertexResolvable): void;
    public remove(e: Edge): void;
    public remove(v: VertexResolvable | Edge): void {
        if (v instanceof Edge) {
            this.edges.delete(v);
            v.to.edges.to.delete(v);
            v.from.edges.from.delete(v);
        } else {
            const u = this.vertex(v);

            this.verticies.delete(u);
            u.edges.to.forEach((e) => this.remove(e));
            u.edges.from.forEach((e) => this.remove(e));
        }
    }

    public adjacent(v: VertexResolvable, u: VertexResolvable): boolean {
        for (const edge of this.vertex(v).edges.to) {
            if (edge.from === u) return true;
        }

        for(const edge of this.vertex(v).edges.from) {
            if (edge.to === u) return true; 
        }

        return false;
    }

    /** Get a topological ordering of the graph.
     * Useful for creating execution orders.
     */
    public sort(): Vertex[] {
        const V =  Array.from(this.verticies);
        const S = V.filter((v) => v.edges.to.size === 0);

        const D = new Map(V.map<[Vertex, number]>((v) => [v, v.edges.to.size]));

        const L: Vertex[] = [];

        while (S.length > 0) {
          const v = S.pop()!;
          L.push(v);
          for (const e of v.edges.from) {
            const u = e.to;
            const d = D.get(u)! - 1;

            D.set(u, d);

            if (d === 0) {
                S.unshift(u);
            }
          }
        }
  
        if (L.length !== this.verticies.size) {
          throw 'Could not create topological sort due to circular dependecies!';
        } else {
          return L;
        }
      }
}

example.ts

interface Package {
    name: string;
    dependecies: string[];
  }
  
  const a: Package = { name: 'a', dependecies: [] };
  const b: Package = { name: 'b', dependecies: ['a'] };
  const c: Package = { name: 'c', dependecies: ['a', 'b'] };
  
  const packages = [b, c, a];
  
  const G = new Digraph();
  
  for (const pkg of packages) {
      for (const dependency of pkg.dependecies) {
          G.edge(G.vertex(dependency), G.vertex(pkg.name));
      }
  }
  
  // See an image of this graph here https://i.imgur.com/F0FTZd4.png
  
for (const pkg of G.sort()) {
    console.log(pkg.name);
}