Skip to content

pgr_maxFlowMinCost_Cost.rst

Latest commit

 

History

History
240 lines (157 loc) · 6.64 KB

pgr_maxFlowMinCost_Cost.rst

File metadata and controls

240 lines (157 loc) · 6.64 KB
Raw
.. index::
   single: Flow Family ; pgr_maxFlowMinCost_Cost - Experimental
   single: Cost Category ; pgr_maxFlowMinCost_Cost - Experimental
   single: maxFlowMinCost_Cost - Experimental on v3.0

pgr_maxFlowMinCost_Cost - Experimental

pgr_maxFlowMinCost_Cost — Calculates the minimum total cost of the maximum flow on a graph

Availability

  • Version 3.2.0
    • New experimental signature:
      • pgr_maxFlowMinCost_Cost(Combinations)
  • Version 3.0.0
    • New experimental function.

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 source has the same value as target.
  • Any duplicated values in source or target are ignored.
  • Uses :doc:`pgr_maxFlowMinCost`.
  • Running time: O(U * (E + V * logV))
    • where U is the value of the max flow.
    • U is upper bound on number of iterations. In many real world cases number of iterations is much smaller than U.

|Boost| Boost Graph Inside

Signatures

Summary

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vid)
pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vids)
pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vid)
pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vids)
pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL)
RETURNS FLOAT
.. index::
    single: maxFlowMinCost_Cost - Experimental on v3.0 ; One to One - Experimental on v3.0

One to One

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


.. index::
    single: maxFlowMinCost_Cost - Experimental on v3.0 ; One to Many - Experimental on v3.0

One to Many

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vids)
RETURNS FLOAT
Example:From vertex 11 to vertices \{5, 10, 12\} 
.. literalinclude:: maxFlowMinCost_Cost.queries
   :start-after: -- q3
   :end-before: -- q4


.. index::
    single: maxFlowMinCost_Cost - Experimental on v3.0 ; Many to One - Experimental on v3.0

Many to One

pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vid)
RETURNS FLOAT
Example:From vertices \{11, 3, 17\} to vertex 12 
.. literalinclude:: maxFlowMinCost_Cost.queries
   :start-after: -- q2
   :end-before: -- q3


.. index::
    single: maxFlowMinCost_Cost - Experimental on v3.0 ; Many to Many - Experimental on v3.0

Many to Many

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


.. index::
    single: maxFlowMinCost_Cost - Experimental on v3.0 ; Combinations - Experimental on v3.2

Combinations

pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL)
RETURNS FLOAT
Example:Using a combinations table, equivalent to calculating result from vertices \{5, 6\} to vertices \{10, 15, 14\}.

The combinations table:

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

The query:

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

Parameters

Inner Queries

Edges SQL

Combinations SQL

Return columns

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

Additional Examples

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

See Also

Indices and tables