graph-alg

A Node.js module to manipulate Graph

Installation

npm install graph-alg --save

Usage

Javascript

const Dijkstra = require('graph-alg').Dijkstra;

TypeScript

import { Dijkstra } from 'graph-alg';

Test

npm run test

Graph class

Dijkstra

Example:

import { Dijkstra } from 'graph-alg';
 
/**
 * Oriented Graph with ponderation
 * +-+        +-+         +-+         +-+
 * |0+---5---->1+----+-4-->3+-----3--->5|
 * +++        +^+    |    +++         +^+
 *  |          |     |     |           |
 *  |          8     2     6           |
 *  |          |     |     |           |
 *  |         +++    |    +v+          |
 *  +----2---->2+--7-+---->4+-----1----+
 *            +-+         +-+
 */
const graph: IDirectedGraph = {
    "0": { "1": 5, "2": 2 },
    "1": { "3": 4, "4": 2 },
    "2": { "1": 8, "4": 7 },
    "3": { "5": 3, "4": 6 },
    "4": { "5": 1 },
    "5": {},
};
// Initialize Dijkstra alg with an oriented graph
const dijkstra = new Dijkstra(graph);
// Compute the smaller path from node 0 to node 5
const result = dijkstra.resolve("0", "5");
 
// result.distance equals 8
// result.path equals ["0", "1", "4", "5"]