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