graph-typed
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
methods
Directed Graph
Undirected Graph
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
Data Structures
| Data Structure | Unit Test | Performance Test | API Documentation | Implemented |
|---|---|---|---|---|
| Binary Tree | 
|
|
Binary Tree | |
| Binary Search Tree (BST) | |
|
BST | |
| AVL Tree | |
|
AVLTree | |
| Tree Multiset | |
|
TreeMultiset | |
| Segment Tree | SegmentTree | |
||
| Binary Indexed Tree | |
BinaryIndexedTree | |
|
| Graph | |
|
AbstractGraph | |
| Directed Graph | |
|
DirectedGraph | |
| Undirected Graph | |
|
UndirectedGraph | |
| Linked List | |
|
SinglyLinkedList | |
| Singly Linked List | |
|
SinglyLinkedList | |
| Doubly Linked List | |
|
DoublyLinkedList | |
| Queue | |
|
Queue | |
| Object Deque | |
|
ObjectDeque | |
| Array Deque | |
|
ArrayDeque | |
| Stack | |
Stack | |
|
| Coordinate Set | CoordinateSet | |
||
| Coordinate Map | CoordinateMap | |
||
| Heap | |
|
Heap | |
| Priority Queue | |
|
PriorityQueue | |
| Max Priority Queue | |
|
MaxPriorityQueue | |
| Min Priority Queue | |
|
MinPriorityQueue | |
| Trie | |
Trie | |
Why
Complexities
performance of Big O
| Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 |
| O(log N) | Logarithmic | 3 | 6 | 9 |
| O(N) | Linear | 10 | 100 | 1000 |
| O(N log N) | n log(n) | 30 | 600 | 9000 |
| O(N^2) | Quadratic | 100 | 10000 | 1000000 |
| O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |
Data Structure Complexity
| Data Structure | Access | Search | Insertion | Deletion | Comments |
|---|---|---|---|---|---|
| Array | 1 | n | n | n | |
| Stack | n | n | 1 | 1 | |
| Queue | n | n | 1 | 1 | |
| Linked List | n | n | 1 | n | |
| Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |
| Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |
| B-Tree | log(n) | log(n) | log(n) | log(n) | |
| Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
| AVL Tree | log(n) | log(n) | log(n) | log(n) | |
| Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |
Sorting Complexity
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 | Yes | |
| Insertion sort | n | n2 | n2 | 1 | Yes | |
| Selection sort | n2 | n2 | n2 | 1 | No | |
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |
| Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |
| Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |
| Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |
