Skip to content

Instantly share code, notes, and snippets.

@dhkatz
Last active June 25, 2019 02:36
Show Gist options
  • Save dhkatz/14ce2b5ae654e6c79a49d837770a096b to your computer and use it in GitHub Desktop.
Save dhkatz/14ce2b5ae654e6c79a49d837770a096b to your computer and use it in GitHub Desktop.
Directed Graph Execution Order
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;
}
}
}
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment