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