Ford-Fulkerson Algorithm for Maximum Flow Problem Written in JS
Branch: master
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
example Partial progress on README and repo organization Feb 18, 2016
images Updated Readme Feb 19, 2016
test Updated tests Feb 19, 2016
.npmignore Added npm Installation info Feb 20, 2016
.travis.yml added travis.ci Feb 14, 2016
README.md Added npm Installation info Feb 20, 2016
index.js Updated Readme Feb 19, 2016
package.json Added npm Installation info Feb 20, 2016

README.md

Graph-Theory-Ford-Fulkerson Build Status Dependency Status

Ford-Fulkerson Algorithm for Maximum Flow Problem

Introduction

When a Graph Represent a Flow Network where every edge has a capacity. Also given that two vertices, source 's' and sink 't' in the graph, we can find the maximum possible flow from s to t with having following constraints:

  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

  1. Start with f(e) = 0 for all edge e ∈ E.
  2. Find an augmenting path P in the residual graph Gf .
  3. Augment flow along path P.
  4. Repeat until you get stuck.

Example

Consider the following graph

Maximum possible flow in the given graph is 23

var fordFulkerson = require('graph-theory-ford-fulkerson');

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 " +
	fordFulkerson(graph, 0, 5));

Usage

require('graph-theory-ford-fulkerson')( graph, source, sink )

Compute the maximum flow in a flow network between source node source and sink node sink.

Arguments:

  • graph: The Graph which representing the flow network
  • source: source vertex
  • sink: sink vertex

Returns: Returns a number representing the maximum flow.

Installation

npm install graph-theory-ford-fulkerson

License

© 2016 Prabod Rathnayaka. MIT License.