Skip to content

pgr_maxFlow.rst

Latest commit

 

History

History
238 lines (153 loc) · 5.94 KB

pgr_maxFlow.rst

File metadata and controls

238 lines (153 loc) · 5.94 KB
.. index::
   single: Flow Family ; pgr_maxFlow
   single: maxFlow

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.

Availability

Version 4.0.0

  • Combinations signature promoted to official.

Version 3.2.0

  • New proposed signature:
    • pgr_maxFlow(Combinations)

Version 3.0.0

  • Function promoted to official.

Version 2.4.0

  • New proposed function.

Description

The main characteristics are:

  • The graph is directed.
  • Calculates the maximum flow from the sources to the targets.
    • When the maximum flow is 0 then there is no flow and 0 is returned.
    • There is no flow when source has the same value as target.
  • Any duplicated values in source or target are ignored.
  • Uses the :doc:`pgr_pushRelabel <pgr_pushRelabel>` algorithm.
  • Running time: O( V ^ 3)

|Boost| Boost Graph Inside

Signatures

Summary

pgr_maxFlow(Edges SQL, start vid, end vid)
pgr_maxFlow(Edges SQL, start vid, end vids)
pgr_maxFlow(Edges SQL, start vids, end vid)
pgr_maxFlow(Edges SQL, start vids, end vids)
RETURNS BIGINT
.. index::
    single: maxFlow ; One to One

One to One

pgr_maxFlow(Edges SQL, start vid, end vid)
RETURNS BIGINT
Example:From vertex 11 to vertex 12 
.. literalinclude:: maxFlow.queries
   :start-after: -- q1
   :end-before: -- q2


.. index::
    single: maxFlow ; One to Many

One to Many

pgr_maxFlow(Edges SQL, start vid, end vids)
RETURNS BIGINT
Example:From vertex 11 to vertices \{5, 10, 12\} 
.. literalinclude:: maxFlow.queries
   :start-after: -- q2
   :end-before: -- q3


.. index::
    single: maxFlow ; Many to One

Many to One

pgr_maxFlow(Edges SQL, start vids, end vid)
RETURNS BIGINT
Example:From vertices \{11, 3, 17\} to vertex 12 
.. literalinclude:: maxFlow.queries
   :start-after: -- q3
   :end-before: -- q4


.. index::
    single: maxFlow ; Many to Many

Many to Many

pgr_maxFlow(Edges SQL, start vids, end vids)
RETURNS BIGINT
Example:From vertices \{11, 3, 17\} to vertices \{5, 10, 12\} 
.. literalinclude:: maxFlow.queries
   :start-after: -- q4
   :end-before: -- q5


.. index::
    single: maxFlow ; Combinations

Combinations

RETURNS BIGINT
Example:Using a combinations table, equivalent to calculating result from vertices \{5, 6\} to vertices \{10, 15, 14\}.

The combinations table:

.. literalinclude:: maxFlow.queries
   :start-after: -- q5
   :end-before: -- q51

The query:

.. literalinclude:: maxFlow.queries
   :start-after: -- q51
   :end-before: -- q6

Parameters

Inner Queries

Edges SQL

Combinations SQL

Result columns

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

Additional Examples

Example:Manually assigned vertex combinations. 
.. literalinclude:: maxFlow.queries
   :start-after: -- q6
   :end-before: -- q7

See Also

Indices and tables