In this tutorial, we will create a reference generator for a job portal with the help of Breadth First Search (BFS) algorithm. For instance, we have few users who are friends with each other, we will create nodes for each of the user and associate each of the nodes with data, such as their name and the company they work in.
Once we create all the nodes, we will join them based on some predefined relationships between the nodes. Then, we will use these predefined relationships to determine who a user would have to talk to, in order to get referred for a job interview at a company of their choice. For example, A who works at company X and B who works at company Y are friends, B and C who works at company Z are friends. So, if A wants to get referred to company Z, then A talks to B, who can introduce them to C for a referral to company Z.
In most production-level apps, you will not be creating graphs in such a fashion. You can simply use a graph database, which can perform a lot of features out of the box.
Returning to our example, in more technical terms, we have an undirected graph (think of users as nodes and friendship as edges between them), and we want to determine the shortest path from one node to another.
To perform what we have described so far, we will be using a technique known as Breadth First Search (BFS). BFS is a graph traversal mechanism in which the neighboring nodes are examined or evaluated first before moving on to the next level. This helps to ensure that the number of links found in the resulting chain is always minimum, hence we always get the shortest possible path from node A to node B.
Although there are other algorithms, such as Dijkstra, to achieve similar results, we will go with BFS because Dijkstra is a more complex algorithm that is well suited when each edge has an associated cost with it. For example, in our case, we would go with Dijkstra if our user’s friendships have a weight associated with it such as acquaintance, friend, and close friend, which would help us associate weights with each of those paths.
A good use case to consider Dijkstra would be for something such as a Maps application, which would give you directions from point A to B based on the traffic (that is, the weight or cost associated with each edge) in between.
Creating a bidirectional graph
We can start with logic for our graph by creating a new file under utils/graph.js, which will hold the edges and then provide a simple shortestPath method to access the Graph and apply the BFS algorithm on the graph that is generated, as shown in the following code:
var _ = require('lodash'); class Graph {
constructor(users) {
// initialize edges this.edges = {};
// save users for later access this.users = users;
// add users and edges of each
_.forEach(users, (user) => { this.edges[user.id] = user.friends;
});
}
}
module.exports = Graph;Once we add the edges to our graph, it has nodes (user IDs), and edges are defined as the relationship between each user ID and friend in the friends array, which is available for each user. Forming the graph was an easy task, thanks to the way our data is structured. In our example dataset, each user has a set of friends list, which is listed in the following code:
[
{
id: 1,
name: 'Adam', company: 'Facebook',
friends: [2, 3, 4, 5, 7]
},
{
id: 2,
name: 'John', company: 'Google', friends: [1, 6, 8]
},
{
id: 3,
name: 'Bill', company: 'Twitter', friends: [1, 4, 5, 8]
},
{
id: 4,
name: 'Jose', company: 'Apple', friends: [1, 3, 6, 8]
},
{
id: 5,
name: 'Jack', company: 'Samsung', friends: [1, 3, 7]
},
{
id: 6,
name: 'Rita', company: 'Toyota', friends: [2, 4, 7, 8]
},
{
id: 7,
name: 'Smith', company: 'Matlab', friends: [1, 5, 6, 8]
},
{
id: 8,
name: 'Jane', company: 'Ford',
friends: [2, 3, 4, 6, 7]
}
]As you can note in the preceding code, we did not really have to establish a bidirectional edge exclusively here because if user 1 is a friend of user 2 then user 2 is also a friend of user 1.
Generating a pseudocode for the shortest path generation
Before its implementation, let’s quickly jot down what we are about to do so that the actual implementation becomes a lot easier:
INITIALIZE tail to 0 for subsequent iterations MARK source node as visited
WHILE result not found
GET neighbors of latest visited node (extracted using tail) FOR each of the node
IF node already visited RETURN
Mark node as visited
IF node is our expected result
INITIALIZE result with current neighbor node WHILE not source node
BACKTRACK steps by popping users from previously visited path until the source user
ADD source user to the result
CREATE and format result variable
IF result found return control
NO result found, add user to previously visited path ADD friend to queue for BFS in next iteration
INCREMENT tail for next loop
RETURN NO_RESULTImplementing the shortest path generation
Let’s now create our customized BFS algorithm to parse the graph and generate the shortest possible path for our user to get referred to company A:
var _ = require('lodash'); class Graph {
constructor(users) {
// initialize edges this.edges = {};
// save users for later access this.users = users;
// add users and edges of each
_.forEach(users, (user) => { this.edges[user.id] = user.friends;
});
}
shortestPath(sourceUser, targetCompany) {
// final shortestPath var shortestPath;
// for iterating along the breadth var tail = 0;
// queue of users being visited var queue = [ sourceUser ];
// mark visited users var visitedNodes = [];
// previous path to backtrack steps when shortestPath is found var prevPath = {};
// request is same as response
if (_.isEqual(sourceUser.company, targetCompany)) { return;
}
// mark source user as visited so
// next time we skip the processing visitedNodes.push(sourceUser.id);
// loop queue until match is found
// OR until the end of queue i.e no match while (!shortestPath && tail < queue.length) {
// take user breadth first var user = queue[tail];
// take nodes forming edges with user var friendsIds = this.edges[user.id];
// loop over each node
_.forEach(friendsIds, (friendId) => {
// result found in previous iteration, so we can stop if (shortestPath) return;
// get all details of node
var friend = _.find(this.users, ['id', friendId]);
// if visited already,
// nothing to recheck so return
if (_.includes(visitedNodes, friendId)) { return;
}
// mark as visited visitedNodes.push(friendId);
// if company matched
if (_.isEqual(friend.company, targetCompany)) {
// create result path with the matched node var path = [ friend ];
// keep backtracking until source user and add to path
while (user.id !== sourceUser.id) {
// add user to shortest path path.unshift(user);
// prepare for next iteration user = prevPath[user.id];
}
// add source user to the path path.unshift(user);
// format and return shortestPath
shortestPath = _.map(path, 'name').join(' -> ');
}
// break loop if shortestPath found if (shortestPath) return;
// no match found at current user,
// add it to previous path to help backtracking later prevPath[friend.id] = user;
// add to queue in the order of visit
// i.e. breadth wise for next iteration queue.push(friend);
});
// increment counter tail++;
}
return shortestPath ||
`No path between ${sourceUser.name} & ${targetCompany}`;
}
}
module.exports = Graph;The most important part of the code is when the match is found, as shown in the following code block from the preceding code:
// if company matched
if (_.isEqual(friend.company, targetCompany)) {
// create result path with the matched node
var path = [ friend ];
// keep backtracking until source user and add to path while (user.id !== sourceUser.id) {
// add user to shortest path path.unshift(user);
// prepare for next iteration user = prevPath[user.id];
}
// add source user to the path path.unshift(user);
// format and return shortestPath
shortestPath = _.map(path, 'name').join(' -> ');
}Here, we are employing a technique called backtracking, which helps us retrace our steps when the result is found. The idea here is that we add the current state of the iteration to a map whenever the result is not found—the key as the node being visited currently, and the value as the node from which we are visiting.
So, for example, if we visited node 1 from node 3, then the map would contain { 1: 3 } until we visit node 1 from some other node, and when that happens, our map will update to point to the new node from which we got to node 1, such as { 1: newNode }. Once we set up these previous paths, we can easily trace our steps back by looking at this map. By adding some log statements (available only in the GitHub code to avoid confusion), we can easily take a look at the long but simple flow of the data. Let us take an example of the data set that we defined earlier, so when Bill tries to look for friends who can refer him to Toyota, we see the following log statements:
starting the shortest path determination added 3 to the queue
marked 3 as visited
shortest path not found, moving on to next node in queue: 3 extracting neighbor nodes of node 3 (1,4,5,8)
accessing neighbor 1 mark 1 as visited
result not found, mark our path from 3 to 1
result not found, add 1 to queue for next iteration current queue content : 3,1
accessing neighbor 4 mark 4 as visited
result not found, mark our path from 3 to 4
result not found, add 4 to queue for next iteration current queue content : 3,1,4
accessing neighbor 5 mark 5 as visited
result not found, mark our path from 3 to 5
result not found, add 5 to queue for next iteration current queue content : 3,1,4,5
accessing neighbor 8 mark 8 as visited
result not found, mark our path from 3 to 8
result not found, add 8 to queue for next iteration current queue content : 3,1,4,5,8
increment tail to 1
shortest path not found, moving on to next node in queue: 1 extracting neighbor nodes of node 1 (2,3,4,5,7)
accessing neighbor 2 mark 2 as visited
result not found, mark our path from 1 to 2
result not found, add 2 to queue for next iteration current queue content : 3,1,4,5,8,2
accessing neighbor 3
neighbor 3 already visited, return control to top accessing neighbor 4
neighbor 4 already visited, return control to top accessing neighbor 5
neighbor 5 already visited, return control to top accessing neighbor 7
mark 7 as visited
result not found, mark our path from 1 to 7
result not found, add 7 to queue for next iteration current queue content : 3,1,4,5,8,2,7
increment tail to 2
shortest path not found, moving on to next node in queue: 4 extracting neighbor nodes of node 4 (1,3,6,8)
accessing neighbor 1
neighbor 1 already visited, return control to top accessing neighbor 3
neighbor 3 already visited, return control to top accessing neighbor 6
mark 6 as visited
result found at 6, add it to result path ([6]) backtracking steps to 3
we got to 6 from 4
update path accordingly: ([4,6]) add source user 3 to result
form result [3,4,6] return result
increment tail to 3
return result Bill -> Jose -> RitaWhat we basically have here is an iterative process using BFS to traverse the tree and backtracking the result. This forms the core of our functionality.
Creating a web server
We can now add a route to access this graph and its corresponding shortestPath method. Let’s first create the route under routes/references and add it as a middleware to the web server:
var express = require('express'); var app = express();
var bodyParser = require('body-parser');
// register endpoints
var references = require('./routes/references');
// middleware to parse the body of input requests app.use(bodyParser.json());
// route middleware app.use('/references', references);
// start server app.listen(3000, function () {
console.log('Application listening on port 3000!');
});Then, create the route as shown in the following code:
var express = require('express'); var router = express.Router();
var Graph = require('../utils/graph'); var _ = require('lodash');
var userGraph;
// sample set of users with friends
// same as list shown earlier var users = [...];
// middleware to create the users graph router.use(function(req) {
// form graph
userGraph = new Graph(users);
// continue to next step req.next();
});
// create the route for generating reference path
// this can also be a get request with params based
// on developer preference router.route('/')
.post(function(req, res) {
// take user Id
const userId = req.body.userId;
// target company name
const companyName = req.body.companyName;
// extract current user info
const user = _.find(users, ['id', userId]);
// get shortest path
const path = userGraph.shortestPath(user, companyName);
// return res.send(path);
});
module.exports = router;Running the reference generator
To test this, simply start the web server by running the npm start command from the root of the project as shown earlier.
Once the server is up and running, you can use any tool you wish to post the request to your web server, as shown in the following screenshot:
As you can see in the preceding screenshot, we get the response back as expected. This can, of course, be changed in a way to return all the user objects instead of just the names. That could be a fun extension of the example for you to try on your own.
We learned to create a reference generator for a job portal using the Breadth First Search (BFS) algorithm in JavaScript.
If you have found this post interesting, do check out this book, Hands-On Data Structures and Algorithms with JavaScript to create and employ various data structures in a way that is demanded by your project or use case.
