Function revelations in Typescript: Graphs
Posted By Tom Larkworthy, Jan 7, 2015
My struggles are over. I have the final graph representation. For years I have implemented Graph libraries in every language I have programmed in. Every time I am irritated by the design choices I am forced to make. I want a graph to represent the relationships in my prexisting programs. I want the graph data structure to reusable. Yet everytime I try and make it flexible it ends up annoying to fit it into an already developed program.
The standard design I normally go for is derived from the mathematical definition.
In the most common sense of the term, a graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or links, which are 2-element subsets of V wikipedia
So my class is a set of vertices and a set of edges. An edge is a pair, so this itself is another class. An edge might have a weight, and might be unordered depending on the flavour of graph we want. This is where things start to get annoying. JGraphT sets the library up as follows (JGraphT is an exemplar of the mutable set representation) :-
- Graph <V,E> {Set<V> vertices; HashSet<V, Set<E>> outedges}
- EdgeFactory <V,E>
Often I don't need custom stuff on the edges, so its annoying to have to specify an unused edge type all the time. Most annoying though is how to specify the vertices and edges... you have to add them to the graph one at a time. When I am trying to abstract a graph out of an existing application this now means replicating all the information already in the program. This is fragile, because the graph can easily get out of sync with the relationships in the program. Also what if the graph is infinite or in a database?
Anyway, years have gone by since my early Java days, and recently I have been leveling up my functional skills in Scala. Now the time has come to to implement a Graph in my new favourite language, Typescript, and at last I think I have nailed the Graph representation!
First up, our constructor, which only requires specifying the vertex type
/// <reference path="../lib/collections.ts" />
class Graph<V> {
constructor(public adjacency: (from: V, cb: (to: V) => any) => any) {}
...
}
Our constructor also takes an adjacency function, which can be called with a start vertex (from) and a callback that iterates the adjacent vertices. By modifying the adjacency param to be public I save having to assign the param to an instance variable (Good one Typescript!).
Whilst in Javascript I could easily create a graph like this too, I probably wouldn't because documenting how the constructor should be called would be too laborious and difficult to express. With Typescript the compiler is documenting exactly how to call the constructor in a way that prose could not.
Next we can start writing some fundamental graph algorithms like breadth first search (BFS). Our BFS will call a callback in the order edges are traversed, until the callback signals to stop the traversal by returning false. This makes the BFS routine very reusable as we can search for a more than one vertex or until some other criteria is triggered. It is also works with infinite graphs.
bfs(start: V, cb: (from: V, to: V) => boolean) {
var visited: Set<V> = new Set<V>();
var open: LinkedList<[V, V]> = new LinkedList<[V, V]>();
var keepGoing: boolean = true;
visited.add(start);
this.adjacent(start, function(to: V) {
open.add([start, to]);
});
while(!open.isEmpty() && keepGoing) {
var from_to: [V, V] = open.removeElementAtIndex(0);
var from = from_to[0];
var to = from_to[1];
if (!visited.contains(to)){
keepGoing = cb(from, to);
visited.add(to);
this.adjacent(to, function(adjacent: V) {
if (!visited.contains(adjacent)) {
open.add([to, adjacent]);
}
});
}
}
}
I have not implemented this beautifully, the main Typescript innovation I like though is that you can create an ordered pair type with [V V]. This is used in the BFS routine so that the start and end of an edge can be tracked. I don't need to create no bleedin’ edge factory!
The real power of the bfs routine is that it is a stepping stone to other algorithms like shortest path:
shortestPath(start: V, end: V): LinkedList<[V, V]> {
var backtrack: Dictionary<V, V> = new Dictionary<V, V>();
var last: V = undefined;
this.bfs(start, function(from: V, to: V): boolean {
backtrack.setValue(to, from);
last = to;
return to != end; //terminate BFS when we reach the end vertex
});
if (last == end) {
//we found a path between start and end
var path: LinkedList<[V, V]> = new LinkedList<[V, V]>();
var prev = backtrack.getValue(last);
while (last != start) {
path.add([prev, last], 0);
last = prev;
prev = backtrack.getValue(last);
}
return path;
} else return null; //end is not connected to start
}
With shortest path we maintain a backtracking index, so we can efficiently retrace the BFSs steps that brought it from the start vertex to the end vertex. Nothing particuarly clever here other than we have some decent collection libraries availible thanks to typescript-collections. Functional purist might slap me for using mutable state within methods and returning null instead of a Maybe, but null returns are fairly idiomatic in many languages.
So I am very happy at last. I feel this style of implementing a graph has many desirable properties over the mutable sets representation. It works on infinite graphs. It feels more mathematical, because given an adjacency function you imply a shortest path on a space. There is no keeping the graph in sync with some other part of the program. To add a graph you just need to define a lightweight adjacency function which despite its fearsome type arguments is actually quite easy in practice. This is my new go to graph representation for the next 10 years! Yay Typescript. Yay functional style.