|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
#include <max_flow.h>
Public Types | |
| enum | Status { NOT_SOLVED, OPTIMAL, FEASIBLE, INFEASIBLE, BAD_INPUT, BAD_RESULT } |
| Different statuses for a given problem. More... | |
Public Member Functions | |
| MaxFlow (const StarGraph *graph, NodeIndex source, NodeIndex target) | |
| virtual | ~MaxFlow () |
| const StarGraph * | graph () const |
| Returns the graph associated to the current object. | |
| Status | status () const |
| Returns the status of last call to Solve(). | |
| NodeIndex | GetSourceNodeIndex () const |
| Returns the index of the node corresponding to the source of the network. | |
| NodeIndex | GetSinkNodeIndex () const |
| Returns the index of the node corresponding to the sink of the network. | |
| void | SetArcCapacity (ArcIndex arc, FlowQuantity new_capacity) |
| Sets the capacity for arc to new_capacity. | |
| void | SetArcFlow (ArcIndex arc, FlowQuantity new_flow) |
| Sets the flow for arc. | |
| bool | Solve () |
| Returns true if a maximum flow was solved. | |
| FlowQuantity | GetOptimalFlow () const |
| Returns the total 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_. | |
Protected Member Functions | |
| bool | IsAdmissible (ArcIndex arc) const |
| Returns true if arc is admissible. | |
| bool | IsActive (NodeIndex node) const |
| Returns true if node is active, i.e. | |
| ArcIndex | GetFirstIncidentArc (NodeIndex node) const |
| Returns the first incident arc of node. | |
| void | PushFlowUnsafe (ArcIndex arc, FlowQuantity flow) |
| Reduces the residual capacity on arc by flow. | |
| void | SetCapacityResetFlow (ArcIndex arc, FlowQuantity capacity) |
| Sets the capacity of arc to 'capacity' and clears the flow on arc. | |
| void | SetCapacitySaturate (ArcIndex arc, FlowQuantity capacity) |
| Sets the capacity of arc to 'capacity' and saturates the flow on arc. | |
| bool | CheckInputConsistency () const |
| Checks the consistency of the input, i.e. | |
| bool | CheckResult () const |
| Checks whether the result is valid, i.e. | |
| bool | CheckRelabelPrecondition (NodeIndex node) const |
| Returns true if a precondition for Relabel is met, i.e. | |
| string | DebugString (const string &context, ArcIndex arc) const |
| Returns context concatenated with information about arc in a human-friendly way. | |
| virtual void | InitializeActiveNodeContainer () |
| Initializes the container active_nodes_. | |
| virtual NodeIndex | GetAndRemoveFirstActiveNode () |
| Get the first element from the active node container. | |
| virtual void | PushActiveNode (const NodeIndex &node) |
| Push element to the active node container. | |
| virtual bool | IsEmptyActiveNodeContainer () |
| Check the emptiness of the container. | |
| void | Refine () |
| Performs optimization step. | |
| virtual void | Discharge (NodeIndex node) |
| Discharges an active node node by saturating its admissible adjacent arcs, if any, and by relabelling it when it becomes inactive. | |
| void | ResetFirstAdmissibleArcs () |
| Resets the first_admissible_arc_ array to the first incident arc of each node. | |
| void | InitializePreflow () |
| Initializes the preflow to a state that enables to run Optimize. | |
| void | PushFlow (FlowQuantity flow, ArcIndex arc) |
| Pushes flow on arc, i.e. | |
| void | Relabel (NodeIndex node) |
| Relabels a node, i.e. increases its height by the minimum necessary amount. | |
| NodeIndex | Head (ArcIndex arc) const |
| Handy member functions to make the code more compact. | |
| NodeIndex | Tail (ArcIndex arc) const |
| ArcIndex | Opposite (ArcIndex arc) const |
| bool | IsDirect (ArcIndex arc) const |
| DISALLOW_COPY_AND_ASSIGN (MaxFlow) | |
Protected Attributes | |
| const StarGraph * | graph_ |
| A pointer to the graph passed as argument. | |
| QuantityArray | node_excess_ |
| A packed array representing the excess for each node in graph_. | |
| CostArray | node_potential_ |
| A packed array representing the height function for each node in graph_. | |
| QuantityArray | residual_arc_capacity_ |
| A packed array representing the residual_capacity for each arc in graph_. | |
| ArcIndexArray | first_admissible_arc_ |
| A packed array representing the first admissible arc for each node in graph_. | |
| std::stack< NodeIndex > | active_nodes_ |
| A stack used for managing active nodes in the algorithm. | |
| NodeIndex | source_ |
| The index of the source node in graph_. | |
| NodeIndex | sink_ |
| The index of the sink node in graph_. | |
| FlowQuantity | total_flow_ |
| The total flow. | |
| Status | status_ |
| The status of the problem. | |
Definition at line 129 of file max_flow.h.
Different statuses for a given problem.
| NOT_SOLVED | The problem was not solved, or its data were edited. |
| OPTIMAL | Solve() was called and found an optimal solution. |
| FEASIBLE | There is a feasible flow. |
| INFEASIBLE | There is no feasible flow. |
| BAD_INPUT | The input is inconsistent. |
| BAD_RESULT | There was an error. |
Definition at line 132 of file max_flow.h.
| operations_research::MaxFlow::MaxFlow | ( | const StarGraph * | graph, | |
| NodeIndex | source, | |||
| NodeIndex | target | |||
| ) |
Definition at line 28 of file max_flow.cc.
| virtual operations_research::MaxFlow::~MaxFlow | ( | ) | [inline, virtual] |
Definition at line 143 of file max_flow.h.
| const StarGraph* operations_research::MaxFlow::graph | ( | ) | const [inline] |
| Status operations_research::MaxFlow::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 151 of file max_flow.h.
| NodeIndex operations_research::MaxFlow::GetSourceNodeIndex | ( | ) | const [inline] |
Returns the index of the node corresponding to the source of the network.
Definition at line 154 of file max_flow.h.
| NodeIndex operations_research::MaxFlow::GetSinkNodeIndex | ( | ) | const [inline] |
Returns the index of the node corresponding to the sink of the network.
Definition at line 157 of file max_flow.h.
| void operations_research::MaxFlow::SetArcCapacity | ( | ArcIndex | arc, | |
| FlowQuantity | new_capacity | |||
| ) |
| void operations_research::MaxFlow::SetArcFlow | ( | ArcIndex | arc, | |
| FlowQuantity | new_flow | |||
| ) | [inline] |
| bool operations_research::MaxFlow::Solve | ( | ) |
| FlowQuantity operations_research::MaxFlow::GetOptimalFlow | ( | ) | const [inline] |
| FlowQuantity operations_research::MaxFlow::Flow | ( | ArcIndex | arc | ) | const [inline] |
Returns the flow on arc using the equations given in the comment on residual_arc_capacity_.
Definition at line 180 of file max_flow.h.
| FlowQuantity operations_research::MaxFlow::Capacity | ( | ArcIndex | arc | ) | const [inline] |
Returns the capacity of arc using the equations given in the comment on residual_arc_capacity_.
Definition at line 191 of file max_flow.h.
Returns true if node is active, i.e.
if its supply is positive and it is neither the source or the target of the graph.
Definition at line 210 of file max_flow.h.
| void operations_research::MaxFlow::PushFlowUnsafe | ( | ArcIndex | arc, | |
| FlowQuantity | flow | |||
| ) | [inline, protected] |
Reduces the residual capacity on arc by flow.
Increase the residual capacity on opposite arc by flow. Does not update the excesses at the tail and head of arc. No check is performed either.
Definition at line 224 of file max_flow.h.
| void operations_research::MaxFlow::SetCapacityResetFlow | ( | ArcIndex | arc, | |
| FlowQuantity | capacity | |||
| ) | [inline, protected] |
Sets the capacity of arc to 'capacity' and clears the flow on arc.
Definition at line 232 of file max_flow.h.
| void operations_research::MaxFlow::SetCapacitySaturate | ( | ArcIndex | arc, | |
| FlowQuantity | capacity | |||
| ) | [inline, protected] |
Sets the capacity of arc to 'capacity' and saturates the flow on arc.
Definition at line 238 of file max_flow.h.
| bool operations_research::MaxFlow::CheckInputConsistency | ( | ) | const [protected] |
Checks the consistency of the input, i.e.
that capacities on the arcs are non-negative (>=0.)
Definition at line 57 of file max_flow.cc.
| bool operations_research::MaxFlow::CheckResult | ( | ) | const [protected] |
Checks whether the result is valid, i.e.
that node excesses are all equal to zero (we have a flow) and that residual capacities are all non-negative (>=0.)
Definition at line 107 of file max_flow.cc.
Returns true if a precondition for Relabel is met, i.e.
the outgoing arcs of node are all either saturated or the heights of their heads are greater or equal to the height of node.
Definition at line 144 of file max_flow.cc.
| string operations_research::MaxFlow::DebugString | ( | const string & | context, | |
| ArcIndex | arc | |||
| ) | const [protected] |
Returns context concatenated with information about arc in a human-friendly way.
Definition at line 155 of file max_flow.cc.
| void operations_research::MaxFlow::InitializeActiveNodeContainer | ( | ) | [protected, virtual] |
| virtual NodeIndex operations_research::MaxFlow::GetAndRemoveFirstActiveNode | ( | ) | [inline, protected, virtual] |
| virtual void operations_research::MaxFlow::PushActiveNode | ( | const NodeIndex & | node | ) | [inline, protected, virtual] |
| virtual bool operations_research::MaxFlow::IsEmptyActiveNodeContainer | ( | ) | [inline, protected, virtual] |
| void operations_research::MaxFlow::Refine | ( | ) | [protected] |
| void operations_research::MaxFlow::Discharge | ( | NodeIndex | node | ) | [protected, virtual] |
Discharges an active node node by saturating its admissible adjacent arcs, if any, and by relabelling it when it becomes inactive.
Definition at line 263 of file max_flow.cc.
| void operations_research::MaxFlow::ResetFirstAdmissibleArcs | ( | ) | [protected] |
Resets the first_admissible_arc_ array to the first incident arc of each node.
Definition at line 193 of file max_flow.cc.
| void operations_research::MaxFlow::InitializePreflow | ( | ) | [protected] |
Initializes the preflow to a state that enables to run Optimize.
Definition at line 200 of file max_flow.cc.
| void operations_research::MaxFlow::PushFlow | ( | FlowQuantity | flow, | |
| ArcIndex | arc | |||
| ) | [protected] |
Pushes flow on arc, i.e.
consumes flow on residual_arc_capacity_[arc], and consumes -flow on residual_arc_capacity_[Opposite(arc)]. Updates node_excess_ at the tail and head of arc accordingly.
Definition at line 227 of file max_flow.cc.
| void operations_research::MaxFlow::Relabel | ( | NodeIndex | node | ) | [protected] |
Relabels a node, i.e. increases its height by the minimum necessary amount.
Definition at line 295 of file max_flow.cc.
Definition at line 306 of file max_flow.h.
Definition at line 308 of file max_flow.h.
Definition at line 310 of file max_flow.h.
| operations_research::MaxFlow::DISALLOW_COPY_AND_ASSIGN | ( | MaxFlow | ) | [protected] |
const StarGraph* operations_research::MaxFlow::graph_ [protected] |
A packed array representing the excess for each node in graph_.
Definition at line 316 of file max_flow.h.
A packed array representing the height function for each node in graph_.
Definition at line 319 of file max_flow.h.
A packed array representing the residual_capacity for each arc in graph_.
Residual capacities enable one to represent the capacity and flow for all arcs in the graph in the following manner. For all arc, residual_arc_capacity_[arc] = capacity[arc] - flow[arc] Moreover, for reverse arcs, capacity[arc] = 0 by definition, Also flow[Opposite(arc)] = -flow[arc] by definition. Therefore:
Definition at line 338 of file max_flow.h.
A packed array representing the first admissible arc for each node in graph_.
Definition at line 342 of file max_flow.h.
std::stack<NodeIndex> operations_research::MaxFlow::active_nodes_ [protected] |
A stack used for managing active nodes in the algorithm.
Note that the papers cited above recommend the use of a queue, but benchmarking so far has not proved it is better.
Definition at line 347 of file max_flow.h.
NodeIndex operations_research::MaxFlow::source_ [protected] |
NodeIndex operations_research::MaxFlow::sink_ [protected] |
Status operations_research::MaxFlow::status_ [protected] |