Graph | The directed graph type the algorithm runs on. | |
LowerMap | The type of the lower bound map. | |
CapacityMap | The type of the capacity (upper bound) map. | |
CostMap | The type of the cost (length) map. | |
SupplyMap | The type of the supply map. |
CostMap::Value
must be signed type.#include <lemon/network_simplex.h>
Classes | |
class | AlteringListPivotRule |
Implementation of the "Altering Candidate List" pivot rule for the network simplex algorithm. More... | |
class | BestEligiblePivotRule |
Implementation of the "Best Eligible" pivot rule for the network simplex algorithm. More... | |
class | BlockSearchPivotRule |
Implementation of the "Block Search" pivot rule for the network simplex algorithm. More... | |
class | CandidateListPivotRule |
Implementation of the "Candidate List" pivot rule for the network simplex algorithm. More... | |
class | FirstEligiblePivotRule |
Implementation of the "First Eligible" pivot rule for the network simplex algorithm. More... | |
Public Types | |
enum | PivotRuleEnum |
Enum type to select the pivot rule used by run(). | |
typedef Graph::template EdgeMap< Capacity > | FlowMap |
The type of the flow map. | |
typedef Graph::template NodeMap< Cost > | PotentialMap |
The type of the potential map. | |
Public Member Functions | |
NetworkSimplex (const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, const CostMap &cost, const SupplyMap &supply) | |
General constructor (with lower bounds). | |
NetworkSimplex (const Graph &graph, const CapacityMap &capacity, const CostMap &cost, const SupplyMap &supply) | |
General constructor (without lower bounds). | |
NetworkSimplex (const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, const CostMap &cost, Node s, Node t, Capacity flow_value) | |
Simple constructor (with lower bounds). | |
NetworkSimplex (const Graph &graph, const CapacityMap &capacity, const CostMap &cost, Node s, Node t, Capacity flow_value) | |
Simple constructor (without lower bounds). | |
~NetworkSimplex () | |
Destructor. | |
NetworkSimplex & | flowMap (FlowMap &map) |
Set the flow map. | |
NetworkSimplex & | potentialMap (PotentialMap &map) |
Set the potential map. | |
Execution control | |
bool | run (PivotRuleEnum pivot_rule=BLOCK_SEARCH_PIVOT) |
Runs the algorithm. | |
Query Functions | |
The results of the algorithm can be obtained using these functions. run() must be called before using them. | |
const FlowMap & | flowMap () const |
Return a const reference to the edge map storing the found flow. | |
const PotentialMap & | potentialMap () const |
Return a const reference to the node map storing the found potentials (the dual solution). | |
Capacity | flow (const typename Graph::Edge &edge) const |
Return the flow on the given edge. | |
Cost | potential (const typename Graph::Node &node) const |
Return the potential of the given node. | |
Cost | totalCost () const |
Return the total cost of the found flow. |
NetworkSimplex | ( | const Graph & | graph, | |
const LowerMap & | lower, | |||
const CapacityMap & | capacity, | |||
const CostMap & | cost, | |||
const SupplyMap & | supply | |||
) | [inline] |
General constructor (with lower bounds).
graph | The directed graph the algorithm runs on. | |
lower | The lower bounds of the edges. | |
capacity | The capacities (upper bounds) of the edges. | |
cost | The cost (length) values of the edges. | |
supply | The supply values of the nodes (signed). |
NetworkSimplex | ( | const Graph & | graph, | |
const CapacityMap & | capacity, | |||
const CostMap & | cost, | |||
const SupplyMap & | supply | |||
) | [inline] |
General constructor (without lower bounds).
graph | The directed graph the algorithm runs on. | |
capacity | The capacities (upper bounds) of the edges. | |
cost | The cost (length) values of the edges. | |
supply | The supply values of the nodes (signed). |
NetworkSimplex | ( | const Graph & | graph, | |
const LowerMap & | lower, | |||
const CapacityMap & | capacity, | |||
const CostMap & | cost, | |||
Node | s, | |||
Node | t, | |||
Capacity | flow_value | |||
) | [inline] |
Simple constructor (with lower bounds).
graph | The directed graph the algorithm runs on. | |
lower | The lower bounds of the edges. | |
capacity | The capacities (upper bounds) of the edges. | |
cost | The cost (length) values of the edges. | |
s | The source node. | |
t | The target node. | |
flow_value | The required amount of flow from node s to node t (i.e. the supply of s and the demand of t ). |
NetworkSimplex | ( | const Graph & | graph, | |
const CapacityMap & | capacity, | |||
const CostMap & | cost, | |||
Node | s, | |||
Node | t, | |||
Capacity | flow_value | |||
) | [inline] |
Simple constructor (without lower bounds).
graph | The directed graph the algorithm runs on. | |
capacity | The capacities (upper bounds) of the edges. | |
cost | The cost (length) values of the edges. | |
s | The source node. | |
t | The target node. | |
flow_value | The required amount of flow from node s to node t (i.e. the supply of s and the demand of t ). |
NetworkSimplex& flowMap | ( | FlowMap & | map | ) | [inline] |
Set the flow map.
(*this) NetworkSimplex& potentialMap | ( | PotentialMap & | map | ) | [inline] |
Set the potential map.
(*this) bool run | ( | PivotRuleEnum | pivot_rule = BLOCK_SEARCH_PIVOT |
) | [inline] |
Runs the algorithm.
pivot_rule | The pivot rule that is used during the algorithm. |
According to our comprehensive benchmark tests the "Block Search" pivot rule proved to be the fastest and the most robust on various test inputs. Thus it is the default option.
true
if a feasible flow can be found. const FlowMap& flowMap | ( | ) | const [inline] |
Return a const reference to the edge map storing the found flow.
const PotentialMap& potentialMap | ( | ) | const [inline] |
Return a const reference to the node map storing the found potentials (the dual solution).
Capacity flow | ( | const typename Graph::Edge & | edge | ) | const [inline] |
Cost potential | ( | const typename Graph::Node & | node | ) | const [inline] |
Return the potential of the given node.
Cost totalCost | ( | ) | const [inline] |
Return the total cost of the found flow. The complexity of the function is .