How to use the Minimum Spanning Tree of a Graph algorithm (Kruskal) for an airport problem.

Violeta — Sun, 23 Aug 2020 16:32:09 +0000

Given a number of airports connections with the time duration between them find the route that pass through all airports in the shortest time possible (returns to the same airport are excluded).

The problem can be translated as: find the Minimum Spaning Tree (MST) in an undirected weighted connected graph.

A MST is a subgraph consisting of all the nodes in the graph with one exclusive path from a node to every other one (no cycles) and having the minimum sum of all edges weight among all such subgraphs.

Example of 5 airports with 7 direct flight connections and their duration in hours:

5 7
MAD XDT 2
MAD OTP 3
MAD FRA 4
MAD BER 4
XDT OTP 3
OTP FRA 4
FRA BER 2

The shortest route through all airports would take 11 hours:

MAD -- XDT ( 2 )
FRA -- BER ( 2 )
MAD -- OTP ( 3 )
MAD -- FRA ( 4 )
time:  11

Example of 4 airports with 6 direct flight connections and their duration in hours:

4 6
ANK BCN 3
ANK COS 2
DTM ANK 6
BCN DTM 7
COS BCN 4
COS DTM 5

So, from Ankara (ANK) to Barcelona (BCN) are 3 hours to fly.

The shortest route through all airports would take 12 hours:

ANK -- COS ( 3 )
COS -- BCN ( 4 )
COS -- DTM ( 5 )
time:  12

We can use Kruskal algorithm to find a graph minimum spanning tree. If the number of nodes in a graph is V, then each of its spanning trees should have (V-1) edges and contain no cycles.
Kruskal STEPS:

Initialize an empty edge set T 
Sort all graph edges by the ascending order of their weight values
Foreach edge in the sorted edge list
    Check whether it will create a cycle with the edges inside T
    If the edge doesn't introduce any cycles, add it into T
    If T has (V-1) edges, exit the loop
return T

The Node.js implementation:

'use strict';

let fs = require('fs'),
    readline = require('readline');

class Edge {
    constructor(v1, v2, w = 0) {
        this.v1 = v1;
        this.v2 = v2;
        this.w = w;
    }
}

class Graph {
    constructor(v, e) {
      this.v = v;
      this.e = e;
      this.edges = [];
      this.nodes = [];
    }

    addEdge(edge) {
      this.edges.push(edge);
      if (!this.nodes.includes(edge.v1)) {
        this.nodes.push(edge.v1);
      }
      if (!this.nodes.includes(edge.v2)) {
        this.nodes.push(edge.v2);
      }
    }

    getEdge(pos) {
      return this.edges[pos]
    }

    getEdges() {
      return this.edges
    }

    getNodes() {
      return this.nodes
    }

    // get the root of node
    find(subsets, node) {
      let nodeInfo = subsets.get(node);
      if (nodeInfo.parent != node) {
        nodeInfo.parent = this.find(subsets, nodeInfo.parent)
      }

      return nodeInfo.parent; 
    }

    // unite the x and y subsets based on rank
    union(subsets, x, y) {
        let xroot = this.find(subsets, x);
        let yroot = this.find(subsets, y);

        if (subsets.get(xroot).rank < subsets.get(yroot).rank) {
            subsets.get(xroot).parent = yroot;
        } else if (subsets.get(xroot).rank > subsets.get(yroot).rank) {
          subsets.get(yroot).parent = xroot;
        } else {
          subsets.get(yroot).parent = xroot;
          subsets.get(xroot).rank++;
        }
    } 
}

function kruskal(gNodes, gEdges, gFrom, gTo, gWeight) {
    let i = 0, j = 0, cost = 0;
    let subsets = new Map(),
        result = [];

    let graph = new Graph(gNodes, gEdges);

    while(i < gEdges) {
      graph.addEdge(new Edge(gFrom[i], gTo[i], gWeight[i]));
      i++;
    }

    graph.getEdges().sort((edge1, edge2) => {
      if (edge1.w === edge2.w) {
        return 1;
      }

      return edge1.w < edge2.w ? -1 : 1;
    });

    console.log('sorted edges:' , graph.getEdges());

    graph.getNodes().forEach(node => {
      subsets.set(node, { parent: node, rank: 0 });
    });

    i = 0;
    while(j < gNodes-1) {
      let edge = graph.getEdge(i++);
      let root1 = graph.find(subsets, edge.v1); 
      let root2 = graph.find(subsets, edge.v2);

      // if the nodes doesn't create a cycle then we add the edge to final subgraph
      if (root1 != root2) {
          result[j++] = edge;
          // update the total weight of the subgraph
          cost += edge.w;
          graph.union(subsets, root1, root2);
      }
    }

    i = 0;
    while(i < j) {
      console.log(`${result[i].v1} -- ${result[i].v2} ( ${result[i++].w} )`);
    }
    console.log('time: ', cost);
}

