OR-Tools  8.2
graph.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 //
15 //
16 // This file defines a generic graph interface on which most algorithms can be
17 // built and provides a few efficient implementations with a fast construction
18 // time. Its design is based on the experience acquired by the Operations
19 // Research team in their various graph algorithm implementations.
20 //
21 // The main ideas are:
22 // - Graph nodes and arcs are represented by integers.
23 // - Node or arc annotations (weight, cost, ...) are not part of the graph
24 // class, they can be stored outside in one or more arrays and can be easily
25 // retrieved using a node or arc as an index.
26 //
27 // Terminology:
28 // - An arc of a graph is directed and going from a tail node to a head node.
29 // - Some implementations also store 'reverse' arcs and can be used for
30 // undirected graph or flow-like algorithm.
31 // - A node or arc index is 'valid' if it represents a node or arc of
32 // the graph. The validity ranges are always [0, num_nodes()) for nodes and
33 // [0, num_arcs()) for forward arcs. Reverse arcs are elements of
34 // [-num_arcs(), 0) and are also considered valid by the implementations that
35 // store them.
36 //
37 // Provided implementations:
38 // - ListGraph<> for the simplest api. Also aliased to util::Graph.
39 // - StaticGraph<> for performance, but require calling Build(), see below
40 // - CompleteGraph<> if you need a fully connected graph
41 // - CompleteBipartiteGraph<> if you need a fully connected bipartite graph
42 // - ReverseArcListGraph<> to add reverse arcs to ListGraph<>
43 // - ReverseArcStaticGraph<> to add reverse arcs to StaticGraph<>
44 // - ReverseArcMixedGraph<> for a smaller memory footprint
45 //
46 // Utility classes & functions:
47 // - Permute() to permute an array according to a given permutation.
48 // - SVector<> vector with index range [-size(), size()) for ReverseArcGraph.
49 //
50 // Basic usage:
51 // typedef ListGraph<> Graph; // Choose a graph implementation.
52 // Graph graph;
53 // for (...) {
54 // graph.AddArc(tail, head);
55 // }
56 // ...
57 // for (int node = 0; node < graph.num_nodes(); ++node) {
58 // for (const int arc : graph.OutgoingArcs(node)) {
59 // head = graph.Head(arc);
60 // tail = node; // or graph.Tail(arc) which is fast but not as much.
61 // }
62 // }
63 //
64 // Iteration over the arcs touching a node:
65 //
66 // - OutgoingArcs(node): All the forward arcs leaving the node.
67 // - IncomingArcs(node): All the forward arcs arriving at the node.
68 //
69 // And two more involved ones:
70 //
71 // - OutgoingOrOppositeIncomingArcs(node): This returns both the forward arcs
72 // leaving the node (i.e. OutgoingArcs(node)) and the reverse arcs leaving the
73 // node (i.e. the opposite arcs of the ones returned by IncomingArcs(node)).
74 // - OppositeIncomingArcs(node): This returns the reverse arcs leaving the node.
75 //
76 // Note on iteration efficiency: When re-indexing the arcs it is not possible to
77 // have both the outgoing arcs and the incoming ones form a consecutive range.
78 //
79 // It is however possible to do so for the outgoing arcs and the opposite
80 // incoming arcs. It is why the OutgoingOrOppositeIncomingArcs() and
81 // OutgoingArcs() iterations are more efficient than the IncomingArcs() one.
82 //
83 // If you know the graph size in advance, this already set the number of nodes,
84 // reserve space for the arcs and check in DEBUG mode that you don't go over the
85 // bounds:
86 // Graph graph(num_nodes, arc_capacity);
87 //
88 // Storing and using node annotations:
89 // vector<bool> is_visited(graph.num_nodes(), false);
90 // ...
91 // for (int node = 0; node < graph.num_nodes(); ++node) {
92 // if (!is_visited[node]) ...
93 // }
94 //
95 // Storing and using arc annotations:
96 // vector<int> weights;
97 // for (...) {
98 // graph.AddArc(tail, head);
99 // weights.push_back(arc_weight);
100 // }
101 // ...
102 // for (const int arc : graph.OutgoingArcs(node)) {
103 // ... weights[arc] ...;
104 // }
105 //
106 // More efficient version:
107 // typedef StaticGraph<> Graph;
108 // Graph graph(num_nodes, arc_capacity); // Optional, but help memory usage.
109 // vector<int> weights;
110 // weights.reserve(arc_capacity); // Optional, but help memory usage.
111 // for (...) {
112 // graph.AddArc(tail, head);
113 // weights.push_back(arc_weight);
114 // }
115 // ...
116 // vector<Graph::ArcIndex> permutation;
117 // graph.Build(&permutation); // A static graph must be Build() before usage.
118 // Permute(permutation, &weights); // Build() may permute the arc index.
119 // ...
120 //
121 // Encoding an undirected graph: If you don't need arc annotation, then the best
122 // is to add two arcs for each edge (one in each direction) to a directed graph.
123 // Otherwise you can do the following.
124 //
125 // typedef ReverseArc... Graph;
126 // Graph graph;
127 // for (...) {
128 // graph.AddArc(tail, head); // or graph.AddArc(head, tail) but not both.
129 // edge_annotations.push_back(value);
130 // }
131 // ...
132 // for (const Graph::NodeIndex node : graph.AllNodes()) {
133 // for (const Graph::ArcIndex arc :
134 // graph.OutgoingOrOppositeIncomingArcs(node)) {
135 // destination = graph.Head(arc);
136 // annotation = edge_annotations[arc < 0 ? graph.OppositeArc(arc) : arc];
137 // }
138 // }
139 //
140 //
141 // Note: The graphs are primarily designed to be constructed first and then used
142 // because it covers most of the use cases. It is possible to extend the
143 // interface with more dynamicity (like removing arcs), but this is not done at
144 // this point. Note that a "dynamic" implementation will break some assumptions
145 // we make on what node or arc are valid and also on the indices returned by
146 // AddArc(). Some arguments for simplifying the interface at the cost of
147 // dynamicity are:
148 //
149 // - It is always possible to construct a static graph from a dynamic one
150 // before calling a complex algo.
151 // - If you really need a dynamic graph, maybe it is better to compute a graph
152 // property incrementally rather than calling an algorithm that starts from
153 // scratch each time.
154 
155 #ifndef UTIL_GRAPH_GRAPH_H_
156 #define UTIL_GRAPH_GRAPH_H_
157 
158 #include <algorithm>
159 #include <cstddef>
160 #include <cstdlib>
161 #include <limits>
162 #include <new>
163 #include <vector>
164 
165 #include "absl/debugging/leak_check.h"
167 #include "ortools/base/logging.h"
168 #include "ortools/base/macros.h"
169 #include "ortools/graph/iterators.h"
170 
171 namespace util {
172 
173 // Forward declaration.
174 template <typename T>
175 class SVector;
176 
177 // Base class of all Graphs implemented here. The default value for the graph
178 // index types is int32 since allmost all graphs that fit into memory do not
179 // need bigger indices.
180 //
181 // Note: The type can be unsigned, except for the graphs with reverse arcs
182 // where the ArcIndexType must be signed, but not necessarly the NodeIndexType.
183 template <typename NodeIndexType = int32, typename ArcIndexType = int32,
184  bool HasReverseArcs = false>
185 class BaseGraph {
186  public:
187  // Typedef so you can use Graph::NodeIndex and Graph::ArcIndex to be generic
188  // but also to improve the readability of your code. We also recommend
189  // that you define a typedef ... Graph; for readability.
190  typedef NodeIndexType NodeIndex;
191  typedef ArcIndexType ArcIndex;
192 
194  : num_nodes_(0),
195  node_capacity_(0),
196  num_arcs_(0),
197  arc_capacity_(0),
198  const_capacities_(false) {}
199  virtual ~BaseGraph() {}
200 
201  // Returns the number of valid nodes in the graph.
202  NodeIndexType num_nodes() const { return num_nodes_; }
203 
204  // Returns the number of valid arcs in the graph.
205  ArcIndexType num_arcs() const { return num_arcs_; }
206 
207  // Allows nice range-based for loop:
208  // for (const NodeIndex node : graph.AllNodes()) { ... }
209  // for (const ArcIndex arc : graph.AllForwardArcs()) { ... }
212 
213  // Returns true if the given node is a valid node of the graph.
214  bool IsNodeValid(NodeIndexType node) const {
215  return node >= 0 && node < num_nodes_;
216  }
217 
218  // Returns true if the given arc is a valid arc of the graph.
219  // Note that the arc validity range changes for graph with reverse arcs.
220  bool IsArcValid(ArcIndexType arc) const {
221  return (HasReverseArcs ? -num_arcs_ : 0) <= arc && arc < num_arcs_;
222  }
223 
224  // Capacity reserved for future nodes, always >= num_nodes_.
225  NodeIndexType node_capacity() const;
226 
227  // Capacity reserved for future arcs, always >= num_arcs_.
228  ArcIndexType arc_capacity() const;
229 
230  // Changes the graph capacities. The functions will fail in debug mode if:
231  // - const_capacities_ is true.
232  // - A valid node does not fall into the new node range.
233  // - A valid arc does not fall into the new arc range.
234  // In non-debug mode, const_capacities_ is ignored and nothing will happen
235  // if the new capacity value for the arcs or the nodes is too small.
236  virtual void ReserveNodes(NodeIndexType bound) {
239  if (bound <= num_nodes_) return;
241  }
242  virtual void ReserveArcs(ArcIndexType bound) {
245  if (bound <= num_arcs_) return;
247  }
248  void Reserve(NodeIndexType node_capacity, ArcIndexType arc_capacity) {
251  }
252 
253  // FreezeCapacities() makes any future attempt to change the graph capacities
254  // crash in DEBUG mode.
256 
257  // Constants that will never be a valid node or arc.
258  // They are the maximum possible node and arc capacity.
259  static const NodeIndexType kNilNode;
260  static const ArcIndexType kNilArc;
261 
262  // TODO(user): remove the public functions below. They are just here during
263  // the transition from the old ebert_graph api to this new graph api.
264  template <typename A, typename B>
265  void GroupForwardArcsByFunctor(const A& a, B* b) {
266  LOG(FATAL) << "Not supported";
267  }
268  ArcIndexType max_end_arc_index() const { return arc_capacity_; }
269 
270  protected:
271  // Functions commented when defined because they are implementation details.
272  void ComputeCumulativeSum(std::vector<ArcIndexType>* v);
274  std::vector<ArcIndexType>* start,
275  std::vector<ArcIndexType>* permutation);
276 
277  NodeIndexType num_nodes_;
278  NodeIndexType node_capacity_;
279  ArcIndexType num_arcs_;
280  ArcIndexType arc_capacity_;
282 };
283 
284 // Basic graph implementation without reverse arc. This class also serves as a
285 // documentation for the generic graph interface (minus the part related to
286 // reverse arcs).
287 //
288 // This implementation uses a linked list and compared to StaticGraph:
289 // - Is a bit faster to construct (if the arcs are not ordered by tail).
290 // - Does not require calling Build().
291 // - Has slower outgoing arc iteration.
292 // - Uses more memory: ArcIndexType * node_capacity()
293 // + (ArcIndexType + NodeIndexType) * arc_capacity().
294 // - Has an efficient Tail() but need an extra NodeIndexType/arc memory for it.
295 // - Never changes the initial arc index returned by AddArc().
296 //
297 template <typename NodeIndexType = int32, typename ArcIndexType = int32>
298 class ListGraph : public BaseGraph<NodeIndexType, ArcIndexType, false> {
300  using Base::arc_capacity_;
302  using Base::node_capacity_;
303  using Base::num_arcs_;
304  using Base::num_nodes_;
305 
306  public:
307  using Base::IsArcValid;
309 
310  // Reserve space for the graph at construction and do not allow it to grow
311  // beyond that, see FreezeCapacities(). This constructor also makes any nodes
312  // in [0, num_nodes) valid.
313  ListGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity) {
314  this->Reserve(num_nodes, arc_capacity);
315  this->FreezeCapacities();
316  this->AddNode(num_nodes - 1);
317  }
318 
319  // If node is not a valid node, sets num_nodes_ to node + 1 so that the given
320  // node becomes valid. It will fail in DEBUG mode if the capacities are fixed
321  // and the new node is out of range.
322  void AddNode(NodeIndexType node);
323 
324  // Adds an arc to the graph and returns its current index which will always
325  // be num_arcs() - 1. It will also automatically call AddNode(tail)
326  // and AddNode(head). It will fail in DEBUG mode if the capacities
327  // are fixed and this cause the graph to grow beyond them.
328  //
329  // Note: Self referencing arcs and duplicate arcs are supported.
330  ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head);
331 
332  // Some graph implementations need to be finalized with Build() before they
333  // can be used. After Build() is called, the arc indices (which had been the
334  // return values of previous AddArc() calls) may change: the new index of
335  // former arc #i will be stored in permutation[i] if #i is smaller than
336  // permutation.size() or will be unchanged otherwise. If you don't care about
337  // these, just call the simple no-output version Build().
338  //
339  // Note that some implementations become immutable after calling Build().
340  void Build() { Build(nullptr); }
341  void Build(std::vector<ArcIndexType>* permutation);
342 
343  // Do not use directly.
344  class OutgoingArcIterator;
345  class OutgoingHeadIterator;
346 
347  // Graph jargon: the "degree" of a node is its number of arcs. The out-degree
348  // is the number of outgoing arcs. The in-degree is the number of incoming
349  // arcs, and is only available for some graph implementations, below.
350  //
351  // ListGraph<>::OutDegree() works in O(degree).
352  ArcIndexType OutDegree(NodeIndexType node) const;
353 
354  // Allows to iterate over the forward arcs that verify Tail(arc) == node.
355  // This is meant to be used as:
356  // for (const ArcIndex arc : graph.OutgoingArcs(node)) { ... }
358 
359  // Advanced usage. Same as OutgoingArcs(), but allows to restart the iteration
360  // from an already known outgoing arc of the given node.
362  NodeIndexType node, ArcIndexType from) const;
363 
364  // This loops over the heads of the OutgoingArcs(node). It is just a more
365  // convenient way to achieve this. Moreover this interface is used by some
366  // graph algorithms.
367  BeginEndWrapper<OutgoingHeadIterator> operator[](NodeIndexType node) const;
368 
369  // Returns the tail/head of a valid arc.
370  NodeIndexType Tail(ArcIndexType arc) const;
371  NodeIndexType Head(ArcIndexType arc) const;
372 
373  void ReserveNodes(NodeIndexType bound) override;
374  void ReserveArcs(ArcIndexType bound) override;
375 
376  private:
377  std::vector<ArcIndexType> start_;
378  std::vector<ArcIndexType> next_;
379  std::vector<NodeIndexType> head_;
380  std::vector<NodeIndexType> tail_;
381 };
382 
383 // Most efficient implementation of a graph without reverse arcs:
384 // - Build() needs to be called after the arc and node have been added.
385 // - The graph is really compact memory wise:
386 // ArcIndexType * node_capacity() + 2 * NodeIndexType * arc_capacity(),
387 // but when Build() is called it uses a temporary extra space of
388 // ArcIndexType * arc_capacity().
389 // - The construction is really fast.
390 //
391 // NOTE(user): if the need arises for very-well compressed graphs, we could
392 // shave NodeIndexType * arc_capacity() off the permanent memory requirement
393 // with a similar class that doesn't support Tail(), i.e.
394 // StaticGraphWithoutTail<>. This almost corresponds to a past implementation
395 // of StaticGraph<> @CL 116144340.
396 template <typename NodeIndexType = int32, typename ArcIndexType = int32>
397 class StaticGraph : public BaseGraph<NodeIndexType, ArcIndexType, false> {
399  using Base::arc_capacity_;
401  using Base::node_capacity_;
402  using Base::num_arcs_;
403  using Base::num_nodes_;
404 
405  public:
406  using Base::IsArcValid;
407  StaticGraph() : is_built_(false), arc_in_order_(true), last_tail_seen_(0) {}
408  StaticGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
409  : is_built_(false), arc_in_order_(true), last_tail_seen_(0) {
410  this->Reserve(num_nodes, arc_capacity);
411  this->FreezeCapacities();
412  this->AddNode(num_nodes - 1);
413  }
414 
415  // Do not use directly. See instead the arc iteration functions below.
416  class OutgoingArcIterator;
417 
418  NodeIndexType Head(ArcIndexType arc) const;
419  NodeIndexType Tail(ArcIndexType arc) const;
420  ArcIndexType OutDegree(NodeIndexType node) const; // Work in O(1).
423  NodeIndexType node, ArcIndexType from) const;
424 
425  // This loops over the heads of the OutgoingArcs(node). It is just a more
426  // convenient way to achieve this. Moreover this interface is used by some
427  // graph algorithms.
428  BeginEndWrapper<NodeIndexType const*> operator[](NodeIndexType node) const;
429 
430  void ReserveNodes(NodeIndexType bound) override;
431  void ReserveArcs(ArcIndexType bound) override;
432  void AddNode(NodeIndexType node);
433  ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head);
434 
435  void Build() { Build(nullptr); }
436  void Build(std::vector<ArcIndexType>* permutation);
437 
438  private:
439  ArcIndexType DirectArcLimit(NodeIndexType node) const {
440  DCHECK(is_built_);
441  DCHECK(Base::IsNodeValid(node));
442  return node + 1 < num_nodes_ ? start_[node + 1] : num_arcs_;
443  }
444 
445  bool is_built_;
446  bool arc_in_order_;
447  NodeIndexType last_tail_seen_;
448  std::vector<ArcIndexType> start_;
449  std::vector<NodeIndexType> head_;
450  std::vector<NodeIndexType> tail_;
451 };
452 
453 // Extends the ListGraph by also storing the reverse arcs.
454 // This class also documents the Graph interface related to reverse arc.
455 // - NodeIndexType can be unsigned, but ArcIndexType must be signed.
456 // - It has most of the same advantanges and disadvantages as ListGraph.
457 // - It takes 2 * ArcIndexType * node_capacity()
458 // + 2 * (ArcIndexType + NodeIndexType) * arc_capacity() memory.
459 template <typename NodeIndexType = int32, typename ArcIndexType = int32>
461  : public BaseGraph<NodeIndexType, ArcIndexType, true> {
463  using Base::arc_capacity_;
465  using Base::node_capacity_;
466  using Base::num_arcs_;
467  using Base::num_nodes_;
468 
469  public:
472  ReverseArcListGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity) {
473  this->Reserve(num_nodes, arc_capacity);
474  this->FreezeCapacities();
475  this->AddNode(num_nodes - 1);
476  }
477 
478  // Returns the opposite arc of a given arc. That is the reverse arc of the
479  // given forward arc or the forward arc of a given reverse arc.
480  ArcIndexType OppositeArc(ArcIndexType arc) const;
481 
482  // Do not use directly. See instead the arc iteration functions below.
483  class OutgoingOrOppositeIncomingArcIterator;
484  class OppositeIncomingArcIterator;
485  class IncomingArcIterator;
486  class OutgoingArcIterator;
487  class OutgoingHeadIterator;
488 
489  // ReverseArcListGraph<>::OutDegree() and ::InDegree() work in O(degree).
490  ArcIndexType OutDegree(NodeIndexType node) const;
491  ArcIndexType InDegree(NodeIndexType node) const;
492 
493  // Arc iterations functions over the arcs touching a node (see the top-level
494  // comment for the different types). To be used as follows:
495  // for (const Graph::ArcIndex arc : IterationFunction(node)) { ... }
496  //
497  // The StartingFrom() version are similar, but restart the iteration from a
498  // given arc position (which must be valid in the iteration context).
502  OutgoingOrOppositeIncomingArcs(NodeIndexType node) const;
504  NodeIndexType node) const;
506  NodeIndexType node, ArcIndexType from) const;
508  NodeIndexType node, ArcIndexType from) const;
511  ArcIndexType from) const;
513  NodeIndexType node, ArcIndexType from) const;
514 
515  // This loops over the heads of the OutgoingArcs(node). It is just a more
516  // convenient way to achieve this. Moreover this interface is used by some
517  // graph algorithms.
519 
520  NodeIndexType Head(ArcIndexType arc) const;
521  NodeIndexType Tail(ArcIndexType arc) const;
522 
523  void ReserveNodes(NodeIndexType bound) override;
524  void ReserveArcs(ArcIndexType bound) override;
525  void AddNode(NodeIndexType node);
526  ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head);
527 
528  void Build() { Build(nullptr); }
529  void Build(std::vector<ArcIndexType>* permutation);
530 
531  private:
532  std::vector<ArcIndexType> start_;
533  std::vector<ArcIndexType> reverse_start_;
534  SVector<ArcIndexType> next_;
536 };
537 
538 // StaticGraph with reverse arc.
539 // - NodeIndexType can be unsigned, but ArcIndexType must be signed.
540 // - It has most of the same advantanges and disadvantages as StaticGraph.
541 // - It takes 2 * ArcIndexType * node_capacity()
542 // + 2 * (ArcIndexType + NodeIndexType) * arc_capacity() memory.
543 // - If the ArcIndexPermutation is needed, then an extra ArcIndexType *
544 // arc_capacity() is needed for it.
545 // - The reverse arcs from a node are sorted by head (so we could add a log()
546 // time lookup function).
547 template <typename NodeIndexType = int32, typename ArcIndexType = int32>
549  : public BaseGraph<NodeIndexType, ArcIndexType, true> {
551  using Base::arc_capacity_;
553  using Base::node_capacity_;
554  using Base::num_arcs_;
555  using Base::num_nodes_;
556 
557  public:
558  using Base::IsArcValid;
559  ReverseArcStaticGraph() : is_built_(false) {}
560  ReverseArcStaticGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
561  : is_built_(false) {
562  this->Reserve(num_nodes, arc_capacity);
563  this->FreezeCapacities();
564  this->AddNode(num_nodes - 1);
565  }
566 
567  // Deprecated.
568  class OutgoingOrOppositeIncomingArcIterator;
569  class OppositeIncomingArcIterator;
570  class IncomingArcIterator;
571  class OutgoingArcIterator;
572 
573  // ReverseArcStaticGraph<>::OutDegree() and ::InDegree() work in O(1).
574  ArcIndexType OutDegree(NodeIndexType node) const;
575  ArcIndexType InDegree(NodeIndexType node) const;
576 
580  OutgoingOrOppositeIncomingArcs(NodeIndexType node) const;
582  NodeIndexType node) const;
584  NodeIndexType node, ArcIndexType from) const;
586  NodeIndexType node, ArcIndexType from) const;
589  ArcIndexType from) const;
591  NodeIndexType node, ArcIndexType from) const;
592 
593  // This loops over the heads of the OutgoingArcs(node). It is just a more
594  // convenient way to achieve this. Moreover this interface is used by some
595  // graph algorithms.
596  BeginEndWrapper<NodeIndexType const*> operator[](NodeIndexType node) const;
597 
598  ArcIndexType OppositeArc(ArcIndexType arc) const;
599  // TODO(user): support Head() and Tail() before Build(), like StaticGraph<>.
600  NodeIndexType Head(ArcIndexType arc) const;
601  NodeIndexType Tail(ArcIndexType arc) const;
602 
603  void ReserveArcs(ArcIndexType bound) override;
604  void AddNode(NodeIndexType node);
605  ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head);
606 
607  void Build() { Build(nullptr); }
608  void Build(std::vector<ArcIndexType>* permutation);
609 
610  private:
611  ArcIndexType DirectArcLimit(NodeIndexType node) const {
612  DCHECK(is_built_);
613  DCHECK(Base::IsNodeValid(node));
614  return node + 1 < num_nodes_ ? start_[node + 1] : num_arcs_;
615  }
616  ArcIndexType ReverseArcLimit(NodeIndexType node) const {
617  DCHECK(is_built_);
618  DCHECK(Base::IsNodeValid(node));
619  return node + 1 < num_nodes_ ? reverse_start_[node + 1] : 0;
620  }
621 
622  bool is_built_;
623  std::vector<ArcIndexType> start_;
624  std::vector<ArcIndexType> reverse_start_;
625  SVector<NodeIndexType> head_;
626  SVector<ArcIndexType> opposite_;
627 };
628 
629 // This graph is a mix between the ReverseArcListGraph and the
630 // ReverseArcStaticGraph. It uses less memory:
631 // - It takes 2 * ArcIndexType * node_capacity()
632 // + (2 * NodeIndexType + ArcIndexType) * arc_capacity() memory.
633 // - If the ArcIndexPermutation is needed, then an extra ArcIndexType *
634 // arc_capacity() is needed for it.
635 template <typename NodeIndexType = int32, typename ArcIndexType = int32>
637  : public BaseGraph<NodeIndexType, ArcIndexType, true> {
639  using Base::arc_capacity_;
641  using Base::node_capacity_;
642  using Base::num_arcs_;
643  using Base::num_nodes_;
644 
645  public:
646  using Base::IsArcValid;
647  ReverseArcMixedGraph() : is_built_(false) {}
648  ReverseArcMixedGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
649  : is_built_(false) {
650  this->Reserve(num_nodes, arc_capacity);
651  this->FreezeCapacities();
652  this->AddNode(num_nodes - 1);
653  }
654 
655  // Deprecated.
656  class OutgoingOrOppositeIncomingArcIterator;
657  class OppositeIncomingArcIterator;
658  class IncomingArcIterator;
659  class OutgoingArcIterator;
660 
661  ArcIndexType OutDegree(NodeIndexType node) const; // O(1)
662  ArcIndexType InDegree(NodeIndexType node) const; // O(in-degree)
663 
667  OutgoingOrOppositeIncomingArcs(NodeIndexType node) const;
669  NodeIndexType node) const;
671  NodeIndexType node, ArcIndexType from) const;
673  NodeIndexType node, ArcIndexType from) const;
676  ArcIndexType from) const;
678  NodeIndexType node, ArcIndexType from) const;
679 
680  // This loops over the heads of the OutgoingArcs(node). It is just a more
681  // convenient way to achieve this. Moreover this interface is used by some
682  // graph algorithms.
683  BeginEndWrapper<NodeIndexType const*> operator[](NodeIndexType node) const;
684 
685  ArcIndexType OppositeArc(ArcIndexType arc) const;
686  // TODO(user): support Head() and Tail() before Build(), like StaticGraph<>.
687  NodeIndexType Head(ArcIndexType arc) const;
688  NodeIndexType Tail(ArcIndexType arc) const;
689 
690  void ReserveArcs(ArcIndexType bound) override;
691  void AddNode(NodeIndexType node);
692  ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head);
693 
694  void Build() { Build(nullptr); }
695  void Build(std::vector<ArcIndexType>* permutation);
696 
697  private:
698  ArcIndexType DirectArcLimit(NodeIndexType node) const {
699  DCHECK(is_built_);
700  DCHECK(Base::IsNodeValid(node));
701  return node + 1 < num_nodes_ ? start_[node + 1] : num_arcs_;
702  }
703 
704  bool is_built_;
705  std::vector<ArcIndexType> start_;
706  std::vector<ArcIndexType> reverse_start_;
707  std::vector<ArcIndexType> next_;
708  SVector<NodeIndexType> head_;
709 };
710 
711 // Permutes the elements of array_to_permute: element #i will be moved to
712 // position permutation[i]. permutation must be either empty (in which case
713 // nothing happens), or a permutation of [0, permutation.size()).
714 //
715 // The algorithm is fast but need extra memory for a copy of the permuted part
716 // of array_to_permute.
717 //
718 // TODO(user): consider slower but more memory efficient implementations that
719 // follow the cycles of the permutation and use a bitmap to indicate what has
720 // been permuted or to mark the beginning of each cycle.
721 
722 // Some compiler do not know typeof(), so we have to use this extra function
723 // internally.
724 template <class IntVector, class Array, class ElementType>
725 void PermuteWithExplicitElementType(const IntVector& permutation,
726  Array* array_to_permute,
727  ElementType unused) {
728  std::vector<ElementType> temp(permutation.size());
729  for (int i = 0; i < permutation.size(); ++i) {
730  temp[i] = (*array_to_permute)[i];
731  }
732  for (int i = 0; i < permutation.size(); ++i) {
733  (*array_to_permute)[permutation[i]] = temp[i];
734  }
735 }
736 
737 template <class IntVector, class Array>
738 void Permute(const IntVector& permutation, Array* array_to_permute) {
739  if (permutation.empty()) {
740  return;
741  }
742  PermuteWithExplicitElementType(permutation, array_to_permute,
743  (*array_to_permute)[0]);
744 }
745 
746 // We need a specialization for vector<bool>, because the default code uses
747 // (*array_to_permute)[0] as ElementType, which isn't 'bool' in that case.
748 template <class IntVector>
749 void Permute(const IntVector& permutation,
750  std::vector<bool>* array_to_permute) {
751  if (permutation.empty()) {
752  return;
753  }
754  bool unused = false;
755  PermuteWithExplicitElementType(permutation, array_to_permute, unused);
756 }
757 
758 // A vector-like class where valid indices are in [- size_, size_) and reserved
759 // indices for future growth are in [- capacity_, capacity_). It is used to hold
760 // arc related information for graphs with reverse arcs.
761 // It supports only up to 2^31-1 elements, for compactness. If you ever need
762 // more, consider using templates for the size/capacity integer types.
763 //
764 // Sample usage:
765 //
766 // SVector<int> v;
767 // v.grow(left_value, right_value);
768 // v.resize(10);
769 // v.clear();
770 // v.swap(new_v);
771 // std:swap(v[i], v[~i]);
772 template <typename T>
773 class SVector {
774  public:
775  SVector() : base_(nullptr), size_(0), capacity_(0) {}
776 
778 
779  // Copy constructor and assignment operator.
780  SVector(const SVector& other) : SVector() { *this = other; }
781  SVector& operator=(const SVector& other) {
782  if (capacity_ < other.size_) {
784  // NOTE(user): Alternatively, our capacity could inherit from the other
785  // vector's capacity, which can be (much) greater than its size.
786  capacity_ = other.size_;
787  base_ = Allocate(capacity_);
788  CHECK(base_ != nullptr);
789  base_ += capacity_;
790  } else { // capacity_ >= other.size
791  clear();
792  }
793  // Perform the actual copy of the payload.
794  size_ = other.size_;
795  for (int i = -size_; i < size_; ++i) {
796  new (base_ + i) T(other.base_[i]);
797  }
798  return *this;
799  }
800 
801  // Move constructor and move assignment operator.
802  SVector(SVector&& other) : SVector() { swap(other); }
804  // NOTE(user): We could just swap() and let the other's destruction take
805  // care of the clean-up, but it is probably less bug-prone to perform the
806  // destruction immediately.
808  swap(other);
809  return *this;
810  }
811 
812  T& operator[](int n) {
813  DCHECK_LT(n, size_);
814  DCHECK_GE(n, -size_);
815  return base_[n];
816  }
817 
818  const T& operator[](int n) const {
819  DCHECK_LT(n, size_);
820  DCHECK_GE(n, -size_);
821  return base_[n];
822  }
823 
824  void resize(int n) {
825  reserve(n);
826  for (int i = -n; i < -size_; ++i) {
827  new (base_ + i) T();
828  }
829  for (int i = size_; i < n; ++i) {
830  new (base_ + i) T();
831  }
832  for (int i = -size_; i < -n; ++i) {
833  base_[i].~T();
834  }
835  for (int i = n; i < size_; ++i) {
836  base_[i].~T();
837  }
838  size_ = n;
839  }
840 
841  void clear() { resize(0); }
842 
843  T* data() const { return base_; }
844 
845  void swap(SVector<T>& x) {
846  std::swap(base_, x.base_);
847  std::swap(size_, x.size_);
848  std::swap(capacity_, x.capacity_);
849  }
850 
851  void reserve(int n) {
852  DCHECK_GE(n, 0);
853  DCHECK_LE(n, max_size());
854  if (n > capacity_) {
855  const int new_capacity = std::min(n, max_size());
856  T* new_storage = Allocate(new_capacity);
857  CHECK(new_storage != nullptr);
858  T* new_base = new_storage + new_capacity;
859  // TODO(user): in C++17 we could use std::uninitialized_move instead
860  // of this loop.
861  for (int i = -size_; i < size_; ++i) {
862  new (new_base + i) T(std::move(base_[i]));
863  }
864  int saved_size = size_;
866  size_ = saved_size;
867  base_ = new_base;
868  capacity_ = new_capacity;
869  }
870  }
871 
872  // NOTE(user): This doesn't currently support movable-only objects, but we
873  // could fix that.
874  void grow(const T& left = T(), const T& right = T()) {
875  if (size_ == capacity_) {
876  // We have to copy the elements because they are allowed to be element of
877  // *this.
878  T left_copy(left); // NOLINT
879  T right_copy(right); // NOLINT
880  reserve(NewCapacity(1));
881  new (base_ + size_) T(right_copy);
882  new (base_ - size_ - 1) T(left_copy);
883  ++size_;
884  } else {
885  new (base_ + size_) T(right);
886  new (base_ - size_ - 1) T(left);
887  ++size_;
888  }
889  }
890 
891  int size() const { return size_; }
892 
893  int capacity() const { return capacity_; }
894 
895  int max_size() const { return std::numeric_limits<int>::max(); }
896 
898  if (base_ == nullptr) return;
899  clear();
900  if (capacity_ > 0) {
901  free(base_ - capacity_);
902  }
903  capacity_ = 0;
904  base_ = nullptr;
905  }
906 
907  private:
908  T* Allocate(int capacity) const {
909  return absl::IgnoreLeak(
910  static_cast<T*>(malloc(2LL * capacity * sizeof(T))));
911  }
912 
913  int NewCapacity(int delta) {
914  // TODO(user): check validity.
915  double candidate = 1.3 * static_cast<double>(capacity_);
916  if (candidate > static_cast<double>(max_size())) {
917  candidate = static_cast<double>(max_size());
918  }
919  int new_capacity = static_cast<int>(candidate);
920  if (new_capacity > capacity_ + delta) {
921  return new_capacity;
922  }
923  return capacity_ + delta;
924  }
925 
926  T* base_; // Pointer to the element of index 0.
927  int size_; // Valid index are [- size_, size_).
928  int capacity_; // Reserved index are [- capacity_, capacity_).
929 };
930 
931 // BaseGraph implementation ----------------------------------------------------
932 
933 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
934 IntegerRange<NodeIndexType>
936  return IntegerRange<NodeIndexType>(0, num_nodes_);
937 }
938 
939 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
942  return IntegerRange<ArcIndexType>(0, num_arcs_);
943 }
944 
945 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
946 const NodeIndexType
949 
950 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
951 const ArcIndexType
954 
955 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
956 NodeIndexType
958  // TODO(user): Is it needed? remove completely? return the real capacities
959  // at the cost of having a different implementation for each graphs?
960  return node_capacity_ > num_nodes_ ? node_capacity_ : num_nodes_;
961 }
962 
963 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
964 ArcIndexType
966  // TODO(user): Same questions as the ones in node_capacity().
967  return arc_capacity_ > num_arcs_ ? arc_capacity_ : num_arcs_;
968 }
969 
970 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
971 void BaseGraph<NodeIndexType, ArcIndexType,
972  HasReverseArcs>::FreezeCapacities() {
973  // TODO(user): Only define this in debug mode at the cost of having a lot
974  // of ifndef NDEBUG all over the place? remove the function completely ?
975  const_capacities_ = true;
976  node_capacity_ = std::max(node_capacity_, num_nodes_);
977  arc_capacity_ = std::max(arc_capacity_, num_arcs_);
978 }
979 
980 // Computes the cummulative sum of the entry in v. We only use it with
981 // in/out degree distribution, hence the Check() at the end.
982 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
984  ComputeCumulativeSum(std::vector<ArcIndexType>* v) {
985  ArcIndexType sum = 0;
986  for (int i = 0; i < num_nodes_; ++i) {
987  ArcIndexType temp = (*v)[i];
988  (*v)[i] = sum;
989  sum += temp;
990  }
991  DCHECK(sum == num_arcs_);
992 }
993 
994 // Given the tail of arc #i in (*head)[i] and the head of arc #i in (*head)[~i]
995 // - Reorder the arc by increasing tail.
996 // - Put the head of the new arc #i in (*head)[i].
997 // - Put in start[i] the index of the first arc with tail >= i.
998 // - Update "permutation" to reflect the change, unless it is NULL.
999 template <typename NodeIndexType, typename ArcIndexType, bool HasReverseArcs>
1002  std::vector<ArcIndexType>* start,
1003  std::vector<ArcIndexType>* permutation) {
1004  // Computes the outgoing degree of each nodes and check if we need to permute
1005  // something or not. Note that the tails are currently stored in the positive
1006  // range of the SVector head.
1007  start->assign(num_nodes_, 0);
1008  int last_tail_seen = 0;
1009  bool permutation_needed = false;
1010  for (int i = 0; i < num_arcs_; ++i) {
1011  NodeIndexType tail = (*head)[i];
1012  if (!permutation_needed) {
1013  permutation_needed = tail < last_tail_seen;
1014  last_tail_seen = tail;
1015  }
1016  (*start)[tail]++;
1017  }
1018  ComputeCumulativeSum(start);
1019 
1020  // Abort early if we do not need the permutation: we only need to put the
1021  // heads in the positive range.
1022  if (!permutation_needed) {
1023  for (int i = 0; i < num_arcs_; ++i) {
1024  (*head)[i] = (*head)[~i];
1025  }
1026  if (permutation != nullptr) {
1027  permutation->clear();
1028  }
1029  return;
1030  }
1031 
1032  // Computes the forward arc permutation.
1033  // Note that this temporarily alters the start vector.
1034  std::vector<ArcIndexType> perm(num_arcs_);
1035  for (int i = 0; i < num_arcs_; ++i) {
1036  perm[i] = (*start)[(*head)[i]]++;
1037  }
1038 
1039  // Restore in (*start)[i] the index of the first arc with tail >= i.
1040  for (int i = num_nodes_ - 1; i > 0; --i) {
1041  (*start)[i] = (*start)[i - 1];
1042  }
1043  (*start)[0] = 0;
1044 
1045  // Permutes the head into their final position in head.
1046  // We do not need the tails anymore at this point.
1047  for (int i = 0; i < num_arcs_; ++i) {
1048  (*head)[perm[i]] = (*head)[~i];
1049  }
1050  if (permutation != nullptr) {
1051  permutation->swap(perm);
1052  }
1053 }
1054 
1055 // ---------------------------------------------------------------------------
1056 // Macros to wrap old style iteration into the new range-based for loop style.
1057 // ---------------------------------------------------------------------------
1058 
1059 // The parameters are:
1060 // - c: the class name.
1061 // - t: the iteration type (Outgoing, Incoming, OutgoingOrOppositeIncoming
1062 // or OppositeIncoming).
1063 // - e: the "end" ArcIndexType.
1064 #define DEFINE_RANGE_BASED_ARC_ITERATION(c, t, e) \
1065  template <typename NodeIndexType, typename ArcIndexType> \
1066  BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \
1067  c<NodeIndexType, ArcIndexType>::t##Arcs(NodeIndexType node) const { \
1068  return BeginEndWrapper<t##ArcIterator>(t##ArcIterator(*this, node), \
1069  t##ArcIterator(*this, node, e)); \
1070  } \
1071  template <typename NodeIndexType, typename ArcIndexType> \
1072  BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \
1073  c<NodeIndexType, ArcIndexType>::t##ArcsStartingFrom( \
1074  NodeIndexType node, ArcIndexType from) const { \
1075  return BeginEndWrapper<t##ArcIterator>(t##ArcIterator(*this, node, from), \
1076  t##ArcIterator(*this, node, e)); \
1077  }
1078 
1079 // Adapt our old iteration style to support range-based for loops. Add typedefs
1080 // required by std::iterator_traits.
1081 #define DEFINE_STL_ITERATOR_FUNCTIONS(iterator_class_name) \
1082  using iterator_category = std::input_iterator_tag; \
1083  using difference_type = ptrdiff_t; \
1084  using pointer = const ArcIndexType*; \
1085  using reference = const ArcIndexType&; \
1086  using value_type = ArcIndexType; \
1087  bool operator!=(const iterator_class_name& other) const { \
1088  return this->index_ != other.index_; \
1089  } \
1090  bool operator==(const iterator_class_name& other) const { \
1091  return this->index_ == other.index_; \
1092  } \
1093  ArcIndexType operator*() const { return this->Index(); } \
1094  void operator++() { this->Next(); }
1095 
1096 // ListGraph implementation ----------------------------------------------------
1097 
1099 
1100 template <typename NodeIndexType, typename ArcIndexType>
1105  OutgoingHeadIterator(*this, node),
1106  OutgoingHeadIterator(*this, node, Base::kNilArc));
1107 }
1108 
1109 template <typename NodeIndexType, typename ArcIndexType>
1111  ArcIndexType arc) const {
1112  DCHECK(IsArcValid(arc));
1113  return tail_[arc];
1114 }
1115 
1116 template <typename NodeIndexType, typename ArcIndexType>
1118  ArcIndexType arc) const {
1119  DCHECK(IsArcValid(arc));
1120  return head_[arc];
1121 }
1122 
1123 template <typename NodeIndexType, typename ArcIndexType>
1125  NodeIndexType node) const {
1126  ArcIndexType degree(0);
1127  for (auto arc ABSL_ATTRIBUTE_UNUSED : OutgoingArcs(node)) ++degree;
1128  return degree;
1129 }
1130 
1131 template <typename NodeIndexType, typename ArcIndexType>
1133  if (node < num_nodes_) return;
1134  DCHECK(!const_capacities_ || node < node_capacity_);
1135  num_nodes_ = node + 1;
1136  start_.resize(num_nodes_, Base::kNilArc);
1137 }
1138 
1139 template <typename NodeIndexType, typename ArcIndexType>
1141  NodeIndexType tail, NodeIndexType head) {
1142  DCHECK_GE(tail, 0);
1143  DCHECK_GE(head, 0);
1144  AddNode(tail > head ? tail : head);
1145  head_.push_back(head);
1146  tail_.push_back(tail);
1147  next_.push_back(start_[tail]);
1148  start_[tail] = num_arcs_;
1149  DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1150  return num_arcs_++;
1151 }
1152 
1153 template <typename NodeIndexType, typename ArcIndexType>
1155  Base::ReserveNodes(bound);
1156  if (bound <= num_nodes_) return;
1157  start_.reserve(bound);
1158 }
1159 
1160 template <typename NodeIndexType, typename ArcIndexType>
1162  Base::ReserveArcs(bound);
1163  if (bound <= num_arcs_) return;
1164  head_.reserve(bound);
1165  tail_.reserve(bound);
1166  next_.reserve(bound);
1167 }
1168 
1169 template <typename NodeIndexType, typename ArcIndexType>
1171  std::vector<ArcIndexType>* permutation) {
1172  if (permutation != nullptr) {
1173  permutation->clear();
1174  }
1175 }
1176 
1177 template <typename NodeIndexType, typename ArcIndexType>
1178 class ListGraph<NodeIndexType, ArcIndexType>::OutgoingArcIterator {
1179  public:
1180  OutgoingArcIterator(const ListGraph& graph, NodeIndexType node)
1181  : graph_(graph), index_(graph.start_[node]) {
1182  DCHECK(graph.IsNodeValid(node));
1183  }
1184  OutgoingArcIterator(const ListGraph& graph, NodeIndexType node,
1185  ArcIndexType arc)
1186  : graph_(graph), index_(arc) {
1187  DCHECK(graph.IsNodeValid(node));
1188  DCHECK(arc == Base::kNilArc || graph.Tail(arc) == node);
1189  }
1190  bool Ok() const { return index_ != Base::kNilArc; }
1191  ArcIndexType Index() const { return index_; }
1192  void Next() {
1193  DCHECK(Ok());
1194  index_ = graph_.next_[index_];
1195  }
1196 
1198 
1199  private:
1200  const ListGraph& graph_;
1201  ArcIndexType index_;
1202 };
1203 
1204 template <typename NodeIndexType, typename ArcIndexType>
1205 class ListGraph<NodeIndexType, ArcIndexType>::OutgoingHeadIterator {
1206  public:
1207  using iterator_category = std::input_iterator_tag;
1208  using difference_type = ptrdiff_t;
1209  using pointer = const NodeIndexType*;
1210  using reference = const NodeIndexType&;
1211  using value_type = NodeIndexType;
1212 
1213  OutgoingHeadIterator(const ListGraph& graph, NodeIndexType node)
1214  : graph_(graph), index_(graph.start_[node]) {
1215  DCHECK(graph.IsNodeValid(node));
1216  }
1217  OutgoingHeadIterator(const ListGraph& graph, NodeIndexType node,
1218  ArcIndexType arc)
1219  : graph_(graph), index_(arc) {
1220  DCHECK(graph.IsNodeValid(node));
1221  DCHECK(arc == Base::kNilArc || graph.Tail(arc) == node);
1222  }
1223  bool Ok() const { return index_ != Base::kNilArc; }
1224  NodeIndexType Index() const { return graph_.Head(index_); }
1225  void Next() {
1226  DCHECK(Ok());
1227  index_ = graph_.next_[index_];
1228  }
1229 
1231  const typename ListGraph<
1232  NodeIndexType, ArcIndexType>::OutgoingHeadIterator& other) const {
1233  return index_ != other.index_;
1234  }
1235  NodeIndexType operator*() const { return Index(); }
1236  void operator++() { Next(); }
1237 
1238  private:
1239  const ListGraph& graph_;
1240  ArcIndexType index_;
1241 };
1242 
1243 // StaticGraph implementation --------------------------------------------------
1244 
1245 DEFINE_RANGE_BASED_ARC_ITERATION(StaticGraph, Outgoing, DirectArcLimit(node));
1246 
1247 template <typename NodeIndexType, typename ArcIndexType>
1251  head_.data() + start_[node], head_.data() + DirectArcLimit(node));
1252 }
1253 
1254 template <typename NodeIndexType, typename ArcIndexType>
1256  NodeIndexType node) const {
1257  return DirectArcLimit(node) - start_[node];
1258 }
1259 
1260 template <typename NodeIndexType, typename ArcIndexType>
1262  NodeIndexType bound) {
1263  Base::ReserveNodes(bound);
1264  if (bound <= num_nodes_) return;
1265  start_.reserve(bound);
1266 }
1267 
1268 template <typename NodeIndexType, typename ArcIndexType>
1270  Base::ReserveArcs(bound);
1271  if (bound <= num_arcs_) return;
1272  head_.reserve(bound);
1273  tail_.reserve(bound);
1274 }
1275 
1276 template <typename NodeIndexType, typename ArcIndexType>
1278  if (node < num_nodes_) return;
1279  DCHECK(!const_capacities_ || node < node_capacity_) << node;
1280  num_nodes_ = node + 1;
1281  start_.resize(num_nodes_, 0);
1282 }
1283 
1284 template <typename NodeIndexType, typename ArcIndexType>
1286  NodeIndexType tail, NodeIndexType head) {
1287  DCHECK_GE(tail, 0);
1288  DCHECK_GE(head, 0);
1289  DCHECK(!is_built_);
1290  AddNode(tail > head ? tail : head);
1291  if (arc_in_order_) {
1292  if (tail >= last_tail_seen_) {
1293  start_[tail]++;
1294  last_tail_seen_ = tail;
1295  } else {
1296  arc_in_order_ = false;
1297  }
1298  }
1299  tail_.push_back(tail);
1300  head_.push_back(head);
1301  DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1302  return num_arcs_++;
1303 }
1304 
1305 template <typename NodeIndexType, typename ArcIndexType>
1307  ArcIndexType arc) const {
1308  DCHECK(IsArcValid(arc));
1309  return tail_[arc];
1310 }
1311 
1312 template <typename NodeIndexType, typename ArcIndexType>
1314  ArcIndexType arc) const {
1315  DCHECK(IsArcValid(arc));
1316  return head_[arc];
1317 }
1318 
1319 // Implementation details: A reader may be surprised that we do many passes
1320 // into the data where things could be done in one pass. For instance, during
1321 // construction, we store the edges first, and then do a second pass at the
1322 // end to compute the degree distribution.
1323 //
1324 // This is because it is a lot more efficient cache-wise to do it this way.
1325 // This was determined by various experiments, but can also be understood:
1326 // - during repetitive call to AddArc() a client usually accesses various
1327 // areas of memory, and there is no reason to polute the cache with
1328 // possibly random access to degree[i].
1329 // - When the degrees are needed, we compute them in one go, maximizing the
1330 // chance of cache hit during the computation.
1331 template <typename NodeIndexType, typename ArcIndexType>
1333  std::vector<ArcIndexType>* permutation) {
1334  DCHECK(!is_built_);
1335  if (is_built_) return;
1336  is_built_ = true;
1337  node_capacity_ = num_nodes_;
1338  arc_capacity_ = num_arcs_;
1339  this->FreezeCapacities();
1340 
1341  // If Arc are in order, start_ already contains the degree distribution.
1342  if (arc_in_order_) {
1343  if (permutation != nullptr) {
1344  permutation->clear();
1345  }
1346  this->ComputeCumulativeSum(&start_);
1347  return;
1348  }
1349 
1350  // Computes outgoing degree of each nodes. We have to clear start_, since
1351  // at least the first arc was processed with arc_in_order_ == true.
1352  start_.assign(num_nodes_, 0);
1353  for (int i = 0; i < num_arcs_; ++i) {
1354  start_[tail_[i]]++;
1355  }
1356  this->ComputeCumulativeSum(&start_);
1357 
1358  // Computes the forward arc permutation.
1359  // Note that this temporarily alters the start_ vector.
1360  std::vector<ArcIndexType> perm(num_arcs_);
1361  for (int i = 0; i < num_arcs_; ++i) {
1362  perm[i] = start_[tail_[i]]++;
1363  }
1364 
1365  // We use "tail_" (which now contains rubbish) to permute "head_" faster.
1366  CHECK_EQ(tail_.size(), num_arcs_);
1367  tail_.swap(head_);
1368  for (int i = 0; i < num_arcs_; ++i) {
1369  head_[perm[i]] = tail_[i];
1370  }
1371 
1372  if (permutation != nullptr) {
1373  permutation->swap(perm);
1374  }
1375 
1376  // Restore in start_[i] the index of the first arc with tail >= i.
1377  for (int i = num_nodes_ - 1; i > 0; --i) {
1378  start_[i] = start_[i - 1];
1379  }
1380  start_[0] = 0;
1381 
1382  // Recompute the correct tail_ vector
1383  for (const NodeIndexType node : Base::AllNodes()) {
1384  for (const ArcIndexType arc : OutgoingArcs(node)) {
1385  tail_[arc] = node;
1386  }
1387  }
1388 }
1389 
1390 template <typename NodeIndexType, typename ArcIndexType>
1391 class StaticGraph<NodeIndexType, ArcIndexType>::OutgoingArcIterator {
1392  public:
1393  OutgoingArcIterator(const StaticGraph& graph, NodeIndexType node)
1394  : index_(graph.start_[node]), limit_(graph.DirectArcLimit(node)) {}
1395  OutgoingArcIterator(const StaticGraph& graph, NodeIndexType node,
1396  ArcIndexType arc)
1397  : index_(arc), limit_(graph.DirectArcLimit(node)) {
1398  DCHECK_GE(arc, graph.start_[node]);
1399  }
1400 
1401  bool Ok() const { return index_ < limit_; }
1402  ArcIndexType Index() const { return index_; }
1403  void Next() {
1404  DCHECK(Ok());
1405  index_++;
1406  }
1407 
1408  // Note(user): we lose a bit by returning a BeginEndWrapper<> on top of
1409  // this iterator rather than a simple IntegerRange<> on the arc indices.
1410  // On my computer: around 420M arcs/sec instead of 440M arcs/sec.
1411  //
1412  // However, it is slightly more consistent to do it this way, and we don't
1413  // have two different codes depending on the way a client iterates on the
1414  // arcs.
1416 
1417  private:
1418  ArcIndexType index_;
1419  const ArcIndexType limit_;
1420 };
1421 
1422 // ReverseArcListGraph implementation ------------------------------------------
1423 
1427  OutgoingOrOppositeIncoming, Base::kNilArc);
1429  Base::kNilArc);
1430 
1431 template <typename NodeIndexType, typename ArcIndexType>
1433  NodeIndexType, ArcIndexType>::OutgoingHeadIterator>
1435  NodeIndexType node) const {
1437  OutgoingHeadIterator(*this, node),
1438  OutgoingHeadIterator(*this, node, Base::kNilArc));
1439 }
1440 
1441 template <typename NodeIndexType, typename ArcIndexType>
1443  NodeIndexType node) const {
1444  ArcIndexType degree(0);
1445  for (auto arc ABSL_ATTRIBUTE_UNUSED : OutgoingArcs(node)) ++degree;
1446  return degree;
1447 }
1448 
1449 template <typename NodeIndexType, typename ArcIndexType>
1451  NodeIndexType node) const {
1452  ArcIndexType degree(0);
1453  for (auto arc ABSL_ATTRIBUTE_UNUSED : OppositeIncomingArcs(node)) ++degree;
1454  return degree;
1455 }
1456 
1457 template <typename NodeIndexType, typename ArcIndexType>
1459  ArcIndexType arc) const {
1460  DCHECK(IsArcValid(arc));
1461  return ~arc;
1462 }
1463 
1464 template <typename NodeIndexType, typename ArcIndexType>
1466  ArcIndexType arc) const {
1467  DCHECK(IsArcValid(arc));
1468  return head_[arc];
1469 }
1470 
1471 template <typename NodeIndexType, typename ArcIndexType>
1473  ArcIndexType arc) const {
1474  return head_[OppositeArc(arc)];
1475 }
1476 
1477 template <typename NodeIndexType, typename ArcIndexType>
1479  NodeIndexType bound) {
1480  Base::ReserveNodes(bound);
1481  if (bound <= num_nodes_) return;
1482  start_.reserve(bound);
1483  reverse_start_.reserve(bound);
1484 }
1485 
1486 template <typename NodeIndexType, typename ArcIndexType>
1488  ArcIndexType bound) {
1489  Base::ReserveArcs(bound);
1490  if (bound <= num_arcs_) return;
1491  head_.reserve(bound);
1492  next_.reserve(bound);
1493 }
1494 
1495 template <typename NodeIndexType, typename ArcIndexType>
1497  NodeIndexType node) {
1498  if (node < num_nodes_) return;
1499  DCHECK(!const_capacities_ || node < node_capacity_);
1500  num_nodes_ = node + 1;
1501  start_.resize(num_nodes_, Base::kNilArc);
1502  reverse_start_.resize(num_nodes_, Base::kNilArc);
1503 }
1504 
1505 template <typename NodeIndexType, typename ArcIndexType>
1507  NodeIndexType tail, NodeIndexType head) {
1508  DCHECK_GE(tail, 0);
1509  DCHECK_GE(head, 0);
1510  AddNode(tail > head ? tail : head);
1511  head_.grow(tail, head);
1512  next_.grow(reverse_start_[head], start_[tail]);
1513  start_[tail] = num_arcs_;
1514  reverse_start_[head] = ~num_arcs_;
1515  DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1516  return num_arcs_++;
1517 }
1518 
1519 template <typename NodeIndexType, typename ArcIndexType>
1521  std::vector<ArcIndexType>* permutation) {
1522  if (permutation != nullptr) {
1523  permutation->clear();
1524  }
1525 }
1526 
1527 template <typename NodeIndexType, typename ArcIndexType>
1528 class ReverseArcListGraph<NodeIndexType, ArcIndexType>::OutgoingArcIterator {
1529  public:
1530  OutgoingArcIterator(const ReverseArcListGraph& graph, NodeIndexType node)
1531  : graph_(graph), index_(graph.start_[node]) {
1532  DCHECK(graph.IsNodeValid(node));
1533  }
1534  OutgoingArcIterator(const ReverseArcListGraph& graph, NodeIndexType node,
1535  ArcIndexType arc)
1536  : graph_(graph), index_(arc) {
1537  DCHECK(graph.IsNodeValid(node));
1538  DCHECK(arc == Base::kNilArc || arc >= 0);
1539  DCHECK(arc == Base::kNilArc || graph.Tail(arc) == node);
1540  }
1541  bool Ok() const { return index_ != Base::kNilArc; }
1542  ArcIndexType Index() const { return index_; }
1543  void Next() {
1544  DCHECK(Ok());
1545  index_ = graph_.next_[index_];
1546  }
1547 
1549 
1550  private:
1551  const ReverseArcListGraph& graph_;
1552  ArcIndexType index_;
1553 };
1554 
1555 template <typename NodeIndexType, typename ArcIndexType>
1556 class ReverseArcListGraph<NodeIndexType,
1557  ArcIndexType>::OppositeIncomingArcIterator {
1558  public:
1560  NodeIndexType node)
1561  : graph_(graph), index_(graph.reverse_start_[node]) {
1562  DCHECK(graph.IsNodeValid(node));
1563  }
1565  NodeIndexType node, ArcIndexType arc)
1566  : graph_(graph), index_(arc) {
1567  DCHECK(graph.IsNodeValid(node));
1568  DCHECK(arc == Base::kNilArc || arc < 0);
1569  DCHECK(arc == Base::kNilArc || graph.Tail(arc) == node);
1570  }
1571 
1572  bool Ok() const { return index_ != Base::kNilArc; }
1573  ArcIndexType Index() const { return index_; }
1574  void Next() {
1575  DCHECK(Ok());
1576  index_ = graph_.next_[index_];
1577  }
1578 
1580 
1581  protected:
1583  ArcIndexType index_;
1584 };
1585 
1586 template <typename NodeIndexType, typename ArcIndexType>
1587 class ReverseArcListGraph<NodeIndexType, ArcIndexType>::IncomingArcIterator
1588  : public OppositeIncomingArcIterator {
1589  public:
1590  IncomingArcIterator(const ReverseArcListGraph& graph, NodeIndexType node)
1591  : OppositeIncomingArcIterator(graph, node) {}
1592  IncomingArcIterator(const ReverseArcListGraph& graph, NodeIndexType node,
1593  ArcIndexType arc)
1595  graph, node,
1596  arc == Base::kNilArc ? Base::kNilArc : graph.OppositeArc(arc)) {}
1597 
1598  // We overwrite OppositeIncomingArcIterator::Index() here.
1599  ArcIndexType Index() const {
1600  return this->index_ == Base::kNilArc
1601  ? Base::kNilArc
1602  : this->graph_.OppositeArc(this->index_);
1603  }
1604 
1606 };
1607 
1608 template <typename NodeIndexType, typename ArcIndexType>
1609 class ReverseArcListGraph<NodeIndexType,
1610  ArcIndexType>::OutgoingOrOppositeIncomingArcIterator {
1611  public:
1613  NodeIndexType node)
1614  : graph_(graph), index_(graph.reverse_start_[node]), node_(node) {
1615  DCHECK(graph.IsNodeValid(node));
1616  if (index_ == Base::kNilArc) index_ = graph.start_[node];
1617  }
1619  NodeIndexType node, ArcIndexType arc)
1620  : graph_(graph), index_(arc), node_(node) {
1621  DCHECK(graph.IsNodeValid(node));
1622  DCHECK(arc == Base::kNilArc || graph.Tail(arc) == node);
1623  }
1624 
1625  bool Ok() const { return index_ != Base::kNilArc; }
1626  ArcIndexType Index() const { return index_; }
1627  void Next() {
1628  DCHECK(Ok());
1629  if (index_ < 0) {
1630  index_ = graph_.next_[index_];
1631  if (index_ == Base::kNilArc) {
1632  index_ = graph_.start_[node_];
1633  }
1634  } else {
1635  index_ = graph_.next_[index_];
1636  }
1637  }
1638 
1640 
1641  private:
1642  const ReverseArcListGraph& graph_;
1643  ArcIndexType index_;
1644  const NodeIndexType node_;
1645 };
1646 
1647 template <typename NodeIndexType, typename ArcIndexType>
1648 class ReverseArcListGraph<NodeIndexType, ArcIndexType>::OutgoingHeadIterator {
1649  public:
1650  OutgoingHeadIterator(const ReverseArcListGraph& graph, NodeIndexType node)
1651  : graph_(&graph), index_(graph.start_[node]) {
1652  DCHECK(graph.IsNodeValid(node));
1653  }
1654  OutgoingHeadIterator(const ReverseArcListGraph& graph, NodeIndexType node,
1655  ArcIndexType arc)
1656  : graph_(&graph), index_(arc) {
1657  DCHECK(graph.IsNodeValid(node));
1658  DCHECK(arc == Base::kNilArc || arc >= 0);
1659  DCHECK(arc == Base::kNilArc || graph.Tail(arc) == node);
1660  }
1661  bool Ok() const { return index_ != Base::kNilArc; }
1662  ArcIndexType Index() const { return graph_->Head(index_); }
1663  void Next() {
1664  DCHECK(Ok());
1665  index_ = graph_->next_[index_];
1666  }
1667 
1669 
1670  private:
1671  const ReverseArcListGraph* graph_;
1672  ArcIndexType index_;
1673 };
1674 
1675 // ReverseArcStaticGraph implementation ----------------------------------------
1676 
1678  DirectArcLimit(node));
1680  ReverseArcLimit(node));
1682  OutgoingOrOppositeIncoming,
1683  DirectArcLimit(node));
1685  ReverseArcLimit(node));
1686 
1687 template <typename NodeIndexType, typename ArcIndexType>
1689  NodeIndexType node) const {
1690  return DirectArcLimit(node) - start_[node];
1691 }
1692 
1693 template <typename NodeIndexType, typename ArcIndexType>
1695  NodeIndexType node) const {
1696  return ReverseArcLimit(node) - reverse_start_[node];
1697 }
1698 
1699 template <typename NodeIndexType, typename ArcIndexType>
1702  NodeIndexType node) const {
1704  head_.data() + start_[node], head_.data() + DirectArcLimit(node));
1705 }
1706 
1707 template <typename NodeIndexType, typename ArcIndexType>
1709  ArcIndexType arc) const {
1710  DCHECK(is_built_);
1711  DCHECK(IsArcValid(arc));
1712  return opposite_[arc];
1713 }
1714 
1715 template <typename NodeIndexType, typename ArcIndexType>
1717  ArcIndexType arc) const {
1718  DCHECK(is_built_);
1719  DCHECK(IsArcValid(arc));
1720  return head_[arc];
1721 }
1722 
1723 template <typename NodeIndexType, typename ArcIndexType>
1725  ArcIndexType arc) const {
1726  DCHECK(is_built_);
1727  return head_[OppositeArc(arc)];
1728 }
1729 
1730 template <typename NodeIndexType, typename ArcIndexType>
1732  ArcIndexType bound) {
1733  Base::ReserveArcs(bound);
1734  if (bound <= num_arcs_) return;
1735  head_.reserve(bound);
1736 }
1737 
1738 template <typename NodeIndexType, typename ArcIndexType>
1740  NodeIndexType node) {
1741  if (node < num_nodes_) return;
1742  DCHECK(!const_capacities_ || node < node_capacity_);
1743  num_nodes_ = node + 1;
1744 }
1745 
1746 template <typename NodeIndexType, typename ArcIndexType>
1748  NodeIndexType tail, NodeIndexType head) {
1749  DCHECK_GE(tail, 0);
1750  DCHECK_GE(head, 0);
1751  AddNode(tail > head ? tail : head);
1752 
1753  // We inverse head and tail here because it is more convenient this way
1754  // during build time, see Build().
1755  head_.grow(head, tail);
1756  DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1757  return num_arcs_++;
1758 }
1759 
1760 template <typename NodeIndexType, typename ArcIndexType>
1762  std::vector<ArcIndexType>* permutation) {
1763  DCHECK(!is_built_);
1764  if (is_built_) return;
1765  is_built_ = true;
1766  node_capacity_ = num_nodes_;
1767  arc_capacity_ = num_arcs_;
1768  this->FreezeCapacities();
1769  this->BuildStartAndForwardHead(&head_, &start_, permutation);
1770 
1771  // Computes incoming degree of each nodes.
1772  reverse_start_.assign(num_nodes_, 0);
1773  for (int i = 0; i < num_arcs_; ++i) {
1774  reverse_start_[head_[i]]++;
1775  }
1776  this->ComputeCumulativeSum(&reverse_start_);
1777 
1778  // Computes the reverse arcs of the forward arcs.
1779  // Note that this sort the reverse arcs with the same tail by head.
1780  opposite_.reserve(num_arcs_);
1781  for (int i = 0; i < num_arcs_; ++i) {
1782  // TODO(user): the 0 is wasted here, but minor optimisation.
1783  opposite_.grow(0, reverse_start_[head_[i]]++ - num_arcs_);
1784  }
1785 
1786  // Computes in reverse_start_ the start index of the reverse arcs.
1787  for (int i = num_nodes_ - 1; i > 0; --i) {
1788  reverse_start_[i] = reverse_start_[i - 1] - num_arcs_;
1789  }
1790  if (num_nodes_ != 0) {
1791  reverse_start_[0] = -num_arcs_;
1792  }
1793 
1794  // Fill reverse arc information.
1795  for (int i = 0; i < num_arcs_; ++i) {
1796  opposite_[opposite_[i]] = i;
1797  }
1798  for (const NodeIndexType node : Base::AllNodes()) {
1799  for (const ArcIndexType arc : OutgoingArcs(node)) {
1800  head_[opposite_[arc]] = node;
1801  }
1802  }
1803 }
1804 
1805 template <typename NodeIndexType, typename ArcIndexType>
1806 class ReverseArcStaticGraph<NodeIndexType, ArcIndexType>::OutgoingArcIterator {
1807  public:
1808  OutgoingArcIterator(const ReverseArcStaticGraph& graph, NodeIndexType node)
1809  : index_(graph.start_[node]), limit_(graph.DirectArcLimit(node)) {}
1810  OutgoingArcIterator(const ReverseArcStaticGraph& graph, NodeIndexType node,
1811  ArcIndexType arc)
1812  : index_(arc), limit_(graph.DirectArcLimit(node)) {
1813  DCHECK_GE(arc, graph.start_[node]);
1814  }
1815 
1816  bool Ok() const { return index_ < limit_; }
1817  ArcIndexType Index() const { return index_; }
1818  void Next() {
1819  DCHECK(Ok());
1820  index_++;
1821  }
1822 
1823  // TODO(user): we lose a bit by returning a BeginEndWrapper<> on top of this
1824  // iterator rather than a simple IntegerRange on the arc indices.
1826 
1827  private:
1828  ArcIndexType index_;
1829  const ArcIndexType limit_;
1830 };
1831 
1832 template <typename NodeIndexType, typename ArcIndexType>
1833 class ReverseArcStaticGraph<NodeIndexType,
1834  ArcIndexType>::OppositeIncomingArcIterator {
1835  public:
1837  NodeIndexType node)
1838  : graph_(graph),
1839  limit_(graph.ReverseArcLimit(node)),
1840  index_(graph.reverse_start_[node]) {
1841  DCHECK(graph.IsNodeValid(node));
1842  DCHECK_LE(index_, limit_);
1843  }
1845  NodeIndexType node, ArcIndexType arc)
1846  : graph_(graph), limit_(graph.ReverseArcLimit(node)), index_(arc) {
1847  DCHECK(graph.IsNodeValid(node));
1848  DCHECK_GE(index_, graph.reverse_start_[node]);
1849  DCHECK_LE(index_, limit_);
1850  }
1851 
1852  bool Ok() const { return index_ < limit_; }
1853  ArcIndexType Index() const { return index_; }
1854  void Next() {
1855  DCHECK(Ok());
1856  index_++;
1857  }
1858 
1860 
1861  protected:
1863  const ArcIndexType limit_;
1864  ArcIndexType index_;
1865 };
1866 
1867 template <typename NodeIndexType, typename ArcIndexType>
1868 class ReverseArcStaticGraph<NodeIndexType, ArcIndexType>::IncomingArcIterator
1869  : public OppositeIncomingArcIterator {
1870  public:
1871  IncomingArcIterator(const ReverseArcStaticGraph& graph, NodeIndexType node)
1872  : OppositeIncomingArcIterator(graph, node) {}
1873  IncomingArcIterator(const ReverseArcStaticGraph& graph, NodeIndexType node,
1874  ArcIndexType arc)
1875  : OppositeIncomingArcIterator(graph, node,
1876  arc == graph.ReverseArcLimit(node)
1877  ? graph.ReverseArcLimit(node)
1878  : graph.OppositeArc(arc)) {}
1879 
1880  ArcIndexType Index() const {
1881  return this->index_ == this->limit_
1882  ? this->limit_
1883  : this->graph_.OppositeArc(this->index_);
1884  }
1885 
1887 };
1888 
1889 template <typename NodeIndexType, typename ArcIndexType>
1891  NodeIndexType, ArcIndexType>::OutgoingOrOppositeIncomingArcIterator {
1892  public:
1894  NodeIndexType node)
1895  : index_(graph.reverse_start_[node]),
1896  first_limit_(graph.ReverseArcLimit(node)),
1897  next_start_(graph.start_[node]),
1898  limit_(graph.DirectArcLimit(node)) {
1899  if (index_ == first_limit_) index_ = next_start_;
1900  DCHECK(graph.IsNodeValid(node));
1901  DCHECK((index_ < first_limit_) || (index_ >= next_start_));
1902  }
1904  NodeIndexType node, ArcIndexType arc)
1905  : index_(arc),
1906  first_limit_(graph.ReverseArcLimit(node)),
1907  next_start_(graph.start_[node]),
1908  limit_(graph.DirectArcLimit(node)) {
1909  DCHECK(graph.IsNodeValid(node));
1910  DCHECK((index_ >= graph.reverse_start_[node] && index_ < first_limit_) ||
1911  (index_ >= next_start_));
1912  }
1913 
1914  ArcIndexType Index() const { return index_; }
1915  bool Ok() const { return index_ < limit_; }
1916  void Next() {
1917  DCHECK(Ok());
1918  index_++;
1919  if (index_ == first_limit_) {
1920  index_ = next_start_;
1921  }
1922  }
1923 
1925 
1926  private:
1927  ArcIndexType index_;
1928  const ArcIndexType first_limit_;
1929  const ArcIndexType next_start_;
1930  const ArcIndexType limit_;
1931 };
1932 
1933 // ReverseArcMixedGraph implementation -----------------------------------------
1934 
1936  DirectArcLimit(node));
1939  OutgoingOrOppositeIncoming,
1940  DirectArcLimit(node));
1942  Base::kNilArc);
1943 
1944 template <typename NodeIndexType, typename ArcIndexType>
1946  NodeIndexType node) const {
1947  return DirectArcLimit(node) - start_[node];
1948 }
1949 
1950 template <typename NodeIndexType, typename ArcIndexType>
1952  NodeIndexType node) const {
1953  ArcIndexType degree(0);
1954  for (auto arc ABSL_ATTRIBUTE_UNUSED : OppositeIncomingArcs(node)) ++degree;
1955  return degree;
1956 }
1957 
1958 template <typename NodeIndexType, typename ArcIndexType>
1961  NodeIndexType node) const {
1963  head_.data() + start_[node], head_.data() + DirectArcLimit(node));
1964 }
1965 
1966 template <typename NodeIndexType, typename ArcIndexType>
1968  ArcIndexType arc) const {
1969  DCHECK(IsArcValid(arc));
1970  return ~arc;
1971 }
1972 
1973 template <typename NodeIndexType, typename ArcIndexType>
1975  ArcIndexType arc) const {
1976  DCHECK(is_built_);
1977  DCHECK(IsArcValid(arc));
1978  return head_[arc];
1979 }
1980 
1981 template <typename NodeIndexType, typename ArcIndexType>
1983  ArcIndexType arc) const {
1984  DCHECK(is_built_);
1985  return head_[OppositeArc(arc)];
1986 }
1987 
1988 template <typename NodeIndexType, typename ArcIndexType>
1990  ArcIndexType bound) {
1991  Base::ReserveArcs(bound);
1992  if (bound <= num_arcs_) return;
1993  head_.reserve(bound);
1994 }
1995 
1996 template <typename NodeIndexType, typename ArcIndexType>
1998  NodeIndexType node) {
1999  if (node < num_nodes_) return;
2000  DCHECK(!const_capacities_ || node < node_capacity_);
2001  num_nodes_ = node + 1;
2002 }
2003 
2004 template <typename NodeIndexType, typename ArcIndexType>
2006  NodeIndexType tail, NodeIndexType head) {
2007  DCHECK_GE(tail, 0);
2008  DCHECK_GE(head, 0);
2009  AddNode(tail > head ? tail : head);
2010 
2011  // We inverse head and tail here because it is more convenient this way
2012  // during build time, see Build().
2013  head_.grow(head, tail);
2014  DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
2015  return num_arcs_++;
2016 }
2017 
2018 template <typename NodeIndexType, typename ArcIndexType>
2020  std::vector<ArcIndexType>* permutation) {
2021  DCHECK(!is_built_);
2022  if (is_built_) return;
2023  is_built_ = true;
2024  node_capacity_ = num_nodes_;
2025  arc_capacity_ = num_arcs_;
2026  this->FreezeCapacities();
2027  this->BuildStartAndForwardHead(&head_, &start_, permutation);
2028 
2029  // Fill tails.
2030  for (const NodeIndexType node : Base::AllNodes()) {
2031  for (const ArcIndexType arc : OutgoingArcs(node)) {
2032  head_[~arc] = node;
2033  }
2034  }
2035 
2036  // Fill information for iterating over reverse arcs.
2037  reverse_start_.assign(num_nodes_, Base::kNilArc);
2038  next_.reserve(num_arcs_);
2039  for (const ArcIndexType arc : Base::AllForwardArcs()) {
2040  next_.push_back(reverse_start_[Head(arc)]);
2041  reverse_start_[Head(arc)] = -next_.size();
2042  }
2043 }
2044 
2045 template <typename NodeIndexType, typename ArcIndexType>
2046 class ReverseArcMixedGraph<NodeIndexType, ArcIndexType>::OutgoingArcIterator {
2047  public:
2048  OutgoingArcIterator(const ReverseArcMixedGraph& graph, NodeIndexType node)
2049  : index_(graph.start_[node]), limit_(graph.DirectArcLimit(node)) {}
2050  OutgoingArcIterator(const ReverseArcMixedGraph& graph, NodeIndexType node,
2051  ArcIndexType arc)
2052  : index_(arc), limit_(graph.DirectArcLimit(node)) {
2053  DCHECK_GE(arc, graph.start_[node]);
2054  }
2055 
2056  bool Ok() const { return index_ < limit_; }
2057  ArcIndexType Index() const { return index_; }
2058  void Next() {
2059  DCHECK(Ok());
2060  index_++;
2061  }
2062 
2063  // TODO(user): we lose a bit by returning a BeginEndWrapper<> on top of this
2064  // iterator rather than a simple IntegerRange on the arc indices.
2066 
2067  private:
2068  ArcIndexType index_;
2069  const ArcIndexType limit_;
2070 };
2071 
2072 template <typename NodeIndexType, typename ArcIndexType>
2073 class ReverseArcMixedGraph<NodeIndexType,
2074  ArcIndexType>::OppositeIncomingArcIterator {
2075  public:
2077  NodeIndexType node)
2078  : graph_(&graph) {
2079  DCHECK(graph.is_built_);
2080  DCHECK(graph.IsNodeValid(node));
2081  index_ = graph.reverse_start_[node];
2082  }
2084  NodeIndexType node, ArcIndexType arc)
2085  : graph_(&graph), index_(arc) {
2086  DCHECK(graph.is_built_);
2087  DCHECK(graph.IsNodeValid(node));
2088  DCHECK(arc == Base::kNilArc || arc < 0);
2089  DCHECK(arc == Base::kNilArc || graph.Tail(arc) == node);
2090  }
2091  bool Ok() const { return index_ != Base::kNilArc; }
2092  ArcIndexType Index() const { return index_; }
2093  void Next() {
2094  DCHECK(Ok());
2095  index_ = graph_->next_[~index_];
2096  }
2097 
2099 
2100  protected:
2102  ArcIndexType index_;
2103 };
2104 
2105 template <typename NodeIndexType, typename ArcIndexType>
2106 class ReverseArcMixedGraph<NodeIndexType, ArcIndexType>::IncomingArcIterator
2107  : public OppositeIncomingArcIterator {
2108  public:
2109  IncomingArcIterator(const ReverseArcMixedGraph& graph, NodeIndexType node)
2110  : OppositeIncomingArcIterator(graph, node) {}
2111  IncomingArcIterator(const ReverseArcMixedGraph& graph, NodeIndexType node,
2112  ArcIndexType arc)
2114  graph, node, arc == Base::kNilArc ? arc : graph.OppositeArc(arc)) {}
2115  ArcIndexType Index() const {
2116  return this->index_ == Base::kNilArc
2117  ? Base::kNilArc
2118  : this->graph_->OppositeArc(this->index_);
2119  }
2120 
2122 };
2123 
2124 template <typename NodeIndexType, typename ArcIndexType>
2126  NodeIndexType, ArcIndexType>::OutgoingOrOppositeIncomingArcIterator {
2127  public:
2129  NodeIndexType node)
2130  : graph_(&graph) {
2131  limit_ = graph.DirectArcLimit(node); // also DCHECKs node and is_built_.
2132  index_ = graph.reverse_start_[node];
2133  restart_ = graph.start_[node];
2134  if (index_ == Base::kNilArc) {
2135  index_ = restart_;
2136  }
2137  }
2139  NodeIndexType node, ArcIndexType arc)
2140  : graph_(&graph) {
2141  limit_ = graph.DirectArcLimit(node);
2142  index_ = arc;
2143  restart_ = graph.start_[node];
2144  DCHECK(arc == Base::kNilArc || arc == limit_ || graph.Tail(arc) == node);
2145  }
2146  bool Ok() const {
2147  // Note that we always have limit_ <= Base::kNilArc.
2148  return index_ < limit_;
2149  }
2150  ArcIndexType Index() const { return index_; }
2151  void Next() {
2152  DCHECK(Ok());
2153  if (index_ < 0) {
2154  index_ = graph_->next_[graph_->OppositeArc(index_)];
2155  if (index_ == Base::kNilArc) {
2156  index_ = restart_;
2157  }
2158  } else {
2159  index_++;
2160  }
2161  }
2162 
2164 
2165  private:
2166  const ReverseArcMixedGraph* graph_;
2167  ArcIndexType index_;
2168  ArcIndexType restart_;
2169  ArcIndexType limit_;
2170 };
2171 
2172 // CompleteGraph implementation ------------------------------------------------
2173 // Nodes and arcs are implicit and not stored.
2174 
2175 template <typename NodeIndexType = int32, typename ArcIndexType = int32>
2176 class CompleteGraph : public BaseGraph<NodeIndexType, ArcIndexType, false> {
2178  using Base::arc_capacity_;
2180  using Base::node_capacity_;
2181  using Base::num_arcs_;
2182  using Base::num_nodes_;
2183 
2184  public:
2185  // Builds a complete graph with num_nodes nodes.
2186  explicit CompleteGraph(NodeIndexType num_nodes) {
2187  this->Reserve(num_nodes, num_nodes * num_nodes);
2188  this->FreezeCapacities();
2189  num_nodes_ = num_nodes;
2190  num_arcs_ = num_nodes * num_nodes;
2191  }
2192 
2193  NodeIndexType Head(ArcIndexType arc) const;
2194  NodeIndexType Tail(ArcIndexType arc) const;
2195  ArcIndexType OutDegree(NodeIndexType node) const;
2196  IntegerRange<ArcIndexType> OutgoingArcs(NodeIndexType node) const;
2198  ArcIndexType from) const;
2199  IntegerRange<NodeIndexType> operator[](NodeIndexType node) const;
2200 };
2201 
2202 template <typename NodeIndexType, typename ArcIndexType>
2204  ArcIndexType arc) const {
2205  DCHECK(this->IsArcValid(arc));
2206  return arc % num_nodes_;
2207 }
2208 
2209 template <typename NodeIndexType, typename ArcIndexType>
2211  ArcIndexType arc) const {
2212  DCHECK(this->IsArcValid(arc));
2213  return arc / num_nodes_;
2214 }
2215 
2216 template <typename NodeIndexType, typename ArcIndexType>
2218  NodeIndexType node) const {
2219  return num_nodes_;
2220 }
2221 
2222 template <typename NodeIndexType, typename ArcIndexType>
2225  NodeIndexType node) const {
2226  DCHECK_LT(node, num_nodes_);
2228  static_cast<ArcIndexType>(num_nodes_) * node,
2229  static_cast<ArcIndexType>(num_nodes_) * (node + 1));
2230 }
2231 
2232 template <typename NodeIndexType, typename ArcIndexType>
2235  NodeIndexType node, ArcIndexType from) const {
2236  DCHECK_LT(node, num_nodes_);
2238  from, static_cast<ArcIndexType>(num_nodes_) * (node + 1));
2239 }
2240 
2241 template <typename NodeIndexType, typename ArcIndexType>
2244  NodeIndexType node) const {
2245  DCHECK_LT(node, num_nodes_);
2246  return IntegerRange<NodeIndexType>(0, num_nodes_);
2247 }
2248 
2249 // CompleteBipartiteGraph implementation ---------------------------------------
2250 // Nodes and arcs are implicit and not stored.
2251 
2252 template <typename NodeIndexType = int32, typename ArcIndexType = int32>
2254  : public BaseGraph<NodeIndexType, ArcIndexType, false> {
2256  using Base::arc_capacity_;
2258  using Base::node_capacity_;
2259  using Base::num_arcs_;
2260  using Base::num_nodes_;
2261 
2262  public:
2263  // Builds a complete bipartite graph from a set of left nodes to a set of
2264  // right nodes.
2265  // Indices of left nodes of the bipartite graph range from 0 to left_nodes-1;
2266  // indices of right nodes range from left_nodes to left_nodes+right_nodes-1.
2267  CompleteBipartiteGraph(NodeIndexType left_nodes, NodeIndexType right_nodes)
2268  : left_nodes_(left_nodes), right_nodes_(right_nodes) {
2269  this->Reserve(left_nodes + right_nodes, left_nodes * right_nodes);
2270  this->FreezeCapacities();
2271  num_nodes_ = left_nodes + right_nodes;
2272  num_arcs_ = left_nodes * right_nodes;
2273  }
2274 
2275  NodeIndexType Head(ArcIndexType arc) const;
2276  NodeIndexType Tail(ArcIndexType arc) const;
2277  ArcIndexType OutDegree(NodeIndexType node) const;
2278  IntegerRange<ArcIndexType> OutgoingArcs(NodeIndexType node) const;
2280  ArcIndexType from) const;
2281  IntegerRange<NodeIndexType> operator[](NodeIndexType node) const;
2282 
2283  // Deprecated interface.
2285  public:
2286  OutgoingArcIterator(const CompleteBipartiteGraph& graph, NodeIndexType node)
2287  : index_(graph.right_nodes_ * node),
2288  limit_(node >= graph.left_nodes_ ? index_
2289  : graph.right_nodes_ * (node + 1)) {}
2290 
2291  bool Ok() const { return index_ < limit_; }
2292  ArcIndexType Index() const { return index_; }
2293  void Next() { index_++; }
2294 
2295  private:
2296  ArcIndexType index_;
2297  const ArcIndexType limit_;
2298  };
2299 
2300  private:
2301  const NodeIndexType left_nodes_;
2302  const NodeIndexType right_nodes_;
2303 };
2304 
2305 template <typename NodeIndexType, typename ArcIndexType>
2307  ArcIndexType arc) const {
2308  DCHECK(this->IsArcValid(arc));
2309  return left_nodes_ + arc % right_nodes_;
2310 }
2311 
2312 template <typename NodeIndexType, typename ArcIndexType>
2314  ArcIndexType arc) const {
2315  DCHECK(this->IsArcValid(arc));
2316  return arc / right_nodes_;
2317 }
2318 
2319 template <typename NodeIndexType, typename ArcIndexType>
2321  NodeIndexType node) const {
2322  return (node < left_nodes_) ? right_nodes_ : 0;
2323 }
2324 
2325 template <typename NodeIndexType, typename ArcIndexType>
2328  NodeIndexType node) const {
2329  if (node < left_nodes_) {
2330  return IntegerRange<ArcIndexType>(right_nodes_ * node,
2331  right_nodes_ * (node + 1));
2332  } else {
2333  return IntegerRange<ArcIndexType>(0, 0);
2334  }
2335 }
2336 
2337 template <typename NodeIndexType, typename ArcIndexType>
2340  NodeIndexType node, ArcIndexType from) const {
2341  if (node < left_nodes_) {
2342  return IntegerRange<ArcIndexType>(from, right_nodes_ * (node + 1));
2343  } else {
2344  return IntegerRange<ArcIndexType>(0, 0);
2345  }
2346 }
2347 
2348 template <typename NodeIndexType, typename ArcIndexType>
2351  NodeIndexType node) const {
2352  if (node < left_nodes_) {
2353  return IntegerRange<NodeIndexType>(left_nodes_, left_nodes_ + right_nodes_);
2354  } else {
2355  return IntegerRange<NodeIndexType>(0, 0);
2356  }
2357 }
2358 
2359 // Defining the simplest Graph interface as Graph for convenience.
2361 
2362 } // namespace util
2363 
2364 #undef DEFINE_RANGE_BASED_ARC_ITERATION
2365 #undef DEFINE_STL_ITERATOR_FUNCTIONS
2366 
2367 #endif // UTIL_GRAPH_GRAPH_H_
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
ArcIndexType arc_capacity_
Definition: graph.h:280
static const NodeIndexType kNilNode
Definition: graph.h:259
IntegerRange< ArcIndex > AllForwardArcs() const
Definition: graph.h:941
void GroupForwardArcsByFunctor(const A &a, B *b)
Definition: graph.h:265
void FreezeCapacities()
Definition: graph.h:972
bool IsNodeValid(NodeIndexType node) const
Definition: graph.h:214
virtual void ReserveArcs(ArcIndexType bound)
Definition: graph.h:242
void Reserve(NodeIndexType node_capacity, ArcIndexType arc_capacity)
Definition: graph.h:248
NodeIndexType node_capacity_
Definition: graph.h:278
ArcIndexType num_arcs() const
Definition: graph.h:205
void BuildStartAndForwardHead(SVector< NodeIndexType > *head, std::vector< ArcIndexType > *start, std::vector< ArcIndexType > *permutation)
Definition: graph.h:1001
NodeIndexType num_nodes() const
Definition: graph.h:202
ArcIndexType arc_capacity() const
Definition: graph.h:965
IntegerRange< NodeIndex > AllNodes() const
Definition: graph.h:935
bool const_capacities_
Definition: graph.h:281
ArcIndexType ArcIndex
Definition: graph.h:191
NodeIndexType num_nodes_
Definition: graph.h:277
static const ArcIndexType kNilArc
Definition: graph.h:260
void ComputeCumulativeSum(std::vector< ArcIndexType > *v)
Definition: graph.h:984
ArcIndexType max_end_arc_index() const
Definition: graph.h:268
virtual ~BaseGraph()
Definition: graph.h:199
NodeIndexType node_capacity() const
Definition: graph.h:957
bool IsArcValid(ArcIndexType arc) const
Definition: graph.h:220
NodeIndexType NodeIndex
Definition: graph.h:190
ArcIndexType num_arcs_
Definition: graph.h:279
virtual void ReserveNodes(NodeIndexType bound)
Definition: graph.h:236
OutgoingArcIterator(const CompleteBipartiteGraph &graph, NodeIndexType node)
Definition: graph.h:2286
IntegerRange< ArcIndexType > OutgoingArcs(NodeIndexType node) const
Definition: graph.h:2327
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:2313
ArcIndexType OutDegree(NodeIndexType node) const
Definition: graph.h:2320
CompleteBipartiteGraph(NodeIndexType left_nodes, NodeIndexType right_nodes)
Definition: graph.h:2267
IntegerRange< NodeIndexType > operator[](NodeIndexType node) const
Definition: graph.h:2350
IntegerRange< ArcIndexType > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
Definition: graph.h:2339
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:2306
IntegerRange< ArcIndexType > OutgoingArcs(NodeIndexType node) const
Definition: graph.h:2224
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:2210
CompleteGraph(NodeIndexType num_nodes)
Definition: graph.h:2186
ArcIndexType OutDegree(NodeIndexType node) const
Definition: graph.h:2217
IntegerRange< NodeIndexType > operator[](NodeIndexType node) const
Definition: graph.h:2243
IntegerRange< ArcIndexType > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
Definition: graph.h:2234
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:2203
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingArcIterator)
OutgoingArcIterator(const ListGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1184
OutgoingArcIterator(const ListGraph &graph, NodeIndexType node)
Definition: graph.h:1180
ArcIndexType Index() const
Definition: graph.h:1191
const NodeIndexType * pointer
Definition: graph.h:1209
NodeIndexType Index() const
Definition: graph.h:1224
const NodeIndexType & reference
Definition: graph.h:1210
bool operator!=(const typename ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator &other) const
Definition: graph.h:1230
NodeIndexType operator*() const
Definition: graph.h:1235
std::input_iterator_tag iterator_category
Definition: graph.h:1207
OutgoingHeadIterator(const ListGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1217
OutgoingHeadIterator(const ListGraph &graph, NodeIndexType node)
Definition: graph.h:1213
BeginEndWrapper< OutgoingHeadIterator > operator[](NodeIndexType node) const
Definition: graph.h:1103
ListGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
Definition: graph.h:313
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:1110
void ReserveArcs(ArcIndexType bound) override
Definition: graph.h:1161
void ReserveNodes(NodeIndexType bound) override
Definition: graph.h:1154
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
void Build()
Definition: graph.h:340
void AddNode(NodeIndexType node)
Definition: graph.h:1132
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: graph.h:1140
ArcIndexType OutDegree(NodeIndexType node) const
Definition: graph.h:1124
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1117
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
IncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1592
IncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
Definition: graph.h:1590
OppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1564
DEFINE_STL_ITERATOR_FUNCTIONS(OppositeIncomingArcIterator)
OppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
Definition: graph.h:1559
OutgoingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
Definition: graph.h:1530
OutgoingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1534
OutgoingHeadIterator(const ReverseArcListGraph &graph, NodeIndexType node)
Definition: graph.h:1650
OutgoingHeadIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1654
OutgoingOrOppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
Definition: graph.h:1612
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingOrOppositeIncomingArcIterator)
OutgoingOrOppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1618
ArcIndexType OppositeArc(ArcIndexType arc) const
Definition: graph.h:1458
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:1472
void ReserveArcs(ArcIndexType bound) override
Definition: graph.h:1487
BeginEndWrapper< IncomingArcIterator > IncomingArcs(NodeIndexType node) const
void ReserveNodes(NodeIndexType bound) override
Definition: graph.h:1478
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
ArcIndexType InDegree(NodeIndexType node) const
Definition: graph.h:1450
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
void AddNode(NodeIndexType node)
Definition: graph.h:1496
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: graph.h:1506
ReverseArcListGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
Definition: graph.h:472
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs(NodeIndexType node) const
ArcIndexType OutDegree(NodeIndexType node) const
Definition: graph.h:1442
void Build(std::vector< ArcIndexType > *permutation)
Definition: graph.h:1520
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1465
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
BeginEndWrapper< OutgoingHeadIterator > operator[](NodeIndexType node) const
Definition: graph.h:1434
IncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
Definition: graph.h:2109
IncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:2111
DEFINE_STL_ITERATOR_FUNCTIONS(OppositeIncomingArcIterator)
OppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:2083
OppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
Definition: graph.h:2076
OutgoingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:2050
OutgoingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
Definition: graph.h:2048
OutgoingOrOppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
Definition: graph.h:2128
OutgoingOrOppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:2138
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingOrOppositeIncomingArcIterator)
ArcIndexType OppositeArc(ArcIndexType arc) const
Definition: graph.h:1967
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:1982
void ReserveArcs(ArcIndexType bound) override
Definition: graph.h:1989
BeginEndWrapper< IncomingArcIterator > IncomingArcs(NodeIndexType node) const
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
ArcIndexType InDegree(NodeIndexType node) const
Definition: graph.h:1951
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< NodeIndexType const * > operator[](NodeIndexType node) const
Definition: graph.h:1960
void AddNode(NodeIndexType node)
Definition: graph.h:1997
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: graph.h:2005
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs(NodeIndexType node) const
ArcIndexType OutDegree(NodeIndexType node) const
Definition: graph.h:1945
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1974
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
ReverseArcMixedGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
Definition: graph.h:648
IncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
Definition: graph.h:1871
IncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1873
OppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
Definition: graph.h:1836
OppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1844
DEFINE_STL_ITERATOR_FUNCTIONS(OppositeIncomingArcIterator)
OutgoingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1810
OutgoingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
Definition: graph.h:1808
OutgoingOrOppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
Definition: graph.h:1893
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingOrOppositeIncomingArcIterator)
OutgoingOrOppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1903
ArcIndexType OppositeArc(ArcIndexType arc) const
Definition: graph.h:1708
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:1724
ReverseArcStaticGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
Definition: graph.h:560
void ReserveArcs(ArcIndexType bound) override
Definition: graph.h:1731
BeginEndWrapper< IncomingArcIterator > IncomingArcs(NodeIndexType node) const
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
ArcIndexType InDegree(NodeIndexType node) const
Definition: graph.h:1694
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< NodeIndexType const * > operator[](NodeIndexType node) const
Definition: graph.h:1701
void AddNode(NodeIndexType node)
Definition: graph.h:1739
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: graph.h:1747
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs(NodeIndexType node) const
ArcIndexType OutDegree(NodeIndexType node) const
Definition: graph.h:1688
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1716
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
T * data() const
Definition: graph.h:843
SVector(const SVector &other)
Definition: graph.h:780
const T & operator[](int n) const
Definition: graph.h:818
SVector(SVector &&other)
Definition: graph.h:802
SVector & operator=(const SVector &other)
Definition: graph.h:781
void resize(int n)
Definition: graph.h:824
void clear_and_dealloc()
Definition: graph.h:897
void reserve(int n)
Definition: graph.h:851
SVector & operator=(SVector &&other)
Definition: graph.h:803
void grow(const T &left=T(), const T &right=T())
Definition: graph.h:874
void clear()
Definition: graph.h:841
int capacity() const
Definition: graph.h:893
void swap(SVector< T > &x)
Definition: graph.h:845
int max_size() const
Definition: graph.h:895
T & operator[](int n)
Definition: graph.h:812
int size() const
Definition: graph.h:891
OutgoingArcIterator(const StaticGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: graph.h:1395
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingArcIterator)
OutgoingArcIterator(const StaticGraph &graph, NodeIndexType node)
Definition: graph.h:1393
ArcIndexType Index() const
Definition: graph.h:1402
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:1306
void ReserveArcs(ArcIndexType bound) override
Definition: graph.h:1269
void ReserveNodes(NodeIndexType bound) override
Definition: graph.h:1261
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
void Build()
Definition: graph.h:435
BeginEndWrapper< NodeIndexType const * > operator[](NodeIndexType node) const
Definition: graph.h:1249
void AddNode(NodeIndexType node)
Definition: graph.h:1277
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: graph.h:1285
StaticGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
Definition: graph.h:408
ArcIndexType OutDegree(NodeIndexType node) const
Definition: graph.h:1255
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1313
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
const int64 limit_
int int32
const int FATAL
Definition: log_severity.h:32
ListGraph Graph
Definition: graph.h:2360
DEFINE_RANGE_BASED_ARC_ITERATION(ListGraph, Outgoing, Base::kNilArc)
void Permute(const IntVector &permutation, Array *array_to_permute)
Definition: graph.h:738
void PermuteWithExplicitElementType(const IntVector &permutation, Array *array_to_permute, ElementType unused)
Definition: graph.h:725
void * malloc(YYSIZE_T)
void free(void *)
int64 delta
Definition: resource.cc:1684
int64 tail
int64 head
int64 bound