Directed Graph Pathfinding Algorithm in Functional JS

Photo by Benjamin Elliott on Unsplash

There are lots of pathfinding algorithms available on books, tutorial sites, and even StackOverflow. Most of them mention names like Dijkstra, A*, Breadth — of the wild? — first, and many others. I must admit that I did tried to learn all of them though not necessarily understood everything. Among their examples of implementation, most of them strictly used for loop and conditional statements. I haven’t found any that strictly goes by functional paradigm, and I think that’s where I can come in contributing a new one. I can’t quite say that the algorithm implemented below accurately follows any of them mentioned above, for I also have different way of seeing how things should be done and what the function should return. Enough ranting of my incapabilities, let’s face this challenge head on.

I’ve learned that in graph theory there are many ways a graph could form depends on how each elements/nodes interact with each other, each vertices/edges could be undirected, directed, self-directional, or something else I don’t know. But the most relevant case would be directed graphs like the figure below. I can Imagine such graph conceptually appears everywhere, like landmarks in cities where some roads might be one-way only, a big warehouse with multi-stories shelves where some escalators might be one-way only, or probably a game where the enemy bots looking for the shortest route to stab you on the back. The graph could be as simple as two nodes connected by one edge or thousands of nodes connected by only-God-knows number of edges. It’s safe to assume that the more complex a graph is, the more time complexity the algorithm must go through to yield the results.

Directed graph from Indiana.edu

What’s the best way of representing that graph in computer friendly format? Is it in form of lists of list? A diagonal matrix? I actually tried converting it to both forms following all the tutorials I can find and looking for ways to build an algorithm upon it which yield the shortest route, only to find myself kept failing over and over. So I think I need to step back to the drawing board and specify few things before getting dirty in the codes:

1. I want a function that can accept a graph, the initial position, and the destination
2. I want that function to yield not only the shortest route but also all the alternative routes it can find
3. I want each of yielded path not only tells me where to go, but also the distance I must go through for each steps
4. I want the function to be strictly follows functional paradigm that involves no for-loops nor if-statements. And God-forbid, mutates anything outside the function itself.
5. As I believe that a recursive-like problem should be paired with recursive solution, then a recursive function should be on the menu tonight.

Aren’t these requests too much to ask for? It probably is. But if I do nailed it, creating a function that could do all of those at once, then it’d bust out of enjoyment. No different than beating a Dark Souls final boss. Now give me some space and time (or space-time?) to take this on.

In the shower, on my meals, on the way to work and back, while playing games, while tucking myself in the bed, all were occupied by this problem alone. At some points I nearly gave up and seeing myself throwing it all in the bin, but I kept on going and finally have the mental picture of how the recursion would fit in this problem. I must shamelessly admit that this ordeal took more than a week of precious — or useless — life of mine. So, let me elaborate the whole product in this article.

First, let me show you how I represent the whole graph into a format, not a list of lists, nor a matrix, but a structured object:

cityMap = {
  a: {b: 20, d: 80, g: 90},
  b: {f: 10},
  c: {f: 50, h: 20, d: 10},
  d: {g: 20, c: 10},
  e: {b: 50, g: 30},
  f: {c: 10, d: 40},
  g: {a: 20},
  h: {h: 0} // a dead end
}

Let’s call the graph containing variable as cityMap (for all we care). This object contains uniqe pairs of key and value where the key represent a node and the value represents all the other nodes directly accessible from the current one. Notice that H shall have a leading key here though it has no outward connection to any other nodes, yet it had to have an outward path into itself with 0 value. f: {c: 10, d: 40} means that F node might travel to C in 10 points of distance and to D in another 40. The order of key-value pairs in this entire object doesn’t matter, as long as none of the keys redundant and inconsistant like a: {b: 20}, a: {c: 15}. Now let me present you the main course of the day, the pFinder function.

pFinder = (graph, from, dest, path = {[from]: 1}) =>
  Object.keys(graph).filter(step => !path[step]).reduce(
    (acc, next) => graph[from]?.[next] ? [...acc, ...pFinder(
      graph, next, dest, {...path, [from]: graph[from][next]}
    )] : [...acc, ...(!acc.length && from === dest ? [path] : [])], []
  )

