Network -> Cohesion -> Max Flow

Contents - Index

NETWORK > COHESION > MAX FLOW

PURPOSE Compute the maximum flow (= the minimum cut) between all pairs of nodes in a network.

DESCRIPTION In a valued or binary network the value of each edge (1 or 0 for binary networks) can represent a capacity. Let c(x) denote the capacity of each edge of a network N. A flow in N between two nodes s and t is a function f such that 0 £ f(x) £ c(x) for every edge x and for every node z ¹ s or t, Sf(yz) =Sf(zw). So that for each node, except s and t, the total amount of flow into the node equals the total flow leaving the node.

The total flow leaving s is the same as that going into t, this value is called the value of the flow. The maximum flow is simply the maximum value possible between two vertices.

This procedure computes the maximum flow between all pairs of vertices of a directed graph with integer weights.

PARAMETERS
Input dataset
Name of file containing network to be analyzed. Data type: Valued digraph - only with integer values.

Output Filename (Default = 'MaxFlow').
Name of data file containing maximum flows between all pairs of vertices.

LOG FILE An nxn matrix in which row i column j gives the value of the maximum flow from vertex i to vertex j (i¹j).

TIMING O(N^4).

COMMENTS The maximum flow in a network is equal to the minimum cut. A cut between two vertices s and t is a collection of edges which contains an edge from every s-t path. The value of a cut is the sum of the value of the edges. A minimum cut is the minimum value of all possible cuts between two vertices. For a binary network this value is called the local edge connectivity.

REFERENCES Ford L R and Fulkerson D R (1956). 'Maximum flow through a network'. Canadian Journal of Mathematics, 8, 399-404.

Gomory R E and Hu T C (1964). 'Synthesis of a communication network'. Journal of SIAM (Appl Math), 12, 348.