Need private packages and team management tools?Check out npm Teams »

@vila91/graph

2.0.1 • Public • Published

Directed and Undirected graph implementation based on the following node structure. Nodes can be added using at construction or by using the .set(x, y, cost) method with cost defaulting to 1.

 
    let nodes = {x: {y: 2}, y: {z: 3}},
        graph = Directed(nodes).set(z, x)
    console.log(graph)
    // Directed {x: {y: 2}, y: {z: 3}, z: {x: 1}}
 

The .routes(x, y, limit) method returns the shortest routes from x to y, same-cost routes are sorted by number of nodes ascending, limit defaults to Infinity, for performance purposes it is recommended to set it to exactly the number needed.

 
    graph.set("B", "C").set("C", "D").set("B", "D").set("A", "D", 3)
    console.log(graph.routes("A", "D"))
    /* [
            {cost: 2, nodes: ["A", "B", "D"]}, 
            {cost: 3, nodes: ["A", "D"]}, 
            {cost: 3, nodes: ["A", "B", "C", "D"]}
        ] */
        
    console.log(graph.routes("A", "D", 1))
    // [{cost: 2, nodes: ["A", "B", "D"]}]
    
 

The .route(x, ...y) method returns the cheapest route going from x through all ...y nodes. It is based on calls to .routes with limit = 1.

    
    let route = graph.route("A", "B", "D")
    console.log(route)
    // {cost: 2, nodes: ["A", "B", "D"]}
    
    

Install

npm i @vila91/graph

DownloadsWeekly Downloads

2

Version

2.0.1

License

Apache 2.0

Unpacked Size

16.4 kB

Total Files

5

Last publish

Collaborators

  • avatar