C++ Reference

C++ Reference: Graph

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