bobbrady/basic-algorithms

Basic algorithms implemented as a Node.js package

Data Structures and Algorithms in JavaScript

Basic data structures and algorithms JavaScript implementations that can be used both as a Node.js package and a browser library.

The data structures and algorithms were implemented from psuedo code found in various texts given below. The particular style of an algorithm was selected by big-O performance and ease of understanding/coding (e.g, Prim's MST algorithm with node weight key and predecessor arrays).

• Algorithms 4Ed by Sedgewick
• Data Structures and Algorithms in Java 2Ed by LaFlore
• Algorithms in a Nutshell by Heinman

Usage

• Install Node.js
• Clone this repo
• Run npm install
• Place scripts where Node's require can find it
• Require the data structures and algorithm functions you need
• Read and run the tests to see how it works

View The Current Functionality Provided

$ node
> require('./basic-algorithms')
{ array: { shiftArrayRight: [Function], shiftArrayLeft: [Function] },
  graph: { Edge: [Function], Vertex: [Function], Graph: [Function] },
  graphSearch: 
   { depthFirstSearch: [Function],
     minSpanningTree: [Function],
     breadthFirstSearch: [Function],
     getDiscoveredOrder: [Function] },
  weightedGraphMST: { MinSpanningTree: [Function], weightedMST: [Function] },
  node: { Node: [Function], deleteNode: [Function] } }
> 

Read the Annotated Code to Learn the API

/*
 * MinSpanningTree: Wrapper object containing the Minimum Spanning Tree (MST)
 * results for a graph: predecessor array and edge weights array.
 *
 * @constructor
 * @param {Array} pred, the predecessor array of vertices
 * @param {Array} key, the final array of edge weights keyed by vertex logical id
 */
    exports.MinSpanningTree = function(pred, key) {
        this.predecessors = pred;
        this.weights = key;
    };

Example Usage with Mocha-Chai Test

var should = require('chai').should(),
    Graph = require('../lib/basic-algorithms').graph.Graph,
graphSearch = require('../lib/basic-algorithms').graphSearch;

describe('Graph Search algorithms: Depth First', function() {

    var numV = 7;
    var myGraph;

    beforeEach(function(done) {
        myGraph = new Graph().withNumberVertices(numV);
        myGraph.addEdge(0, 1);
        myGraph.addEdge(0, 2);
        myGraph.addEdge(1, 3);
        myGraph.addEdge(1, 4);
        myGraph.addEdge(2, 5);
        myGraph.addEdge(2, 6);
        done();
    });

    it('should visit all vertices in a connected graph', function(done) {
        graphSearch.depthFirstSearch(myGraph, 0);
        for (var i = 0; i < numV; i++) {
            myGraph.getVertex(i).isMarked().should.be.equal(true);
        }
		done();
    });

    it('should discover all vertices in depth first order', function(done) {
        graphSearch.depthFirstSearch(myGraph, 0);
        graphSearch.getDiscoveredOrder().should.be.deep.equal([0, 1, 4, 2, 3, 5, 6]);
		done();
    });

    it('should throw an Error on start vertex < 0 or undefined ', function(done) {
        should.throw(function() {
        graphSearch.depthFirstSearch(myGraph, -1);
        }, 'Graph Search Error: start vertex index < 0 or undefined');
		done();
    });

    it('should throw an Error on input graph has no vertices', function(done) {
		myGraph = new Graph();
        should.throw(function() {
        graphSearch.depthFirstSearch(myGraph, 0);
        }, 'Graph Search Error: Graph has no vertices');
		done();
    });
});