pFinder = ( // Let's dissect the function
  graph, from, dest, // required inputs
  path = {[from]: 1} // an object to store a traced path
) => Object.keys(graph) // list all the outgoing paths
  .filter(step => !path[step]) // only gets the untraced steps
  .reduce( // accumulate all the possible paths in an empty array
    (acc, next) => graph[from]?.[next] ? [ // is the next path available?
      ...acc, ...pFinder( // if yes, recursively trace it down
        graph, next, dest, // with the initial position shifted to next
        {...path, [from]: graph[from][next]} // pass current traced path
      ) // if it's not, then stop here, return what's in the path object
    ] : [...acc, ...( // when the "from" is finally equal to "dest" then
      !acc.length && from === dest ?
      [path] : [] // return what's traced in the path object
    )], [] // store the results here to be resurfaced later
  )

The pFinder function accepts 1. the graph, 2. starting position, 3. destination target. The path argument must be left untouched as it is for passing a tracer inside the recursive loop, where the default value is an initial position. The main idea here is to create a combinatorial path of each possible paths according to all available outgoing nodes. If such node exists according to given graph, then it shall recursively call the function itself passing down the traced nodes in the path object. The key to prevent infinite loop here is by passing what’s been traced in the path object, making sure that the loop shall stop when all nodes has traced once. When it has reached the destination or the targeted node doesn’t exists then return the last traced path, indicated by equal ‘from’ and ‘dest’ value. Perhaps the codes itself provides better explanation than my attempt here. Now let’s see the function in action.

pFinder(cityMap, 'a', 'f') /* get [
  {a: 20, b: 10},
  {a: 80, d: 10, c: 50}
]*/

pFinder(cityMap, 'g', 'h') /* get [
  {g: 20, a: 20, b: 10, f: 10, c: 20},
  {g: 20, a: 20, b: 10, f: 40, d: 10, c: 20},
  {g: 20, a: 80, d: 10, c: 20}
]*/

Have a look at the first instance of pFinder call where we say that we’re at A node and looking for ways to F node. The function return an array with 2 elements where each represents a path along with its respective distance. {a: 20, b: 10} means there’s a path from A to B in 20 points then from B to F in 10 points. There’s also another path through {a: 80, d: 10, c: 50} where we could go from A to D in 80, D to C in 10, and C to F in 50. This is the moment when I finally feel like I’ve beaten the Black Dragon Midir, but in the software engineering field.

Again, I can’t quite claim that this function belongs to any of the prior algorithms for it has a little bit of this and that, here and there. If I may be so bold, I’d like to call it “The Clairvoyance” algorithm, inspired from Elder Scrolls 5: Skyrim.

More Functions

Some of the skeptics might see my crafts adds nothing new onto the table, “why wouldn’t it yield the shortest path right away?”. I intentionally left the algorithm as is, that yields all the possible solutions at once and leave the users choose which path best suited to their needs. Not everyone would like to have the shortest route, some might want to see more of the town before arriving at the destination, some might have special requirements along the way. Few new functions below might show you what I have in mind:

between = (low, mid, high) => low < mid && mid < high
sum = arr => arr.reduce((a, b) => a + b)
sub = ([first, ...rest]) => first - sum(rest)

shortestPath = (graph, from, dest) =>
  pFinder(graph, from, dest).sort((a, b) => sub([
    sum(Object.values(a)), sum(Object.values(b))
  ]))[0]

longestPath = (graph, from, dest) =>
  pFinder(graph, from, dest).sort((a, b) => sub([
    sum(Object.values(b)), sum(Object.values(a))
  ]))[0]

conditionPath = (graph, from, dest, cond) =>
  pFinder(graph, from, dest).filter(cond)

shortestPath(cityMap, 'e', 'h') // get {e: 50, b: 10, f: 10, c: 20}

