Lite-Pathfindings
Simple, intuitive and lightweight pathfinding algorithms.
Installation
$ npm install lite-pathfindings
Features
Algorithms
Implementeds algorithms are the following (with others coming soon !) :
- Djikstra
- Floyd-Warshall
Utility library
To make it easier, handle graphs with a few extra functions :
- Transform a map of edge to its matrix representation
- Recover your edge names from a matrix
- Verify the content of an edgeMap
How to use
Djikstra
Djikstra is a well-known algorithm aiming to find the shortest path between a given edge and every other edges, it works with ponderated graph, oriented and not oriented. Djikstra doesn't work with negative weight.
API :
- init(edgeMap, sDeb) : Given an edgeMap, and an existing vertex name, create an Object "predecessor", used to get the path.
- getPath(predecessor, sDeb, sEnd) : Given the predecessor object, the vertex name used in init, and a vertex name representing the end of the path, return the vertex list of the shortest path.
- getWeight(path, edgeMap) : Given the path and the edge, return the total weight of the path.
var litepathfindings = ;var Djikstra = litepathfindingsDjikstra;// Structure which contains edge and weightvar edgeMap = a:b:12 c:20 d:9 b:a:12 g:13 c:a:20 d:8 f:11 g:2 d:a:9 c:8 f:21 e:g:9 f:3 f:c:11 d:21 e:3 g:5 g:b:13 c:2 f:5 e:9; var sDeb = "a"; // Start edgevar predecessor = Djikstra;var path = Djikstra; // We're looking for the shortest path to evar weight = Djikstra; // Find total weight console;console;
Returns :
'a' 'd' 'c' 'g' 'f' 'e' 27
Floyd-Warshall
Floyd-Warshall is an algorithm aiming to find the shortest path between every pair of edge, it works with ponderated graph, oriented and not oriented. It works thanks to a matrix which represents every vertex (and weight) of a graph. Floyd-Warhsall works with negative weight, with the exception of circuit with negative weight.
API :
- init(matrix) : Given a matrix, return an Object "next" used to easily find paths. It also modifies the given matrix by its reference.
- getPath(next, vertex1, vertex2) : Given the "next" Object and the two vertex of a path, return the list of vertex (number as it's a matrix) that make it up.
- getWeight(edgeMap, vertex1, vertex2) : Given an edgeMap and the two vertex of a path, return its total weight.
- containNegativeCycle(matrix) : Given a matrix after "init", return a boolean telling if it contains a negative cycle.
var litepathfindings = ;var FloydWarshall = litepathfindingsFloydWarshall; // Matrix which contains edge and weightvar matrixEdges = 0 12 20 9 NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY12 0 NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY 1320 NumberPOSITIVE_INFINITY 0 8 NumberPOSITIVE_INFINITY 11 29 NumberPOSITIVE_INFINITY 8 0 NumberPOSITIVE_INFINITY 21 NumberPOSITIVE_INFINITYNumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY 0 3 9NumberPOSITIVE_INFINITY NumberPOSITIVE_INFINITY 11 21 3 0 5NumberPOSITIVE_INFINITY 13 20 NumberPOSITIVE_INFINITY 9 5 0; var matrix = matrixEdges;var next = FloydWarshall; // Unless you are confident (...), you have to look for negative cycles after calling "init"if!FloydWarshall var path = FloydWarshall; var weight = FloydWarshall; console; console;else console;
Returns :
0 3 2 6 5 4 27
Helpers
As iI'd rather work with name (a, b, c, d, e, ...), an utility library is added with a few methods.
API :
- edgeMapToMatrix(edgeMap) : Given an edgeMap, return the corresponding matrix, and an "edges" object which links edge name to number : {matrix, edges}.
- getEdgeNumber(edges, edgeName) : Given a list of edges and a name, return the corresponding edge number.
- getEdgeName(edges, number) : Given a list of edges and a number, return the corresponding edge name.
- getNamedPath(path, edges) : Given a list of number representing a path, and the correspondance between number and edge name, return the corresponding list of edge name.
But also :
- edgeMapContainNegativeValue(edgeMap) : Given an edgeMap, return true if contain an edge with negative value, false otherwise.
As an example, it allows to work with edgeMap and Floyd-Warshall :
var litepathfindings = ;var FloydWarshall = litepathfindingsFloydWarshall;var Helpers = litepathfindingsHelpers; // Structure which contains edge and weightvar edgeMap = a:b:12 c:20 d:9 b:a:12 g:13 c:a:20 d:8 f:11 g:2 d:a:9 c:8 f:21 e:g:9 f:3 f:c:11 d:21 e:3 g:5 g:b:13 c:2 f:5 e:9; var matrixEdges = Helpers;var matrix = matrixEdgesmatrix;var edges = matrixEdgesedges;var next = FloydWarshall;var path = FloydWarshall;var weight = FloydWarshall; console;console;console;console;console;
Returns :
0 12 17 9 27 24 19 12 0 15 21 21 18 13 17 15 0 8 10 7 2 9 21 8 0 18 15 10 27 21 10 18 0 3 8 24 18 7 15 3 0 5 19 13 2 10 8 5 0 a: 0 b: 1 c: 2 d: 3 e: 4 f: 5 g: 6 0 3 2 6 5 4 27 'a' 'd' 'c' 'g' 'f' 'e'
License
MIT