Noiseless Praying Mantis

# npm

## lite-pathfindings

1.1.3 • Public • Published

# Lite-Pathfindings

Simple, intuitive and lightweight pathfinding algorithms.

### 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.

Returns :

##### 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.

Returns :

#### Helpers

###### 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 :

Returns :

MIT

## Keywords

### Install

`npm i lite-pathfindings`

### Repository

github.com/morintd/lite-pathfindings

### Homepage

github.com/morintd/lite-pathfindings