[JavaScript Quiz #16] Smallest number of flights

Consider you have a set of places (CAI, FRA, MAD, NYC, SFO) and there are available flights between some of these destinations as shown below.

CAI -> FRA
FRA -> MAD
MAD -> NYC
CAI -> MAD
NYC -> SFO
FRA -> CAI
MAD -> FRA

Design and develop a JavaScript function that can get the shortest possible path from a destination X to destination Y if there is any.
.
.
.
.
.
.
.
.
.
.
.
.
.
In order to develop a JavaScript function which can get the shortest path between two destinations, first of all, we need to think about the proper data structure which can represent these places and the connections between them. If we think about it, we will find that these placed can be represented as nodes and the connections between these places can be represented as edges which is typically a Graph. We can represent this Graph as a 2D N X N array as shown below.

    CAI FRA MAD NYC SFO
CAI  0   1   1   0   0
FRA  1   0   1   0   0
MAD  0   1   0   1   0
NYC  0   0   0   0   1
SFO  0   0   0   0   0

The previous matrix can be translated to the following JavaScript code.

var mapping = {
    "CAI": 0,
    "FRA": 1,
    "MAD": 2,
    "NYC": 3,
    "SFO": 4
};

var routeGraph = 
[
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]    
];

After make the proper representation, we need to think about how to get the shortest path between any two nodes in this unweighted graph. Since this graph is unweighted, we can use directly BFS (Breath First Search) in order to get the shortest path. For more information about BFS, check: https://en.wikipedia.org/wiki/Breadth-first_search.

In order to implement BFS, there are some notes for our implementation below:

  1. We utilized the Queue data structure for storing the nodes in a first-in, first-out (FIFO) style, we explore the oldest unexplored nodes first. Thus our explorations radiate out slowly from the starting node, defining a breadth-first search.
  2. In order to keep track of the shortest path, we have a JavaScript map nodeParent object which stores the first visited parent of the current visited node.
  3. Finally, when the search finds the destination then we construct the final path from the nodeParent object and stores it in the finalPath array.

The code below shows our BFS implementation in order to get the shortest path between the start and destination nodes.

var ShortestPathFinder = function() {
}

ShortestPathFinder.find = function (start, destination) {
    var visited = {}; // A map containing all of the visited nodes ...
    var nodeParent = {}; // An map containing the node parents ...
    var queue = [start], i, found = false, finalPath = [], neighbours = [];    
    
    nodeParent[start] = null;
    
    var current = queue.shift();
    
    while ((neighbours = ShortestPathFinder.getNeighbours(current)) != null) {
    
        for (i = 0; i < neighbours.length; ++i) {
            
            // If we find the destination then exit these loops ...
            if (neighbours[i] == destination) {
                found = true;
                nodeParent[neighbours[i]] = current;
                break;
            }
        
            if (! visited[neighbours[i]]) {
                
                // Mark this node as "visited" ...
                visited[neighbours[i]] = true;
            
                // Add element to the queue ...
                queue.push(neighbours[i]);
                nodeParent[neighbours[i]] = current;
            }
        }
        
        if (queue.length == 0) {
            break;
        }
        
        current = queue.shift();
    }
    
    if (! found) {
        console.error("No path is found between " + start + " and " + destination);
        
        return null;
    }
    
    // Construct the final path from the node parent map ...
    current = destination;
    
    finalPath.push(destination);
    
    while (nodeParent[current] != start) {
        finalPath.push(nodeParent[current]);
        
        current = nodeParent[current];
    }
    
    finalPath.push(start);    
    
    return finalPath.reverse();
}

In order to get the neighbours of the current node, a simple function is implemented to get the neighbours from the routeGraph matrix as follows.

ShortestPathFinder.getNeighbours = function(current) {
    var currentIndex = mapping[current], i, result = [];
    
    for (i = 0; i < routeGraph[currentIndex].length; ++i) {
        if (routeGraph[currentIndex][i] == 1) {
            result.push(mapping.getKey(i));
        }
    }
    
    return result;
}

Finally, we can test our developed JavaScript function by having the following test cases.

console.log(ShortestPathFinder.find("CAI", "NYC"));
console.log(ShortestPathFinder.find("CAI", "SFO"));
console.log(ShortestPathFinder.find("FRA", "NYC"));
console.log(ShortestPathFinder.find("SFO", "CAI"));
console.log(ShortestPathFinder.find("MAD", "CAI"));

Below is the output of the console.

["CAI", "MAD", "NYC"]
["CAI", "MAD", "NYC", "SFO"]
["FRA", "MAD", "NYC"]
No path is found between SFO and CAI
null
["MAD", "FRA", "CAI"]

Attached below, the complete solution code for your reference, if you have comments or a better solution, feel free to comment below.

/*
CAI -> FRA
FRA -> MAD
MAD -> NYC
CAI -> MAD
NYC -> SFO
FRA -> CAI
MAD -> FRA

    CAI FRA MAD NYC SFO
CAI  0   1   1   0   0
FRA  1   0   1   0   0
MAD  0   1   0   1   0
NYC  0   0   0   0   1
SFO  0   0   0   0   0
*/

var mapping = {
    "CAI": 0,
    "FRA": 1,
    "MAD": 2,
    "NYC": 3,
    "SFO": 4
};

var routeGraph = 
[
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]    
];

Object.prototype.getKey = function(value){
  for(var key in this){
    if(this[key] == value){
      return key;
    }
  }
  return null;
};


var ShortestPathFinder = function() {
}

ShortestPathFinder.find = function (start, destination) {
    var visited = {}; // A map containing all of the visited nodes ...
    var nodeParent = {}; // An map containing the node parents ...
    var queue = [start], i, found = false, finalPath = [], neighbours = [];    
    
    nodeParent[start] = null;
    
    var current = queue.shift();
    
    while ((neighbours = ShortestPathFinder.getNeighbours(current)) != null) {
    
        for (i = 0; i < neighbours.length; ++i) {
            
            // If we find the destination then exit these loops ...
            if (neighbours[i] == destination) {
                found = true;
                nodeParent[neighbours[i]] = current;
                break;
            }
        
            if (! visited[neighbours[i]]) {
                
                // Mark this node as "visited" ...
                visited[neighbours[i]] = true;
            
                // Add element to the queue ...
                queue.push(neighbours[i]);
                nodeParent[neighbours[i]] = current;
            }
        }
        
        if (queue.length == 0) {
            break;
        }
        
        current = queue.shift();
    }
    
    if (! found) {
        console.error("No path is found between " + start + " and " + destination);
        
        return null;
    }
    
    // Construct the final path from the node parent map ...
    current = destination;
    
    finalPath.push(destination);
    
    while (nodeParent[current] != start) {
        finalPath.push(nodeParent[current]);
        
        current = nodeParent[current];
    }
    
    finalPath.push(start);    
    
    return finalPath.reverse();
}

ShortestPathFinder.getNeighbours = function(current) {
    var currentIndex = mapping[current], i, result = [];
    
    for (i = 0; i < routeGraph[currentIndex].length; ++i) {
        if (routeGraph[currentIndex][i] == 1) {
            result.push(mapping.getKey(i));
        }
    }
    
    return result;
}

console.log(ShortestPathFinder.find("CAI", "NYC"));
console.log(ShortestPathFinder.find("CAI", "SFO"));
console.log(ShortestPathFinder.find("FRA", "NYC"));
console.log(ShortestPathFinder.find("SFO", "CAI"));
console.log(ShortestPathFinder.find("MAD", "CAI"));

Creating Cordova jQuery Mobile Apps Rapidly

Cordova jQuery npm plugin allows you to add jQuery mobile’s ready-made templates to your existing Apache Cordova app using a neat easy-to-use CLI.

You can install Cordova jQuery npm plugin using the following npm command:
npm install -g cordova-jquery

Once you install it, you can start using it by executing cordova-jquery command from your Apache Cordova app’s root directory. The next six videos shows you how to create six Cordova jQuery mobile apps with different templates (Multipages, Header Navigation Bar, Persistent Navigation Bar, External Panel, Accordion, and ListView).

As shown in the videos below, after executing cordova-jquery command, all what you need to do is to choose the template you would like to apply to your existing Cordova app. All of the examples below work on Apache Cordova version 5.1.1 (The latest Cordova release until the moment).

Cordova jQuery plugin supports the following templates.

  1. Multiple Pages
    This template will apply a simple two page jQuery mobile template to your index.html file.
  2. Header Navbar
    This template will apply a three page jQuery mobile template to your index.html file that includes a header navbar for the header on each page.
  3. Persistent Navbar
    This template will apply a three page jQuery mobile template to your index.html file that includes a persistent navbar for the footer on each page.
  4. External Panel
    This template will apply an external panel to jQuery mobile. When this option is selected you will also be prompted for additional information such as which side of the page you’d like the panel to open on (left, right) and which reveal style would you like (reveal, push, overlay)
  5. Accordion
    This template will apply three sections’ jQuery mobile accordion template to your index.html file. Your existing content will be placed as part of the first section. It is important to note that you have to make sure that your existing content parent element does not use CSS “absolute” position in order to be controlled by the accordion section.
  6. List View
    This template will apply a jQuery mobile list view template to your index.html file. The first item of the list view points to your existing content page, and the second and the third items of the list view point to two placeholder pages.

The main objective of this plugin is to facilitate the usage of the jQuery Mobile in Apache Cordova, so feel free to use it and submit any issues you are facing to:
https://github.com/Open-I-Beam/cordova-jquery-npm/issues

Related Plugin Videos: