OR-Tools  8.2
ebert_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#ifndef OR_TOOLS_GRAPH_EBERT_GRAPH_H_
15#define OR_TOOLS_GRAPH_EBERT_GRAPH_H_
16
17// A few variations on a theme of the "star" graph representation by
18// Ebert, as described in J. Ebert, "A versatile data structure for
19// edge-oriented graph algorithms." Communications of the ACM
20// 30(6):513-519 (June 1987).
21// http://portal.acm.org/citation.cfm?id=214769
22//
23// In this file there are three representations that have much in
24// common. The general one, called simply EbertGraph, contains both
25// forward- and backward-star representations. The other, called
26// ForwardEbertGraph, contains only the forward-star representation of
27// the graph, and is appropriate for applications where the reverse
28// arcs are not needed.
29//
30// The point of including all the representations in this one file is
31// to capitalize, where possible, on the commonalities among them, and
32// those commonalities are mostly factored out into base classes as
33// described below. Despite the commonalities, however, each of the
34// three representations presents a somewhat different interface
35// because of their different underlying semantics. A quintessential
36// example is that the AddArc() method, very natural for the
37// EbertGraph representation, cannot exist for an inherently static
38// representation like ForwardStaticGraph.
39//
40// Many clients are expected to use the interfaces to the graph
41// objects directly, but some clients are parameterized by graph type
42// and need a consistent interface for their underlying graph
43// objects. For such clients, a small library of class templates is
44// provided to give a consistent interface to clients where the
45// underlying graph interfaces differ. Examples are the
46// AnnotatedGraphBuildManager<> template, which provides a uniform
47// interface for building the various types of graphs; and the
48// TailArrayManager<> template, which provides a uniform interface for
49// applications that need to map from arc indices to arc tail nodes,
50// accounting for the fact that such a mapping has to be requested
51// explicitly from the ForwardStaticGraph and ForwardStarGraph
52// representations.
53//
54// There are two base class templates, StarGraphBase, and
55// EbertGraphBase; their purpose is to hold methods and data
56// structures that are in common among their descendants. Only classes
57// that are leaves in the following hierarchy tree are eligible for
58// free-standing instantiation and use by clients. The parentheses
59// around StarGraphBase and EbertGraphBase indicate that they should
60// not normally be instantiated by clients:
61//
62// (StarGraphBase) |
63// / \ |
64// / \ |
65// / \ |
66// / \ |
67// (EbertGraphBase) ForwardStaticGraph |
68// / \ |
69// / \ |
70// EbertGraph ForwardEbertGraph |
71//
72// In the general EbertGraph case, the graph is represented with three
73// arrays.
74// Let n be the number of nodes and m be the number of arcs.
75// Let i be an integer in [0..m-1], denoting the index of an arc.
76// * head_[i] contains the end-node of arc i,
77// * head_[-i-1] contains the start-node of arc i.
78// Note that in two's-complement arithmetic, -i-1 = ~i.
79// Consequently:
80// * head_[~i] contains the end-node of the arc reverse to arc i,
81// * head_[i] contains the start-node of the arc reverse to arc i.
82// Note that if arc (u, v) is defined, then the data structure also stores
83// (v, u).
84// Arc ~i thus denotes the arc reverse to arc i.
85// This is what makes this representation useful for undirected graphs and for
86// implementing algorithms like bidirectional shortest paths.
87// Also note that the representation handles multi-graphs. If several arcs
88// going from node u to node v are added to the graph, they will be handled as
89// separate arcs.
90//
91// Now, for an integer u in [0..n-1] denoting the index of a node:
92// * first_incident_arc_[u] denotes the first arc in the adjacency list of u.
93// * going from an arc i, the adjacency list can be traversed using
94// j = next_adjacent_arc_[i].
95//
96// The EbertGraph implementation has the following benefits:
97// * It is able to handle both directed or undirected graphs.
98// * Being based on indices, it is easily serializable. Only the contents
99// of the head_ array need to be stored. Even so, serialization is
100// currently not implemented.
101// * The node indices and arc indices can be stored in 32 bits, while
102// still allowing to go a bit further than the 4-gigabyte
103// limitation (48 gigabytes for a pure graph, without capacities or
104// costs.)
105// * The representation can be recomputed if edges have been loaded from
106// * The representation can be recomputed if edges have been loaded from
107// external memory or if edges have been re-ordered.
108// * The memory consumption is: 2 * m * sizeof(NodeIndexType)
109// + 2 * m * sizeof(ArcIndexType)
110// + n * sizeof(ArcIndexType)
111// plus a small constant.
112//
113// The EbertGraph implementation differs from the implementation described in
114// [Ebert 1987] in the following respects:
115// * arcs are represented using an (i, ~i) approach, whereas Ebert used
116// (i, -i). Indices for direct arcs thus start at 0, in a fashion that is
117// compatible with the index numbering in C and C++. Note that we also tested
118// a (2*i, 2*i+1) storage pattern, which did not show any speed benefit, and
119// made the use of the API much more difficult.
120// * because of this, the 'nil' values for nodes and arcs are not 0, as Ebert
121// first described. The value for the 'nil' node is set to -1, while the
122// value for the 'nil' arc is set to the smallest integer representable with
123// ArcIndexSize bytes.
124// * it is possible to add arcs to the graph, with AddArc, in a much simpler
125// way than described by Ebert.
126// * TODO(user) although it is already possible, using the
127// GroupForwardArcsByFunctor method, to group all the outgoing (resp.
128// incoming) arcs of a node, the iterator logic could still be improved to
129// allow traversing the outgoing (resp. incoming) arcs in O(out_degree(node))
130// (resp. O(in_degree(node))) instead of O(degree(node)).
131// * TODO(user) it is possible to implement arc deletion and garbage collection
132// in an efficient (relatively) manner. For the time being we haven't seen an
133// application for this.
134//
135// The ForwardEbertGraph representation is like the EbertGraph case described
136// above, with the following modifications:
137// * The part of the head_[] array with negative indices is absent. In its
138// place is a pointer tail_ which, if assigned, points to an array of tail
139// nodes indexed by (nonnegative) arc index. In typical usage tail_ is NULL
140// and the memory for the tail nodes need not be allocated.
141// * The array of arc tails can be allocated as needed and populated from the
142// adjacency lists of the graph.
143// * Representing only the forward star of each node implies that the graph
144// cannot be serialized directly nor rebuilt from scratch from just the head_
145// array. Rebuilding from scratch requires constructing the array of arc
146// tails from the adjacency lists first, and serialization can be done either
147// by first constructing the array of arc tails from the adjacency lists, or
148// by serializing directly from the adjacency lists.
149// * The memory consumption is: m * sizeof(NodeIndexType)
150// + m * sizeof(ArcIndexType)
151// + n * sizeof(ArcIndexType)
152// plus a small constant when the array of arc tails is absent. Allocating
153// the arc tail array adds another m * sizeof(NodeIndexType).
154//
155// The ForwardStaticGraph representation is restricted yet farther
156// than ForwardEbertGraph, with the benefit that it provides higher
157// performance to those applications that can use it.
158// * As with ForwardEbertGraph, the presence of the array of arc
159// tails is optional.
160// * The outgoing adjacency list for each node is stored in a
161// contiguous segment of the head_[] array, obviating the
162// next_adjacent_arc_ structure entirely and ensuring good locality
163// of reference for applications that iterate over outgoing
164// adjacency lists.
165// * The memory consumption is: m * sizeof(NodeIndexType)
166// + n * sizeof(ArcIndexType)
167// plus a small constant when the array of arc tails is absent. Allocating
168// the arc tail array adds another m * sizeof(NodeIndexType).
169
170#include <algorithm>
171#include <limits>
172#include <memory>
173#include <string>
174#include <utility>
175#include <vector>
176
177#include "absl/strings/str_cat.h"
179#include "ortools/base/logging.h"
180#include "ortools/base/macros.h"
182#include "ortools/util/zvector.h"
183
184namespace operations_research {
185
186// Forward declarations.
187template <typename NodeIndexType, typename ArcIndexType>
188class EbertGraph;
189template <typename NodeIndexType, typename ArcIndexType>
190class ForwardEbertGraph;
191template <typename NodeIndexType, typename ArcIndexType>
192class ForwardStaticGraph;
193
194// Standard instantiation of ForwardEbertGraph (named 'ForwardStarGraph') of
195// EbertGraph (named 'StarGraph'); and relevant type shortcuts. Unless their use
196// cases prevent them from doing so, users are encouraged to use StarGraph or
197// ForwardStarGraph according to whether or not they require reverse arcs to be
198// represented explicitly. Along with either graph representation, the other
199// type shortcuts here will often come in handy.
211
212template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
214 public:
215 // The index of the 'nil' node in the graph.
216 static const NodeIndexType kNilNode;
217
218 // The index of the 'nil' arc in the graph.
219 static const ArcIndexType kNilArc;
220
221 // The index of the first node in the graph.
222 static const NodeIndexType kFirstNode;
223
224 // The index of the first arc in the graph.
225 static const ArcIndexType kFirstArc;
226
227 // The maximum possible number of nodes in the graph. (The maximum
228 // index is kMaxNumNodes-1, since indices start at 0. Unfortunately
229 // we waste a value representing this and the max_num_nodes_ member.)
230 static const NodeIndexType kMaxNumNodes;
231
232 // The maximum possible number of arcs in the graph. (The maximum
233 // index is kMaxNumArcs-1, since indices start at 0. Unfortunately
234 // we waste a value representing this and the max_num_arcs_ member.)
235 static const ArcIndexType kMaxNumArcs;
236 // Returns the number of nodes in the graph.
237 NodeIndexType num_nodes() const { return num_nodes_; }
238
239 // Returns the number of original arcs in the graph
240 // (The ones with positive indices.)
241 ArcIndexType num_arcs() const { return num_arcs_; }
242
243 // Returns one more than the largest index of an extant node,
244 // meaning a node that is mentioned as the head or tail of some arc
245 // in the graph. To be used as a helper when clients need to
246 // dimension or iterate over arrays of node annotation information.
247 NodeIndexType end_node_index() const { return kFirstNode + num_nodes_; }
248
249 // Returns one more than the largest index of an extant direct
250 // arc. To be used as a helper when clients need to dimension or
251 // iterate over arrays of arc annotation information.
252 ArcIndexType end_arc_index() const { return kFirstArc + num_arcs_; }
253
254 // Returns the maximum possible number of nodes in the graph.
255 NodeIndexType max_num_nodes() const { return max_num_nodes_; }
256
257 // Returns the maximum possible number of original arcs in the graph.
258 // (The ones with positive indices.)
259 ArcIndexType max_num_arcs() const { return max_num_arcs_; }
260
261 // Returns one more than the largest valid index of a node. To be
262 // used as a helper when clients need to dimension or iterate over
263 // arrays of node annotation information.
264 NodeIndexType max_end_node_index() const {
265 return kFirstNode + max_num_nodes_;
266 }
267
268 // Returns one more than the largest valid index of a direct arc. To
269 // be used as a helper when clients need to dimension or iterate
270 // over arrays of arc annotation information.
271 ArcIndexType max_end_arc_index() const { return kFirstArc + max_num_arcs_; }
272
273 // Utility function to check that a node index is within the bounds AND
274 // different from kNilNode.
275 // Returns true if node is in the range [kFirstNode .. max_num_nodes_).
276 // It is exported so that users of the DerivedGraph class can use it.
277 // To be used in a DCHECK; also used internally to validate
278 // arguments passed to our methods from clients (e.g., AddArc()).
279 bool IsNodeValid(NodeIndexType node) const {
280 return node >= kFirstNode && node < max_num_nodes_;
281 }
282
283 // Returns the first arc going from tail to head, if it exists, or kNilArc
284 // if such an arc does not exist.
285 ArcIndexType LookUpArc(const NodeIndexType tail,
286 const NodeIndexType head) const {
287 for (ArcIndexType arc = FirstOutgoingArc(tail); arc != kNilArc;
288 arc = ThisAsDerived()->NextOutgoingArc(tail, arc)) {
289 if (Head(arc) == head) {
290 return arc;
291 }
292 }
293 return kNilArc;
294 }
295
296 // Returns the head or end-node of arc.
297 NodeIndexType Head(const ArcIndexType arc) const {
298 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
299 return head_[arc];
300 }
301
302 std::string NodeDebugString(const NodeIndexType node) const {
303 if (node == kNilNode) {
304 return "NilNode";
305 } else {
306 return absl::StrCat(static_cast<int64>(node));
307 }
308 }
309
310 std::string ArcDebugString(const ArcIndexType arc) const {
311 if (arc == kNilArc) {
312 return "NilArc";
313 } else {
314 return absl::StrCat(static_cast<int64>(arc));
315 }
316 }
317
318#if !defined(SWIG)
319 // Iterator class for traversing all the nodes in the graph.
321 public:
322 explicit NodeIterator(const DerivedGraph& graph)
323 : graph_(graph), head_(graph_.StartNode(kFirstNode)) {}
324
325 // Returns true unless all the nodes have been traversed.
326 bool Ok() const { return head_ != kNilNode; }
327
328 // Advances the current node index.
329 void Next() { head_ = graph_.NextNode(head_); }
330
331 // Returns the index of the node currently pointed to by the iterator.
332 NodeIndexType Index() const { return head_; }
333
334 private:
335 // A reference to the current DerivedGraph considered.
336 const DerivedGraph& graph_;
337
338 // The index of the current node considered.
339 NodeIndexType head_;
340 };
341
342 // Iterator class for traversing the arcs in the graph.
344 public:
345 explicit ArcIterator(const DerivedGraph& graph)
346 : graph_(graph), arc_(graph_.StartArc(kFirstArc)) {}
347
348 // Returns true unless all the arcs have been traversed.
349 bool Ok() const { return arc_ != kNilArc; }
350
351 // Advances the current arc index.
352 void Next() { arc_ = graph_.NextArc(arc_); }
353
354 // Returns the index of the arc currently pointed to by the iterator.
355 ArcIndexType Index() const { return arc_; }
356
357 private:
358 // A reference to the current DerivedGraph considered.
359 const DerivedGraph& graph_;
360
361 // The index of the current arc considered.
362 ArcIndexType arc_;
363 };
364
365 // Iterator class for traversing the outgoing arcs associated to a given node.
367 public:
368 OutgoingArcIterator(const DerivedGraph& graph, NodeIndexType node)
369 : graph_(graph),
370 node_(graph_.StartNode(node)),
371 arc_(graph_.StartArc(graph_.FirstOutgoingArc(node))) {
372 DCHECK(CheckInvariant());
373 }
374
375 // This constructor takes an arc as extra argument and makes the iterator
376 // start at arc.
377 OutgoingArcIterator(const DerivedGraph& graph, NodeIndexType node,
378 ArcIndexType arc)
379 : graph_(graph),
380 node_(graph_.StartNode(node)),
381 arc_(graph_.StartArc(arc)) {
382 DCHECK(CheckInvariant());
383 }
384
385 // Can only assign from an iterator on the same graph.
386 void operator=(const OutgoingArcIterator& iterator) {
387 DCHECK(&iterator.graph_ == &graph_);
388 node_ = iterator.node_;
389 arc_ = iterator.arc_;
390 }
391
392 // Returns true unless all the outgoing arcs have been traversed.
393 bool Ok() const { return arc_ != kNilArc; }
394
395 // Advances the current outgoing arc index.
396 void Next() {
397 arc_ = graph_.NextOutgoingArc(node_, arc_);
398 DCHECK(CheckInvariant());
399 }
400
401 // Returns the index of the arc currently pointed to by the iterator.
402 ArcIndexType Index() const { return arc_; }
403
404 private:
405 // Returns true if the invariant for the iterator is verified.
406 // To be used in a DCHECK.
407 bool CheckInvariant() const {
408 if (arc_ == kNilArc) {
409 return true; // This occurs when the iterator has reached the end.
410 }
411 DCHECK(graph_.IsOutgoing(arc_, node_));
412 return true;
413 }
414
415 // A reference to the current DerivedGraph considered.
416 const DerivedGraph& graph_;
417
418 // The index of the node on which arcs are iterated.
419 NodeIndexType node_;
420
421 // The index of the current arc considered.
422 ArcIndexType arc_;
423 };
424#endif // SWIG
425
426 protected:
428 : max_num_nodes_(0),
429 max_num_arcs_(0),
430 num_nodes_(0),
431 num_arcs_(0),
433
435
436 // Returns kNilNode if the graph has no nodes or node if it has at least one
437 // node. Useful for initializing iterators correctly in the case of empty
438 // graphs.
439 NodeIndexType StartNode(NodeIndexType node) const {
440 return num_nodes_ == 0 ? kNilNode : node;
441 }
442
443 // Returns kNilArc if the graph has no arcs arc if it has at least one arc.
444 // Useful for initializing iterators correctly in the case of empty graphs.
445 ArcIndexType StartArc(ArcIndexType arc) const {
446 return num_arcs_ == 0 ? kNilArc : arc;
447 }
448
449 // Returns the node following the argument in the graph.
450 // Returns kNilNode (= end) if the range of nodes has been exhausted.
451 // It is called by NodeIterator::Next() and as such does not expect to be
452 // passed an argument equal to kNilNode.
453 // This is why the return line is simplified from
454 // return (node == kNilNode || next_node >= num_nodes_)
455 // ? kNilNode : next_node;
456 // to
457 // return next_node < num_nodes_ ? next_node : kNilNode;
458 NodeIndexType NextNode(const NodeIndexType node) const {
459 DCHECK(IsNodeValid(node));
460 const NodeIndexType next_node = node + 1;
461 return next_node < num_nodes_ ? next_node : kNilNode;
462 }
463
464 // Returns the arc following the argument in the graph.
465 // Returns kNilArc (= end) if the range of arcs has been exhausted.
466 // It is called by ArcIterator::Next() and as such does not expect to be
467 // passed an argument equal to kNilArc.
468 // This is why the return line is simplified from
469 // return ( arc == kNilArc || next_arc >= num_arcs_) ? kNilArc : next_arc;
470 // to
471 // return next_arc < num_arcs_ ? next_arc : kNilArc;
472 ArcIndexType NextArc(const ArcIndexType arc) const {
473 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
474 const ArcIndexType next_arc = arc + 1;
475 return next_arc < num_arcs_ ? next_arc : kNilArc;
476 }
477
478 // Returns the first outgoing arc for node.
479 ArcIndexType FirstOutgoingArc(const NodeIndexType node) const {
480 DCHECK(IsNodeValid(node));
481 return ThisAsDerived()->FindNextOutgoingArc(
482 ThisAsDerived()->FirstOutgoingOrOppositeIncomingArc(node));
483 }
484
485 // The maximum number of nodes that the graph can hold.
486 NodeIndexType max_num_nodes_;
487
488 // The maximum number of arcs that the graph can hold.
489 ArcIndexType max_num_arcs_;
490
491 // The maximum index of the node currently held by the graph.
492 NodeIndexType num_nodes_;
493
494 // The current number of arcs held by the graph.
495 ArcIndexType num_arcs_;
496
497 // Array of node indices. head_[i] contains the head node of arc i.
499
500 // Array of arc indices. first_incident_arc_[i] contains the first arc
501 // incident to node i.
503
504 private:
505 // Shorthand: returns a const DerivedGraph*-typed version of our
506 // "this" pointer.
507 inline const DerivedGraph* ThisAsDerived() const {
508 return static_cast<const DerivedGraph*>(this);
509 }
510
511 // Shorthand: returns a DerivedGraph*-typed version of our "this"
512 // pointer.
513 inline DerivedGraph* ThisAsDerived() {
514 return static_cast<DerivedGraph*>(this);
515 }
516};
517
518template <typename NodeIndexType, typename ArcIndexType>
520 public:
523 : head_(head) {}
524
525 bool operator()(ArcIndexType a, ArcIndexType b) const {
526 return head_[a] < head_[b];
527 }
528
529 private:
530 const ZVector<NodeIndexType>& head_;
531};
532
533template <typename NodeIndexType, typename ArcIndexType>
535 : public StarGraphBase<NodeIndexType, ArcIndexType,
536 ForwardStaticGraph<NodeIndexType, ArcIndexType> > {
537 typedef StarGraphBase<NodeIndexType, ArcIndexType,
540 friend class StarGraphBase<NodeIndexType, ArcIndexType,
541 ForwardStaticGraph<NodeIndexType, ArcIndexType> >;
542
545
547 using Base::head_;
550 using Base::num_arcs_;
551 using Base::num_nodes_;
552
553 public:
554#if !defined(SWIG)
556 using Base::Head;
557 using Base::IsNodeValid;
558
559 using Base::kFirstArc;
560 using Base::kFirstNode;
561 using Base::kNilArc;
562#endif // SWIG
563
564 typedef NodeIndexType NodeIndex;
565 typedef ArcIndexType ArcIndex;
566
567// TODO(user): Configure SWIG to handle the
568// CycleHandlerForAnnotatedArcs class.
569#if !defined(SWIG)
571 : public ArrayIndexCycleHandler<NodeIndexType, ArcIndexType> {
573
574 public:
576 PermutationCycleHandler<ArcIndexType>* annotation_handler,
577 NodeIndexType* data)
578 : ArrayIndexCycleHandler<NodeIndexType, ArcIndexType>(&data[kFirstArc]),
579 annotation_handler_(annotation_handler) {}
580
581 void SetTempFromIndex(ArcIndexType source) override {
583 annotation_handler_->SetTempFromIndex(source);
584 }
585
586 void SetIndexFromIndex(ArcIndexType source,
587 ArcIndexType destination) const override {
588 Base::SetIndexFromIndex(source, destination);
589 annotation_handler_->SetIndexFromIndex(source, destination);
590 }
591
592 void SetIndexFromTemp(ArcIndexType destination) const override {
593 Base::SetIndexFromTemp(destination);
594 annotation_handler_->SetIndexFromTemp(destination);
595 }
596
597 private:
598 PermutationCycleHandler<ArcIndexType>* annotation_handler_;
599
600 DISALLOW_COPY_AND_ASSIGN(CycleHandlerForAnnotatedArcs);
601 };
602#endif // SWIG
603
604 // Constructor for use by GraphBuilderFromArcs instances and direct
605 // clients that want to materialize a graph in one step.
606 // Materializing all at once is the only choice available with a
607 // static graph.
608 //
609 // Args:
610 // sort_arcs_by_head: determines whether arcs incident to each tail
611 // node are sorted by head node.
612 // client_cycle_handler: if non-NULL, mediates the permutation of
613 // arbitrary annotation data belonging to the client according
614 // to the permutation applied to the arcs in forming the
615 // graph. Two permutations may be composed to form the final one
616 // that affects the arcs. First, the arcs are always permuted to
617 // group them by tail node because ForwardStaticGraph requires
618 // this. Second, if each node's outgoing arcs are sorted by head
619 // node (according to sort_arcs_by_head), that sorting implies
620 // an additional permutation on the arcs.
622 const NodeIndexType num_nodes, const ArcIndexType num_arcs,
623 const bool sort_arcs_by_head,
624 std::vector<std::pair<NodeIndexType, NodeIndexType> >* client_input_arcs,
625 // TODO(user): For some reason, SWIG breaks if the
626 // operations_research namespace is not explicit in the
627 // following argument declaration.
629 client_cycle_handler) {
633 // A more convenient name for a parameter required by style to be
634 // a pointer, because we modify its referent.
635 std::vector<std::pair<NodeIndexType, NodeIndexType> >& input_arcs =
636 *client_input_arcs;
637
638 // We coopt the first_incident_arc_ array as a node-indexed vector
639 // used for two purposes related to degree before setting up its
640 // final values. First, it counts the out-degree of each
641 // node. Second, it is reused to count the number of arcs outgoing
642 // from each node that have already been put in place from the
643 // given input_arcs. We reserve an extra entry as a sentinel at
644 // the end.
647 for (ArcIndexType arc = kFirstArc; arc < kFirstArc + num_arcs; ++arc) {
648 first_incident_arc_[kFirstNode + input_arcs[arc].first] += 1;
649 // Take this opportunity to see how many nodes are really
650 // mentioned in the arc list.
652 num_nodes_, static_cast<NodeIndexType>(input_arcs[arc].first + 1));
654 num_nodes_, static_cast<NodeIndexType>(input_arcs[arc].second + 1));
655 }
656 ArcIndexType next_arc = kFirstArc;
657 for (NodeIndexType node = 0; node < num_nodes; ++node) {
658 ArcIndexType degree = first_incident_arc_[kFirstNode + node];
659 first_incident_arc_[kFirstNode + node] = next_arc;
660 next_arc += degree;
661 }
662 DCHECK_EQ(num_arcs, next_arc);
664 std::unique_ptr<ArcIndexType[]> arc_permutation;
665 if (client_cycle_handler != nullptr) {
666 arc_permutation.reset(new ArcIndexType[end_arc_index()]);
667 for (ArcIndexType input_arc = 0; input_arc < num_arcs; ++input_arc) {
668 NodeIndexType tail = input_arcs[input_arc].first;
669 NodeIndexType head = input_arcs[input_arc].second;
670 ArcIndexType arc = first_incident_arc_[kFirstNode + tail];
671 // The head_ entry will get permuted into the right place
672 // later.
673 head_[kFirstArc + input_arc] = kFirstNode + head;
674 arc_permutation[kFirstArc + arc] = input_arc;
676 }
677 } else {
678 if (sizeof(input_arcs[0].first) >= sizeof(first_incident_arc_[0])) {
679 // We reuse the input_arcs[].first entries to hold our
680 // mapping to the head_ array. This allows us to spread out
681 // cache badness.
682 for (ArcIndexType input_arc = 0; input_arc < num_arcs; ++input_arc) {
683 NodeIndexType tail = input_arcs[input_arc].first;
684 ArcIndexType arc = first_incident_arc_[kFirstNode + tail];
686 input_arcs[input_arc].first = static_cast<NodeIndexType>(arc);
687 }
688 for (ArcIndexType input_arc = 0; input_arc < num_arcs; ++input_arc) {
689 ArcIndexType arc =
690 static_cast<ArcIndexType>(input_arcs[input_arc].first);
691 NodeIndexType head = input_arcs[input_arc].second;
692 head_[kFirstArc + arc] = kFirstNode + head;
693 }
694 } else {
695 // We cannot reuse the input_arcs[].first entries so we map to
696 // the head_ array in a single loop.
697 for (ArcIndexType input_arc = 0; input_arc < num_arcs; ++input_arc) {
698 NodeIndexType tail = input_arcs[input_arc].first;
699 NodeIndexType head = input_arcs[input_arc].second;
700 ArcIndexType arc = first_incident_arc_[kFirstNode + tail];
702 head_[kFirstArc + arc] = kFirstNode + head;
703 }
704 }
705 }
706 // Shift the entries in first_incident_arc_ to compensate for the
707 // counting each one has done through its incident arcs. Note that
708 // there is a special sentry element at the end of
709 // first_incident_arc_.
710 for (NodeIndexType node = kFirstNode + num_nodes; node > /* kFirstNode */ 0;
711 --node) {
713 }
715 if (sort_arcs_by_head) {
716 ArcIndexType begin = first_incident_arc_[kFirstNode];
717 if (client_cycle_handler != nullptr) {
718 for (NodeIndexType node = 0; node < num_nodes; ++node) {
719 ArcIndexType end = first_incident_arc_[node + 1];
720 std::sort(
721 &arc_permutation[begin], &arc_permutation[end],
723 head_));
724 begin = end;
725 }
726 } else {
727 for (NodeIndexType node = 0; node < num_nodes; ++node) {
728 ArcIndexType end = first_incident_arc_[node + 1];
729 // The second argument in the following has a strange index
730 // expression because ZVector claims that no index is valid
731 // unless it refers to an element in the vector. In particular
732 // an index one past the end is invalid.
733 ArcIndexType begin_index = (begin < num_arcs ? begin : begin - 1);
734 ArcIndexType begin_offset = (begin < num_arcs ? 0 : 1);
735 ArcIndexType end_index = (end > 0 ? end - 1 : end);
736 ArcIndexType end_offset = (end > 0 ? 1 : 0);
737 std::sort(&head_[begin_index] + begin_offset,
738 &head_[end_index] + end_offset);
739 begin = end;
740 }
741 }
742 }
743 if (client_cycle_handler != nullptr && num_arcs > 0) {
744 // Apply the computed permutation if we haven't already.
745 CycleHandlerForAnnotatedArcs handler_for_constructor(
746 client_cycle_handler, &head_[kFirstArc] - kFirstArc);
747 // We use a permutation cycle handler to place the head array
748 // indices and permute the client's arc annotation data along
749 // with them.
750 PermutationApplier<ArcIndexType> permutation(&handler_for_constructor);
751 permutation.Apply(&arc_permutation[0], kFirstArc, end_arc_index());
752 }
753 }
754
755 // Returns the tail or start-node of arc.
756 NodeIndexType Tail(const ArcIndexType arc) const {
759 return (*tail_)[arc];
760 }
761
762 // Returns true if arc is incoming to node.
763 bool IsIncoming(ArcIndexType arc, NodeIndexType node) const {
764 return Head(arc) == node;
765 }
766
767 // Utility function to check that an arc index is within the bounds.
768 // It is exported so that users of the ForwardStaticGraph class can use it.
769 // To be used in a DCHECK.
770 bool CheckArcBounds(const ArcIndexType arc) const {
771 return ((arc == kNilArc) || (arc >= kFirstArc && arc < max_num_arcs_));
772 }
773
774 // Utility function to check that an arc index is within the bounds AND
775 // different from kNilArc.
776 // It is exported so that users of the ForwardStaticGraph class can use it.
777 // To be used in a DCHECK.
778 bool CheckArcValidity(const ArcIndexType arc) const {
779 return ((arc != kNilArc) && (arc >= kFirstArc && arc < max_num_arcs_));
780 }
781
782 // Returns true if arc is a valid index into the (*tail_) array.
783 bool CheckTailIndexValidity(const ArcIndexType arc) const {
784 return ((tail_ != nullptr) && (arc >= kFirstArc) &&
785 (arc <= tail_->max_index()));
786 }
787
788 ArcIndexType NextOutgoingArc(const NodeIndexType node,
789 ArcIndexType arc) const {
790 DCHECK(IsNodeValid(node));
792 ++arc;
793 if (arc < first_incident_arc_[node + 1]) {
794 return arc;
795 } else {
796 return kNilArc;
797 }
798 }
799
800 // Returns a debug string containing all the information contained in the
801 // data structure in raw form.
802 std::string DebugString() const {
803 std::string result = "Arcs:(node) :\n";
804 for (ArcIndexType arc = kFirstArc; arc < num_arcs_; ++arc) {
805 result += " " + ArcDebugString(arc) + ":(" + NodeDebugString(head_[arc]) +
806 ")\n";
807 }
808 result += "Node:First arc :\n";
809 for (NodeIndexType node = kFirstNode; node <= num_nodes_; ++node) {
810 result += " " + NodeDebugString(node) + ":" +
812 }
813 return result;
814 }
815
817 // If (*tail_) is already allocated, we have the invariant that
818 // its contents are canonical, so we do not need to do anything
819 // here in that case except return true.
820 if (tail_ == nullptr) {
821 if (!RepresentationClean()) {
822 // We have been asked to build the (*tail_) array, but we have
823 // no valid information from which to build it. The graph is
824 // in an unrecoverable, inconsistent state.
825 return false;
826 }
827 // Reallocate (*tail_) and rebuild its contents from the
828 // adjacency lists.
829 tail_.reset(new ZVector<NodeIndexType>);
830 tail_->Reserve(kFirstArc, max_num_arcs_ - 1);
831 typename Base::NodeIterator node_it(*this);
832 for (; node_it.Ok(); node_it.Next()) {
833 NodeIndexType node = node_it.Index();
834 typename Base::OutgoingArcIterator arc_it(*this, node);
835 for (; arc_it.Ok(); arc_it.Next()) {
836 (*tail_)[arc_it.Index()] = node;
837 }
838 }
839 }
841 return true;
842 }
843
844 void ReleaseTailArray() { tail_.reset(nullptr); }
845
846 // To be used in a DCHECK().
847 bool TailArrayComplete() const {
848 CHECK(tail_);
849 for (ArcIndexType arc = kFirstArc; arc < num_arcs_; ++arc) {
851 CHECK(IsNodeValid((*tail_)[arc]));
852 }
853 return true;
854 }
855
856 private:
857 bool IsDirect() const { return true; }
858 bool RepresentationClean() const { return true; }
859 bool IsOutgoing(const NodeIndexType node,
860 const ArcIndexType unused_arc) const {
861 return true;
862 }
863
864 // Returns the first arc in node's incidence list.
865 ArcIndexType FirstOutgoingOrOppositeIncomingArc(NodeIndexType node) const {
866 DCHECK(RepresentationClean());
867 DCHECK(IsNodeValid(node));
868 ArcIndexType result = first_incident_arc_[node];
869 return ((result != first_incident_arc_[node + 1]) ? result : kNilArc);
870 }
871
872 // Utility method that finds the next outgoing arc.
873 ArcIndexType FindNextOutgoingArc(ArcIndexType arc) const {
875 return arc;
876 }
877
878 // Array of node indices, not always present. (*tail_)[i] contains
879 // the tail node of arc i. This array is not needed for normal graph
880 // traversal operations, but is used in optimizing the graph's
881 // layout so arcs are grouped by tail node, and can be used in one
882 // approach to serializing the graph.
883 //
884 // Invariants: At any time when we are not executing a method of
885 // this class, either tail_ == NULL or the tail_ array's contents
886 // are kept canonical. If tail_ != NULL, any method that modifies
887 // adjacency lists must also ensure (*tail_) is modified
888 // correspondingly. The converse does not hold: Modifications to
889 // (*tail_) are allowed without updating the adjacency lists. If
890 // such modifications take place, representation_clean_ must be set
891 // to false, of course, to indicate that the adjacency lists are no
892 // longer current.
893 std::unique_ptr<ZVector<NodeIndexType> > tail_;
894};
895
896// The index of the 'nil' node in the graph.
897template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
898const NodeIndexType
900
901// The index of the 'nil' arc in the graph.
902template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
903const ArcIndexType
906
907// The index of the first node in the graph.
908template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
909const NodeIndexType
911
912// The index of the first arc in the graph.
913template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
914const ArcIndexType
916
917// The maximum possible node index in the graph.
918template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
919const NodeIndexType
922
923// The maximum possible number of arcs in the graph.
924// (The maximum index is kMaxNumArcs-1, since indices start at 0.)
925template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
926const ArcIndexType
929
930// A template for the base class that holds the functionality that exists in
931// common between the EbertGraph<> template and the ForwardEbertGraph<>
932// template.
933//
934// This template is for internal use only, and this is enforced by making all
935// constructors for this class template protected. Clients should use one of the
936// two derived-class templates. Most clients will not even use those directly,
937// but will use the StarGraph and ForwardStarGraph typenames declared above.
938//
939// The DerivedGraph template argument must be the type of the class (typically
940// itself built from a template) that:
941// 1. implements the full interface expected for either ForwardEbertGraph or
942// EbertGraph, and
943// 2. inherits from an instance of this template.
944// The base class needs access to some members of the derived class such as, for
945// example, NextOutgoingArc(), and it gets this access via the DerivedGraph
946// template argument.
947template <typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
949 : public StarGraphBase<NodeIndexType, ArcIndexType, DerivedGraph> {
951 friend class StarGraphBase<NodeIndexType, ArcIndexType, DerivedGraph>;
952
953 protected:
960
961 public:
962#if !SWIG
965
972#endif // SWIG
973
974 // Reserves memory needed for max_num_nodes nodes and max_num_arcs arcs.
975 // Returns false if the parameters passed are not OK.
976 // It can be used to enlarge the graph, but does not shrink memory
977 // if called with smaller values.
978 bool Reserve(NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs) {
979 if (new_max_num_nodes < 0 || new_max_num_nodes > kMaxNumNodes) {
980 return false;
981 }
982 if (new_max_num_arcs < 0 || new_max_num_arcs > kMaxNumArcs) {
983 return false;
984 }
985 first_incident_arc_.Reserve(kFirstNode, new_max_num_nodes - 1);
986 for (NodeIndexType node = max_num_nodes_;
987 node <= first_incident_arc_.max_index(); ++node) {
989 }
990 ThisAsDerived()->ReserveInternal(new_max_num_nodes, new_max_num_arcs);
991 max_num_nodes_ = new_max_num_nodes;
992 max_num_arcs_ = new_max_num_arcs;
993 return true;
994 }
995
996 // Adds an arc to the graph and returns its index.
997 // Returns kNilArc if the arc could not be added.
998 // Note that for a given pair (tail, head) AddArc does not overwrite an
999 // already-existing arc between tail and head: Another arc is created
1000 // instead. This makes it possible to handle multi-graphs.
1001 ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head) {
1003 !IsNodeValid(head)) {
1004 return kNilArc;
1005 }
1006 if (tail + 1 > num_nodes_) {
1007 num_nodes_ = tail + 1; // max does not work on int16.
1008 }
1009 if (head + 1 > num_nodes_) {
1010 num_nodes_ = head + 1;
1011 }
1012 ArcIndexType arc = num_arcs_;
1013 ++num_arcs_;
1014 ThisAsDerived()->RecordArc(arc, tail, head);
1015 return arc;
1016 }
1017
1018// TODO(user): Configure SWIG to handle the GroupForwardArcsByFunctor
1019// member template and the CycleHandlerForAnnotatedArcs class.
1020#if !SWIG
1021 template <typename ArcIndexTypeStrictWeakOrderingFunctor>
1023 const ArcIndexTypeStrictWeakOrderingFunctor& compare,
1024 PermutationCycleHandler<ArcIndexType>* annotation_handler) {
1025 std::unique_ptr<ArcIndexType[]> arc_permutation(
1026 new ArcIndexType[end_arc_index()]);
1027
1028 // Determine the permutation that groups arcs by their tail nodes.
1029 for (ArcIndexType i = 0; i < end_arc_index(); ++i) {
1030 // Start with the identity permutation.
1031 arc_permutation[i] = i;
1032 }
1033 std::sort(&arc_permutation[kFirstArc], &arc_permutation[end_arc_index()],
1034 compare);
1035
1036 // Now we actually permute the head_ array and the
1037 // scaled_arc_cost_ array according to the sorting permutation.
1038 CycleHandlerForAnnotatedArcs cycle_handler(annotation_handler,
1039 ThisAsDerived());
1040 PermutationApplier<ArcIndexType> permutation(&cycle_handler);
1041 permutation.Apply(&arc_permutation[0], kFirstArc, end_arc_index());
1042
1043 // Finally, rebuild the graph from its permuted head_ array.
1044 ThisAsDerived()->BuildRepresentation();
1045 }
1046
1048 : public PermutationCycleHandler<ArcIndexType> {
1049 public:
1051 PermutationCycleHandler<ArcIndexType>* annotation_handler,
1052 DerivedGraph* graph)
1053 : annotation_handler_(annotation_handler),
1054 graph_(graph),
1055 head_temp_(kNilNode),
1056 tail_temp_(kNilNode) {}
1057
1058 void SetTempFromIndex(ArcIndexType source) override {
1059 if (annotation_handler_ != nullptr) {
1060 annotation_handler_->SetTempFromIndex(source);
1061 }
1062 head_temp_ = graph_->Head(source);
1063 tail_temp_ = graph_->Tail(source);
1064 }
1065
1066 void SetIndexFromIndex(ArcIndexType source,
1067 ArcIndexType destination) const override {
1068 if (annotation_handler_ != nullptr) {
1069 annotation_handler_->SetIndexFromIndex(source, destination);
1070 }
1071 graph_->SetHead(destination, graph_->Head(source));
1072 graph_->SetTail(destination, graph_->Tail(source));
1073 }
1074
1075 void SetIndexFromTemp(ArcIndexType destination) const override {
1076 if (annotation_handler_ != nullptr) {
1077 annotation_handler_->SetIndexFromTemp(destination);
1078 }
1079 graph_->SetHead(destination, head_temp_);
1080 graph_->SetTail(destination, tail_temp_);
1081 }
1082
1083 // Since we are free to destroy the permutation array we use the
1084 // kNilArc value to mark entries in the array that have been
1085 // processed already. There is no need to be able to recover the
1086 // original permutation array entries once they have been seen.
1087 void SetSeen(ArcIndexType* permutation_element) const override {
1088 *permutation_element = kNilArc;
1089 }
1090
1091 bool Unseen(ArcIndexType permutation_element) const override {
1092 return permutation_element != kNilArc;
1093 }
1094
1096
1097 private:
1098 PermutationCycleHandler<ArcIndexType>* annotation_handler_;
1099 DerivedGraph* graph_;
1100 NodeIndexType head_temp_;
1101 NodeIndexType tail_temp_;
1102
1103 DISALLOW_COPY_AND_ASSIGN(CycleHandlerForAnnotatedArcs);
1104 };
1105#endif // SWIG
1106
1107 protected:
1109
1111
1112 void Initialize(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs) {
1114 LOG(DFATAL) << "Could not reserve memory for "
1115 << static_cast<int64>(max_num_nodes) << " nodes and "
1116 << static_cast<int64>(max_num_arcs) << " arcs.";
1117 }
1119 ThisAsDerived()->InitializeInternal(max_num_nodes, max_num_arcs);
1120 }
1121
1122 // Returns the first arc in node's incidence list.
1124 const NodeIndexType node) const {
1126 DCHECK(IsNodeValid(node));
1127 return first_incident_arc_[node];
1128 }
1129
1130 // Returns the next arc following the passed argument in its adjacency list.
1131 ArcIndexType NextAdjacentArc(const ArcIndexType arc) const {
1133 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
1134 return next_adjacent_arc_[arc];
1135 }
1136
1137 // Returns the outgoing arc following the argument in the adjacency list.
1138 ArcIndexType NextOutgoingArc(const NodeIndexType unused_node,
1139 const ArcIndexType arc) const {
1140 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
1141 DCHECK(ThisAsDerived()->IsDirect(arc));
1142 return ThisAsDerived()->FindNextOutgoingArc(NextAdjacentArc(arc));
1143 }
1144
1145 // Array of next indices.
1146 // next_adjacent_arc_[i] contains the next arc in the adjacency list of arc i.
1148
1149 // Flag to indicate that BuildRepresentation() needs to be called
1150 // before the adjacency lists are examined. Only for DCHECK in debug
1151 // builds.
1153
1154 private:
1155 // Shorthand: returns a const DerivedGraph*-typed version of our
1156 // "this" pointer.
1157 inline const DerivedGraph* ThisAsDerived() const {
1158 return static_cast<const DerivedGraph*>(this);
1159 }
1160
1161 // Shorthand: returns a DerivedGraph*-typed version of our "this"
1162 // pointer.
1163 inline DerivedGraph* ThisAsDerived() {
1164 return static_cast<DerivedGraph*>(this);
1165 }
1166
1167 void InitializeInternal(NodeIndexType max_num_nodes,
1168 ArcIndexType max_num_arcs) {
1170 }
1171
1172 bool RepresentationClean() const { return representation_clean_; }
1173
1174 // Using the SetHead() method implies that the BuildRepresentation()
1175 // method must be called to restore consistency before the graph is
1176 // used.
1177 void SetHead(const ArcIndexType arc, const NodeIndexType head) {
1178 representation_clean_ = false;
1179 head_.Set(arc, head);
1180 }
1181};
1182
1183// Most users should only use StarGraph, which is EbertGraph<int32, int32>, and
1184// other type shortcuts; see the bottom of this file.
1185template <typename NodeIndexType, typename ArcIndexType>
1187 : public EbertGraphBase<NodeIndexType, ArcIndexType,
1188 EbertGraph<NodeIndexType, ArcIndexType> > {
1189 typedef EbertGraphBase<NodeIndexType, ArcIndexType,
1192 friend class EbertGraphBase<NodeIndexType, ArcIndexType,
1193 EbertGraph<NodeIndexType, ArcIndexType> >;
1194 friend class StarGraphBase<NodeIndexType, ArcIndexType,
1195 EbertGraph<NodeIndexType, ArcIndexType> >;
1196
1199 using Base::Initialize;
1202
1204 using Base::head_;
1205 using Base::max_num_arcs_;
1208 using Base::num_arcs_;
1209 using Base::num_nodes_;
1211
1212 public:
1213#if !SWIG
1214 using Base::Head;
1215 using Base::IsNodeValid;
1216
1217 using Base::kFirstArc;
1218 using Base::kFirstNode;
1219 using Base::kNilArc;
1220 using Base::kNilNode;
1221#endif // SWIG
1222
1223 typedef NodeIndexType NodeIndex;
1224 typedef ArcIndexType ArcIndex;
1225
1227
1228 EbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs) {
1230 }
1231
1233
1234#if !SWIG
1235 // Iterator class for traversing the arcs incident to a given node in the
1236 // graph.
1238 public:
1240 NodeIndexType node)
1241 : graph_(graph),
1242 node_(graph_.StartNode(node)),
1243 arc_(graph_.StartArc(
1244 graph_.FirstOutgoingOrOppositeIncomingArc(node))) {
1245 DCHECK(CheckInvariant());
1246 }
1247
1248 // This constructor takes an arc as extra argument and makes the iterator
1249 // start at arc.
1251 NodeIndexType node, ArcIndexType arc)
1252 : graph_(graph),
1253 node_(graph_.StartNode(node)),
1254 arc_(graph_.StartArc(arc)) {
1255 DCHECK(CheckInvariant());
1256 }
1257
1258 // Can only assign from an iterator on the same graph.
1260 DCHECK(&iterator.graph_ == &graph_);
1261 node_ = iterator.node_;
1262 arc_ = iterator.arc_;
1263 }
1264
1265 // Returns true unless all the adjancent arcs have been traversed.
1266 bool Ok() const { return arc_ != kNilArc; }
1267
1268 // Advances the current adjacent arc index.
1269 void Next() {
1270 arc_ = graph_.NextAdjacentArc(arc_);
1271 DCHECK(CheckInvariant());
1272 }
1273
1274 // Returns the index of the arc currently pointed to by the iterator.
1275 ArcIndexType Index() const { return arc_; }
1276
1277 private:
1278 // Returns true if the invariant for the iterator is verified.
1279 // To be used in a DCHECK.
1280 bool CheckInvariant() const {
1281 if (arc_ == kNilArc) {
1282 return true; // This occurs when the iterator has reached the end.
1283 }
1284 DCHECK(graph_.IsOutgoingOrOppositeIncoming(arc_, node_));
1285 return true;
1286 }
1287 // A reference to the current EbertGraph considered.
1288 const EbertGraph& graph_;
1289
1290 // The index of the node on which arcs are iterated.
1291 NodeIndexType node_;
1292
1293 // The index of the current arc considered.
1294 ArcIndexType arc_;
1295 };
1296
1297 // Iterator class for traversing the incoming arcs associated to a given node.
1299 public:
1300 IncomingArcIterator(const EbertGraph& graph, NodeIndexType node)
1301 : graph_(graph),
1302 node_(graph_.StartNode(node)),
1303 arc_(graph_.StartArc(graph_.FirstIncomingArc(node))) {
1304 DCHECK(CheckInvariant());
1305 }
1306
1307 // This constructor takes an arc as extra argument and makes the iterator
1308 // start at arc.
1309 IncomingArcIterator(const EbertGraph& graph, NodeIndexType node,
1310 ArcIndexType arc)
1311 : graph_(graph),
1312 node_(graph_.StartNode(node)),
1313 arc_(arc == kNilArc ? kNilArc
1314 : graph_.StartArc(graph_.Opposite(arc))) {
1315 DCHECK(CheckInvariant());
1316 }
1317
1318 // Can only assign from an iterator on the same graph.
1319 void operator=(const IncomingArcIterator& iterator) {
1320 DCHECK(&iterator.graph_ == &graph_);
1321 node_ = iterator.node_;
1322 arc_ = iterator.arc_;
1323 }
1324
1325 // Returns true unless all the incoming arcs have been traversed.
1326 bool Ok() const { return arc_ != kNilArc; }
1327
1328 // Advances the current incoming arc index.
1329 void Next() {
1330 arc_ = graph_.NextIncomingArc(arc_);
1331 DCHECK(CheckInvariant());
1332 }
1333
1334 // Returns the index of the arc currently pointed to by the iterator.
1335 ArcIndexType Index() const {
1336 return arc_ == kNilArc ? kNilArc : graph_.Opposite(arc_);
1337 }
1338
1339 private:
1340 // Returns true if the invariant for the iterator is verified.
1341 // To be used in a DCHECK.
1342 bool CheckInvariant() const {
1343 if (arc_ == kNilArc) {
1344 return true; // This occurs when the iterator has reached the end.
1345 }
1346 DCHECK(graph_.IsIncoming(Index(), node_));
1347 return true;
1348 }
1349 // A reference to the current EbertGraph considered.
1350 const EbertGraph& graph_;
1351
1352 // The index of the node on which arcs are iterated.
1353 NodeIndexType node_;
1354
1355 // The index of the current arc considered.
1356 ArcIndexType arc_;
1357 };
1358#endif // SWIG
1359
1360 // Utility function to check that an arc index is within the bounds.
1361 // It is exported so that users of the EbertGraph class can use it.
1362 // To be used in a DCHECK.
1363 bool CheckArcBounds(const ArcIndexType arc) const {
1364 return (arc == kNilArc) || (arc >= -max_num_arcs_ && arc < max_num_arcs_);
1365 }
1366
1367 // Utility function to check that an arc index is within the bounds AND
1368 // different from kNilArc.
1369 // It is exported so that users of the EbertGraph class can use it.
1370 // To be used in a DCHECK.
1371 bool CheckArcValidity(const ArcIndexType arc) const {
1372 return (arc != kNilArc) && (arc >= -max_num_arcs_ && arc < max_num_arcs_);
1373 }
1374
1375 // Returns the tail or start-node of arc.
1376 NodeIndexType Tail(const ArcIndexType arc) const {
1378 return head_[Opposite(arc)];
1379 }
1380
1381 // Returns the tail or start-node of arc if it is positive
1382 // (i.e. it is taken in the direction it was entered in the graph),
1383 // and the head or end-node otherwise. 'This' in Ebert's paper.
1384 NodeIndexType DirectArcTail(const ArcIndexType arc) const {
1385 return Tail(DirectArc(arc));
1386 }
1387
1388 // Returns the head or end-node of arc if it is positive
1389 // (i.e. it is taken in the direction it was entered in the graph),
1390 // and the tail or start-node otherwise. 'That' in Ebert's paper.
1391 NodeIndexType DirectArcHead(const ArcIndexType arc) const {
1392 return Head(DirectArc(arc));
1393 }
1394
1395 // Returns the arc in normal/direct direction.
1396 ArcIndexType DirectArc(const ArcIndexType arc) const {
1398 return std::max(arc, Opposite(arc));
1399 }
1400
1401 // Returns the arc in reverse direction.
1402 ArcIndexType ReverseArc(const ArcIndexType arc) const {
1404 return std::min(arc, Opposite(arc));
1405 }
1406
1407 // Returns the opposite arc, i.e the direct arc is the arc is in reverse
1408 // direction, and the reverse arc if the arc is direct.
1409 ArcIndexType Opposite(const ArcIndexType arc) const {
1410 const ArcIndexType opposite = ~arc;
1412 DCHECK(CheckArcValidity(opposite));
1413 return opposite;
1414 }
1415
1416 // Returns true if the arc is direct.
1417 bool IsDirect(const ArcIndexType arc) const {
1418 DCHECK(CheckArcBounds(arc));
1419 return arc != kNilArc && arc >= 0;
1420 }
1421
1422 // Returns true if the arc is in the reverse direction.
1423 bool IsReverse(const ArcIndexType arc) const {
1424 DCHECK(CheckArcBounds(arc));
1425 return arc != kNilArc && arc < 0;
1426 }
1427
1428 // Returns true if arc is incident to node.
1429 bool IsOutgoingOrOppositeIncoming(ArcIndexType arc,
1430 NodeIndexType node) const {
1431 return Tail(arc) == node;
1432 }
1433
1434 // Returns true if arc is incoming to node.
1435 bool IsIncoming(ArcIndexType arc, NodeIndexType node) const {
1436 return IsDirect(arc) && Head(arc) == node;
1437 }
1438
1439 // Returns true if arc is outgoing from node.
1440 bool IsOutgoing(ArcIndexType arc, NodeIndexType node) const {
1441 return IsDirect(arc) && Tail(arc) == node;
1442 }
1443
1444 // Recreates the next_adjacent_arc_ and first_incident_arc_ variables from
1445 // the array head_ in O(n + m) time.
1446 // This is useful if head_ array has been sorted according to a given
1447 // criterion, for example.
1450 for (ArcIndexType arc = kFirstArc; arc < max_num_arcs_; ++arc) {
1451 Attach(arc);
1452 }
1453 representation_clean_ = true;
1454 }
1455
1456 // Returns a debug string containing all the information contained in the
1457 // data structure in raw form.
1458 std::string DebugString() const {
1460 std::string result = "Arcs:(node, next arc) :\n";
1461 for (ArcIndexType arc = -num_arcs_; arc < num_arcs_; ++arc) {
1462 result += " " + ArcDebugString(arc) + ":(" + NodeDebugString(head_[arc]) +
1463 "," + ArcDebugString(next_adjacent_arc_[arc]) + ")\n";
1464 }
1465 result += "Node:First arc :\n";
1466 for (NodeIndexType node = kFirstNode; node < num_nodes_; ++node) {
1467 result += " " + NodeDebugString(node) + ":" +
1468 ArcDebugString(first_incident_arc_[node]) + "\n";
1469 }
1470 return result;
1471 }
1472
1473 private:
1474 // Handles reserving space in the next_adjacent_arc_ and head_
1475 // arrays, which are always present and are therefore in the base
1476 // class. Although they reside in the base class, those two arrays
1477 // are maintained differently by different derived classes,
1478 // depending on whether the derived class stores reverse arcs. Hence
1479 // the code to set those arrays up is in a method of the derived
1480 // class.
1481 void ReserveInternal(NodeIndexType new_max_num_nodes,
1482 ArcIndexType new_max_num_arcs) {
1483 head_.Reserve(-new_max_num_arcs, new_max_num_arcs - 1);
1484 next_adjacent_arc_.Reserve(-new_max_num_arcs, new_max_num_arcs - 1);
1485 for (ArcIndexType arc = -new_max_num_arcs; arc < -max_num_arcs_; ++arc) {
1486 head_.Set(arc, kNilNode);
1488 }
1489 for (ArcIndexType arc = max_num_arcs_; arc < new_max_num_arcs; ++arc) {
1490 head_.Set(arc, kNilNode);
1492 }
1493 }
1494
1495 // Returns the first incoming arc for node.
1496 ArcIndexType FirstIncomingArc(const NodeIndexType node) const {
1497 DCHECK_LE(kFirstNode, node);
1499 return FindNextIncomingArc(FirstOutgoingOrOppositeIncomingArc(node));
1500 }
1501
1502 // Returns the incoming arc following the argument in the adjacency list.
1503 ArcIndexType NextIncomingArc(const ArcIndexType arc) const {
1505 DCHECK(IsReverse(arc));
1506 return FindNextIncomingArc(NextAdjacentArc(arc));
1507 }
1508
1509 // Handles the part of AddArc() that is not in common with other
1510 // graph classes based on the EbertGraphBase template.
1511 void RecordArc(ArcIndexType arc, NodeIndexType tail, NodeIndexType head) {
1512 head_.Set(Opposite(arc), tail);
1513 head_.Set(arc, head);
1514 Attach(arc);
1515 }
1516
1517 // Using the SetTail() method implies that the BuildRepresentation()
1518 // method must be called to restore consistency before the graph is
1519 // used.
1520 void SetTail(const ArcIndexType arc, const NodeIndexType tail) {
1521 representation_clean_ = false;
1522 head_.Set(Opposite(arc), tail);
1523 }
1524
1525 // Utility method to attach a new arc.
1526 void Attach(ArcIndexType arc) {
1528 const NodeIndexType tail = head_[Opposite(arc)];
1532 const NodeIndexType head = head_[arc];
1536 }
1537
1538 // Utility method that finds the next outgoing arc.
1539 ArcIndexType FindNextOutgoingArc(ArcIndexType arc) const {
1540 DCHECK(CheckArcBounds(arc));
1541 while (IsReverse(arc)) {
1542 arc = NextAdjacentArc(arc);
1543 DCHECK(CheckArcBounds(arc));
1544 }
1545 return arc;
1546 }
1547
1548 // Utility method that finds the next incoming arc.
1549 ArcIndexType FindNextIncomingArc(ArcIndexType arc) const {
1550 DCHECK(CheckArcBounds(arc));
1551 while (IsDirect(arc)) {
1552 arc = NextAdjacentArc(arc);
1553 DCHECK(CheckArcBounds(arc));
1554 }
1555 return arc;
1556 }
1557};
1558
1559// A forward-star-only graph representation for greater efficiency in
1560// those algorithms that don't need reverse arcs.
1561template <typename NodeIndexType, typename ArcIndexType>
1563 : public EbertGraphBase<NodeIndexType, ArcIndexType,
1564 ForwardEbertGraph<NodeIndexType, ArcIndexType> > {
1565 typedef EbertGraphBase<NodeIndexType, ArcIndexType,
1568 friend class EbertGraphBase<NodeIndexType, ArcIndexType,
1569 ForwardEbertGraph<NodeIndexType, ArcIndexType> >;
1570 friend class StarGraphBase<NodeIndexType, ArcIndexType,
1571 ForwardEbertGraph<NodeIndexType, ArcIndexType> >;
1572
1574 using Base::Initialize;
1577
1579 using Base::head_;
1580 using Base::max_num_arcs_;
1583 using Base::num_arcs_;
1584 using Base::num_nodes_;
1586
1587 public:
1588#if !SWIG
1589 using Base::Head;
1590 using Base::IsNodeValid;
1591
1592 using Base::kFirstArc;
1593 using Base::kFirstNode;
1594 using Base::kNilArc;
1595 using Base::kNilNode;
1596#endif // SWIG
1597
1598 typedef NodeIndexType NodeIndex;
1599 typedef ArcIndexType ArcIndex;
1600
1602
1603 ForwardEbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs) {
1605 }
1606
1608
1609 // Utility function to check that an arc index is within the bounds.
1610 // It is exported so that users of the ForwardEbertGraph class can use it.
1611 // To be used in a DCHECK.
1612 bool CheckArcBounds(const ArcIndexType arc) const {
1613 return (arc == kNilArc) || (arc >= kFirstArc && arc < max_num_arcs_);
1614 }
1615
1616 // Utility function to check that an arc index is within the bounds AND
1617 // different from kNilArc.
1618 // It is exported so that users of the ForwardEbertGraph class can use it.
1619 // To be used in a DCHECK.
1620 bool CheckArcValidity(const ArcIndexType arc) const {
1621 return (arc != kNilArc) && (arc >= kFirstArc && arc < max_num_arcs_);
1622 }
1623
1624 // Returns true if arc is a valid index into the (*tail_) array.
1625 bool CheckTailIndexValidity(const ArcIndexType arc) const {
1626 return (tail_ != nullptr) && (arc >= kFirstArc) &&
1627 (arc <= tail_->max_index());
1628 }
1629
1630 // Returns the tail or start-node of arc.
1631 NodeIndexType Tail(const ArcIndexType arc) const {
1634 return (*tail_)[arc];
1635 }
1636
1637 // Returns true if arc is incoming to node.
1638 bool IsIncoming(ArcIndexType arc, NodeIndexType node) const {
1639 return IsDirect(arc) && Head(arc) == node;
1640 }
1641
1642 // Recreates the next_adjacent_arc_ and first_incident_arc_
1643 // variables from the arrays head_ and tail_ in O(n + m) time. This
1644 // is useful if the head_ and tail_ arrays have been sorted
1645 // according to a given criterion, for example.
1649 for (ArcIndexType arc = kFirstArc; arc < max_num_arcs_; ++arc) {
1651 Attach((*tail_)[arc], arc);
1652 }
1653 representation_clean_ = true;
1654 }
1655
1657 // If (*tail_) is already allocated, we have the invariant that
1658 // its contents are canonical, so we do not need to do anything
1659 // here in that case except return true.
1660 if (tail_ == nullptr) {
1661 if (!representation_clean_) {
1662 // We have been asked to build the (*tail_) array, but we have
1663 // no valid information from which to build it. The graph is
1664 // in an unrecoverable, inconsistent state.
1665 return false;
1666 }
1667 // Reallocate (*tail_) and rebuild its contents from the
1668 // adjacency lists.
1669 tail_.reset(new ZVector<NodeIndexType>);
1670 tail_->Reserve(kFirstArc, max_num_arcs_ - 1);
1671 typename Base::NodeIterator node_it(*this);
1672 for (; node_it.Ok(); node_it.Next()) {
1673 NodeIndexType node = node_it.Index();
1674 typename Base::OutgoingArcIterator arc_it(*this, node);
1675 for (; arc_it.Ok(); arc_it.Next()) {
1676 (*tail_)[arc_it.Index()] = node;
1677 }
1678 }
1679 }
1681 return true;
1682 }
1683
1684 void ReleaseTailArray() { tail_.reset(nullptr); }
1685
1686 // To be used in a DCHECK().
1687 bool TailArrayComplete() const {
1688 CHECK(tail_);
1689 for (ArcIndexType arc = kFirstArc; arc < num_arcs_; ++arc) {
1691 CHECK(IsNodeValid((*tail_)[arc]));
1692 }
1693 return true;
1694 }
1695
1696 // Returns a debug string containing all the information contained in the
1697 // data structure in raw form.
1698 std::string DebugString() const {
1700 std::string result = "Arcs:(node, next arc) :\n";
1701 for (ArcIndexType arc = kFirstArc; arc < num_arcs_; ++arc) {
1702 result += " " + ArcDebugString(arc) + ":(" + NodeDebugString(head_[arc]) +
1703 "," + ArcDebugString(next_adjacent_arc_[arc]) + ")\n";
1704 }
1705 result += "Node:First arc :\n";
1706 for (NodeIndexType node = kFirstNode; node < num_nodes_; ++node) {
1707 result += " " + NodeDebugString(node) + ":" +
1708 ArcDebugString(first_incident_arc_[node]) + "\n";
1709 }
1710 return result;
1711 }
1712
1713 private:
1714 // Reserves space for the (*tail_) array.
1715 //
1716 // This method is separate from ReserveInternal() because our
1717 // practice of making the (*tail_) array optional implies that the
1718 // tail_ pointer might not be constructed when the ReserveInternal()
1719 // method is called. Therefore we have this method also, and we
1720 // ensure that it is called only when tail_ is guaranteed to have
1721 // been initialized.
1722 void ReserveTailArray(ArcIndexType new_max_num_arcs) {
1723 if (tail_ != nullptr) {
1724 // The (*tail_) values are already canonical, so we're just
1725 // reserving additional space for new arcs that haven't been
1726 // added yet.
1727 if (tail_->Reserve(kFirstArc, new_max_num_arcs - 1)) {
1728 for (ArcIndexType arc = tail_->max_index() + 1; arc < new_max_num_arcs;
1729 ++arc) {
1730 tail_->Set(arc, kNilNode);
1731 }
1732 }
1733 }
1734 }
1735
1736 // Reserves space for the arrays indexed by arc indices, except
1737 // (*tail_) even if it is present. We cannot grow the (*tail_) array
1738 // in this method because this method is called from
1739 // Base::Reserve(), which in turn is called from the base template
1740 // class constructor. That base class constructor is called on *this
1741 // before tail_ is constructed. Hence when this method is called,
1742 // tail_ might contain garbage. This method can safely refer only to
1743 // fields of the base template class, not to fields of *this outside
1744 // the base template class.
1745 //
1746 // The strange situation in which this method of a derived class can
1747 // refer only to members of the base class arises because different
1748 // derived classes use the data members of the base class in
1749 // slightly different ways. The purpose of this derived class
1750 // method, then, is only to encode the derived-class-specific
1751 // conventions for how the derived class uses the data members of
1752 // the base class.
1753 //
1754 // To be specific, the forward-star graph representation, lacking
1755 // reverse arcs, allocates only the positive index range for the
1756 // head_ and next_adjacent_arc_ arrays, while the general
1757 // representation allocates space for both positive- and
1758 // negative-indexed arcs (i.e., both forward and reverse arcs).
1759 void ReserveInternal(NodeIndexType new_max_num_nodes,
1760 ArcIndexType new_max_num_arcs) {
1761 head_.Reserve(kFirstArc, new_max_num_arcs - 1);
1762 next_adjacent_arc_.Reserve(kFirstArc, new_max_num_arcs - 1);
1763 for (ArcIndexType arc = max_num_arcs_; arc < new_max_num_arcs; ++arc) {
1764 head_.Set(arc, kNilNode);
1766 }
1767 ReserveTailArray(new_max_num_arcs);
1768 }
1769
1770 // Handles the part of AddArc() that is not in common wth other
1771 // graph classes based on the EbertGraphBase template.
1772 void RecordArc(ArcIndexType arc, NodeIndexType tail, NodeIndexType head) {
1773 head_.Set(arc, head);
1774 Attach(tail, arc);
1775 }
1776
1777 // Using the SetTail() method implies that the BuildRepresentation()
1778 // method must be called to restore consistency before the graph is
1779 // used.
1780 void SetTail(const ArcIndexType arc, const NodeIndexType tail) {
1782 CHECK(tail_);
1783 representation_clean_ = false;
1784 tail_->Set(arc, tail);
1785 }
1786
1787 // Utility method to attach a new arc.
1788 void Attach(NodeIndexType tail, ArcIndexType arc) {
1793 const NodeIndexType head = head_[arc];
1795 // Because Attach() is a public method, keeping (*tail_) canonical
1796 // requires us to record the new arc's tail here.
1797 if (tail_ != nullptr) {
1799 tail_->Set(arc, tail);
1800 }
1801 }
1802
1803 // Utility method that finds the next outgoing arc.
1804 ArcIndexType FindNextOutgoingArc(ArcIndexType arc) const {
1805 DCHECK(CheckArcBounds(arc));
1806 return arc;
1807 }
1808
1809 private:
1810 // Always returns true because for any ForwardEbertGraph, only
1811 // direct arcs are represented, so all valid arc indices refer to
1812 // arcs that are outgoing from their tail nodes.
1813 bool IsOutgoing(const ArcIndex unused_arc,
1814 const NodeIndex unused_node) const {
1815 return true;
1816 }
1817
1818 // Always returns true because for any ForwardEbertGraph, only
1819 // outgoing arcs are represented, so all valid arc indices refer to
1820 // direct arcs.
1821 bool IsDirect(const ArcIndex unused_arc) const { return true; }
1822
1823 // Array of node indices, not always present. (*tail_)[i] contains
1824 // the tail node of arc i. This array is not needed for normal graph
1825 // traversal operations, but is used in optimizing the graph's
1826 // layout so arcs are grouped by tail node, and can be used in one
1827 // approach to serializing the graph.
1828 //
1829 // Invariants: At any time when we are not executing a method of
1830 // this class, either tail_ == NULL or the tail_ array's contents
1831 // are kept canonical. If tail_ != NULL, any method that modifies
1832 // adjacency lists must also ensure (*tail_) is modified
1833 // correspondingly. The converse does not hold: Modifications to
1834 // (*tail_) are allowed without updating the adjacency lists. If
1835 // such modifications take place, representation_clean_ must be set
1836 // to false, of course, to indicate that the adjacency lists are no
1837 // longer current.
1838 std::unique_ptr<ZVector<NodeIndexType> > tail_;
1839};
1840
1841// Traits for EbertGraphBase types, for use in testing and clients
1842// that work with both forward-only and forward/reverse graphs.
1843//
1844// The default is to assume reverse arcs so if someone forgets to
1845// specialize the traits of a new forward-only graph type, they will
1846// get errors from tests rather than incomplete testing.
1847template <typename GraphType>
1849 static constexpr bool has_reverse_arcs = true;
1850 static constexpr bool is_dynamic = true;
1851};
1852
1853template <typename NodeIndexType, typename ArcIndexType>
1854struct graph_traits<ForwardEbertGraph<NodeIndexType, ArcIndexType> > {
1855 static constexpr bool has_reverse_arcs = false;
1856 static constexpr bool is_dynamic = true;
1857};
1858
1859template <typename NodeIndexType, typename ArcIndexType>
1860struct graph_traits<ForwardStaticGraph<NodeIndexType, ArcIndexType> > {
1861 static constexpr bool has_reverse_arcs = false;
1862 static constexpr bool is_dynamic = false;
1863};
1864
1865namespace or_internal {
1866
1867// The TailArrayBuilder class template is not expected to be used by
1868// clients. It is a helper for the TailArrayManager template.
1869//
1870// The TailArrayBuilder for graphs with reverse arcs does nothing.
1871template <typename GraphType, bool has_reverse_arcs>
1873 explicit TailArrayBuilder(GraphType* unused_graph) {}
1874
1875 bool BuildTailArray() const { return true; }
1876};
1877
1878// The TailArrayBuilder for graphs without reverse arcs calls the
1879// appropriate method on the graph from the TailArrayBuilder
1880// constructor.
1881template <typename GraphType>
1882struct TailArrayBuilder<GraphType, false> {
1883 explicit TailArrayBuilder(GraphType* graph) : graph_(graph) {}
1884
1885 bool BuildTailArray() const { return graph_->BuildTailArray(); }
1886
1887 GraphType* const graph_;
1888};
1889
1890// The TailArrayReleaser class template is not expected to be used by
1891// clients. It is a helper for the TailArrayManager template.
1892//
1893// The TailArrayReleaser for graphs with reverse arcs does nothing.
1894template <typename GraphType, bool has_reverse_arcs>
1896 explicit TailArrayReleaser(GraphType* unused_graph) {}
1897
1898 void ReleaseTailArray() const {}
1899};
1900
1901// The TailArrayReleaser for graphs without reverse arcs calls the
1902// appropriate method on the graph from the TailArrayReleaser
1903// constructor.
1904template <typename GraphType>
1905struct TailArrayReleaser<GraphType, false> {
1906 explicit TailArrayReleaser(GraphType* graph) : graph_(graph) {}
1907
1908 void ReleaseTailArray() const { graph_->ReleaseTailArray(); }
1909
1910 GraphType* const graph_;
1911};
1912
1913} // namespace or_internal
1914
1915template <typename GraphType>
1917 public:
1918 explicit TailArrayManager(GraphType* g) : graph_(g) {}
1919
1923 tail_array_builder(graph_);
1924 return tail_array_builder.BuildTailArray();
1925 }
1926
1930 tail_array_releaser(graph_);
1931 tail_array_releaser.ReleaseTailArray();
1932 }
1933
1934 private:
1935 GraphType* graph_;
1936};
1937
1938template <typename GraphType>
1940 public:
1941 explicit ArcFunctorOrderingByTailAndHead(const GraphType& graph)
1942 : graph_(graph) {}
1943
1945 typename GraphType::ArcIndex b) const {
1946 return ((graph_.Tail(a) < graph_.Tail(b)) ||
1947 ((graph_.Tail(a) == graph_.Tail(b)) &&
1948 (graph_.Head(a) < graph_.Head(b))));
1949 }
1950
1951 private:
1952 const GraphType& graph_;
1953};
1954
1955namespace or_internal {
1956
1957// The GraphBuilderFromArcs class template is not expected to be used
1958// by clients. It is a helper for the AnnotatedGraphBuildManager
1959// template.
1960//
1961// Deletes itself upon returning the graph!
1962template <typename GraphType, bool is_dynamic>
1964 public:
1966 typename GraphType::ArcIndex max_num_arcs,
1967 bool sort_arcs)
1968 : num_arcs_(0), sort_arcs_(sort_arcs) {
1969 Reserve(max_num_nodes, max_num_arcs);
1970 }
1971
1973 typename GraphType::NodeIndex head) {
1974 DCHECK_LT(num_arcs_, max_num_arcs_);
1975 DCHECK_LT(tail, GraphType::kFirstNode + max_num_nodes_);
1976 DCHECK_LT(head, GraphType::kFirstNode + max_num_nodes_);
1977 if (num_arcs_ < max_num_arcs_ &&
1978 tail < GraphType::kFirstNode + max_num_nodes_ &&
1979 head < GraphType::kFirstNode + max_num_nodes_) {
1980 typename GraphType::ArcIndex result = GraphType::kFirstArc + num_arcs_;
1981 arcs_.push_back(std::make_pair(tail, head));
1982 num_arcs_ += 1;
1983 return result;
1984 } else {
1985 // Too many arcs or node index out of bounds!
1986 return GraphType::kNilArc;
1987 }
1988 }
1989
1990 // Builds the graph from the given arcs.
1992 client_cycle_handler) {
1993 GraphType* graph = new GraphType(max_num_nodes_, num_arcs_, sort_arcs_,
1994 &arcs_, client_cycle_handler);
1995 delete this;
1996 return graph;
1997 }
1998
1999 private:
2000 bool Reserve(typename GraphType::NodeIndex new_max_num_nodes,
2001 typename GraphType::ArcIndex new_max_num_arcs) {
2002 max_num_nodes_ = new_max_num_nodes;
2003 max_num_arcs_ = new_max_num_arcs;
2004 arcs_.reserve(new_max_num_arcs);
2005 return true;
2006 }
2007
2008 typename GraphType::NodeIndex max_num_nodes_;
2009 typename GraphType::ArcIndex max_num_arcs_;
2010 typename GraphType::ArcIndex num_arcs_;
2011
2012 std::vector<
2013 std::pair<typename GraphType::NodeIndex, typename GraphType::NodeIndex> >
2014 arcs_;
2015
2016 const bool sort_arcs_;
2017};
2018
2019// Trivial delegating specialization for dynamic graphs.
2020//
2021// Deletes itself upon returning the graph!
2022template <typename GraphType>
2023class GraphBuilderFromArcs<GraphType, true> {
2024 public:
2026 typename GraphType::ArcIndex max_num_arcs,
2027 bool sort_arcs)
2028 : graph_(new GraphType(max_num_nodes, max_num_arcs)),
2029 sort_arcs_(sort_arcs) {}
2030
2031 bool Reserve(const typename GraphType::NodeIndex new_max_num_nodes,
2032 const typename GraphType::ArcIndex new_max_num_arcs) {
2033 return graph_->Reserve(new_max_num_nodes, new_max_num_arcs);
2034 }
2035
2037 const typename GraphType::NodeIndex tail,
2038 const typename GraphType::NodeIndex head) {
2039 return graph_->AddArc(tail, head);
2040 }
2041
2043 client_cycle_handler) {
2044 if (sort_arcs_) {
2045 TailArrayManager<GraphType> tail_array_manager(graph_);
2047 ArcFunctorOrderingByTailAndHead<GraphType> arc_ordering(*graph_);
2048 graph_->GroupForwardArcsByFunctor(arc_ordering, client_cycle_handler);
2049 tail_array_manager.ReleaseTailArrayIfForwardGraph();
2050 }
2051 GraphType* result = graph_;
2052 delete this;
2053 return result;
2054 }
2055
2056 private:
2057 GraphType* const graph_;
2058 const bool sort_arcs_;
2059};
2060
2061} // namespace or_internal
2062
2063template <typename GraphType>
2066 GraphType, graph_traits<GraphType>::is_dynamic> {
2067 public:
2069 typename GraphType::ArcIndex num_arcs,
2070 bool sort_arcs)
2071 : or_internal::GraphBuilderFromArcs<GraphType,
2072 graph_traits<GraphType>::is_dynamic>(
2073 num_nodes, num_arcs, sort_arcs) {}
2074};
2075
2076// Builds a directed line graph for 'graph' (see "directed line graph" in
2077// http://en.wikipedia.org/wiki/Line_graph). Arcs of the original graph
2078// become nodes and the new graph contains only nodes created from arcs in the
2079// original graph (we use the notation (a->b) for these new nodes); the index
2080// of the node (a->b) in the new graph is exactly the same as the index of the
2081// arc a->b in the original graph.
2082// An arc from node (a->b) to node (c->d) in the new graph is added if and only
2083// if b == c in the original graph.
2084// This method expects that 'line_graph' is an empty graph (it has no nodes
2085// and no arcs).
2086// Returns false on an error.
2087template <typename GraphType>
2088bool BuildLineGraph(const GraphType& graph, GraphType* const line_graph) {
2089 if (line_graph == nullptr) {
2090 LOG(DFATAL) << "line_graph must not be NULL";
2091 return false;
2092 }
2093 if (line_graph->num_nodes() != 0) {
2094 LOG(DFATAL) << "line_graph must be empty";
2095 return false;
2096 }
2097 typedef typename GraphType::ArcIterator ArcIterator;
2098 typedef typename GraphType::OutgoingArcIterator OutgoingArcIterator;
2099 // Sizing then filling.
2100 typename GraphType::ArcIndex num_arcs = 0;
2101 for (ArcIterator arc_iterator(graph); arc_iterator.Ok();
2102 arc_iterator.Next()) {
2103 const typename GraphType::ArcIndex arc = arc_iterator.Index();
2104 const typename GraphType::NodeIndex head = graph.Head(arc);
2105 for (OutgoingArcIterator iterator(graph, head); iterator.Ok();
2106 iterator.Next()) {
2107 ++num_arcs;
2108 }
2109 }
2110 line_graph->Reserve(graph.num_arcs(), num_arcs);
2111 for (ArcIterator arc_iterator(graph); arc_iterator.Ok();
2112 arc_iterator.Next()) {
2113 const typename GraphType::ArcIndex arc = arc_iterator.Index();
2114 const typename GraphType::NodeIndex head = graph.Head(arc);
2115 for (OutgoingArcIterator iterator(graph, head); iterator.Ok();
2116 iterator.Next()) {
2117 line_graph->AddArc(arc, iterator.Index());
2118 }
2119 }
2120 return true;
2121}
2122
2123} // namespace operations_research
2124#endif // OR_TOOLS_GRAPH_EBERT_GRAPH_H_
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
AnnotatedGraphBuildManager(typename GraphType::NodeIndex num_nodes, typename GraphType::ArcIndex num_arcs, bool sort_arcs)
Definition: ebert_graph.h:2068
bool operator()(typename GraphType::ArcIndex a, typename GraphType::ArcIndex b) const
Definition: ebert_graph.h:1944
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
void operator=(const IncomingArcIterator &iterator)
Definition: ebert_graph.h:1319
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: ebert_graph.h:1309
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
Definition: ebert_graph.h:1300
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: ebert_graph.h:1250
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
Definition: ebert_graph.h:1239
void operator=(const OutgoingOrOppositeIncomingArcIterator &iterator)
Definition: ebert_graph.h:1259
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
Definition: ebert_graph.h:1066
bool Unseen(ArcIndexType permutation_element) const override
Definition: ebert_graph.h:1091
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, DerivedGraph *graph)
Definition: ebert_graph.h:1050
void SetIndexFromTemp(ArcIndexType destination) const override
Definition: ebert_graph.h:1075
void SetSeen(ArcIndexType *permutation_element) const override
Definition: ebert_graph.h:1087
static const NodeIndexType kNilNode
Definition: ebert_graph.h:216
ZVector< ArcIndexType > next_adjacent_arc_
Definition: ebert_graph.h:1147
bool IsNodeValid(NodeIndexType node) const
Definition: ebert_graph.h:279
static const ArcIndexType kFirstArc
Definition: ebert_graph.h:225
ArcIndexType NextOutgoingArc(const NodeIndexType unused_node, const ArcIndexType arc) const
Definition: ebert_graph.h:1138
ZVector< ArcIndexType > first_incident_arc_
Definition: ebert_graph.h:502
static const ArcIndexType kMaxNumArcs
Definition: ebert_graph.h:235
bool Reserve(NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs)
Definition: ebert_graph.h:978
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: ebert_graph.h:1001
ZVector< NodeIndexType > head_
Definition: ebert_graph.h:498
ArcIndexType end_arc_index() const
Definition: ebert_graph.h:252
void Initialize(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
Definition: ebert_graph.h:1112
ArcIndexType FirstOutgoingOrOppositeIncomingArc(const NodeIndexType node) const
Definition: ebert_graph.h:1123
void GroupForwardArcsByFunctor(const ArcIndexTypeStrictWeakOrderingFunctor &compare, PermutationCycleHandler< ArcIndexType > *annotation_handler)
Definition: ebert_graph.h:1022
static const ArcIndexType kNilArc
Definition: ebert_graph.h:219
static const NodeIndexType kMaxNumNodes
Definition: ebert_graph.h:230
static const NodeIndexType kFirstNode
Definition: ebert_graph.h:222
ArcIndexType NextAdjacentArc(const ArcIndexType arc) const
Definition: ebert_graph.h:1131
bool IsOutgoingOrOppositeIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1429
bool IsDirect(const ArcIndexType arc) const
Definition: ebert_graph.h:1417
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1435
NodeIndexType DirectArcHead(const ArcIndexType arc) const
Definition: ebert_graph.h:1391
bool CheckArcValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:1371
ArcIndexType Opposite(const ArcIndexType arc) const
Definition: ebert_graph.h:1409
bool IsOutgoing(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1440
std::string DebugString() const
Definition: ebert_graph.h:1458
bool IsReverse(const ArcIndexType arc) const
Definition: ebert_graph.h:1423
ArcIndexType ReverseArc(const ArcIndexType arc) const
Definition: ebert_graph.h:1402
ArcIndexType DirectArc(const ArcIndexType arc) const
Definition: ebert_graph.h:1396
NodeIndexType Tail(const ArcIndexType arc) const
Definition: ebert_graph.h:1376
EbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
Definition: ebert_graph.h:1228
bool CheckArcBounds(const ArcIndexType arc) const
Definition: ebert_graph.h:1363
NodeIndexType DirectArcTail(const ArcIndexType arc) const
Definition: ebert_graph.h:1384
ForwardEbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
Definition: ebert_graph.h:1603
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1638
bool CheckArcValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:1620
bool CheckTailIndexValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:1625
NodeIndexType Tail(const ArcIndexType arc) const
Definition: ebert_graph.h:1631
bool CheckArcBounds(const ArcIndexType arc) const
Definition: ebert_graph.h:1612
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
Definition: ebert_graph.h:586
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, NodeIndexType *data)
Definition: ebert_graph.h:575
void SetIndexFromTemp(ArcIndexType destination) const override
Definition: ebert_graph.h:592
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:763
bool CheckArcValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:778
bool CheckTailIndexValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:783
ArcIndexType NextOutgoingArc(const NodeIndexType node, ArcIndexType arc) const
Definition: ebert_graph.h:788
ForwardStaticGraph(const NodeIndexType num_nodes, const ArcIndexType num_arcs, const bool sort_arcs_by_head, std::vector< std::pair< NodeIndexType, NodeIndexType > > *client_input_arcs, operations_research::PermutationCycleHandler< ArcIndexType > *const client_cycle_handler)
Definition: ebert_graph.h:621
NodeIndexType Tail(const ArcIndexType arc) const
Definition: ebert_graph.h:756
bool CheckArcBounds(const ArcIndexType arc) const
Definition: ebert_graph.h:770
void Apply(IndexType permutation[], int permutation_start, int permutation_end)
virtual void SetIndexFromTemp(IndexType destination) const =0
virtual void SetTempFromIndex(IndexType source)=0
virtual void SetIndexFromIndex(IndexType source, IndexType destination) const =0
PermutationIndexComparisonByArcHead(const ZVector< NodeIndexType > &head)
Definition: ebert_graph.h:521
bool operator()(ArcIndexType a, ArcIndexType b) const
Definition: ebert_graph.h:525
void operator=(const OutgoingArcIterator &iterator)
Definition: ebert_graph.h:386
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: ebert_graph.h:377
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node)
Definition: ebert_graph.h:368
static const NodeIndexType kNilNode
Definition: ebert_graph.h:216
ArcIndexType NextArc(const ArcIndexType arc) const
Definition: ebert_graph.h:472
NodeIndexType max_num_nodes() const
Definition: ebert_graph.h:255
bool IsNodeValid(NodeIndexType node) const
Definition: ebert_graph.h:279
static const ArcIndexType kFirstArc
Definition: ebert_graph.h:225
ArcIndexType num_arcs() const
Definition: ebert_graph.h:241
NodeIndexType Head(const ArcIndexType arc) const
Definition: ebert_graph.h:297
ZVector< ArcIndexType > first_incident_arc_
Definition: ebert_graph.h:502
std::string ArcDebugString(const ArcIndexType arc) const
Definition: ebert_graph.h:310
static const ArcIndexType kMaxNumArcs
Definition: ebert_graph.h:235
NodeIndexType num_nodes() const
Definition: ebert_graph.h:237
ArcIndexType max_num_arcs() const
Definition: ebert_graph.h:259
std::string NodeDebugString(const NodeIndexType node) const
Definition: ebert_graph.h:302
ZVector< NodeIndexType > head_
Definition: ebert_graph.h:498
ArcIndexType end_arc_index() const
Definition: ebert_graph.h:252
static const ArcIndexType kNilArc
Definition: ebert_graph.h:219
ArcIndexType max_end_arc_index() const
Definition: ebert_graph.h:271
static const NodeIndexType kMaxNumNodes
Definition: ebert_graph.h:230
NodeIndexType end_node_index() const
Definition: ebert_graph.h:247
NodeIndexType StartNode(NodeIndexType node) const
Definition: ebert_graph.h:439
ArcIndexType FirstOutgoingArc(const NodeIndexType node) const
Definition: ebert_graph.h:479
static const NodeIndexType kFirstNode
Definition: ebert_graph.h:222
NodeIndexType max_end_node_index() const
Definition: ebert_graph.h:264
NodeIndexType NextNode(const NodeIndexType node) const
Definition: ebert_graph.h:458
ArcIndexType StartArc(ArcIndexType arc) const
Definition: ebert_graph.h:445
ArcIndexType LookUpArc(const NodeIndexType tail, const NodeIndexType head) const
Definition: ebert_graph.h:285
bool BuildTailArrayFromAdjacencyListsIfForwardGraph() const
Definition: ebert_graph.h:1920
void Set(int64 index, T value)
Definition: zvector.h:88
bool Reserve(int64 new_min_index, int64 new_max_index)
Definition: zvector.h:98
int64 max_index() const
Definition: zvector.h:60
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
Definition: ebert_graph.h:2042
bool Reserve(const typename GraphType::NodeIndex new_max_num_nodes, const typename GraphType::ArcIndex new_max_num_arcs)
Definition: ebert_graph.h:2031
GraphType::ArcIndex AddArc(const typename GraphType::NodeIndex tail, const typename GraphType::NodeIndex head)
Definition: ebert_graph.h:2036
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
Definition: ebert_graph.h:2025
GraphType::ArcIndex AddArc(typename GraphType::NodeIndex tail, typename GraphType::NodeIndex head)
Definition: ebert_graph.h:1972
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
Definition: ebert_graph.h:1991
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
Definition: ebert_graph.h:1965
int int32
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ZVector< FlowQuantity > QuantityArray
Definition: ebert_graph.h:209
ZVector< NodeIndex > NodeIndexArray
Definition: ebert_graph.h:207
bool BuildLineGraph(const GraphType &graph, GraphType *const line_graph)
Definition: ebert_graph.h:2088
ForwardStaticGraph< NodeIndex, ArcIndex > ForwardStarStaticGraph
Definition: ebert_graph.h:206
ForwardEbertGraph< NodeIndex, ArcIndex > ForwardStarGraph
Definition: ebert_graph.h:205
ZVector< CostValue > CostArray
Definition: ebert_graph.h:210
ZVector< ArcIndex > ArcIndexArray
Definition: ebert_graph.h:208
EbertGraph< NodeIndex, ArcIndex > StarGraph
Definition: ebert_graph.h:204
int64 tail
int64 head
static constexpr bool has_reverse_arcs
Definition: ebert_graph.h:1849
static constexpr bool is_dynamic
Definition: ebert_graph.h:1850