function readFile(fileName) {
  let fileStream = fs.createReadStream(fileName),
      rl,
      data = '', 
      index = 0,
      gNodes = 0, 
      gEdges = 0, 
      gFrom = [],
      gTo = [],
      gWeight = [];

  fileStream.on('error', (err) => {
    console.log('file issue: ', err.message)
  });

  rl = readline.createInterface({
      input: fileStream
  });
  // 'line' event - emitted whenever the input stream receives a new line \n
  rl.on('line', (line) => {
      data = line.split(' ');
      if (index == 0) {
          gNodes = parseInt(data[0], 10);
          gEdges = parseInt(data[1], 10);
      } else if (index <= gEdges) {
          gFrom.push(data[0]);
          gTo.push(data[1]);
          gWeight.push(parseInt(data[2], 10));
      }
      index++;
  });

  rl.on('close', () => {
    if (gNodes && gEdges && gFrom.length && gTo.length && gWeight.length) {
      kruskal(gNodes, gEdges, gFrom, gTo, gWeight);
    } else console.log('invalid data file');
  });
}

readFile('data1.txt');

Check the code on GitHub
Read more articles like this on Girlsincode

Setup Mocha 8, Chai 4 and Babel 7 for JavaScript TDD

Violeta — Wed, 19 Aug 2020 18:18:03 +0000

Let's see how to setup Mocha 8, Chai 4 and Babel 7 to test a ES6 string problem.

Given some strings of different lengths, if the number of vowels are more than 30% of the string length then insert 'summer' for each continuous set (group) of vowels.

Examples:

'' => ''
'a' => 'summer'
'ntv' => 'ntv'
'bla' => 'blsummer'
'blah' => 'blah'
'blaahah' => 'blsummerhsummerh'
'hear' => 'hsummerr'
'blAhE' => 'blsummerhsummer'

Solution:

index.js

const newStr = 'summer';
const regx = /[aeiou]+/ig;
// const regx = /(a|e|i|o|u)+/ig;
// const vowels = 'aeiou';

// const isVowel = (c) => vowels.indexOf(c.toLowerCase()) > -1;

const vowelCount = (word) => {
    // const vCount = [...word].reduce((count, letter) => count + (isVowel(letter)? 1:0), 0);
    // const re = /(a|e|i|o|u){1}/ig;
    const re = /[a|e|i|o|u]{1}/ig;
    return word.match(regx) ? word.match(re).length / word.length > 0.3 : false
};

const replaceVowels = (word) => word.replace(regx, newStr);

const changeStr = (word) => vowelCount(word) ? replaceVowels(word) : word;

export default changeStr;

test\index.spec.js

import { expect } from 'chai';
import changeStr from '../index';

describe('#changeStr', () => {
  it('should not change empty string', () => {
    expect(changeStr('')).to.equal('');
  });

  it('should not change words with no vowels', () => {
    expect(changeStr('ntv')).to.equal('ntv');
  });

  it('should change a vowel', () => {
    expect(changeStr('a')).to.equal('summer');
  });

  it('should change consonents and a vowel', () => {
    expect(changeStr('bla')).to.equal('blsummer');
  });

  it('should not change less than 30 percent vowels', () => {
    expect(changeStr('blah')).to.equal('blah');
  });

  it('should change continuous vowels once', () => {
    expect(changeStr('hear')).to.equal('hsummerr');
  });

  it('should change multiple sets of vowels', () => {
    expect(changeStr('blaahah')).to.equal('blsummerhsummerh');
  });

  it('should change capital vowels', () => {
    expect(changeStr('blAhE')).to.equal('blsummerhsummer');
  });

  it('should error on undefined input', () => {
    expect(() => changeStr()).to.throw();
  });
});

.babelrc

{
    "presets": ["@babel/preset-env"]
}

.mocharc.yml

require: '@babel/register'

.package.json

{
  "name": "tdd",
  "version": "1.0.0",
  "main": "index.js",
  "scripts": {
    "test": "mocha"
  },
  "license": "MIT",
  "devDependencies": {
    "@babel/cli": "^7.10.5",
    "@babel/core": "^7.11.1",
    "@babel/preset-env": "^7.11.0",
    "@babel/register": "^7.10.5",
    "chai": "^4.2.0",
    "mocha": "^8.1.1"
  }
}

DEV Community: Violeta