pgr_maxFlow Proposed¶

Name¶

pgr_maxFlow — Calculates the maximum flow in a directed graph given source(s) and sink(s).

Warning

These are proposed functions

They are not officially of the current release.
They likely will not be officially be part of the next release:
- The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
- Name might change.
- Signature might change.
- Functionality might change.
- pgTap tests might be missing.
- Might need c/c++ coding.
- May lack documentation.
- Documentation if any might need to be rewritten.
- Documentation examples might need to be automatically generated.
- Might need a lot of feedback from the comunity.
- Might depend on a proposed function of pgRouting
- Might depend on a deprecated function of pgRouting

Boost Graph Inside

Synopsis¶

Calculates the maximum flow in a directed graph from a source node to a sink node.

Characteristics:¶

The main characterics are:

Calculates the flow/residual capacity for each edge. In the output, edges with zero flow are omitted.
The maximum flow through the graph can be calculated by aggregation on source/sink.
Edges must be weighted with non-negative capacities.
Returns 0 if source and sink are the same.
Allows multiple sources and sinks.
Running time: \(O( V ^ 3)\)

Signature Summary¶

pgr_maxFlow(edges_sql, source_vertex,  sink_vertex)
pgr_maxFlow(edges_sql, source_vertices,  sink_vertex)
pgr_maxFlow(edges_sql, source_vertex,  sink_vertices)
pgr_maxFlow(edges_sql, source_vertices,  sink_vertices)
RETURNS BIGINT

Signatures¶

One to One¶

Calculates the maximum flow from one source vertex to one sink vertex in a directed graph.

pgr_maxFlow(edges_sql, source_vertex,  sink_vertex)
RETURNS BIGINT

Example:

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            c1.capacity as capacity,
            c2.capacity as reverse_capacity
    FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
    WHERE edge_table.reverse_category_id = c2.category_id
    ORDER BY id'
    , 6, 11
);
 pgr_maxflow 
-------------
         280
(1 row)

One to Many¶

Ccalculates the maximum flow from one source vertex to many sink vertices in a directed graph.

pgr_maxFlow(edges_sql, source_vertex,  sink_vertices)
RETURNS BIGINT

Example:

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            c1.capacity as capacity,
            c2.capacity as reverse_capacity
    FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
    WHERE edge_table.reverse_category_id = c2.category_id
    ORDER BY id'
    , 6, ARRAY[11, 1, 13]
);
 pgr_maxflow 
-------------
         410
(1 row)

Many to One¶

Calculates the maximum flow from many source vertices to one sink vertex in a directed graph.

pgr_maxFlow(edges_sql, source_vertices,  sink_vertex)
RETURNS BIGINT

Example:

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            c1.capacity as capacity,
            c2.capacity as reverse_capacity
    FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
    WHERE edge_table.reverse_category_id = c2.category_id
    ORDER BY id'
    , ARRAY[6, 8, 12], 11
);
 pgr_maxflow 
-------------
         280
(1 row)

Many to Many¶

Calculates the maximum flow from many sources to many sinks in a directed graph.

pgr_maxFlow(edges_sql, source_vertices,  sink_vertices)
RETURNS BIGINT

Example:

SELECT * FROM pgr_maxFlow(
    'SELECT id,
            source,
            target,
            c1.capacity as capacity,
            c2.capacity as reverse_capacity
    FROM edge_table JOIN categories AS c1 USING(category_id), categories AS c2
    WHERE edge_table.reverse_category_id = c2.category_id
    ORDER BY id'
    , ARRAY[6, 8, 12], ARRAY[1, 3, 11]
);
 pgr_maxflow 
-------------
         460
(1 row)

Description of the Signatures¶

Description of the SQL query¶

edges_sql:	an SQL query, which should return a set of rows with the following columns:

Column	Type	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`	Capacity of the edge (source, target). Must be positive.
reverse_capacity	`ANY-INTEGER`	(optional) Weight of the edge (target, source). Must be positive or null.

Where:

ANY-INTEGER:	SMALLINT, INTEGER, BIGINT

Description of the parameters of the signatures¶

Column	Type	Description
edges_sql	`TEXT`	SQL query as described above.
source_vertex	`BIGINT`	Identifier of the source vertex(or vertices).
sink_vertex	`BIGINT`	Identifier of the sink vertex(or vertices).