pgr_maxFlow¶

pgr_maxFlow — Calculates the maximum flow in a directed graph from the source(s) to the targets(s) using the Push Relabel algorithm.

Boost Graph Inside¶

Availability

Version 3.0.0
- Official function
Version 2.4.0
- New Proposed function

Support

Supported versions: current(3.1) 3.0
Unsupported versions: 2.6 2.5 2.4

Description¶

The main characteristics are:

The graph is directed.
Calculates the maximum flow from the source(s) to the target(s).
- When the maximum flow is 0 then there is no flow and 0 is returned.
- There is no flow when a source is the same as a target.
Any duplicated value in the source(s) or target(s) are ignored.
Uses the pgr_pushRelabel algorithm.

Running time: \(O( V ^ 3)\)

Signatures¶

Summary

pgr_maxFlow(Edges SQL, source,  target)
pgr_maxFlow(Edges SQL, sources,  target)
pgr_maxFlow(Edges SQL, source,  targets)
pgr_maxFlow(Edges SQL, sources,  targets)
RETURNS BIGINT

One to One¶

pgr_maxFlow(Edges SQL, source,  target)
RETURNS BIGINT

Example: From vertex \(6\) to vertex \(11\)

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
    , 6, 11
);
 pgr_maxflow
-------------
         230
(1 row)

One to Many¶

pgr_maxFlow(Edges SQL, source,  targets)
RETURNS BIGINT

Example: From vertex \(6\) to vertices \(\{11, 1, 13\}\)

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
    , 6, ARRAY[11, 1, 13]
);
 pgr_maxflow
-------------
         340
(1 row)

Many to One¶

pgr_maxFlow(Edges SQL, sources,  target)
RETURNS BIGINT

Example: From vertices \(\{6, 8, 12\}\) to vertex \(11\)

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
    , ARRAY[6, 8, 12], 11
);
 pgr_maxflow
-------------
         230
(1 row)

Many to Many¶

pgr_maxFlow(Edges SQL, sources,  targets)
RETURNS BIGINT

Example: From vertices \(\{6, 8, 12\}\) to vertices \(\{1, 3, 11\}\)

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            capacity,
            reverse_capacity
    FROM edge_table'
    , ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
 pgr_maxflow
-------------
         360
(1 row)

Parameters¶

Column	Type	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.

Inner query¶

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	`ANY-INTEGER`		Identifier of the edge.
source	`ANY-INTEGER`		Identifier of the first end point vertex of the edge.
target	`ANY-INTEGER`		Identifier of the second end point vertex of the edge.
capacity	`ANY-INTEGER`		Weight of the edge (source, target) When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_capacity	`ANY-INTEGER`	-1	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

Return Columns¶

Type	Description
`BIGINT`	Maximum flow possible from the source(s) to the target(s)