What

Brief

This is a standalone Graph data structure from the data-structure-typed collection. If you wish to access more data structures or advanced features, you can transition to directly installing the complete data-structure-typed package

How

install

npm

npm i graph-typed --save

yarn

yarn add graph-typed

snippet

TS

DirectedGraph

import {DirectedGraph, DirectedVertex, DirectedEdge} from 'data-structure-typed';
// /* or if you prefer */ import {DirectedGraph, DirectedVertex, DirectedEdge} from 'graph-typed';

const graph = new DirectedGraph();
const vertexA = new DirectedVertex('A');
const vertexB = new DirectedVertex('B');
const vertexC = new DirectedVertex('C');
const edgeAB = new DirectedEdge('A', 'B');
const edgeBC = new DirectedEdge('B', 'C');

graph.addVertex(vertexA);
graph.addVertex(vertexB);
graph.addVertex(vertexC);
graph.addEdge(edgeAB);
graph.addEdge(edgeBC);

const topologicalOrder = graph.topologicalSort();
if (topologicalOrder) expect(topologicalOrder).toEqual(['A', 'B', 'C'])

MapGraph

import {MapGraph, MapVertex} from 'data-structure-typed';
// /* or if you prefer */ import {MapGraph, MapVertex} from 'graph-typed';

const mapGraph = new MapGraph([5.500338, 100.173665]);

mapGraph.addVertex(new MapVertex('Surin', 5.466724, 100.274805));
mapGraph.addVertex(new MapVertex('Batu Feringgi Beach', 5.475141, 100.276670));
mapGraph.addVertex(new MapVertex('Lotus', 5.459044, 100.308767));
mapGraph.addVertex(new MapVertex('The Breeza', 5.454197, 100.307859));
mapGraph.addVertex(new MapVertex('Hard Rock Hotel', 5.467850, 100.241876));
mapGraph.addVertex(new MapVertex('Mira', 5.456749, 100.286650));
mapGraph.addVertex(new MapVertex('Penang Bible Church', 5.428683, 100.314825));
mapGraph.addVertex(new MapVertex('Queensbay', 5.332760, 100.306651));
mapGraph.addVertex(new MapVertex('Saanen Goat Farm', 5.405738, 100.207699));
mapGraph.addVertex(new MapVertex('Trinity Auto', 5.401126, 100.303739));
mapGraph.addVertex(new MapVertex('Penang Airport', 5.293185, 100.265772));
mapGraph.addEdge('Surin', 'Lotus', 4.7);
mapGraph.addEdge('Lotus', 'The Breeza', 1);
mapGraph.addEdge('Batu Feringgi Beach', 'Hard Rock Hotel', 5.2);
mapGraph.addEdge('Surin', 'Mira', 2.8);
mapGraph.addEdge('Mira', 'Penang Bible Church', 7.0);
mapGraph.addEdge('Lotus', 'Penang Bible Church', 5.7);
mapGraph.addEdge('Penang Bible Church', 'Queensbay', 13.9);
mapGraph.addEdge('Hard Rock Hotel', 'Saanen Goat Farm', 18.5);
mapGraph.addEdge('The Breeza', 'Trinity Auto', 9.1);
mapGraph.addEdge('Trinity Auto', 'Saanen Goat Farm', 26.3);
mapGraph.addEdge('The Breeza', 'Penang Airport', 24.8);
mapGraph.addEdge('Penang Airport', 'Saanen Goat Farm', 21.2);
const expected1 = ['Surin', 'Lotus', 'The Breeza', 'Trinity Auto', 'Saanen Goat Farm'];

const minPathBetween = mapGraph.getMinPathBetween('Surin', 'Saanen Goat Farm');
expect(minPathBetween?.map(v => v.id)).toEqual(expected1);
const surinToSaanenGoatFarmDij = mapGraph.dijkstra('Surin', 'Saanen Goat Farm', true, true);
expect(surinToSaanenGoatFarmDij?.minPath.map(v => v.id)).toEqual(expected1);
expect(surinToSaanenGoatFarmDij?.minDist).toBe(41.1);
mapGraph.addEdge('Surin', 'Batu Feringgi Beach', 1.5);
const expected2 = ['Surin', 'Batu Feringgi Beach', 'Hard Rock Hotel', 'Saanen Goat Farm'];
const minPathBetweenViaBFB = mapGraph.getMinPathBetween('Surin', 'Saanen Goat Farm', true);
expect(minPathBetweenViaBFB?.map(v => v.id)).toEqual(expected2);
const surinToSaanenGoatFarmViaDij = mapGraph.dijkstra('Surin', 'Saanen Goat Farm', true, true);
expect(surinToSaanenGoatFarmViaDij?.minPath.map(v => v.id)).toEqual(expected2);
expect(surinToSaanenGoatFarmViaDij?.minDist).toBe(25.2);

