Wondering what’s next for npm?Check out our public roadmap! »

    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

    DownloadsWeekly Downloads

    5

    Version

    1.2.2

    License

    MIT

    Unpacked Size

    46.6 kB

    Total Files

    7

    Last publish

    Collaborators

    • avatar