Implementing Graphs in Typescript
22 October, 2020
What?
Recently, I've been working on we-cook-sometimes and came across a part of it that presented an interesting opportunity. One of the main components of the application is a section that asks a question, then displays a new question when the user chooses one of the answers presented by the first question. This continues until the user either navigates away from the questions, or answers all of the questions available. Additionally, what question is asked next is directly decided by what questions came before it.
At first glance, this appeared as if it should be modeled as a tree. However, in some cases, two questions could both lead to the same next question—making the question series better suited to being modeled as a directed acyclic graph. As always, there's an NPM package for that (actually, there's at least two), but why use an existing design when we can reinvent the wheel instead?
Why?
In any serious project, I would of course use one of the existing solutions. But in this case, I chose to implement a graph solution myself because I've recently been studying more on graphs & other data structures & recognized this as a great opportunity to take a more in-depth look at graphs & related algorithms.
How?
To get started, I first needed to model a graph's nodes & edges—luckily, that's easily done with what's called an adjacency list. Essentially, this is a just a list of all the nodes in a graph, each paired with a list of nodes that are adjacent to that node. In Typescript, this is modeled as an object with a key for each node & the value as an array of adjacent nodes:
interface AdjacencyList {
[node: string]: Array<string>
}
For a graph of three nodes; A
, B
, & C
; & three edges; AB
, AC
, & BC
; an adjacency graph looks like this:
const graph: AdjacencyList = {
A: [B, C],
B: [C],
C: [],
}
While this alone is all that is needed to model the graph, it's not of any use if there isn't any way of of interacting with it. Specifically, I knew I needed to be able to do the following with my graph:
- Add nodes
- Add edges
- Traverse the graph
- Detect cycles & enforce acyclicality when adding edges
Additionally, I wanted to be able to interact with this graph structure as a self-contained object with methods attached to the data structure. In some languages, I may choose classes to implement this, but in Javascript (& thus Typescript) I prefer to use functional inheritance.
Adding nodes
Adding nodes is incredibly simple to start. First though, a way of creating the graph is needed:
// Graph.spec.ts
import graph from './Graph'
describe('Graph', () => {
it(
'initializes with an empty adjacency list',
() =>
{
expect(graph.create().adjacencyList)
.to.be.empty
})
})
Starting out, creating the graph is really simple—it's just
a function that returns an object with an AdjacencyList
as
one of it's properties:
// Graph.ts
interface AdjacencyList {
[node: string]: Array<string>
}
interface Graph {
readonly adjacencyList: AdjacencyList
}
const create = (): Graph => ({
adjacencyList: {}
})
export {
create,
}
With that in place, it's easier to use (& thus test) an
implementation of an addNode()
method:
// Graph.spec.ts
// ...
describe('addNode()', () => {
let oldGraph = graph.create()
let newGraph: Graph
it('returns a graph with the new node added', () => {
newGraph = oldGraph.addNode('A')
expect(newGraph.adjacencyList['A']).to.exist
})
})
// Graph.ts
interface State { readonly adjacencyList: AdjacencyList}
interface Graph {
readonly adjacencyList: AdjacencyList
addNode: (node: string): Graph}
const GraphBuilder = (state: State): Graph => ({ adjacencyList: state.adjacencyList, addNode: (node) => { const newList = { ...state.adjacencyList } newList[node] = [] return GraphBuilder({ adjacencyList: newList, }) },})
const create = (): Graph =>
GraphBuilder({ adjacencyList: {} })
export {
create,
}
As you can see, things got a little more complicated here, so I'll walk through the two the major changes in a little more detail.
First, create
no longer simply returns an object.
Instead, it now returns a call to a builder function that
instead creates the object. This function, named
GraphBuilder
, helps me do two things:
- Create this Graph object in a way that allows for easy
refactoring to use functional inheritance via
Object.assign
- Bundle state & methods together into one object, while allowing the methods to return a new instance of the object with it's changes applied (a favorite design pattern of mine that I picked up from Gary Bernhardt's talk on boundaries, where he calls it FauxO—in comparison to OOP).
Second, there's a new interface called State that overlaps
with Graph. This interface defines the internal state of
the Graph (right now just the adjacency list) used by
GraphBuilder
and each of the methods of creates for Graph.
Adding edges
Additional methods follow the same pattern now, making
some things a little simpler going forward. A naive
implementation of addEdge
may look like this:
// Graph.spec.ts
// ...
describe('addEdge()', () => {
let oldGraph = graph
.create()
.addNode('A')
.addNode('B')
let newGraph: Graph
it(
'returns a graph with the new node added',
() =>
{
newGraph = oldGraph.addEdge('A', 'B')
expect(newGraph.adjacencyList['A'])
.to.deep.equal(['B'])
})
})
// Graph.ts
// ...
interface Graph {
readonly adjacencyList: AdjacencyList
addNode: (node: string): Graph
addEdge: (from: string, to: string): Graph}
const GraphBuilder = (state: State): Graph => ({
adjacencyList: state.adjacencyList,
addNode: (node) => {
const newList = { ...state.adjacencyList }
newList[node] = []
return GraphBuilder({
adjacencyList: newList,
})
},
addEdge: (from: string, to: string) => { const newEdges = state.adjacencyList[from] newEdges.push(to) state.adjacencyList[from] = newEdges return GraphBuilder({ adjacencyList: state.adjacencyList }) },
})
// ...
While the one test above would pass, but it hides a whole host of problems just waiting to break things in unexpected ways later. First, is the sneaky Siren-song of side-effects. This Graph implementation is built using a pattern designed to avoid side-effects, so one would hope that adding an edge & assigning the resulting new graph to a new variable would leave the original graph untouched. However, the following new test show that this clearly isn't the case:
// Graph.spec.ts
// ...
describe('addEdge()', () => {
let oldGraph = graph
.create()
.addNode('A')
.addNode('B')
let newGraph: Graph
it(
'returns a graph with the new node added',
() =>
{
newGraph = oldGraph.addEdge('A', 'B')
expect(newGraph.adjacencyList['A'])
.to.deep.equal(['B'])
})
it( 'but leaves the original graph untouched', () => { expect(oldGraph.adjacencyList['A']) .to.deep.equal([]) // but this test would fail, because // oldGraph.adjacencyList['A'] actually // deep equals ['B'] })})
This happens because Javascript (& thus Typescript) passes
objects, like our State object, by reference. When addEdge()
modified the adjacency list in place on state using
state.adjacencyList[from] = newEdges
, it modified the original
object referenced by oldGraph
and referenced this same object
when creating newGraph
.
Luckily, the fix is simple using the spread operator, ...
, (as
long as the consumer doesn't mind not supporting IE):
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
adjacencyList: state.adjacencyList,
// ...
addEdge: (from: string, to: string) => {
// spread the list of neighbors to shallow clone // it to avoid side affecting the given state const newEdges = [ ...state.adjacencyList[from] ] newEdges.push(to)
// spread the adjacency list to shallow clone it adjList = { ...state.adjacencyList } // then replace the old list of neighbors with // the new one adjList[from] = newEdges // this avoids unnecessarily cloning all neighbors // lists when they aren't changing
return GraphBuilder({
adjacencyList: adjList })
},
})
// ...
With this updated implementation of addEdge()
, the tests will
now pass once again, but there's still a couple smaller problems.
Given a Graph with nodes A & B with no edges, adding edge CB will
throw the following error, TypeError: Cannot read property 'push'
of undefined
. Worse yet, adding edge BC won't throw an error,
but will add C as an edge to node B, despite node C not yet
existing. While throwing an error here is good (as long as the
consumer knows to handle it), the error thrown by the first
problem is obtuse and could be made more clear (or exist at all
in the second problem). Throwing a specific error with a custom
message does a long way to help the end user know where they went
wrong. Adding this improvement requires two simple guards in the
method implementation.
// Graph.spec.ts
// ...
describe('addEdge()', () => {
let oldGraph = graph
.create()
.addNode('A')
.addNode('B')
let newGraph: Graph
it(
'returns a graph with the new node added',
() =>
{
newGraph = oldGraph.addEdge('A', 'B')
expect(newGraph.adjacencyList['A'])
.to.deep.equal(['B'])
})
it( "it won't add an edge to a node that doesn't exist yet", () => { expect() => newGraph.addEdge('C', 'A')) .to.throw( TypeError, /node.*c.*does not exist/i ) }) it( "it won't add an edge for an edge doesn't exist as a node", () => { expect() => newGraph.addEdge('A', 'C')) .to.throw( TypeError, /node.*c.*does not exist/i ) })})
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
adjacencyList: state.adjacencyList,
// ...
addEdge: (from: string, to: string) => {
// spread the adjacency list to shallow clone it adjList = { ...state.adjacencyList } // check if node already exists if (!adjList[node]) throw TypeError( `A Node, \`${node}\`, does not exist yet; a Node must exist before an Edge can be added to it.` ) // check if edge already exists if (!adjList[edge]) throw TypeError( `A Node, \`${edge}\`, does not exist yet; an Edge must exist as a Node before it can be an Edge.` )
// spread the list of neighbors to shallow clone
// it to avoid side affecting the given state
const newEdges = [ ...state.adjacencyList[from] ]
newEdges.push(to)
// replace the old list of neighbors with the
// new one
adjList[from] = newEdges
// this avoids unnecessarily cloning all neighbors
// lists when they aren't changing
return GraphBuilder({
adjacencyList: adjList
})
},
})
// ...
Finally, there's one last problem to solve—this implementation
adds an edge even if it already exists. Given a Graph with nodes
A
& B
& edge AB
, aGraph.addEdge('B')
will still add edge AB
again, resulting in an adjacency list of { A: [ 'B', 'B' ] }
.
// Graph.spec.ts
// ...
describe('addEdge()', () => {
let oldGraph = graph
.create()
.addNode('A')
.addNode('B')
let newGraph: Graph
it(
'returns a graph with the new node added',
() =>
{
newGraph = oldGraph.addEdge('A', 'B')
expect(newGraph.adjacencyList['A'])
.to.deep.equal(['B'])
})
// ...
it( "but it won't add an edge again if it already exists", () => { const newNewGraph = newGraph.addEdge('A', 'B') expect(newNewGraph.adjacencyList['A']) .to.not.deep.equal(['B', 'B']) })})
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
adjacencyList: state.adjacencyList,
// ...
addEdge: (from: string, to: string) => {
// spread the adjacency list to shallow
// clone it
adjList = { ...state.adjacencyList }
// check if node already exists
if (!adjList[node])
throw TypeError(
`A Node, \`${node}\`, does not exist yet; a Node must exist before an Edge can be added to it.`
)
// check if edge already exists
if (!adjList[edge])
throw TypeError(
`A Node, \`${edge}\`, does not exist yet; an Edge must exist as a Node before it can be an Edge.`
)
// spread the list of neighbors to shallow clone
// it to avoid side affecting the given state
const newEdges = [ ...state.adjacencyList[from] ]
// check if the edge already exists before // adding it newEdges.includes(edge) ? null : newEdges.push(edge)
// replace the old list of neighbors with the
// new one
adjList[from] = newEdges
// this avoids unnecessarily cloning all neighbors
// lists when they aren't changing
return GraphBuilder({
adjacencyList: adjList
})
},
})
// ...
Traverse the graph
The third core requirement of my graph implementation is to be able to traverse it. This (like everything I've done here) is very much a solved problem, but also one of the primary motivations for me to practice graphs by building this graph implementation. For my purposes, there wasn't much of a difference between a breadth-first search (BFS) or a depth-first one (DFS), but I knew I didn't have need for two traversal algorithms. In the end I chose depth-first, but it could have gone either way.
From reading Hands-On Data Structures and Algorithms with
Python by Dr. Basant Agarwal & Benjamin Baka and
Grokking Algorithms by Aditya Bhargava, I had a pretty
good set of references on how to do a simple traversal
using a DFS algorithm, so I thought I might make things
interesting by creating a Graph.traverser()
method for
my Graph that behaves similarly to Javascript's
iterable protocol
(although it won't be a full implementation of it that
satisfies the entire protocol). To start, the first tests
& interface for traverser()
to match that of@@iterator
look like this:
// Graph.spec.ts
// ...
describe('traverser()', () => {
const aGraph = graph.create()
it('returns an Traverser made from the graph', () => {
expect(aGraph.traverser()).to.exist
})
})
// Graph.ts
// ...
interface Graph {
readonly adjacencyList: AdjacencyList
addNode: (node: string): Graph
addEdge: (from: string, to: string): Graph
traverser: () => { next: () => string | null }}
// ...
For now, the tests fail because in order for the DFS
algorithm to work, we need to know one more thing about
the graph as well. A traversal has to start somewhere,
which means we need to designate a root node. In order to
simplify graph creation create()
is modified to take a
starting adjacency list & a root node as arguments. In the
event a graph is created as empty to start, then it'll
assume the first node added is the root.
// Graph.ts
interface State {
readonly adjacencyList: AdjacencyList
readonly root: string}
// ...
const GraphBuilder = (state: State): Graph => ({
adjacencyList: state.adjacencyList,
addNode: (node) => {
// if this is the first node, make it the root if (Object.keys(state.adjacencyList).length === 0) state.root = node
const newList = { ...state.adjacencyList }
newList[node] = []
return GraphBuilder({
adjacencyList: newList,
})
},
})
const create = ( adjacencyList: AdjacencyList = {}, root: string | null = null): Graph => GraphBuilder({ adjacencyList, root, })
The rest can be computed at execution time. The algorithm used requires tracking what nodes the traversal has visited so far, as well as what nodes it is currently working with (represented as a stack).
Also, now's a good time to test the next()
method returned
by traverser()
.
// Graph.spec.ts
// ...
describe('traverser()', () => {
cosnt adjList = { A: ['B', 'D'], B: [], C: ['B'], D: ['C'], } const aGraph = graph.create(adjList, 'A') // A -> B -> D -> C
)
// ...
describe('next()', () => { let lastNode: string let traverser = aGraph.traverser() it('returns the next item in the traverser ', () => { lastNode = traverser.next() expect(lastNode).to.equal('A') }) it('returns a new value each time', () => { expect(traverser.next()).to.not.equal(lastNode) }) it('uses a depth-first traversal algorithm to determine order', () => { let traversed: Array<string | null> = [] traverser = graph.create(adjList, 'A').traverser() traversed.push(traverser.next()) traversed.push(traverser.next()) traversed.push(traverser.next()) traversed.push(traverser.next()) expect(traversed).to.deep.equal(['A', 'B', 'D', 'C']) }) it('returns null if there are no items left in the traverser', () => { expect(traverser.next()).to.be.null }) })})
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
adjacencyList: state.adjacencyList,
addNode: (node) => {
// ...
},
addEdge: (from: string, to: string) => {
// ...
},
traverser: () => { const visited: Array<string> = [] const stack: Array<string> = [] // start the traversal by examing the root node stack.push(state.root) return { next: () => { // do something to find the next node here... } } }})
// ...
Finding the next node works by applying two tests & stopping at the first one that passes:
- Is there a current node? If not, then the traversal is complete.
- Has the current node been visited? If not, then it's the next node to return.
Implementing them is fairly straightforward:
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
// ...
traverser: () => {
const visited: Array<string> = []
const stack: Array<string> = []
stack.push(state.root)
const recur = (): string | null => { const current = stack[stack.length - 1] if (!current) return null if (!visited.includes(current)) { visited.push(current) return current } // else find the next node, push it to the // stack, & recur... }
return {
next: () => recur()
}
}
})
// ...
Finding the next node when neither check is satisfied
is the trickiest part. First, recur()
need to get
the list of neighbors for the current node, then it
needs to eliminate any neighbor that's already been
visited. If there's no remaining neighbors left, then
it pops the current node off the stack & recur
(making the next node on the stack the new current
node). Otherwise, it picks a node from the remaining
(un-visited) neighbors, push it to the stack (so that
it becomes the new current node), & recur.
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
// ...
traverser: () => {
const visited: Array<string> = []
const stack: Array<string> = []
stack.push(state.root)
const recur = (): string | null => {
const current = stack[stack.length - 1]
if (!current) return null
if (!visited.includes(current)) {
visited.push(current)
return current
}
const neighbors = adjacencyList[current] let remaining = neighbors.reduce( (accumulator: string[], neighbor) => { if (!visited.includes(neighbor)) accumulator.push(neighbor) return accumulator }, [] ) if (remaining.length <= 0) { stack.pop() return recur() } stack.push(remaining[0]) return recur() }
return {
next: () => recur()
}
}
})
// ...
All-together, this is almost enough to pass the tests for next()
,
but it still fails one ('uses a depth-first traversal algorithm to
determine order') at least some of the time. This happens because
the order of remaining is indeterminate. To fix this, remaining can
be sorted before getting the next node from it using
Array.prototype.sort()
:
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
// ...
traverser: () => {
// ...
const recur = (): string | null => {
// ...
remaining = remaining.sort() stack.push(remaining[0])
return recur()
}
return {
next: () => recur()
}
}
})
// ...
By sorting remaining & always grabbing the first element in the array, determining the next node becomes predictable & the algorithm becomes testable. With graph traversal solved, it's now possible to solve the final requirement.
Detect cycles & enforce acyclicality
Fortunately, detecting a cycle is fairly straightforward: given a current node during a traversal, if any one or more of that current node's neighbors are already represented in the stack, then that means there's a cycle. Because this graph implementation is for directed, acyclical graphs, it shouldn't allow cycles, & should throw an error when one is detected.
// Graph.spec.ts
import graph, { CycleError } from './Graph'
// ...
describe('traverser()', () => {
// ...
describe('next()', () => {
// ...
it( 'throws an error if a cycle is detected at the current node', () => { cosnt adjList = { A: ['B'], B: ['A'], } traverser = graph.create(adjList, 'A').traverser() // A -> B -> A -> B ... // stack => ['A'] // current => ['A'] // current's neighbors => ['B'] traverser.next() // returns the root node, 'A' // // stack => ['A', 'B'] // current => ['B'] // current's neighbors => ['A'] // B's neighbor, A, is already in the stack, // so it should throw an error expect(() => traverser.next()).to.throw(CycleError) }) })
})
Getting it next()
to throw the desired error is simple—
it only requires adding another check, this time after neighbors
is defined:
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
// ...
traverser: () => {
const visited: Array<string> = []
const stack: Array<string> = []
stack.push(state.root)
const recur = (): string | null => {
const current = stack[stack.length - 1]
if (!current) return null
if (!visited.includes(current)) {
visited.push(current)
return current
}
const neighbors = adjacencyList[current]
if ( neighbors.some( (neighbor) => stack.includes(neighbor) ) ) { throw new CycleError( 'A cycle has been detected while traversing the graph' ) }
// ...
}
return {
next: () => recur()
}
}
})
// ...
With cycle detection implemented, enforcing acyclicality is the final problem to solve. This needs to happen when adding an edge & should work something like this:
// Graph.spec.ts
// ...
describe('addEdge()', () => {
// ...
it("won't add an edge that would create a cycle", () => { const aGraph = graph .create({ A: ['B'], B: [], }) expect(() => aGraph .addEdge('B', 'A')) .to.throw(CycleError) })})
The simplest way to enforce acyclicality to addEdge()
requires
building a new graph with the new edge, then traversing it in its
entirety. Due to the cycle detection that was just added, this
traversal will throw a CycleError
if the new edge creates a
cycle. This means the traversal just needs wrapped in a
try...catch
, then if no error is thrown, the new graph can
be returned.
// Graph.ts
// ...
const GraphBuilder = (state: State): Graph => ({
// ...
addEdge: (from: string, to: string) => {
adjList = { ...state.adjacencyList }
if (!adjList[node])
throw TypeError(
`A Node, \`${node}\`, does not exist yet; a Node must exist before an Edge can be added to it.`
)
if (!adjList[edge])
throw TypeError(
`A Node, \`${edge}\`, does not exist yet; an Edge must exist as a Node before it can be an Edge.`
)
const newEdges = [ ...state.adjacencyList[from] ]
newEdges.includes(edge)
? null
: newEdges.push(edge)
adjList[from] = newEdges
const newGraph = GraphBuilder({ adjacencyList: adjList }) try { const traverser = newGraph.traverser() let currentNode = traverser.next() while (currentNode !== null) { currentNode = traverser.next() } } catch (err) { if (err instanceof CycleError) throw new CycleError( `Can not add edge ${from}${to} because it would create a cycle` ) else throw err } return newGraph },
// ...
})
// ...
And with this last addition, that's all 4 of the main requirements. In my actual implementation, I created a few more abstractions, but everything here was the core idea. The full version is available on Github with the tests as well.
Takeaways
At the end of the day, this implementation of a graph structure was entirely unnecessary. There's more robust and probably more performant solutions already out there & it took a not insignificant amount of time on implementing this that could have been spent writing other parts of the application logic.
On the other hand, while this implementation missing some basic functionality often used with graphs (.e.g BFS, weighted edges, Dijkstra, Bellman-Ford, etc.), it does exactly what I needed in my scenario & nothing more. If in the future, I find myself trying to keep dependencies down & I want a limited set of graph features & related algorithms, I would actually consider writing something like this again. In all scenarios, I'd start with an existing library first, then re-implement my own graph structure if & only if I thought it was necessary.
Overall, this was a fun exercise that helped reinforce what I've been learning from Hands-On Data Structures and Algorithms with Python by Dr. Basant Agarwal & Benjamin Baka and Grokking Algorithms by Aditya Bhargava.
~~~
Do you have any questions or comments about anything? I'd love to hear from you! Send me a message using the form or any of the social media platforms below, or just send me an email at hello@andrew-chang-dewitt.dev