A push-relabel network flow solver in JavaScript
JavaScript
Permalink
Failed to load latest commit information.
test added some tests Mar 17, 2013
.gitignore adding files Mar 10, 2013
README.md Update README.md Mar 13, 2013
package.json increment version Mar 17, 2013
preflow.js added some tests Mar 17, 2013

README.md

push-relabel

Network flow is a fundamental tool in computer science and operations research, and can be used to solve many common tasks such as:

This library is an implementation of Goldberg and Tarjan's push-relabel algorithm for solving network flow problems in JavaScript. It use relabel-to-front ordering as well as the global and gap relabelling heuristics, as described by Cherkassy and Goldberg, giving it a run time on the order of |V|^3 in the worst case.

Currently in early development, patches welcome!

Usage

To install the library, use npm:

npm install push-relabel

And then you can call it as follows:

//Solve flow for following network:
//
//       1
//      ^ |
//   2 /  |1
//    /   V   1
//  s=0-->2--->3
//      9 |    |
//        |7   |7
//        V    V
//        4--->t=5
//            4
//
var num_vertices = 6
var source       = 0
var sink         = 5
var edges        = [[0,1],[0,2],[1,2],[2,3],[2,4],[3,5],[4,5]]
var capacities   = [   2,   9,    1,    1,    7,    7,    4  ]


//Load library
var pushRelabel = require("push-relabel")

//Compute maximum flow
var flow = pushRelabel.maxFlow(num_vertices, source, sink, edges, capacities)
for(var i=0; i<edges.length; ++i) {
  console.log("edge:", edges[i], flow[i] + "/" + capacities[i])
}

//Compute minimum cut
var cut = pushRelabel.minCut(num_vertices, source, sink, edges, capacities)
console.log(cut)

API

There are two functions exposed by the library:

pushRelabel.maxFlow(num_vertices, source, sink, edges, capacities[, flow, dual])

Computes a maximum flow in a network.

  • num_vertices is the number of vertices in the graph
  • source is the index of the source vertex
  • sink is the index of the sink vertex
  • edges is a list of edges in the graph
  • capacities is a list of per-edge capacities. Must have size >= edges.length
  • flow (optional) is an array which will get the resulting flow. If not specified, a new flow array is allocated. Must be of size at least edges.length
  • dual (optional) is the topological dual of the flow network. If not specified, a new dual is computed.

WARNING If you don't specify a dual, the library will permute the order of the edges/capacities array

Returns: The flow, which is stored in the object flow

pushRelabel.minCut(num_vertices, source, sink, edges, capacities[, cut, dual])

Computes a minimum cut in a flow network

  • num_vertices is the number of vertices in the graph
  • source is the index of the source vertex
  • sink is the index of the sink vertex
  • edges is a list of edges in the graph
  • capacities is a list of per-edge capacities. Must have size >= edges.length
  • cut (optional) is an array which will get the resulting cut. If not specified, a new uint8 array is allocated. Must be of size at least `num_vertices
  • dual (optional) is the topological dual of the flow network. If not specified, a new dual is computed.

WARNING If you don't specify a dual, the library will permute the order of the edges/capacities array

Returns: The cut

Credits

(c) 2013 Mikola Lysenko. BSD License