OR-Tools  8.2
max_flow.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// An implementation of a push-relabel algorithm for the max flow problem.
15//
16// In the following, we consider a graph G = (V,E,s,t) where V denotes the set
17// of nodes (vertices) in the graph, E denotes the set of arcs (edges). s and t
18// denote distinguished nodes in G called source and target. n = |V| denotes the
19// number of nodes in the graph, and m = |E| denotes the number of arcs in the
20// graph.
21//
22// Each arc (v,w) is associated a capacity c(v,w).
23//
24// A flow is a function from E to R such that:
25//
26// a) f(v,w) <= c(v,w) for all (v,w) in E (capacity constraint.)
27//
28// b) f(v,w) = -f(w,v) for all (v,w) in E (flow antisymmetry constraint.)
29//
30// c) sum on v f(v,w) = 0 (flow conservation.)
31//
32// The goal of this algorithm is to find the maximum flow from s to t, i.e.
33// for example to maximize sum v f(s,v).
34//
35// The starting reference for this class of algorithms is:
36// A.V. Goldberg and R.E. Tarjan. A new approach to the maximum flow problem.
37// ACM Symposium on Theory of Computing, pp. 136-146.
38// http://portal.acm.org/citation.cfm?id=12144.
39//
40// The basic idea of the algorithm is to handle preflows instead of flows,
41// and to refine preflows until a maximum flow is obtained.
42// A preflow is like a flow, except that the inflow can be larger than the
43// outflow. If it is the case at a given node v, it is said that there is an
44// excess at node v, and inflow = outflow + excess.
45//
46// More formally, a preflow is a function f such that:
47//
48// 1) f(v,w) <= c(v,w) for all (v,w) in E (capacity constraint). c(v,w) is a
49// value representing the maximum capacity for arc (v,w).
50//
51// 2) f(v,w) = -f(w,v) for all (v,w) in E (flow antisymmetry constraint)
52//
53// 3) excess(v) = sum on u f(u,v) >= 0 is the excess at node v, the
54// algebraic sum of all the incoming preflows at this node.
55//
56// Each node has an associated "height", in addition to its excess. The
57// height of the source is defined to be equal to n, and cannot change. The
58// height of the target is defined to be zero, and cannot change either. The
59// height of all the other nodes is initialized at zero and is updated during
60// the algorithm (see below). For those who want to know the details, the height
61// of a node, corresponds to a reduced cost, and this enables one to prove that
62// the algorithm actually computes the max flow. Note that the height of a node
63// can be initialized to the distance to the target node in terms of number of
64// nodes. This has not been tried in this implementation.
65//
66// A node v is said to be *active* if excess(v) > 0.
67//
68// In this case the following operations can be applied to it:
69//
70// - if there are *admissible* incident arcs, i.e. arcs which are not saturated,
71// and whose head's height is lower than the height of the active node
72// considered, a PushFlow operation can be applied. It consists in sending as
73// much flow as both the excess at the node and the capacity of the arc
74// permit.
75// - if there are no admissible arcs, the active node considered is relabeled,
76// i.e. its height is increased to 1 + the minimum height of its neighboring
77// nodes on admissible arcs.
78// This is implemented in Discharge, which itself calls PushFlow and Relabel.
79//
80// Before running Discharge, it is necessary to initialize the algorithm with a
81// preflow. This is done in InitializePreflow, which saturates all the arcs
82// leaving the source node, and sets the excess at the heads of those arcs
83// accordingly.
84//
85// The algorithm terminates when there are no remaining active nodes, i.e. all
86// the excesses at all nodes are equal to zero. In this case, a maximum flow is
87// obtained.
88//
89// The complexity of this algorithm depends amongst other things on the choice
90// of the next active node. It has been shown, for example in:
91// L. Tuncel, "On the Complexity of Preflow-Push Algorithms for Maximum-Flow
92// Problems", Algorithmica 11(4): 353-359 (1994).
93// and
94// J. Cheriyan and K. Mehlhorn, "An analysis of the highest-level selection rule
95// in the preflow-push max-flow algorithm", Information processing letters,
96// 69(5):239-242 (1999).
97// http://www.math.uwaterloo.ca/~jcheriya/PS_files/me3.0.ps
98//
99// ...that choosing the active node with the highest level yields a
100// complexity of O(n^2 * sqrt(m)).
101//
102// TODO(user): implement the above active node choice rule.
103//
104// This has been validated experimentally in:
105// R.K. Ahuja, M. Kodialam, A.K. Mishra, and J.B. Orlin, "Computational
106// Investigations of Maximum Flow Algorithms", EJOR 97:509-542(1997).
107// http://jorlin.scripts.mit.edu/docs/publications/58-comput%20investigations%20of.pdf.
108//
109//
110// TODO(user): an alternative would be to evaluate:
111// A.V. Goldberg, "The Partial Augment-Relabel Algorithm for the Maximum Flow
112// Problem.” In Proceedings of Algorithms ESA, LNCS 5193:466-477, Springer 2008.
113// http://www.springerlink.com/index/5535k2j1mt646338.pdf
114//
115// An interesting general reference on network flows is:
116// R. K. Ahuja, T. L. Magnanti, J. B. Orlin, "Network Flows: Theory, Algorithms,
117// and Applications," Prentice Hall, 1993, ISBN: 978-0136175490,
118// http://www.amazon.com/dp/013617549X
119//
120// Keywords: Push-relabel, max-flow, network, graph, Goldberg, Tarjan, Dinic,
121// Dinitz.
122
123#ifndef OR_TOOLS_GRAPH_MAX_FLOW_H_
124#define OR_TOOLS_GRAPH_MAX_FLOW_H_
125
126#include <algorithm>
127#include <memory>
128#include <string>
129#include <vector>
130
132#include "ortools/base/logging.h"
133#include "ortools/base/macros.h"
135#include "ortools/graph/flow_problem.pb.h"
136#include "ortools/graph/graph.h"
137#include "ortools/util/stats.h"
138#include "ortools/util/zvector.h"
139
140namespace operations_research {
141
142// Forward declaration.
143template <typename Graph>
144class GenericMaxFlow;
145
146// A simple and efficient max-cost flow interface. This is as fast as
147// GenericMaxFlow<ReverseArcStaticGraph>, which is the fastest, but uses
148// more memory in order to hide the somewhat involved construction of the
149// static graph.
150//
151// TODO(user): If the need arises, extend this interface to support warm start.
153 public:
154 // The constructor takes no size.
155 // New node indices will be created lazily by AddArcWithCapacity().
157
158 // Adds a directed arc with the given capacity from tail to head.
159 // * Node indices and capacity must be non-negative (>= 0).
160 // * Self-looping and duplicate arcs are supported.
161 // * After the method finishes, NumArcs() == the returned ArcIndex + 1.
164
165 // Returns the current number of nodes. This is one more than the largest
166 // node index seen so far in AddArcWithCapacity().
167 NodeIndex NumNodes() const;
168
169 // Returns the current number of arcs in the graph.
170 ArcIndex NumArcs() const;
171
172 // Returns user-provided data.
173 // The implementation will crash if "arc" is not in [0, NumArcs()).
174 NodeIndex Tail(ArcIndex arc) const;
175 NodeIndex Head(ArcIndex arc) const;
176 FlowQuantity Capacity(ArcIndex arc) const;
177
178 // Solves the problem (finds the maximum flow from the given source to the
179 // given sink), and returns the problem status.
180 enum Status {
181 // Solve() was called and found an optimal solution. Note that OptimalFlow()
182 // may be 0 which means that the sink is not reachable from the source.
184 // There is a flow > std::numeric_limits<FlowQuantity>::max(). Note that in
185 // this case, the class will contain a solution with a flow reaching that
186 // bound.
187 //
188 // TODO(user): rename POSSIBLE_OVERFLOW to INT_OVERFLOW and modify our
189 // clients.
191 // The input is inconsistent (bad tail/head/capacity values).
193 // This should not happen. There was an error in our code (i.e. file a bug).
195 };
196 Status Solve(NodeIndex source, NodeIndex sink);
197
198 // Returns the maximum flow we can send from the source to the sink in the
199 // last OPTIMAL Solve() context.
201
202 // Returns the flow on the given arc in the last OPTIMAL Solve() context.
203 //
204 // Note: It is possible that there is more than one optimal solution. The
205 // algorithm is deterministic so it will always return the same solution for
206 // a given problem. However, there is no guarantee of this from one code
207 // version to the next (but the code does not change often).
208 FlowQuantity Flow(ArcIndex arc) const;
209
210 // Returns the nodes reachable from the source by non-saturated arcs (.i.e.
211 // arc with Flow(arc) < Capacity(arc)), the outgoing arcs of this set form a
212 // minimum cut. This works only if Solve() returned OPTIMAL.
213 void GetSourceSideMinCut(std::vector<NodeIndex>* result);
214
215 // Returns the nodes that can reach the sink by non-saturated arcs, the
216 // outgoing arcs of this set form a minimum cut. Note that if this is the
217 // complement set of GetNodeReachableFromSource(), then the min-cut is unique.
218 // This works only if Solve() returned OPTIMAL.
219 void GetSinkSideMinCut(std::vector<NodeIndex>* result);
220
221 // Creates the protocol buffer representation of the problem used by the last
222 // Solve() call. This is mainly useful for debugging.
223 FlowModel CreateFlowModelOfLastSolve();
224
225 // Change the capacity of an arc.
226 // WARNING: This looks like it enables incremental solves, but as of 2018-02,
227 // the next Solve() will restart from scratch anyway.
228 // TODO(user): Support incrementality in the max flow implementation.
230
231 private:
232 NodeIndex num_nodes_;
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_;
238 FlowQuantity optimal_flow_;
239
240 // Note that we cannot free the graph before we stop using the max-flow
241 // instance that uses it.
242 typedef ::util::ReverseArcStaticGraph<NodeIndex, ArcIndex> Graph;
243 std::unique_ptr<Graph> underlying_graph_;
244 std::unique_ptr<GenericMaxFlow<Graph> > underlying_max_flow_;
245
246 DISALLOW_COPY_AND_ASSIGN(SimpleMaxFlow);
247};
248
249// Specific but efficient priority queue implementation. The priority type must
250// be an integer. The queue allows to retrieve the element with highest priority
251// but only allows pushes with a priority greater or equal to the highest
252// priority in the queue minus one. All operations are in O(1) and the memory is
253// in O(num elements in the queue). Elements with the same priority are
254// retrieved with LIFO order.
255//
256// Note(user): As far as I know, this is an original idea and is the only code
257// that use this in the Maximum Flow context. Papers usually refer to an
258// height-indexed array of simple linked lists of active node with the same
259// height. Even worse, sometimes they use double-linked list to allow arbitrary
260// height update in order to detect missing height (used for the Gap heuristic).
261// But this can actually be implemented a lot more efficiently by just
262// maintaining the height distribution of all the node in the graph.
263template <typename Element, typename IntegerPriority>
265 public:
266 PriorityQueueWithRestrictedPush() : even_queue_(), odd_queue_() {}
267
268 // Is the queue empty?
269 bool IsEmpty() const;
270
271 // Clears the queue.
272 void Clear();
273
274 // Push a new element in the queue. Its priority must be greater or equal to
275 // the highest priority present in the queue, minus one. This condition is
276 // DCHECKed, and violating it yields erroneous queue behavior in NDEBUG mode.
277 void Push(Element element, IntegerPriority priority);
278
279 // Returns the element with highest priority and remove it from the queue.
280 // IsEmpty() must be false, this condition is DCHECKed.
281 Element Pop();
282
283 private:
284 // Helper function to get the last element of a vector and pop it.
285 Element PopBack(std::vector<std::pair<Element, IntegerPriority> >* queue);
286
287 // This is the heart of the algorithm. basically we split the elements by
288 // parity of their priority and the precondition on the Push() ensures that
289 // both vectors are always sorted by increasing priority.
290 std::vector<std::pair<Element, IntegerPriority> > even_queue_;
291 std::vector<std::pair<Element, IntegerPriority> > odd_queue_;
292
293 DISALLOW_COPY_AND_ASSIGN(PriorityQueueWithRestrictedPush);
294};
295
296// We want an enum for the Status of a max flow run, and we want this
297// enum to be scoped under GenericMaxFlow<>. Unfortunately, swig
298// doesn't handle templated enums very well, so we need a base,
299// untemplated class to hold it.
301 public:
302 enum Status {
303 NOT_SOLVED, // The problem was not solved, or its data were edited.
304 OPTIMAL, // Solve() was called and found an optimal solution.
305 INT_OVERFLOW, // There is a feasible flow > max possible flow.
306 BAD_INPUT, // The input is inconsistent.
307 BAD_RESULT // There was an error.
308 };
309};
310
311// Generic MaxFlow (there is a default MaxFlow specialization defined below)
312// that works with StarGraph and all the reverse arc graphs from graph.h, see
313// the end of max_flow.cc for the exact types this class is compiled for.
314template <typename Graph>
316 public:
317 typedef typename Graph::NodeIndex NodeIndex;
318 typedef typename Graph::ArcIndex ArcIndex;
319 typedef typename Graph::OutgoingArcIterator OutgoingArcIterator;
320 typedef typename Graph::OutgoingOrOppositeIncomingArcIterator
322 typedef typename Graph::IncomingArcIterator IncomingArcIterator;
324
325 // The height of a node never excess 2 times the number of node, so we
326 // use the same type as a Node index.
329
330 // Initialize a MaxFlow instance on the given graph. The graph does not need
331 // to be fully built yet, but its capacity reservation are used to initialize
332 // the memory of this class. source and sink must also be valid node of
333 // graph.
334 GenericMaxFlow(const Graph* graph, NodeIndex source, NodeIndex sink);
335 virtual ~GenericMaxFlow() {}
336
337 // Returns the graph associated to the current object.
338 const Graph* graph() const { return graph_; }
339
340 // Returns the status of last call to Solve(). NOT_SOLVED is returned if
341 // Solve() has never been called or if the problem has been modified in such a
342 // way that the previous solution becomes invalid.
343 Status status() const { return status_; }
344
345 // Returns the index of the node corresponding to the source of the network.
347
348 // Returns the index of the node corresponding to the sink of the network.
349 NodeIndex GetSinkNodeIndex() const { return sink_; }
350
351 // Sets the capacity for arc to new_capacity.
352 void SetArcCapacity(ArcIndex arc, FlowQuantity new_capacity);
353
354 // Sets the flow for arc.
355 void SetArcFlow(ArcIndex arc, FlowQuantity new_flow);
356
357 // Returns true if a maximum flow was solved.
358 bool Solve();
359
360 // Returns the total flow found by the algorithm.
362
363 // Returns the flow on arc using the equations given in the comment on
364 // residual_arc_capacity_.
366 if (IsArcDirect(arc)) {
367 return residual_arc_capacity_[Opposite(arc)];
368 } else {
369 return -residual_arc_capacity_[arc];
370 }
371 }
372
373 // Returns the capacity of arc using the equations given in the comment on
374 // residual_arc_capacity_.
376 if (IsArcDirect(arc)) {
377 return residual_arc_capacity_[arc] +
379 } else {
380 return 0;
381 }
382 }
383
384 // Returns the nodes reachable from the source in the residual graph, the
385 // outgoing arcs of this set form a minimum cut.
386 void GetSourceSideMinCut(std::vector<NodeIndex>* result);
387
388 // Returns the nodes that can reach the sink in the residual graph, the
389 // outgoing arcs of this set form a minimum cut. Note that if this is the
390 // complement of GetNodeReachableFromSource(), then the min-cut is unique.
391 //
392 // TODO(user): In the two-phases algorithm, we can get this minimum cut
393 // without doing the second phase. Add an option for this if there is a need
394 // to, note that the second phase is pretty fast so the gain will be small.
395 void GetSinkSideMinCut(std::vector<NodeIndex>* result);
396
397 // Checks the consistency of the input, i.e. that capacities on the arcs are
398 // non-negative or null.
399 bool CheckInputConsistency() const;
400
401 // Checks whether the result is valid, i.e. that node excesses are all equal
402 // to zero (we have a flow) and that residual capacities are all non-negative
403 // or zero.
404 bool CheckResult() const;
405
406 // Returns true if there exists a path from the source to the sink with
407 // remaining capacity. This allows us to easily check at the end that the flow
408 // we computed is indeed optimal (provided that all the conditions tested by
409 // CheckResult() also hold).
410 bool AugmentingPathExists() const;
411
412 // Sets the different algorithm options. All default to true.
413 // See the corresponding variable declaration below for more details.
417 }
423 }
424
425 // Returns the protocol buffer representation of the current problem.
426 FlowModel CreateFlowModel();
427
428 protected:
429 // Returns true if arc is admissible.
430 bool IsAdmissible(ArcIndex arc) const {
431 return residual_arc_capacity_[arc] > 0 &&
432 node_potential_[Tail(arc)] == node_potential_[Head(arc)] + 1;
433 }
434
435 // Returns true if node is active, i.e. if its excess is positive and it
436 // is neither the source or the sink of the graph.
437 bool IsActive(NodeIndex node) const {
438 return (node != source_) && (node != sink_) && (node_excess_[node] > 0);
439 }
440
441 // Sets the capacity of arc to 'capacity' and clears the flow on arc.
445 }
446
447 // Returns true if a precondition for Relabel is met, i.e. the outgoing arcs
448 // of node are all either saturated or the heights of their heads are greater
449 // or equal to the height of node.
450 bool CheckRelabelPrecondition(NodeIndex node) const;
451
452 // Returns context concatenated with information about arc
453 // in a human-friendly way.
454 std::string DebugString(const std::string& context, ArcIndex arc) const;
455
456 // Initializes the container active_nodes_.
458
459 // Get the first element from the active node container.
462 const NodeIndex node = active_nodes_.back();
463 active_nodes_.pop_back();
464 return node;
465 }
466
467 // Push element to the active node container.
468 void PushActiveNode(const NodeIndex& node) {
471 } else {
472 active_nodes_.push_back(node);
473 }
474 }
475
476 // Check the emptiness of the container.
480 } else {
481 return active_nodes_.empty();
482 }
483 }
484
485 // Performs optimization step.
486 void Refine();
488
489 // Discharges an active node node by saturating its admissible adjacent arcs,
490 // if any, and by relabelling it when it becomes inactive.
491 void Discharge(NodeIndex node);
492
493 // Initializes the preflow to a state that enables to run Refine.
494 void InitializePreflow();
495
496 // Clears the flow excess at each node by pushing the flow back to the source:
497 // - Do a depth-first search from the source in the direct graph to cancel
498 // flow cycles.
499 // - Then, return flow excess along the depth-first search tree (by pushing
500 // the flow in the reverse dfs topological order).
501 // The theoretical complexity is O(mn), but it is a lot faster in practice.
503
504 // Computes the best possible node potential given the current flow using a
505 // reverse breadth-first search from the sink in the reverse residual graph.
506 // This is an implementation of the global update heuristic mentioned in many
507 // max-flow papers. See for instance: B.V. Cherkassky, A.V. Goldberg, "On
508 // implementing push-relabel methods for the maximum flow problem",
509 // Algorithmica, 19:390-410, 1997.
510 // ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/94/1523/CS-TR-94-1523.pdf
511 void GlobalUpdate();
512
513 // Tries to saturate all the outgoing arcs from the source that can reach the
514 // sink. Most of the time, we can do that in one go, except when more flow
515 // than kMaxFlowQuantity can be pushed out of the source in which case we
516 // have to be careful. Returns true if some flow was pushed.
518
519 // Pushes flow on arc, i.e. consumes flow on residual_arc_capacity_[arc],
520 // and consumes -flow on residual_arc_capacity_[Opposite(arc)]. Updates
521 // node_excess_ at the tail and head of arc accordingly.
522 void PushFlow(FlowQuantity flow, ArcIndex arc);
523
524 // Relabels a node, i.e. increases its height by the minimum necessary amount.
525 // This version of Relabel is relaxed in a way such that if an admissible arc
526 // exists at the current node height, then the node is not relabeled. This
527 // enables us to deal with wrong values of first_admissible_arc_[node] when
528 // updating it is too costly.
529 void Relabel(NodeIndex node);
530
531 // Handy member functions to make the code more compact.
532 NodeIndex Head(ArcIndex arc) const { return graph_->Head(arc); }
533 NodeIndex Tail(ArcIndex arc) const { return graph_->Tail(arc); }
534 ArcIndex Opposite(ArcIndex arc) const;
535 bool IsArcDirect(ArcIndex arc) const;
536 bool IsArcValid(ArcIndex arc) const;
537
538 // Returns the set of nodes reachable from start in the residual graph or in
539 // the reverse residual graph (if reverse is true).
540 template <bool reverse>
541 void ComputeReachableNodes(NodeIndex start, std::vector<NodeIndex>* result);
542
543 // Maximum manageable flow.
545
546 // A pointer to the graph passed as argument.
547 const Graph* graph_;
548
549 // An array representing the excess for each node in graph_.
551
552 // An array representing the height function for each node in graph_. For a
553 // given node, this is a lower bound on the shortest path length from this
554 // node to the sink in the residual network. The height of a node always goes
555 // up during the course of a Solve().
556 //
557 // Since initially we saturate all the outgoing arcs of the source, we can
558 // never reach the sink from the source in the residual graph. Initially we
559 // set the height of the source to n (the number of node of the graph) and it
560 // never changes. If a node as an height >= n, then this node can't reach the
561 // sink and its height minus n is a lower bound on the shortest path length
562 // from this node to the source in the residual graph.
564
565 // An array representing the residual_capacity for each arc in graph_.
566 // Residual capacities enable one to represent the capacity and flow for all
567 // arcs in the graph in the following manner.
568 // For all arc, residual_arc_capacity_[arc] = capacity[arc] - flow[arc]
569 // Moreover, for reverse arcs, capacity[arc] = 0 by definition,
570 // Also flow[Opposite(arc)] = -flow[arc] by definition.
571 // Therefore:
572 // - for a direct arc:
573 // flow[arc] = 0 - flow[Opposite(arc)]
574 // = capacity[Opposite(arc)] - flow[Opposite(arc)]
575 // = residual_arc_capacity_[Opposite(arc)]
576 // - for a reverse arc:
577 // flow[arc] = -residual_arc_capacity_[arc]
578 // Using these facts enables one to only maintain residual_arc_capacity_,
579 // instead of both capacity and flow, for each direct and indirect arc. This
580 // reduces the amount of memory for this information by a factor 2.
582
583 // An array representing the first admissible arc for each node in graph_.
585
586 // A stack used for managing active nodes in the algorithm.
587 // Note that the papers cited above recommend the use of a queue, but
588 // benchmarking so far has not proved it is better. In particular, processing
589 // nodes in LIFO order has better cache locality.
590 std::vector<NodeIndex> active_nodes_;
591
592 // A priority queue used for managing active nodes in the algorithm. It allows
593 // to select the active node with highest height before each Discharge().
594 // Moreover, since all pushes from this node will be to nodes with height
595 // greater or equal to the initial discharged node height minus one, the
596 // PriorityQueueWithRestrictedPush is a perfect fit.
598
599 // The index of the source node in graph_.
601
602 // The index of the sink node in graph_.
604
605 // The status of the problem.
607
608 // BFS queue used by the GlobalUpdate() function. We do not use a C++ queue
609 // because we need access to the vector for different optimizations.
610 std::vector<bool> node_in_bfs_queue_;
611 std::vector<NodeIndex> bfs_queue_;
612
613 // Whether or not to use GlobalUpdate().
615
616 // Whether or not we use a two-phase algorithm:
617 // 1/ Only deal with nodes that can reach the sink. At the end we know the
618 // value of the maximum flow and we have a min-cut.
619 // 2/ Call PushFlowExcessBackToSource() to obtain a max-flow. This is usually
620 // a lot faster than the first phase.
622
623 // Whether or not we use the PriorityQueueWithRestrictedPush to process the
624 // active nodes rather than a simple queue. This can only be true if
625 // use_global_update_ is true.
626 //
627 // Note(user): using a template will be slightly faster, but since we test
628 // this in a non-critical path, this only has a minor impact.
630
631 // Whether or not we check the input, this is a small price to pay for
632 // robustness. Disable only if you know the input is valid because an invalid
633 // input can cause the algorithm to run into an infinite loop!
635
636 // Whether or not we check the result.
637 // TODO(user): Make the check more exhaustive by checking the optimality?
639
640 // Statistics about this class.
642
643 private:
644 DISALLOW_COPY_AND_ASSIGN(GenericMaxFlow);
645};
646
647#if !SWIG
648
649// Default instance MaxFlow that uses StarGraph. Note that we cannot just use a
650// typedef because of dependent code expecting MaxFlow to be a real class.
651// TODO(user): Modify this code and remove it.
652class MaxFlow : public GenericMaxFlow<StarGraph> {
653 public:
654 MaxFlow(const StarGraph* graph, NodeIndex source, NodeIndex target)
655 : GenericMaxFlow(graph, source, target) {}
656};
657
658#endif // SWIG
659
660template <typename Element, typename IntegerPriority>
662 const {
663 return even_queue_.empty() && odd_queue_.empty();
664}
665
666template <typename Element, typename IntegerPriority>
668 even_queue_.clear();
669 odd_queue_.clear();
670}
671
672template <typename Element, typename IntegerPriority>
674 Element element, IntegerPriority priority) {
675 // Since users may rely on it, we DCHECK the exact condition.
676 DCHECK(even_queue_.empty() || priority >= even_queue_.back().second - 1);
677 DCHECK(odd_queue_.empty() || priority >= odd_queue_.back().second - 1);
678
679 // Note that the DCHECK() below are less restrictive than the ones above but
680 // check a necessary and sufficient condition for the priority queue to behave
681 // as expected.
682 if (priority & 1) {
683 DCHECK(odd_queue_.empty() || priority >= odd_queue_.back().second);
684 odd_queue_.push_back(std::make_pair(element, priority));
685 } else {
686 DCHECK(even_queue_.empty() || priority >= even_queue_.back().second);
687 even_queue_.push_back(std::make_pair(element, priority));
688 }
689}
690
691template <typename Element, typename IntegerPriority>
693 DCHECK(!IsEmpty());
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_);
698 } else {
699 return PopBack(&even_queue_);
700 }
701}
702
703template <typename Element, typename IntegerPriority>
705 std::vector<std::pair<Element, IntegerPriority> >* queue) {
706 DCHECK(!queue->empty());
707 Element element = queue->back().first;
708 queue->pop_back();
709 return element;
710}
711
712} // namespace operations_research
713#endif // OR_TOOLS_GRAPH_MAX_FLOW_H_
#define DCHECK(condition)
Definition: base/logging.h:884
Graph::OutgoingArcIterator OutgoingArcIterator
Definition: max_flow.h:319
FlowQuantity GetOptimalFlow() const
Definition: max_flow.h:361
void Relabel(NodeIndex node)
Definition: max_flow.cc:879
bool IsAdmissible(ArcIndex arc) const
Definition: max_flow.h:430
std::vector< NodeIndex > active_nodes_
Definition: max_flow.h:590
void SetArcCapacity(ArcIndex arc, FlowQuantity new_capacity)
Definition: max_flow.cc:175
std::string DebugString(const std::string &context, ArcIndex arc) const
Definition: max_flow.cc:318
Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator
Definition: max_flow.h:321
NodeIndex GetSourceNodeIndex() const
Definition: max_flow.h:346
FlowQuantity Flow(ArcIndex arc) const
Definition: max_flow.h:365
bool CheckRelabelPrecondition(NodeIndex node) const
Definition: max_flow.cc:307
std::vector< NodeIndex > bfs_queue_
Definition: max_flow.h:611
static const FlowQuantity kMaxFlowQuantity
Definition: max_flow.h:544
void SetArcFlow(ArcIndex arc, FlowQuantity new_flow)
Definition: max_flow.cc:209
void PushActiveNode(const NodeIndex &node)
Definition: max_flow.h:468
void SetUseTwoPhaseAlgorithm(bool value)
Definition: max_flow.h:418
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
Definition: max_flow.cc:225
void SetUseGlobalUpdate(bool value)
Definition: max_flow.h:414
void SetCapacityAndClearFlow(ArcIndex arc, FlowQuantity capacity)
Definition: max_flow.h:442
ZVector< NodeHeight > NodeHeightArray
Definition: max_flow.h:328
const Graph * graph() const
Definition: max_flow.h:338
std::vector< bool > node_in_bfs_queue_
Definition: max_flow.h:610
FlowQuantity Capacity(ArcIndex arc) const
Definition: max_flow.h:375
NodeIndex Head(ArcIndex arc) const
Definition: max_flow.h:532
NodeIndex Tail(ArcIndex arc) const
Definition: max_flow.h:533
Graph::IncomingArcIterator IncomingArcIterator
Definition: max_flow.h:322
void PushFlow(FlowQuantity flow, ArcIndex arc)
Definition: max_flow.cc:718
void ComputeReachableNodes(NodeIndex start, std::vector< NodeIndex > *result)
Definition: max_flow.cc:932
bool IsArcValid(ArcIndex arc) const
Definition: max_flow.cc:922
GenericMaxFlow(const Graph *graph, NodeIndex source, NodeIndex sink)
Definition: max_flow.cc:125
ZVector< ArcIndex > ArcIndexArray
Definition: max_flow.h:323
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
Definition: max_flow.cc:231
ArcIndex Opposite(ArcIndex arc) const
Definition: max_flow.cc:912
void ProcessNodeByHeight(bool value)
Definition: max_flow.h:421
bool IsActive(NodeIndex node) const
Definition: max_flow.h:437
bool IsArcDirect(ArcIndex arc) const
Definition: max_flow.cc:917
NodeIndex GetSinkNodeIndex() const
Definition: max_flow.h:349
void Discharge(NodeIndex node)
Definition: max_flow.cc:847
PriorityQueueWithRestrictedPush< NodeIndex, NodeHeight > active_node_by_height_
Definition: max_flow.h:597
MaxFlow(const StarGraph *graph, NodeIndex source, NodeIndex target)
Definition: max_flow.h:654
void Push(Element element, IntegerPriority priority)
Definition: max_flow.h:673
FlowQuantity Flow(ArcIndex arc) const
Definition: max_flow.cc:107
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
Definition: max_flow.cc:109
Status Solve(NodeIndex source, NodeIndex sink)
Definition: max_flow.cc:54
FlowQuantity OptimalFlow() const
Definition: max_flow.cc:105
ArcIndex AddArcWithCapacity(NodeIndex tail, NodeIndex head, FlowQuantity capacity)
Definition: max_flow.cc:27
FlowQuantity Capacity(ArcIndex arc) const
Definition: max_flow.cc:46
NodeIndex Head(ArcIndex arc) const
Definition: max_flow.cc:44
NodeIndex Tail(ArcIndex arc) const
Definition: max_flow.cc:42
void SetArcCapacity(ArcIndex arc, FlowQuantity capacity)
Definition: max_flow.cc:50
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
Definition: max_flow.cc:114
void Set(int64 index, T value)
Definition: zvector.h:88
int64 value
GurobiMPCallbackContext * context
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ListGraph Graph
Definition: graph.h:2360
int64 tail
int64 head
int64 capacity