 |
OR-Tools
8.1
|
Go to the documentation of this file.
123 #ifndef OR_TOOLS_GRAPH_MAX_FLOW_H_
124 #define OR_TOOLS_GRAPH_MAX_FLOW_H_
143 template <
typename Graph>
144 class GenericMaxFlow;
233 std::vector<NodeIndex> arc_tail_;
234 std::vector<NodeIndex> arc_head_;
235 std::vector<FlowQuantity> arc_capacity_;
236 std::vector<ArcIndex> arc_permutation_;
237 std::vector<FlowQuantity> arc_flow_;
242 typedef ::util::ReverseArcStaticGraph<NodeIndex, ArcIndex> Graph;
243 std::unique_ptr<Graph> underlying_graph_;
244 std::unique_ptr<GenericMaxFlow<Graph> > underlying_max_flow_;
263 template <
typename Element,
typename IntegerPriority>
277 void Push(Element element, IntegerPriority priority);
285 Element PopBack(std::vector<std::pair<Element, IntegerPriority> >* queue);
290 std::vector<std::pair<Element, IntegerPriority> > even_queue_;
291 std::vector<std::pair<Element, IntegerPriority> > odd_queue_;
314 template <
typename Graph>
320 typedef typename Graph::OutgoingOrOppositeIncomingArcIterator
540 template <
bool reverse>
660 template <
typename Element,
typename IntegerPriority>
663 return even_queue_.empty() && odd_queue_.empty();
666 template <
typename Element,
typename IntegerPriority>
672 template <
typename Element,
typename IntegerPriority>
674 Element element, IntegerPriority priority) {
676 DCHECK(even_queue_.empty() || priority >= even_queue_.back().second - 1);
677 DCHECK(odd_queue_.empty() || priority >= odd_queue_.back().second - 1);
683 DCHECK(odd_queue_.empty() || priority >= odd_queue_.back().second);
684 odd_queue_.push_back(std::make_pair(element, priority));
686 DCHECK(even_queue_.empty() || priority >= even_queue_.back().second);
687 even_queue_.push_back(std::make_pair(element, priority));
691 template <
typename Element,
typename IntegerPriority>
694 if (even_queue_.empty())
return PopBack(&odd_queue_);
695 if (odd_queue_.empty())
return PopBack(&even_queue_);
696 if (odd_queue_.back().second > even_queue_.back().second) {
697 return PopBack(&odd_queue_);
699 return PopBack(&even_queue_);
703 template <
typename Element,
typename IntegerPriority>
705 std::vector<std::pair<Element, IntegerPriority> >* queue) {
707 Element element = queue->back().first;
713 #endif // OR_TOOLS_GRAPH_MAX_FLOW_H_
ArcIndexArray first_admissible_arc_
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
virtual ~GenericMaxFlow()
bool IsActive(NodeIndex node) const
QuantityArray node_excess_
ArcIndex Opposite(ArcIndex arc) const
FlowQuantity Capacity(ArcIndex arc) const
void PushActiveNode(const NodeIndex &node)
std::vector< NodeIndex > bfs_queue_
NodeIndex Tail(ArcIndex arc) const
void SetUseTwoPhaseAlgorithm(bool value)
void RefineWithGlobalUpdate()
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
bool process_node_by_height_
ZVector< ArcIndex > ArcIndexArray
bool SaturateOutgoingArcsFromSource()
FlowQuantity Flow(ArcIndex arc) const
void Set(int64 index, T value)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
FlowQuantity Flow(ArcIndex arc) const
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
NodeIndex GetAndRemoveFirstActiveNode()
void ProcessNodeByHeight(bool value)
NodeHeightArray node_potential_
GurobiMPCallbackContext * context
bool AugmentingPathExists() const
FlowQuantity Capacity(ArcIndex arc) const
void SetArcCapacity(ArcIndex arc, FlowQuantity capacity)
void Push(Element element, IntegerPriority priority)
Graph::OutgoingArcIterator OutgoingArcIterator
void PushFlowExcessBackToSource()
FlowQuantity OptimalFlow() const
Graph::IncomingArcIterator IncomingArcIterator
Status Solve(NodeIndex source, NodeIndex sink)
void SetArcFlow(ArcIndex arc, FlowQuantity new_flow)
MaxFlow(const StarGraph *graph, NodeIndex source, NodeIndex target)
FlowQuantity GetOptimalFlow() const
NodeIndex Head(ArcIndex arc) const
const Graph * graph() const
ZVector< NodeHeight > NodeHeightArray
void ComputeReachableNodes(NodeIndex start, std::vector< NodeIndex > *result)
QuantityArray residual_arc_capacity_
bool use_two_phase_algorithm_
bool IsArcDirect(ArcIndex arc) const
ArcIndex AddArcWithCapacity(NodeIndex tail, NodeIndex head, FlowQuantity capacity)
void SetArcCapacity(ArcIndex arc, FlowQuantity new_capacity)
#define DCHECK(condition)
void Relabel(NodeIndex node)
bool CheckRelabelPrecondition(NodeIndex node) const
PriorityQueueWithRestrictedPush< NodeIndex, NodeHeight > active_node_by_height_
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
void InitializeActiveNodeContainer()
static const FlowQuantity kMaxFlowQuantity
void Discharge(NodeIndex node)
void SetCheckInput(bool value)
NodeIndex GetSinkNodeIndex() const
NodeIndex Head(ArcIndex arc) const
void SetCheckResult(bool value)
std::vector< NodeIndex > active_nodes_
NodeIndex NumNodes() const
void SetCapacityAndClearFlow(ArcIndex arc, FlowQuantity capacity)
FlowModel CreateFlowModel()
bool CheckInputConsistency() const
bool IsAdmissible(ArcIndex arc) const
Graph::NodeIndex NodeIndex
bool IsArcValid(ArcIndex arc) const
void PushFlow(FlowQuantity flow, ArcIndex arc)
bool IsEmptyActiveNodeContainer()
std::string DebugString(const std::string &context, ArcIndex arc) const
FlowModel CreateFlowModelOfLastSolve()
NodeIndex Tail(ArcIndex arc) const
GenericMaxFlow(const Graph *graph, NodeIndex source, NodeIndex sink)
NodeIndex GetSourceNodeIndex() const
PriorityQueueWithRestrictedPush()
void SetUseGlobalUpdate(bool value)
std::vector< bool > node_in_bfs_queue_
Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator