|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
#include <min_cost_flow.h>
Public Types | |
| enum | Status { NOT_SOLVED, OPTIMAL, FEASIBLE, INFEASIBLE, UNBALANCED, BAD_RESULT, BAD_COST_RANGE } |
| Different statuses for a given problem. More... | |
Public Member Functions | |
| MinCostFlow (const StarGraph *graph) | |
| const StarGraph * | graph () const |
| Returns the graph associated to the current object. | |
| Status | status () const |
| Returns the status of last call to Solve(). | |
| void | SetNodeSupply (NodeIndex node, FlowQuantity supply) |
| Sets the supply corresponding to node. | |
| void | SetArcUnitCost (ArcIndex arc, CostValue unit_cost) |
| Sets the unit cost for arc. | |
| void | SetArcCapacity (ArcIndex arc, FlowQuantity new_capacity) |
| Sets the capacity for arc. | |
| void | SetArcFlow (ArcIndex arc, FlowQuantity new_flow) |
| Sets the flow for arc. | |
| bool | Solve () |
| Runs true is a min-cost flow could be found. | |
| bool | CheckFeasibility (std::vector< NodeIndex > *const infeasible_supply_node, std::vector< NodeIndex > *const infeasible_demand_node) |
| Checks for feasibility, i.e. | |
| bool | MakeFeasible () |
| Makes the min-cost flow problem solvable by truncating supplies and demands to a level acceptable by the network. | |
| CostValue | GetOptimalCost () const |
| Returns the cost of the minimum-cost flow found by the algorithm. | |
| FlowQuantity | Flow (ArcIndex arc) const |
| Returns the flow on arc using the equations given in the comment on residual_arc_capacity_. | |
| FlowQuantity | Capacity (ArcIndex arc) const |
| Returns the capacity of arc using the equations given in the comment on residual_arc_capacity_. | |
| FlowQuantity | Cost (ArcIndex arc) const |
| Returns the unscaled cost for arc. | |
| FlowQuantity | Supply (NodeIndex node) const |
| Returns the supply at node. Demands are modelled as negative supplies. | |
| FlowQuantity | InitialSupply (NodeIndex node) const |
| Returns the initial supply at node, given as data. | |
| FlowQuantity | FeasibleSupply (NodeIndex node) const |
| Returns the largest supply (if > 0) or largest demand in absolute value (if < 0) admissible at node. | |
Definition at line 185 of file min_cost_flow.h.
| operations_research::MinCostFlow::MinCostFlow | ( | const StarGraph * | graph | ) | [explicit] |
Definition at line 45 of file min_cost_flow.cc.
| const StarGraph* operations_research::MinCostFlow::graph | ( | ) | const [inline] |
| Status operations_research::MinCostFlow::status | ( | ) | const [inline] |
Returns the status of last call to Solve().
NOT_SOLVED is returned Solve() has never been called or if the problem has been modified in such a way that the previous solution becomes invalid.
Definition at line 206 of file min_cost_flow.h.
| void operations_research::MinCostFlow::SetNodeSupply | ( | NodeIndex | node, | |
| FlowQuantity | supply | |||
| ) | [inline] |
Sets the supply corresponding to node.
A demand is modeled as a negative supply.
Definition at line 210 of file min_cost_flow.h.
| void operations_research::MinCostFlow::SetArcCapacity | ( | ArcIndex | arc, | |
| FlowQuantity | new_capacity | |||
| ) |
| void operations_research::MinCostFlow::SetArcFlow | ( | ArcIndex | arc, | |
| FlowQuantity | new_flow | |||
| ) | [inline] |
Sets the flow for arc.
Note that new_flow must be smaller than the capacity of arc.
Definition at line 232 of file min_cost_flow.h.
| bool operations_research::MinCostFlow::Solve | ( | ) |
| bool operations_research::MinCostFlow::CheckFeasibility | ( | std::vector< NodeIndex > *const | infeasible_supply_node, | |
| std::vector< NodeIndex > *const | infeasible_demand_node | |||
| ) |
Checks for feasibility, i.e.
that all the supplies and demands can be matched without exceeding bottlenecks in the network. If infeasible_supply_node (resp. infeasible_demand_node) are not NULL, they are populated with the indices of the nodes where the initial supplies (resp. demands) are too large. Feasible values for the supplies and demands are accessible through FeasibleSupply. Note that CheckFeasibility is called by Solve() when the flag min_cost_flow_check_feasibility is set to true (which is the default.)
Definition at line 243 of file min_cost_flow.cc.
| bool operations_research::MinCostFlow::MakeFeasible | ( | ) |
Makes the min-cost flow problem solvable by truncating supplies and demands to a level acceptable by the network.
There may be several ways to do it. In our case, the levels are computed from the result of the max-flow algorithm run in CheckFeasibility(). MakeFeasible returns false if CheckFeasibility() was not called before.
Definition at line 330 of file min_cost_flow.cc.
| CostValue operations_research::MinCostFlow::GetOptimalCost | ( | ) | const [inline] |
Returns the cost of the minimum-cost flow found by the algorithm.
Definition at line 264 of file min_cost_flow.h.
| FlowQuantity operations_research::MinCostFlow::Flow | ( | ArcIndex | arc | ) | const [inline] |
Returns the flow on arc using the equations given in the comment on residual_arc_capacity_.
Definition at line 268 of file min_cost_flow.h.
| FlowQuantity operations_research::MinCostFlow::Capacity | ( | ArcIndex | arc | ) | const [inline] |
Returns the capacity of arc using the equations given in the comment on residual_arc_capacity_.
Definition at line 279 of file min_cost_flow.h.
| FlowQuantity operations_research::MinCostFlow::Cost | ( | ArcIndex | arc | ) | const [inline] |
| FlowQuantity operations_research::MinCostFlow::Supply | ( | NodeIndex | node | ) | const [inline] |
Returns the supply at node. Demands are modelled as negative supplies.
Definition at line 297 of file min_cost_flow.h.
| FlowQuantity operations_research::MinCostFlow::InitialSupply | ( | NodeIndex | node | ) | const [inline] |
| FlowQuantity operations_research::MinCostFlow::FeasibleSupply | ( | NodeIndex | node | ) | const [inline] |
Returns the largest supply (if > 0) or largest demand in absolute value (if < 0) admissible at node.
If the problem is not feasible, some of these values will be smaller (in absolute value) than than the initial supplies and demand given as input.
Definition at line 311 of file min_cost_flow.h.