123#ifndef OR_TOOLS_GRAPH_MAX_FLOW_H_
124#define OR_TOOLS_GRAPH_MAX_FLOW_H_
135#include "ortools/graph/flow_problem.pb.h"
143template <
typename Graph>
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_;
263template <
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_;
314template <
typename Graph>
320 typedef typename Graph::OutgoingOrOppositeIncomingArcIterator
540 template <
bool reverse>
660template <
typename Element,
typename IntegerPriority>
663 return even_queue_.empty() && odd_queue_.empty();
666template <
typename Element,
typename IntegerPriority>
672template <
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));
691template <
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_);
703template <
typename Element,
typename IntegerPriority>
705 std::vector<std::pair<Element, IntegerPriority> >* queue) {
707 Element element = queue->back().first;
#define DCHECK(condition)
Graph::OutgoingArcIterator OutgoingArcIterator
bool CheckInputConsistency() const
FlowQuantity GetOptimalFlow() const
void Relabel(NodeIndex node)
bool IsAdmissible(ArcIndex arc) const
std::vector< NodeIndex > active_nodes_
void SetArcCapacity(ArcIndex arc, FlowQuantity new_capacity)
std::string DebugString(const std::string &context, ArcIndex arc) const
bool SaturateOutgoingArcsFromSource()
Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator
NodeIndex GetSourceNodeIndex() const
FlowQuantity Flow(ArcIndex arc) const
bool CheckRelabelPrecondition(NodeIndex node) const
std::vector< NodeIndex > bfs_queue_
static const FlowQuantity kMaxFlowQuantity
bool process_node_by_height_
ArcIndexArray first_admissible_arc_
void SetArcFlow(ArcIndex arc, FlowQuantity new_flow)
void PushFlowExcessBackToSource()
void PushActiveNode(const NodeIndex &node)
void SetUseTwoPhaseAlgorithm(bool value)
Graph::NodeIndex NodeIndex
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
NodeHeightArray node_potential_
bool use_two_phase_algorithm_
void SetUseGlobalUpdate(bool value)
void InitializeActiveNodeContainer()
void SetCapacityAndClearFlow(ArcIndex arc, FlowQuantity capacity)
ZVector< NodeHeight > NodeHeightArray
const Graph * graph() const
NodeIndex GetAndRemoveFirstActiveNode()
std::vector< bool > node_in_bfs_queue_
bool IsEmptyActiveNodeContainer()
FlowQuantity Capacity(ArcIndex arc) const
void SetCheckResult(bool value)
NodeIndex Head(ArcIndex arc) const
void SetCheckInput(bool value)
QuantityArray residual_arc_capacity_
NodeIndex Tail(ArcIndex arc) const
Graph::IncomingArcIterator IncomingArcIterator
virtual ~GenericMaxFlow()
void PushFlow(FlowQuantity flow, ArcIndex arc)
void ComputeReachableNodes(NodeIndex start, std::vector< NodeIndex > *result)
bool IsArcValid(ArcIndex arc) const
GenericMaxFlow(const Graph *graph, NodeIndex source, NodeIndex sink)
void RefineWithGlobalUpdate()
ZVector< ArcIndex > ArcIndexArray
bool AugmentingPathExists() const
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
ArcIndex Opposite(ArcIndex arc) const
void ProcessNodeByHeight(bool value)
bool IsActive(NodeIndex node) const
bool IsArcDirect(ArcIndex arc) const
NodeIndex GetSinkNodeIndex() const
void Discharge(NodeIndex node)
QuantityArray node_excess_
FlowModel CreateFlowModel()
PriorityQueueWithRestrictedPush< NodeIndex, NodeHeight > active_node_by_height_
MaxFlow(const StarGraph *graph, NodeIndex source, NodeIndex target)
PriorityQueueWithRestrictedPush()
void Push(Element element, IntegerPriority priority)
FlowQuantity Flow(ArcIndex arc) const
NodeIndex NumNodes() const
FlowModel CreateFlowModelOfLastSolve()
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
Status Solve(NodeIndex source, NodeIndex sink)
FlowQuantity OptimalFlow() const
ArcIndex AddArcWithCapacity(NodeIndex tail, NodeIndex head, FlowQuantity capacity)
FlowQuantity Capacity(ArcIndex arc) const
NodeIndex Head(ArcIndex arc) const
NodeIndex Tail(ArcIndex arc) const
void SetArcCapacity(ArcIndex arc, FlowQuantity capacity)
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
void Set(int64 index, T value)
GurobiMPCallbackContext * context
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...