#### Experiments

##### Function revelations in Typescript: GraphsPosted 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 keepGoing: boolean = true;

});

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);
}
});
}
}
}

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