longestPath(cityMap, 'e', 'h') // get {e: 30, g: 20, a: 80, d: 10, c: 20}

There you go, calling the shortestPath function shall immediately give you an object that represent the shortest route possible, and so does the longestPath function that does the opposite. Things gets interesting when the user has some peculiar requests like:

1. I’d like to have a path that crosses the D city once, there’s an ice cream stall there I’d die for.
2. Show me the paths to my destination in 4 steps or less
3. The tour bus family package specifies that the total ride shall cover less than 150 miles yet more than 110 miles in distance, find the path that satisfy this requirement
4. I’d like to have a path where one of the roads is 80 miles or more, I wanna see how fast this Ferrari can fly.

// Solution #1
conditionPath(cityMap, 'e', 'h', path =>
  Object.keys(path).includes('d')
) // gets 3 results

// Solution #2
conditionPath(cityMap, 'e', 'h', path =>
  Object.keys(path).length <= 4
) // gets [{e: 50, b: 10, f: 10, c: 20}]

// Solution #3
conditionPath(cityMap, 'e', 'h', path =>
  between(110, sum(Object.values(path)), 150)
) // gets {e: 50, b: 10, f: 40, d: 10, c: 20} = 130 total

// Solution #4
conditionPath(cityMap, 'e', 'h', path =>
  Object.values(path).filter(i => i >= 80).length
) // gets [{e: 30, g: 20, a: 80, d: 10, c: 20}]

Isn’t it interesting to finally find a simple solution for a problem which thought to be hard at the first place? This is just one among many moments of being curious->struggle->relief cycle I felt throughout my coding journey. And I can’t wait to have just another challenge. Some of the perceptives of you should notice that the first question above is a precursor to a bigger problem people calls by Vehicle Routing Problem, which shall be covered in the next post.

Other Cases

What if one of those vertices has negative numbers? Will the function break? No. Let’s say that the graph above doesn’t represent distance in miles but rather the financial cost of using the path. And the negative numbers represents a path that might reduce the total cost of the trip. Let’s say that you’re in a night fair where the edges represents balance reduction. That particular path from F to D has advertisings all over the place and will somehow compensate your total cost through discount if you choose to cross it, instead of 40 it becomes -40. Some visitors that don’t mind the trouble of seeing ads would choose to cross it for the sake of discount.

Now let’s say that the graph above isn’t about landmarks in cities but a map of interpersonal relationships in work environment. Just change all the names to Andy, Bob, Charlie, ... and to Herbert. A directed vertex could represent how strong someone’s ability to influence or convince the one at the other side. You could use the very same algorithm to find the shortest route to get someone to do a job or certain action.

Other than ice cream trucks, who would find benefit in the longest path function? Let’s say that you’re working in bus routing management, there are lots of stations while there’s only a few of available vehicles. Could you design the routes for each vehicles where each of them drive the longest path before completing their respective round trip? Again, of course you can, just use the longest path algorithm and you’d be sure every vehicles pass by all other stations at least as long as the edges allows it.

Codes Recap

pFinder = (graph, from, dest, path = {[from]: 1}) =>
  Object.keys(graph).filter(step => !path[step]).reduce(
    (acc, next) => graph[from]?.[next] ? [...acc, ...pFinder(
      graph, next, dest, {...path, [from]: graph[from][next]}
    )] : [...acc, ...(!acc.length && from === dest ? [path] : [])], []
  )

between = (low, mid, high) => low < mid && mid < high
sum = arr => arr.reduce((a, b) => a + b)
sub = ([first, ...rest]) => first - sum(rest)

shortestPath = (graph, from, dest) =>
  pFinder(graph, from, dest).sort((a, b) => sub([
    sum(Object.values(a)), sum(Object.values(b))
  ]))[0]

longestPath = (graph, from, dest) =>
  pFinder(graph, from, dest).sort((a, b) => sub([
    sum(Object.values(b)), sum(Object.values(a))
  ]))[0]

conditionPath = (graph, from, dest, cond) =>
  pFinder(graph, from, dest).filter(cond)