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.addNode("A")
.addNode("B")
.addNode("C")
.addNode("D")

graph.addRoute("A","B", 2)
graph.addRoute("A","C", 1)
graph.addRoute("B","C", 2)
graph.addRoute("C","D", 1)

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
.addRoute("A", "B", 2)
.addRoute("A", "C", 1)
.addRoute("B", "C", 2)
.addRoute("C", "D", 1)
.addRoute("B", "D", 200);

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("A");
graph.addNode("B", "C");
graph.addNode("D")
.addNode("E");
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,
});
graph.addNode("A");
graph.addNode("B", "C");
//Create route with cost (or weight) of 100
graph.addRoute("A","B",100);
//Creates two routes (A-C, C-A) with cost (or weight) of 1000
graph.addRoute("A","C",1000, true)
.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

7

1.2.2

MIT

46.6 kB

7