Introduction

1. Flow on an edge doesn't exceed the given edge capacity
2. Incoming flow is equal to Outgoing flow for every vertex excluding sink and source

Algorithm

* Input: network (G = (V, E), s, t, c)
* h[s] := |V |
* for each v ∈ V − {s} do h[v] := 0
* for each (s, v) ∈ E do f(s, v) := c(s, v)
* while f is not a feasible flow
    * let c'(u, v) = c(u, v) + f(u, v) − f(v, u) be the capacities of the residual network
    * if there is a vertex v ∈ V − {s, t} and a vertex w ∈ V such that ef (v) > 0, h(v) > h(w), and c'(v, w) > 0 then
        ∗ push min{c'(v, w), ef (v)} units of flow on the edge (v, w)
    * else, let v be a vertex such that ef (v) > 0, and set h[v] := h[v] + 1
 * output f

Example

var pushRelabel = require('graph-theory-push-relabel');

var graph = [  
    [ 0, 16,  13, 0,  0,  0 ],
    [ 0,  0, 10, 12,  0,  0 ],
    [ 0,  4,  0,  0, 14,  0 ],
    [ 0,  0,  9,  0,  0, 20 ],
    [ 0,  0,  0,  7,  0,  4 ],
    [ 0,  0,  0,  0,  0,  0 ]
];

console.log("The maximum possible flow is " +  
    pushRelabel.PushRelabel(graph, 0, 5));

Usage

require('graph-theory-push-relabel')( graph, source, sink )

Installation

npm install graph-theory-push-relabel

License