Graph Data Structure, adjacency list implementation + Traversals (DFS, BFS)

README.md

Graph Data Structure, adjacency list implementation + Traversals (DFS, BFS)

Simplest implementation of a Graph + Traversal algorithms.

Usage

make

# or, if you want to watch for changes
make watch

Graph.js

module.exports = class Graph {

    constructor(V, E, directed = false) {
        this.vertices = V;
        this.edges = {};

        E.map(e => {
            const a = e[0]; const b = e[1]; const w = e[2] === undefined ? 1 : e[2];

            this.addEdge(a, b, w);
            if (!directed) this.addEdge(b, a, w);
        });
    }

    addEdge(va, vb, w) {
        if (!(va in this.edges)) this.edges[va] = [];
        this.edges[va].push({ node: vb, w });
    }

    getEdges(v) {
        return (v in this.edges) ? this.edges[v] : [];
    }

    getEdge(a, b) {
        return (a in this.edges) ? this.edges[a].find(e => e.node === b) : undefined;
    }
}

index.js

const Graph = require('./Graph');
const { dfs, dfsIterative, bfs } = require('./traversal');

const g = new Graph(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'], [
    ['a', 'b', 4],
    ['b', 'c', 8],
    ['c', 'd', 7],
    ['d', 'e', 9],
    ['e', 'f', 10],
    ['f', 'g', 2],
    ['g', 'h', 1],
    ['h', 'a', 4],
    ['b', 'h', 11],
    ['c', 'i', 2],
    ['c', 'f', 4],
    ['d', 'f', 14],
    ['h', 'i', 7],
]);

const logNode = function(vertex, previous, weight) {
    console.log((previous ? previous : '∅') + ' -' + (weight ? '(' + weight + ')' : '') + '-> ' + vertex);
};

console.log('Depth First Search, starting from a:');
dfs(g, 'a', logNode);

console.log('\nDepth First Search Iterative, starting from a:');
dfsIterative(g, 'a', logNode);

console.log('\nBreadth First Search, starting from a:');
bfs(g, 'a', logNode);

console.log('\nDepth First Search, starting from i:');
dfs(g, 'i', logNode);

console.log('\nBreadth First Search, starting from i:');
bfs(g, 'i', logNode);

Makefile

.DEFAULT_GOAL := run
SRC=$(wildcard *.js)

changed: $(SRC)
	echo "Changed !"
	exit 0

run: $(SRC)
	@node index.js

watch:
	while true; do make -t -s -q changed || (echo "\n---"; make -s run); sleep 0.5; done

traversal.js

module.exports = {
    dfs,
    dfsIterative,
    bfs
};

function dfs(graph, currentVertex, cbk, weight = undefined, visited = {}, previousVertex) {
    visited[currentVertex] = true;
    cbk(currentVertex, previousVertex, weight);

    graph.getEdges(currentVertex).map(e => {
        if (!visited[e.node]) {
            dfs(graph, e.node, cbk, e.w, visited, currentVertex);
        }
    });
}

function dfsIterative(graph, currentVertex, cbk) {
    const stack = [{ v: currentVertex, prev: undefined, weight: undefined}];
    const visited = {};

    while(stack.length) {
        const { v, prev, weight } = stack.pop();
        if (visited[v]) continue;

        visited[v] = true;
        cbk(v, prev, weight);

        graph.getEdges(v).reverse().map(e => {  // reverse: traversal in same order as recursive dfs (stack inverses order)
            stack.push({ v: e.node, prev: v, weight: e.w });
        });
    }
}

function bfs(graph, currentVertex, cbk) {
    const queue = [{ v: currentVertex, prev: undefined, weight: undefined}];
    const visited = {};
    while(queue.length) {
        const { v, prev, weight } = queue.pop();
        if(visited[v]) continue;

        visited[v] = true;
        cbk(v, prev, weight);
        graph.getEdges(v).map(e => {
            if(!visited[e.node])
            queue.unshift({ v: e.node, prev: v, weight: e.w });
        });
    }
}