Node's Pastoral Musicians

# npm

## dijkstra-floydwarshall-graph

1.2.2 • Public • Published

# Node.js implementation of Dijkstra & Floyd-Warshall Algorithms.

## Features

• Find cheapest path between two nodes using Dijkstra or Floyd-Warshall Algorithms (not only the distance matrix).
• Directed and undirected paths between nodes.
• Fixed node costs (As a toll cost).
• Edit/delete/avoid nodes and routes after their creation.
• Multiply by a factor the cost of the routes or toll costs (i.e, when changing its unit of measure).
• Costs formatting.
• Algorithm iteration logging.

## Usage

To use this library, you must only create the graph, set nodes/routes & weights and execute the desired algorithm.

### Simple Example

const {Graph} = require('dijkstra-floydwarshall-graph')

const graph = new Graph()

graph.findPathDijkstra('A', 'D') // output: => { distance: 2, path: ['A', 'C', 'D']}
graph.findMatricesFloydWarshall() // output: => [<distance_matrix>, <precedence_matrix>]

### Another Example

const {Graph} = require('dijkstra-floydwarshall-graph')

const graph = new Graph({
autoCreateNodes: true,
loggingLevel: 0,
constantNodesCost: 100,
ignoreErrors: false,
});

//Say C has a toll of 500.
graph.addNode({ name: "C", cost: 500 });

//Since autoCreateNodes is true, A,B,D nodes will be autoCreated with cost = constantNodesCost (100).
graph

let dijkstra = graph.findPathDijkstra("A", "D"); // output: => { cost: 502, path: ['A', 'B', 'D']}
let floyd_warshall = graph.findMatricesFloydWarshall(); // output: => [<distance_matrix>, <precedence_matrix>]
graph.findPathFloydWarshall("A", "D"); // output: => { cost: 502, path: ['A', 'B', 'D']}

For more examples, see Examples

## Documentation

### Graph

/** Class representing a Weighted (Un)directed Graph */
/**
* Create a Weighted (Un)directed Graph.
* @param {string} [name] - The name of the graph (used in logs).
* @param {Number} [loggingLevel = 0] - The level of the logger used. By default, the logger level will be 0 (minimal logs, mostly errors).
* @param {boolean} [ignoreErrors = true] - If true, errors will be thrown at execution in case of failure.
* @param {boolean} [autoCreateNodes = false] - If true, nodes will be created when creating routes for them in case they don't exist.
* @param {Number} [constantNodesCost = 0] - Constant "toll" cost of the nodes, must be greater than zero.
* @param {Object} [costFormat] - Object to format of the cost/weight of a path.
*/
constructor({
name = null,
loggingLevel = 0,
ignoreErrors = true,
autoCreateNodes = false,
constantNodesCost = 0,
costFormat = null,
}) 

#### Parameters

Graph class includes as parameter an Object which includes these attributes:

• name : string, optional
Custom name of the Graph, used in logs.
Leave blank to use the datetime of its creation.

• loggingLevel : integer [0-3], optional
Logging level of the graph functions & algorithms. By default, it will not show any logs.

• ignoreErrors : boolean, optional
Basically, throws or catches any error ocurred during execution.

• autoCreateNodes : boolean, optional
Allows to create nodes based on routes creation.

• constantNodesCost : number, optional
Constant cost of passing through a node, as a "toll" cost.

• costFormat : object, optional
Object to format of the cost/weight of a path. Must have format() defined or include {suffix?: boolean, prefix?: boolean, format: string}

### Node

Nodes are objects that contains its adjacent nodes and their cost to get there.

graph: {
Node A: {Node B: 10, Node C: 15}
Node B: {Node C: 15}
}

Also, there is costsNodes as an Dictionary that contains the toll cost of a node:

costsNodes: {
Node A: 10,
Node B: 15,
...
}

To create nodes, simply use graph.createNodes(), which can receive a name: string or object and other args are processed the same way. Sample usage:

const {Graph} = require('dijkstra-floydwarshall-graph')

const graph = new Graph({
autoCreateNodes: true,
loggingLevel: 0,
constantNodesCost: 100,
ignoreErrors: false,
});
graph.addNode({ name: "F", cost: 500 });

#### Parameters

• name : string
Name of the node.

• cost : number, optional
Constant toll cost of the node. If null, the cost will be the constantNodesCost of the Graph.

• protectNodeCost: boolean, optional
Avoid changing the cost of a node when changing the constantNodesCost (See Edit constant node costs test).

### Routes

To create routes, simply use graph.createRoutes(), which receive as parameters the startingNode, endingNode, its weight and other optional arguments.

const {Graph} = require('dijkstra-floydwarshall-graph')

const graph = new Graph({
autoCreateNodes: true,
loggingLevel: 0,
constantNodesCost: 100,
ignoreErrors: false,
});
//Create route with cost (or weight) of 100
//Creates two routes (A-C, C-A) with cost (or weight) of 1000
.addRoute("B","A",10)

#### Parameters

• startNode : string
Name of the starting node.

• endNode : string
Name of the ending node.

• weight : number
Weight of the path.

• bidirectional: boolean, optional
If true, creates both (startNode-endNode) route and (endNode-startNode) with the same weight.

• changeCreated: boolean, optional
If true, it will try to change the existing cost of the route of (startNode-endNode). (Used as parameter in editRoutes())

### Install

npm i dijkstra-floydwarshall-graph

9

1.2.2