bellman-ford

Bellman Ford algorithm for node.js

bellman-ford

bellman-ford allows you to run the bellman ford algorithm in node.js.

It is written in C++ and ported to node.js. It uses a directed graph as it's underlying data structure.

npm install bellman-ford

var graph = new bellman-ford();
graph.add_node("a");
graph.add_node("b");
graph.add_node("c");
graph.add_node("d");
graph.add_node("e");
graph.add_edge("a", "b", -0.1);
graph.add_edge("b", "a", 0.2);
graph.add_edge("a", "c", 0.9);
graph.add_edge("c", "e", -0.1);
graph.add_edge("e", "c", 0.2);
graph.add_edge("e", "d", 0.2);
graph.add_edge("d", "e", 0.1);
graph.add_edge("d", "a", 0.4);
graph.add_edge("b", "d", 0.3);
console.log(graph.bellmanford("c"));

which will output

[ [ 'a', '0.5' ],
  [ 'b', '0.4' ],
  [ 'd', '0.1' ],
  [ 'e', '-0.1' ],
  [ 'c', '0' ] ]

where each subarray contains a value in the graph say a and the distance to the source node c whcich in this case is 0.5

This function adds a node to directed graph. It takes one parameter add_node(node_name) If a node with node_name already exists then nothing wil happen

This function adds edges to directed graph. It takes three parameters 'add_edge(node_from, node_to, edge_weight)' If node_from or node_to has not yet beed added to the graph then the function call will fail

This function updates edge weights between nodes It takes three parameters 'update_edge(node_from, node_to, edge_weight)'

This function prints out the current graph

graph.print();

for the given example will output

a:
    weight: -0.1 to: b
    weight: 0.9 to: c
b:
    weight: 0.2 to: a
    weight: 0.3 to: d
d:
    weight: 0.1 to: e
    weight: 0.4 to: a
e:
    weight: 0.2 to: c
    weight: 0.2 to: d
c:
    weight: -0.1 to: e

This function removes all nodes with less then two edges as well as removing all associated edges.

This is the main function which will run the bellman ford algorithm on the current graph. It will return a 2d array of the form [node_name, distance_from_source]

If the graph contains negative weight cycles then it will return an empty array

To compile the code from source you must have python gcc and node-gyp installed on your machine.

Then run

node-gyp configure

and

node-gyp build