Quick program to check a tree for islands (groups of nodes that do not connect to every other node)

check-for-islands.js

/* global process */

// Exhaustively searches for islands in a minimum spanning tree.
var fs = require('fs');

if (process.argv.length < 3) {
  console.log('Usage: node tools/check-for-islands.js minimum-spanning-tree.json');
}

var mst = JSON.parse(fs.readFileSync(process.argv[2]));
var edgesForNodes = mst.reduce(addEdgeToNodeKeys, {});
var nodes = Object.keys(edgesForNodes);
// console.log(edgesForNodes);

visitEveryNode(nodes[0]);

function addEdgeToNodeKeys(edgesForNodes, edge) {
  var edgesForSource = edgesForNodes[edge.src_index];
  if (!edgesForSource) {
    edgesForSource = [];
  }
  edgesForSource.push(edge);
  edgesForNodes[edge.src_index] = edgesForSource;

  var edgesForDest = edgesForNodes[edge.dest_index];
  if (!edgesForDest) {
    edgesForDest = [];
  }
  edgesForDest.push(edge);
  edgesForNodes[edge.dest_index] = edgesForDest;

  return edgesForNodes;
}

function visitEveryNode(startingNode) {
  var visitedNodes = [+startingNode];
  var nextNodes = [+startingNode];

  do {
    console.log('visited:', visitedNodes);
    console.log('nextNodes:', nextNodes);
    let edges = [];
    for (let i = 0; i < nextNodes.length; ++i) {
      let edge = edgesForNodes[nextNodes[i]];
      edges = edges.concat(edge);
    }
    console.log('edges:', edges.map(e => ({src: e.src_index, dest: e.dest_index})));
    if (edges.length < 1) {
      console.log('Was not able to visit every node. Visited nodes:', visitedNodes);
      return false;
    }
    else {
      nextNodes = edges.reduce(addUnvisitedNodes, []);
      debugger;
      visitedNodes = visitedNodes.concat(nextNodes);
    }
  }
  while (visitedNodes.length < nodes.length);

  console.log('Visited every node!', visitedNodes);
  return true;

  function addUnvisitedNodes(unvisitedNodes, edge) {
    if (nodeIsUnvisited(edge.src_index)) {
      unvisitedNodes.push(edge.src_index);
    }
    if (nodeIsUnvisited(edge.dest_index)) {
      unvisitedNodes.push(edge.dest_index);
    }
    return unvisitedNodes;
  }

  function nodeIsUnvisited(node) {
    return visitedNodes.indexOf(node) === -1;
  }
}