JS

DirectedGraph

const {DirectedGraph, DirectedVertex, DirectedEdge} = require('data-structure-typed');
// /* or if you prefer */ const {DirectedGraph, DirectedVertex, DirectedEdge} = require('graph-typed');

const graph = new DirectedGraph();
const vertexA = new DirectedVertex('A');
const vertexB = new DirectedVertex('B');
const vertexC = new DirectedVertex('C');
const edgeAB = new DirectedEdge('A', 'B');
const edgeBC = new DirectedEdge('B', 'C');

graph.addVertex(vertexA);
graph.addVertex(vertexB);
graph.addVertex(vertexC);
graph.addEdge(edgeAB);
graph.addEdge(edgeBC);

const topologicalOrder = graph.topologicalSort();
if (topologicalOrder) expect(topologicalOrder).toEqual(['A', 'B', 'C'])

MapGraph

const {MapGraph, MapVertex} =  require('data-structure-typed');
// /* or if you prefer */ const {MapGraph, MapVertex} = require('graph-typed');

const mapGraph = new MapGraph([5.500338, 100.173665]);

mapGraph.addVertex(new MapVertex('Surin', 5.466724, 100.274805));
mapGraph.addVertex(new MapVertex('Batu Feringgi Beach', 5.475141, 100.276670));
mapGraph.addVertex(new MapVertex('Lotus', 5.459044, 100.308767));
mapGraph.addVertex(new MapVertex('The Breeza', 5.454197, 100.307859));
mapGraph.addVertex(new MapVertex('Hard Rock Hotel', 5.467850, 100.241876));
mapGraph.addVertex(new MapVertex('Mira', 5.456749, 100.286650));
mapGraph.addVertex(new MapVertex('Penang Bible Church', 5.428683, 100.314825));
mapGraph.addVertex(new MapVertex('Queensbay', 5.332760, 100.306651));
mapGraph.addVertex(new MapVertex('Saanen Goat Farm', 5.405738, 100.207699));
mapGraph.addVertex(new MapVertex('Trinity Auto', 5.401126, 100.303739));
mapGraph.addVertex(new MapVertex('Penang Airport', 5.293185, 100.265772));
mapGraph.addEdge('Surin', 'Lotus', 4.7);
mapGraph.addEdge('Lotus', 'The Breeza', 1);
mapGraph.addEdge('Batu Feringgi Beach', 'Hard Rock Hotel', 5.2);
mapGraph.addEdge('Surin', 'Mira', 2.8);
mapGraph.addEdge('Mira', 'Penang Bible Church', 7.0);
mapGraph.addEdge('Lotus', 'Penang Bible Church', 5.7);
mapGraph.addEdge('Penang Bible Church', 'Queensbay', 13.9);
mapGraph.addEdge('Hard Rock Hotel', 'Saanen Goat Farm', 18.5);
mapGraph.addEdge('The Breeza', 'Trinity Auto', 9.1);
mapGraph.addEdge('Trinity Auto', 'Saanen Goat Farm', 26.3);
mapGraph.addEdge('The Breeza', 'Penang Airport', 24.8);
mapGraph.addEdge('Penang Airport', 'Saanen Goat Farm', 21.2);
const expected1 = ['Surin', 'Lotus', 'The Breeza', 'Trinity Auto', 'Saanen Goat Farm'];

const minPathBetween = mapGraph.getMinPathBetween('Surin', 'Saanen Goat Farm');
expect(minPathBetween?.map(v => v.id)).toEqual(expected1);
const surinToSaanenGoatFarmDij = mapGraph.dijkstra('Surin', 'Saanen Goat Farm', true, true);
expect(surinToSaanenGoatFarmDij?.minPath.map(v => v.id)).toEqual(expected1);
expect(surinToSaanenGoatFarmDij?.minDist).toBe(41.1);
mapGraph.addEdge('Surin', 'Batu Feringgi Beach', 1.5);
const expected2 = ['Surin', 'Batu Feringgi Beach', 'Hard Rock Hotel', 'Saanen Goat Farm'];
const minPathBetweenViaBFB = mapGraph.getMinPathBetween('Surin', 'Saanen Goat Farm', true);
expect(minPathBetweenViaBFB?.map(v => v.id)).toEqual(expected2);
const surinToSaanenGoatFarmViaDij = mapGraph.dijkstra('Surin', 'Saanen Goat Farm', true, true);
expect(surinToSaanenGoatFarmViaDij?.minPath.map(v => v.id)).toEqual(expected2);
expect(surinToSaanenGoatFarmViaDij?.minDist).toBe(25.2);

API docs & Examples

API Docs

Live Examples

Examples Repository

Data Structures

Standard library data structure comparison

Benchmark

Built-in classic algorithms

Software Engineering Design Standards