Experimental
Warning
Possible server crash
Warning
Experimental functions
Previous versions of this page
The main characteristics are:
pgr_maxFlow is the maximum Flow and that maximum is guaranteed to be the same on the functions pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov, but the actual flow through each edge may vary.
Column  Type  Default  Description 

Edges SQL  TEXT 
The edges SQL query as described in Inner Query.  
source  BIGINT 
Identifier of the starting vertex of the flow.  
sources  ARRAY[BIGINT] 
Array of identifiers of the starting vertices of the flow.  
target  BIGINT 
Identifier of the ending vertex of the flow.  
targets  ARRAY[BIGINT] 
Array of identifiers of the ending vertices of the flow. 
For pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov :
Edges SQL:  an SQL query of a directed graph of capacities, which should return a set of rows with the following columns: 

Column  Type  Default  Description 

id  ANYINTEGER 
Identifier of the edge.  
source  ANYINTEGER 
Identifier of the first end point vertex of the edge.  
target  ANYINTEGER 
Identifier of the second end point vertex of the edge.  
capacity  ANYINTEGER 
Weight of the edge (source, target)


reverse_capacity  ANYINTEGER 
1  Weight of the edge (target, source),

Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 

For pgr_maxFlowMinCost  Experimental and pgr_maxFlowMinCost_Cost  Experimental:
Edges SQL:  an SQL query of a directed graph of capacities, which should return a set of rows with the following columns: 

Column  Type  Default  Description 

id  ANYINTEGER 
Identifier of the edge.  
source  ANYINTEGER 
Identifier of the first end point vertex of the edge.  
target  ANYINTEGER 
Identifier of the second end point vertex of the edge.  
capacity  ANYINTEGER 
Capacity of the edge (source, target)


reverse_capacity  ANYINTEGER 
1  Capacity of the edge (target, source),

cost  ANYNUMERICAL 
Weight of the edge (source, target) if it exists.  
reverse_cost  ANYNUMERICAL 
0  Weight of the edge (target, source) if it exists. 
Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 

ANYNUMERICAL:  smallint, int, bigint, real, float 
For pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov :
Column  Type  Description 

seq  INT 
Sequential value starting from 1. 
edge  BIGINT 
Identifier of the edge in the original query(edges_sql). 
start_vid  BIGINT 
Identifier of the first end point vertex of the edge. 
end_vid  BIGINT 
Identifier of the second end point vertex of the edge. 
flow  BIGINT 
Flow through the edge in the direction (start_vid , end_vid ). 
residual_capacity  BIGINT 
Residual capacity of the edge in the direction (start_vid , end_vid ). 
For pgr_maxFlowMinCost  Experimental
Column  Type  Description 

seq  INT 
Sequential value starting from 1. 
edge  BIGINT 
Identifier of the edge in the original query(edges_sql). 
source  BIGINT 
Identifier of the first end point vertex of the edge. 
target  BIGINT 
Identifier of the second end point vertex of the edge. 
flow  BIGINT 
Flow through the edge in the direction (source, target). 
residual_capacity  BIGINT 
Residual capacity of the edge in the direction (source, target). 
cost  FLOAT 
The cost of sending this flow through the edge in the direction (source, target). 
agg_cost  FLOAT 
The aggregate cost. 
A flow network is a directed graph where each edge has a capacity and a flow. The flow through an edge must not exceed the capacity of the edge. Additionally, the incoming and outgoing flow of a node must be equal except for source which only has outgoing flow, and the destination(sink) which only has incoming flow.
Maximum flow algorithms calculate the maximum flow through the graph and the flow of each edge.
The maximum flow through the graph is guaranteed to be the same with all implementations, but the actual flow through each edge may vary. Given the following query:
pgr_maxFlow \((edges\_sql, source\_vertex, sink\_vertex)\)
where \(edges\_sql = \{(id_i, source_i, target_i, capacity_i, reverse\_capacity_i)\}\)
Graph definition
The weighted directed graph, \(G(V,E)\), is defined as:
Maximum flow problem
Given:
Then:
Where:
\(\boldsymbol{\Phi}\) is a subset of the original edges with their residual capacity and flow. The maximum flow through the graph can be obtained by aggregating on the source or sink and summing the flow from/to it. In particular: