Max Flow

Description

Following details are taken from Boost Documentation

A flow network is a directed graph G=(V,E) with a source vertex s and a sink vertex t. Each edge has a positive real valued capacity function c and there is a flow function f defined over every vertex pair. The flow function must satisfy three contraints:

• f(u,v) <= c(u,v) for all (u,v) in V x V (Capacity constraint)
• f(u,v) = - f(v,u) for all (u,v) in V x V (Skew symmetry)
• Sum of flow going out of vertex must be equal to sum of flow coming in to vertex.

The flow of the network is the net flow entering the sink vertex t (which is equal to the net flow leaving the source vertex s).

The residual capacity of an edge is r(u,v) = c(u,v) - f(u,v). The edges with r(u,v) > 0 are residual edges Ef which induce the residual graph Gf = (V, Ef). An edge with r(u,v) = 0 is saturated.

The maximum flow problem is to determine the maximum possible value for |f| and the corresponding flow values for every vertex pair in the graph.

More details can be found on the wikipedia page.

Implementation details

At the core of the implementation, we will be using the Push Relabel Max Flow Algorithm of Boost Graph Library.

There are several special requirements on the input graph and property map parameters for this algorithm. First, the directed graph G=(V,E) that represents the network must be augmented to include the reverse edge (or residual edge) E' for every edge in E. That is, the input graph should be Gin = (V,{E U E'}). The ReverseEdgeMap argument rev must map each edge in the original graph to its reverse edge, that is (u,v) -> (v,u) for all (u,v) in E.

###We can have the following 2 Cases:

1. For directed edge, the forward capacity in any edge c(u,v) will be c, and the reverse capacity c(v,u) will be added as 0, since we do not allow flow in reverse direction at start of algorithm. The algorithm basically pushes flow through some edges and re-calculates residual capacities in each direction after each pass. So, if after pass 1, suppose flow f from u to v, then the residual capacities will be c-f for (u,v) and f for (v,u). Thus, the CapacityEdgeMap argument cap must map each edge in E to a positive number, and each edge in E' to 0.

2. For undirected edge, i.e flow is allowed in both directions from start, then capacities for both (u,v) and (v,u) should be c at start. Now suppose algorithm sends flow f from u to v, then the residual capacities will be c-f for (u,v) and c+f for (v,u). This means that in future we can only send flow c-f units from u to v, but we can send a flow of c+f units from v to u. Thus, the CapacityEdgeMap argument cap must map each edge in E to a positive number c, and each edge in E' also to c to represent undirected edge.

So, to handle instances when some edges in graph allow flow in both directions, while some edges are directed, the edge table should have a bool directed attribute. Sample edge table:

Edge
{
    int source;
    int target;
    double capacity;
    bool directed;
    //other attributes
}

SQL flow_result type: This will be the result that will be returned by the query. Note that the last tuple returned will contain only one attribute that is the value of the net flow from source to sink.

CREATE TYPE flow_result AS (src_vertex_id integer, dest_vertex_id integer, flow float8);

Function prototype for Max Flow with single source / sink:

CREATE OR REPLACE FUNCTION pgr_max_flow
(
         sql text,
         sourceList text,
         sinkList text,
         directed boolean
)
RETURNS SETOF flow_result
AS '$libdir/librouting'
LANGUAGE 'C' IMMUTABLE STRICT;

Example Query

Select * from pgr_max_flow
(
     "select source, target, capacity from pipes",
     "select 108 as source",  \\Source
     "select 516 as source",   \\Sink
      false
);