Interface for min-cost flow algorithms.
More...
#include <ogdf/graphalg/MinCostFlowModule.h>
|
| MinCostFlowModule () |
| Initializes a min-cost flow module. More...
|
|
virtual | ~MinCostFlowModule () |
|
virtual bool | call (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow) |
| Computes a min-cost flow in the directed graph G . More...
|
|
virtual bool | call (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow, NodeArray< TCost > &dual)=0 |
| Computes a min-cost flow in the directed graph G . More...
|
|
|
static bool | checkComputedFlow (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, const EdgeArray< int > &flow) |
| checks if a computed flow is a feasible solution to the given problem instance. More...
|
|
static bool | checkComputedFlow (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, const EdgeArray< int > &flow, TCost &value) |
| checks if a computed flow is a feasible solution to the given problem instance. More...
|
|
static bool | checkProblem (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const NodeArray< int > &supply) |
| Checks if a given min-cost flow problem instance satisfies the preconditions. More...
|
|
static void | generateProblem (Graph &G, int n, int m, EdgeArray< int > &lowerBound, EdgeArray< int > &upperBound, EdgeArray< TCost > &cost, NodeArray< int > &supply) |
| Generates an instance of a min-cost flow problem with n nodes and m + n edges. More...
|
|
template<typename TCost>
class ogdf::MinCostFlowModule< TCost >
Interface for min-cost flow algorithms.
Definition at line 48 of file MinCostFlowModule.h.
◆ MinCostFlowModule()
template<typename TCost >
◆ ~MinCostFlowModule()
template<typename TCost >
◆ call() [1/2]
template<typename TCost >
Computes a min-cost flow in the directed graph G
.
- Precondition
G
must be connected, lowerBound
[e] <= upperBound
[e] for all edges e, and the sum over all supplies must be zero.
- Parameters
-
G | is the directed input graph. |
lowerBound | gives the lower bound for the flow on each edge. |
upperBound | gives the upper bound for the flow on each edge. |
cost | gives the costs for each edge. |
supply | gives the supply (or demand if negative) of each node. |
flow | is assigned the computed flow on each edge. |
- Returns
- true iff a feasible min-cost flow exists.
Definition at line 70 of file MinCostFlowModule.h.
◆ call() [2/2]
template<typename TCost >
Computes a min-cost flow in the directed graph G
.
- Precondition
G
must be connected, lowerBound
[e] <= upperBound
[e] for all edges e, and the sum over all supplies must be zero.
- Parameters
-
G | is the directed input graph. |
lowerBound | gives the lower bound for the flow on each edge. |
upperBound | gives the upper bound for the flow on each edge. |
cost | gives the costs for each edge. |
supply | gives the supply (or demand if negative) of each node. |
flow | is assigned the computed flow on each edge. |
dual | is assigned the computed dual variables. |
- Returns
- true iff a feasible min-cost flow exists.
Implemented in ogdf::MinCostFlowReinelt< TCost >.
◆ checkComputedFlow() [1/2]
template<typename TCost >
checks if a computed flow is a feasible solution to the given problem instance.
Checks in particular if:
lowerBound
[e] <= flow
[e] <= upperBound
[e]
- sum
flow
[e], e is outgoing edge of v minus sum flow
[e], e is incoming edge of v equals supply
[v] for each node v
- Parameters
-
G | is the input graph. |
lowerBound | gives the lower bound for the flow on each edge. |
upperBound | gives the upper bound for the flow on each edge. |
cost | gives the costs for each edge. |
supply | gives the supply (or demand if negative) of each node. |
flow | is the flow on each edge. |
- Returns
- true iff the solution is feasible.
Definition at line 176 of file MinCostFlowModule.h.
◆ checkComputedFlow() [2/2]
template<typename TCost >
checks if a computed flow is a feasible solution to the given problem instance.
Checks in particular if:
lowerBound
[e] <= flow
[e] <= upperBound
[e]
- sum
flow
[e], e is outgoing edge of v minus sum flow
[e], e is incoming edge of v equals supply
[v] for each node v
- Parameters
-
G | is the input graph. |
lowerBound | gives the lower bound for the flow on each edge. |
upperBound | gives the upper bound for the flow on each edge. |
cost | gives the costs for each edge. |
supply | gives the supply (or demand if negative) of each node. |
flow | is the flow on each edge. |
value | is assigned the value of the flow. |
- Returns
- true iff the solution is feasible.
Definition at line 242 of file MinCostFlowModule.h.
◆ checkProblem()
template<typename TCost >
Checks if a given min-cost flow problem instance satisfies the preconditions.
The following preconditions are checked:
lowerBound
[e] <= upperBound
[e] for all edges e
- sum over all
supply
[v] = 0
- Parameters
-
G | is the input graph. |
lowerBound | gives the lower bound for the flow on each edge. |
upperBound | gives the upper bound for the flow on each edge. |
supply | gives the supply (or demand if negative) of each node. |
- Returns
- true iff the problem satisfies the preconditions.
Definition at line 221 of file MinCostFlowModule.h.
◆ generateProblem()
template<typename TCost >
Generates an instance of a min-cost flow problem with n
nodes and m
+ n
edges.
Definition at line 187 of file MinCostFlowModule.h.
The documentation for this class was generated from the following file: