graph-typed v2.0.3
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
Examples Repository
Data Structures
Standard library data structure comparison
Benchmark
Built-in classic algorithms
Software Engineering Design Standards
11 months ago
7 months ago
8 months ago
10 months ago
10 months ago
10 months ago
10 months ago
10 months ago
10 months ago
10 months ago
10 months ago
10 months ago
10 months ago
11 months ago
10 months ago
11 months ago
10 months ago
10 months ago
11 months ago
11 months ago
11 months ago
12 months ago
1 year ago
1 year ago
1 year ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago
2 years ago