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 50 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 72 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 178 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 244 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 223 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 189 of file MinCostFlowModule.h.
The documentation for this class was generated from the following file:
Inheritance diagram for ogdf::MinCostFlowModule< TCost >:
