Creating a reference generator for a job portal using Breadth First Search (BFS) algorithm

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_RESULT

Implementing 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 -> Rita

What 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.