pgr_maxFlowMinCost_Cost - Experimental

pgr_maxFlowMinCost_Cost - Calculates the minmum cost maximum flow in a directed graph from the source(s) to the targets(s).

images/boost-inside.jpeg

Boost Graph Inside

Warning

Possible server crash

  • These functions might create a server crash

Warning

Experimental 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

Availability

  • Version 3.0.0

    • New experimental function

Support

  • Supported versions: current( 3.0 )

Description

The main characteristics are:

  • The graph is directed .

  • The cost value of all input edges must be nonnegative.

  • 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_maxFlowMinCost algorithm.

  • Running time: \(O(U * (E + V * logV))\) , where \(U\) is the value of the max flow. \(U\) is upper bound on number of iteration. In many real world cases number of iterations is much smaller than \(U\) .

Signatures

Summary 

pgr_maxFlowMinCost_Cost(Edges SQL, source, target)
pgr_maxFlowMinCost_Cost(Edges SQL, sources, target)
pgr_maxFlowMinCost_Cost(Edges SQL, source, targets)
pgr_maxFlowMinCost_Cost(Edges SQL, sources, targets)
RETURNS FLOAT

One to One 

pgr_maxFlowMinCost_Cost(Edges SQL, source, target)
RETURNS FLOAT
Example :

From vertex \(2\) to vertex \(3\) 

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    2, 3
);
 pgr_maxflowmincost_cost
-------------------------
                     400
(1 row)

One to Many 

pgr_maxFlowMinCost_Cost(Edges SQL, source, targets)
RETURNS FLOAT
Example :

From vertex \(13\) to vertices \(\{7, 1, 4\}\) 

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    13, ARRAY[7, 1, 4]
);
 pgr_maxflowmincost_cost
-------------------------
                     450
(1 row)

Many to One 

pgr_maxFlowMinCost_Cost(Edges SQL, sources, target)
RETURNS FLOAT
Example :

From vertices \(\{1, 7, 14\}\) to vertex \(12\) 

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    ARRAY[1, 7, 14], 12
);
 pgr_maxflowmincost_cost
-------------------------
                     650
(1 row)

Many to Many 

pgr_maxFlowMinCost_Cost(Edges SQL, sources, targets)
RETURNS FLOAT
Example :

From vertices \(\{7, 13\}\) to vertices \(\{3, 9\}\) 

SELECT * FROM pgr_MaxFlowMinCost_Cost(
    'SELECT id,
     source, target,
     capacity, reverse_capacity,
     cost, reverse_cost FROM edge_table',
    ARRAY[7, 13], ARRAY[3, 9]
);
 pgr_maxflowmincost_cost
-------------------------
                     600
(1 row)

Parameters

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.

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

Capacity 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

Capacity of the edge (target, source) ,

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

cost

ANY-NUMERICAL

Weight of the edge (source, target) if it exists.

reverse_cost

ANY-NUMERICAL

0

Weight of the edge (target, source) if it exists.

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL :

smallint, int, bigint, real, float

Result Columns

Type

Description

FLOAT

Minimum Cost Maximum Flow possible from the source(s) to the target(s)

See Also

Indices and tables