155 #ifndef UTIL_GRAPH_GRAPH_H_
156 #define UTIL_GRAPH_GRAPH_H_
165 #include "absl/debugging/leak_check.h"
166 #include "ortools/base/integral_types.h"
167 #include "ortools/base/logging.h"
168 #include "ortools/base/macros.h"
174 template <
typename T>
183 template <
typename NodeIndexType = int32,
typename ArcIndexType = int32,
184 bool HasReverseArcs =
false>
264 template <
typename A,
typename B>
266 LOG(FATAL) <<
"Not supported";
274 std::vector<ArcIndexType>* start,
275 std::vector<ArcIndexType>* permutation);
297 template <
typename NodeIndexType =
int32,
typename ArcIndexType =
int32>
322 void AddNode(NodeIndexType node);
330 ArcIndexType
AddArc(NodeIndexType tail, NodeIndexType head);
341 void Build(std::vector<ArcIndexType>* permutation);
344 class OutgoingArcIterator;
345 class OutgoingHeadIterator;
352 ArcIndexType
OutDegree(NodeIndexType node)
const;
362 NodeIndexType node, ArcIndexType from)
const;
370 NodeIndexType
Tail(ArcIndexType arc)
const;
371 NodeIndexType
Head(ArcIndexType arc)
const;
377 std::vector<ArcIndexType> start_;
378 std::vector<ArcIndexType> next_;
379 std::vector<NodeIndexType> head_;
380 std::vector<NodeIndexType> tail_;
396 template <
typename NodeIndexType =
int32,
typename ArcIndexType =
int32>
407 StaticGraph() : is_built_(false), arc_in_order_(true), last_tail_seen_(0) {}
409 : is_built_(false), arc_in_order_(true), last_tail_seen_(0) {
416 class OutgoingArcIterator;
418 NodeIndexType
Head(ArcIndexType arc)
const;
419 NodeIndexType
Tail(ArcIndexType arc)
const;
420 ArcIndexType
OutDegree(NodeIndexType node)
const;
423 NodeIndexType node, ArcIndexType from)
const;
432 void AddNode(NodeIndexType node);
433 ArcIndexType
AddArc(NodeIndexType tail, NodeIndexType head);
436 void Build(std::vector<ArcIndexType>* permutation);
439 ArcIndexType DirectArcLimit(NodeIndexType node)
const {
442 return node + 1 < num_nodes_ ? start_[node + 1] : num_arcs_;
447 NodeIndexType last_tail_seen_;
448 std::vector<ArcIndexType> start_;
449 std::vector<NodeIndexType> head_;
450 std::vector<NodeIndexType> tail_;
459 template <
typename NodeIndexType =
int32,
typename ArcIndexType =
int32>
461 :
public BaseGraph<NodeIndexType, ArcIndexType, true> {
483 class OutgoingOrOppositeIncomingArcIterator;
484 class OppositeIncomingArcIterator;
485 class IncomingArcIterator;
486 class OutgoingArcIterator;
487 class OutgoingHeadIterator;
490 ArcIndexType
OutDegree(NodeIndexType node)
const;
491 ArcIndexType
InDegree(NodeIndexType node)
const;
504 NodeIndexType node)
const;
506 NodeIndexType node, ArcIndexType from)
const;
508 NodeIndexType node, ArcIndexType from)
const;
511 ArcIndexType from)
const;
513 NodeIndexType node, ArcIndexType from)
const;
520 NodeIndexType
Head(ArcIndexType arc)
const;
521 NodeIndexType
Tail(ArcIndexType arc)
const;
525 void AddNode(NodeIndexType node);
526 ArcIndexType
AddArc(NodeIndexType tail, NodeIndexType head);
529 void Build(std::vector<ArcIndexType>* permutation);
532 std::vector<ArcIndexType> start_;
533 std::vector<ArcIndexType> reverse_start_;
547 template <
typename NodeIndexType =
int32,
typename ArcIndexType =
int32>
549 :
public BaseGraph<NodeIndexType, ArcIndexType, true> {
568 class OutgoingOrOppositeIncomingArcIterator;
569 class OppositeIncomingArcIterator;
570 class IncomingArcIterator;
571 class OutgoingArcIterator;
574 ArcIndexType
OutDegree(NodeIndexType node)
const;
575 ArcIndexType
InDegree(NodeIndexType node)
const;
582 NodeIndexType node)
const;
584 NodeIndexType node, ArcIndexType from)
const;
586 NodeIndexType node, ArcIndexType from)
const;
589 ArcIndexType from)
const;
591 NodeIndexType node, ArcIndexType from)
const;
600 NodeIndexType
Head(ArcIndexType arc)
const;
601 NodeIndexType
Tail(ArcIndexType arc)
const;
604 void AddNode(NodeIndexType node);
605 ArcIndexType
AddArc(NodeIndexType tail, NodeIndexType head);
608 void Build(std::vector<ArcIndexType>* permutation);
611 ArcIndexType DirectArcLimit(NodeIndexType node)
const {
614 return node + 1 < num_nodes_ ? start_[node + 1] : num_arcs_;
616 ArcIndexType ReverseArcLimit(NodeIndexType node)
const {
619 return node + 1 < num_nodes_ ? reverse_start_[node + 1] : 0;
623 std::vector<ArcIndexType> start_;
624 std::vector<ArcIndexType> reverse_start_;
625 SVector<NodeIndexType> head_;
626 SVector<ArcIndexType> opposite_;
635 template <
typename NodeIndexType =
int32,
typename ArcIndexType =
int32>
637 :
public BaseGraph<NodeIndexType, ArcIndexType, true> {
656 class OutgoingOrOppositeIncomingArcIterator;
657 class OppositeIncomingArcIterator;
658 class IncomingArcIterator;
659 class OutgoingArcIterator;
661 ArcIndexType
OutDegree(NodeIndexType node)
const;
662 ArcIndexType
InDegree(NodeIndexType node)
const;
669 NodeIndexType node)
const;
671 NodeIndexType node, ArcIndexType from)
const;
673 NodeIndexType node, ArcIndexType from)
const;
676 ArcIndexType from)
const;
678 NodeIndexType node, ArcIndexType from)
const;
687 NodeIndexType
Head(ArcIndexType arc)
const;
688 NodeIndexType
Tail(ArcIndexType arc)
const;
691 void AddNode(NodeIndexType node);
692 ArcIndexType
AddArc(NodeIndexType tail, NodeIndexType head);
695 void Build(std::vector<ArcIndexType>* permutation);
698 ArcIndexType DirectArcLimit(NodeIndexType node)
const {
701 return node + 1 < num_nodes_ ? start_[node + 1] : num_arcs_;
705 std::vector<ArcIndexType> start_;
706 std::vector<ArcIndexType> reverse_start_;
707 std::vector<ArcIndexType> next_;
708 SVector<NodeIndexType> head_;
724 template <
class IntVector,
class Array,
class ElementType>
726 Array* array_to_permute,
727 ElementType unused) {
728 std::vector<ElementType> temp(permutation.size());
729 for (
int i = 0; i < permutation.size(); ++i) {
730 temp[i] = (*array_to_permute)[i];
732 for (
int i = 0; i < permutation.size(); ++i) {
733 (*array_to_permute)[permutation[i]] = temp[i];
737 template <
class IntVector,
class Array>
738 void Permute(
const IntVector& permutation, Array* array_to_permute) {
739 if (permutation.empty()) {
743 (*array_to_permute)[0]);
748 template <
class IntVector>
750 std::vector<bool>* array_to_permute) {
751 if (permutation.empty()) {
772 template <
typename T>
775 SVector() : base_(nullptr), size_(0), capacity_(0) {}
782 if (capacity_ < other.size_) {
786 capacity_ = other.size_;
787 base_ = Allocate(capacity_);
788 CHECK(base_ !=
nullptr);
795 for (
int i = -size_; i < size_; ++i) {
796 new (base_ + i) T(other.base_[i]);
814 DCHECK_GE(n, -size_);
820 DCHECK_GE(n, -size_);
826 for (
int i = -n; i < -size_; ++i) {
829 for (
int i = size_; i < n; ++i) {
832 for (
int i = -size_; i < -n; ++i) {
835 for (
int i = n; i < size_; ++i) {
843 T*
data()
const {
return base_; }
846 std::swap(base_, x.base_);
847 std::swap(size_, x.size_);
848 std::swap(capacity_, x.capacity_);
855 const int new_capacity = std::min(n,
max_size());
856 T* new_storage = Allocate(new_capacity);
857 CHECK(new_storage !=
nullptr);
858 T* new_base = new_storage + new_capacity;
861 for (
int i = -size_; i < size_; ++i) {
862 new (new_base + i) T(std::move(base_[i]));
864 int saved_size = size_;
868 capacity_ = new_capacity;
874 void grow(
const T& left = T(),
const T& right = T()) {
875 if (size_ == capacity_) {
881 new (base_ + size_) T(right_copy);
882 new (base_ - size_ - 1) T(left_copy);
885 new (base_ + size_) T(right);
886 new (base_ - size_ - 1) T(left);
891 int size()
const {
return size_; }
895 int max_size()
const {
return std::numeric_limits<int>::max(); }
898 if (base_ ==
nullptr)
return;
901 free(base_ - capacity_);
909 return absl::IgnoreLeak(
910 static_cast<T*
>(malloc(2LL *
capacity *
sizeof(T))));
913 int NewCapacity(
int delta) {
915 double candidate = 1.3 *
static_cast<double>(capacity_);
916 if (candidate >
static_cast<double>(
max_size())) {
917 candidate =
static_cast<double>(
max_size());
919 int new_capacity =
static_cast<int>(candidate);
920 if (new_capacity > capacity_ + delta) {
923 return capacity_ + delta;
933 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
934 IntegerRange<NodeIndexType>
939 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
945 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
948 std::numeric_limits<NodeIndexType>::max();
950 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
953 std::numeric_limits<ArcIndexType>::max();
955 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
960 return node_capacity_ > num_nodes_ ? node_capacity_ : num_nodes_;
963 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
967 return arc_capacity_ > num_arcs_ ? arc_capacity_ : num_arcs_;
970 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
971 void BaseGraph<NodeIndexType, ArcIndexType,
972 HasReverseArcs>::FreezeCapacities() {
975 const_capacities_ =
true;
976 node_capacity_ = std::max(node_capacity_, num_nodes_);
977 arc_capacity_ = std::max(arc_capacity_, num_arcs_);
982 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
985 ArcIndexType sum = 0;
986 for (
int i = 0; i < num_nodes_; ++i) {
987 ArcIndexType temp = (*v)[i];
991 DCHECK(sum == num_arcs_);
999 template <
typename NodeIndexType,
typename ArcIndexType,
bool HasReverseArcs>
1002 std::vector<ArcIndexType>* start,
1003 std::vector<ArcIndexType>* permutation) {
1007 start->assign(num_nodes_, 0);
1008 int last_tail_seen = 0;
1009 bool permutation_needed =
false;
1010 for (
int i = 0; i < num_arcs_; ++i) {
1011 NodeIndexType tail = (*head)[i];
1012 if (!permutation_needed) {
1013 permutation_needed = tail < last_tail_seen;
1014 last_tail_seen = tail;
1018 ComputeCumulativeSum(start);
1022 if (!permutation_needed) {
1023 for (
int i = 0; i < num_arcs_; ++i) {
1024 (*head)[i] = (*head)[~i];
1026 if (permutation !=
nullptr) {
1027 permutation->clear();
1034 std::vector<ArcIndexType> perm(num_arcs_);
1035 for (
int i = 0; i < num_arcs_; ++i) {
1036 perm[i] = (*start)[(*head)[i]]++;
1040 for (
int i = num_nodes_ - 1; i > 0; --i) {
1041 (*start)[i] = (*start)[i - 1];
1047 for (
int i = 0; i < num_arcs_; ++i) {
1048 (*head)[perm[i]] = (*head)[~i];
1050 if (permutation !=
nullptr) {
1051 permutation->swap(perm);
1064 #define DEFINE_RANGE_BASED_ARC_ITERATION(c, t, e) \
1065 template <typename NodeIndexType, typename ArcIndexType> \
1066 BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \
1067 c<NodeIndexType, ArcIndexType>::t##Arcs(NodeIndexType node) const { \
1068 return BeginEndWrapper<t##ArcIterator>(t##ArcIterator(*this, node), \
1069 t##ArcIterator(*this, node, e)); \
1071 template <typename NodeIndexType, typename ArcIndexType> \
1072 BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \
1073 c<NodeIndexType, ArcIndexType>::t##ArcsStartingFrom( \
1074 NodeIndexType node, ArcIndexType from) const { \
1075 return BeginEndWrapper<t##ArcIterator>(t##ArcIterator(*this, node, from), \
1076 t##ArcIterator(*this, node, e)); \
1081 #define DEFINE_STL_ITERATOR_FUNCTIONS(iterator_class_name) \
1082 using iterator_category = std::input_iterator_tag; \
1083 using difference_type = ptrdiff_t; \
1084 using pointer = const ArcIndexType*; \
1085 using reference = const ArcIndexType&; \
1086 using value_type = ArcIndexType; \
1087 bool operator!=(const iterator_class_name& other) const { \
1088 return this->index_ != other.index_; \
1090 bool operator==(const iterator_class_name& other) const { \
1091 return this->index_ == other.index_; \
1093 ArcIndexType operator*() const { return this->Index(); } \
1094 void operator++() { this->Next(); }
1100 template <
typename NodeIndexType,
typename ArcIndexType>
1109 template <
typename NodeIndexType,
typename ArcIndexType>
1111 ArcIndexType arc)
const {
1112 DCHECK(IsArcValid(arc));
1116 template <
typename NodeIndexType,
typename ArcIndexType>
1118 ArcIndexType arc)
const {
1119 DCHECK(IsArcValid(arc));
1123 template <
typename NodeIndexType,
typename ArcIndexType>
1125 NodeIndexType node)
const {
1126 ArcIndexType degree(0);
1127 for (
auto arc ABSL_ATTRIBUTE_UNUSED : OutgoingArcs(node)) ++degree;
1131 template <
typename NodeIndexType,
typename ArcIndexType>
1133 if (node < num_nodes_)
return;
1134 DCHECK(!const_capacities_ || node < node_capacity_);
1135 num_nodes_ = node + 1;
1136 start_.resize(num_nodes_, Base::kNilArc);
1139 template <
typename NodeIndexType,
typename ArcIndexType>
1141 NodeIndexType tail, NodeIndexType head) {
1144 AddNode(tail > head ? tail : head);
1145 head_.push_back(head);
1146 tail_.push_back(tail);
1147 next_.push_back(start_[tail]);
1148 start_[tail] = num_arcs_;
1149 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1153 template <
typename NodeIndexType,
typename ArcIndexType>
1155 Base::ReserveNodes(bound);
1156 if (bound <= num_nodes_)
return;
1157 start_.reserve(bound);
1160 template <
typename NodeIndexType,
typename ArcIndexType>
1162 Base::ReserveArcs(bound);
1163 if (bound <= num_arcs_)
return;
1164 head_.reserve(bound);
1165 tail_.reserve(bound);
1166 next_.reserve(bound);
1169 template <
typename NodeIndexType,
typename ArcIndexType>
1171 std::vector<ArcIndexType>* permutation) {
1172 if (permutation !=
nullptr) {
1173 permutation->clear();
1177 template <
typename NodeIndexType,
typename ArcIndexType>
1181 : graph_(graph), index_(graph.start_[node]) {
1186 : graph_(graph), index_(arc) {
1191 ArcIndexType
Index()
const {
return index_; }
1194 index_ = graph_.next_[index_];
1201 ArcIndexType index_;
1204 template <
typename NodeIndexType,
typename ArcIndexType>
1214 : graph_(graph), index_(graph.start_[node]) {
1219 : graph_(graph), index_(arc) {
1224 NodeIndexType
Index()
const {
return graph_.Head(index_); }
1227 index_ = graph_.next_[index_];
1233 return index_ != other.index_;
1240 ArcIndexType index_;
1247 template <
typename NodeIndexType,
typename ArcIndexType>
1251 head_.data() + start_[node], head_.data() + DirectArcLimit(node));
1254 template <
typename NodeIndexType,
typename ArcIndexType>
1256 NodeIndexType node)
const {
1257 return DirectArcLimit(node) - start_[node];
1260 template <
typename NodeIndexType,
typename ArcIndexType>
1262 NodeIndexType bound) {
1263 Base::ReserveNodes(bound);
1264 if (bound <= num_nodes_)
return;
1265 start_.reserve(bound);
1268 template <
typename NodeIndexType,
typename ArcIndexType>
1270 Base::ReserveArcs(bound);
1271 if (bound <= num_arcs_)
return;
1272 head_.reserve(bound);
1273 tail_.reserve(bound);
1276 template <
typename NodeIndexType,
typename ArcIndexType>
1278 if (node < num_nodes_)
return;
1279 DCHECK(!const_capacities_ || node < node_capacity_) << node;
1280 num_nodes_ = node + 1;
1281 start_.resize(num_nodes_, 0);
1284 template <
typename NodeIndexType,
typename ArcIndexType>
1286 NodeIndexType tail, NodeIndexType head) {
1290 AddNode(tail > head ? tail : head);
1291 if (arc_in_order_) {
1292 if (tail >= last_tail_seen_) {
1294 last_tail_seen_ = tail;
1296 arc_in_order_ =
false;
1299 tail_.push_back(tail);
1300 head_.push_back(head);
1301 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1305 template <
typename NodeIndexType,
typename ArcIndexType>
1307 ArcIndexType arc)
const {
1308 DCHECK(IsArcValid(arc));
1312 template <
typename NodeIndexType,
typename ArcIndexType>
1314 ArcIndexType arc)
const {
1315 DCHECK(IsArcValid(arc));
1331 template <
typename NodeIndexType,
typename ArcIndexType>
1333 std::vector<ArcIndexType>* permutation) {
1335 if (is_built_)
return;
1337 node_capacity_ = num_nodes_;
1338 arc_capacity_ = num_arcs_;
1339 this->FreezeCapacities();
1342 if (arc_in_order_) {
1343 if (permutation !=
nullptr) {
1344 permutation->clear();
1346 this->ComputeCumulativeSum(&start_);
1352 start_.assign(num_nodes_, 0);
1353 for (
int i = 0; i < num_arcs_; ++i) {
1356 this->ComputeCumulativeSum(&start_);
1360 std::vector<ArcIndexType> perm(num_arcs_);
1361 for (
int i = 0; i < num_arcs_; ++i) {
1362 perm[i] = start_[tail_[i]]++;
1366 CHECK_EQ(tail_.size(), num_arcs_);
1368 for (
int i = 0; i < num_arcs_; ++i) {
1369 head_[perm[i]] = tail_[i];
1372 if (permutation !=
nullptr) {
1373 permutation->swap(perm);
1377 for (
int i = num_nodes_ - 1; i > 0; --i) {
1378 start_[i] = start_[i - 1];
1383 for (
const NodeIndexType node : Base::AllNodes()) {
1384 for (
const ArcIndexType arc : OutgoingArcs(node)) {
1390 template <
typename NodeIndexType,
typename ArcIndexType>
1394 : index_(graph.start_[node]), limit_(graph.DirectArcLimit(node)) {}
1397 : index_(arc), limit_(graph.DirectArcLimit(node)) {
1398 DCHECK_GE(arc, graph.start_[node]);
1401 bool Ok()
const {
return index_ < limit_; }
1402 ArcIndexType
Index()
const {
return index_; }
1418 ArcIndexType index_;
1419 const ArcIndexType limit_;
1427 OutgoingOrOppositeIncoming, Base::kNilArc);
1431 template <
typename NodeIndexType,
typename ArcIndexType>
1433 NodeIndexType, ArcIndexType>::OutgoingHeadIterator>
1435 NodeIndexType node)
const {
1441 template <
typename NodeIndexType,
typename ArcIndexType>
1443 NodeIndexType node)
const {
1444 ArcIndexType degree(0);
1445 for (
auto arc ABSL_ATTRIBUTE_UNUSED : OutgoingArcs(node)) ++degree;
1449 template <
typename NodeIndexType,
typename ArcIndexType>
1451 NodeIndexType node)
const {
1452 ArcIndexType degree(0);
1453 for (
auto arc ABSL_ATTRIBUTE_UNUSED : OppositeIncomingArcs(node)) ++degree;
1457 template <
typename NodeIndexType,
typename ArcIndexType>
1459 ArcIndexType arc)
const {
1460 DCHECK(IsArcValid(arc));
1464 template <
typename NodeIndexType,
typename ArcIndexType>
1466 ArcIndexType arc)
const {
1467 DCHECK(IsArcValid(arc));
1471 template <
typename NodeIndexType,
typename ArcIndexType>
1473 ArcIndexType arc)
const {
1474 return head_[OppositeArc(arc)];
1477 template <
typename NodeIndexType,
typename ArcIndexType>
1479 NodeIndexType bound) {
1480 Base::ReserveNodes(bound);
1481 if (bound <= num_nodes_)
return;
1482 start_.reserve(bound);
1483 reverse_start_.reserve(bound);
1486 template <
typename NodeIndexType,
typename ArcIndexType>
1488 ArcIndexType bound) {
1489 Base::ReserveArcs(bound);
1490 if (bound <= num_arcs_)
return;
1491 head_.reserve(bound);
1492 next_.reserve(bound);
1495 template <
typename NodeIndexType,
typename ArcIndexType>
1497 NodeIndexType node) {
1498 if (node < num_nodes_)
return;
1499 DCHECK(!const_capacities_ || node < node_capacity_);
1500 num_nodes_ = node + 1;
1501 start_.resize(num_nodes_, Base::kNilArc);
1502 reverse_start_.resize(num_nodes_, Base::kNilArc);
1505 template <
typename NodeIndexType,
typename ArcIndexType>
1507 NodeIndexType tail, NodeIndexType head) {
1510 AddNode(tail > head ? tail : head);
1511 head_.grow(tail, head);
1512 next_.grow(reverse_start_[head], start_[tail]);
1513 start_[tail] = num_arcs_;
1514 reverse_start_[head] = ~num_arcs_;
1515 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1519 template <
typename NodeIndexType,
typename ArcIndexType>
1521 std::vector<ArcIndexType>* permutation) {
1522 if (permutation !=
nullptr) {
1523 permutation->clear();
1527 template <
typename NodeIndexType,
typename ArcIndexType>
1531 : graph_(graph), index_(graph.start_[node]) {
1536 : graph_(graph), index_(arc) {
1542 ArcIndexType
Index()
const {
return index_; }
1545 index_ = graph_.next_[index_];
1552 ArcIndexType index_;
1555 template <
typename NodeIndexType,
typename ArcIndexType>
1561 : graph_(graph), index_(graph.reverse_start_[node]) {
1565 NodeIndexType node, ArcIndexType arc)
1566 : graph_(graph), index_(arc) {
1573 ArcIndexType
Index()
const {
return index_; }
1576 index_ = graph_.next_[index_];
1586 template <
typename NodeIndexType,
typename ArcIndexType>
1602 : this->graph_.OppositeArc(this->index_);
1608 template <
typename NodeIndexType,
typename ArcIndexType>
1614 : graph_(graph), index_(graph.reverse_start_[node]), node_(node) {
1619 NodeIndexType node, ArcIndexType arc)
1620 : graph_(graph), index_(arc), node_(node) {
1626 ArcIndexType
Index()
const {
return index_; }
1630 index_ = graph_.next_[index_];
1632 index_ = graph_.start_[node_];
1635 index_ = graph_.next_[index_];
1643 ArcIndexType index_;
1644 const NodeIndexType node_;
1647 template <
typename NodeIndexType,
typename ArcIndexType>
1651 : graph_(&graph), index_(graph.start_[node]) {
1656 : graph_(&graph), index_(arc) {
1662 ArcIndexType
Index()
const {
return graph_->Head(index_); }
1665 index_ = graph_->next_[index_];
1672 ArcIndexType index_;
1678 DirectArcLimit(node));
1680 ReverseArcLimit(node));
1682 OutgoingOrOppositeIncoming,
1683 DirectArcLimit(node));
1685 ReverseArcLimit(node));
1687 template <
typename NodeIndexType,
typename ArcIndexType>
1689 NodeIndexType node)
const {
1690 return DirectArcLimit(node) - start_[node];
1693 template <
typename NodeIndexType,
typename ArcIndexType>
1695 NodeIndexType node)
const {
1696 return ReverseArcLimit(node) - reverse_start_[node];
1699 template <
typename NodeIndexType,
typename ArcIndexType>
1702 NodeIndexType node)
const {
1704 head_.data() + start_[node], head_.data() + DirectArcLimit(node));
1707 template <
typename NodeIndexType,
typename ArcIndexType>
1709 ArcIndexType arc)
const {
1711 DCHECK(IsArcValid(arc));
1712 return opposite_[arc];
1715 template <
typename NodeIndexType,
typename ArcIndexType>
1717 ArcIndexType arc)
const {
1719 DCHECK(IsArcValid(arc));
1723 template <
typename NodeIndexType,
typename ArcIndexType>
1725 ArcIndexType arc)
const {
1727 return head_[OppositeArc(arc)];
1730 template <
typename NodeIndexType,
typename ArcIndexType>
1732 ArcIndexType bound) {
1733 Base::ReserveArcs(bound);
1734 if (bound <= num_arcs_)
return;
1735 head_.reserve(bound);
1738 template <
typename NodeIndexType,
typename ArcIndexType>
1740 NodeIndexType node) {
1741 if (node < num_nodes_)
return;
1742 DCHECK(!const_capacities_ || node < node_capacity_);
1743 num_nodes_ = node + 1;
1746 template <
typename NodeIndexType,
typename ArcIndexType>
1748 NodeIndexType tail, NodeIndexType head) {
1751 AddNode(tail > head ? tail : head);
1755 head_.grow(head, tail);
1756 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
1760 template <
typename NodeIndexType,
typename ArcIndexType>
1762 std::vector<ArcIndexType>* permutation) {
1764 if (is_built_)
return;
1766 node_capacity_ = num_nodes_;
1767 arc_capacity_ = num_arcs_;
1768 this->FreezeCapacities();
1769 this->BuildStartAndForwardHead(&head_, &start_, permutation);
1772 reverse_start_.assign(num_nodes_, 0);
1773 for (
int i = 0; i < num_arcs_; ++i) {
1774 reverse_start_[head_[i]]++;
1776 this->ComputeCumulativeSum(&reverse_start_);
1780 opposite_.reserve(num_arcs_);
1781 for (
int i = 0; i < num_arcs_; ++i) {
1783 opposite_.grow(0, reverse_start_[head_[i]]++ - num_arcs_);
1787 for (
int i = num_nodes_ - 1; i > 0; --i) {
1788 reverse_start_[i] = reverse_start_[i - 1] - num_arcs_;
1790 if (num_nodes_ != 0) {
1791 reverse_start_[0] = -num_arcs_;
1795 for (
int i = 0; i < num_arcs_; ++i) {
1796 opposite_[opposite_[i]] = i;
1798 for (
const NodeIndexType node : Base::AllNodes()) {
1799 for (
const ArcIndexType arc : OutgoingArcs(node)) {
1800 head_[opposite_[arc]] = node;
1805 template <
typename NodeIndexType,
typename ArcIndexType>
1809 : index_(graph.start_[node]), limit_(graph.DirectArcLimit(node)) {}
1812 : index_(arc), limit_(graph.DirectArcLimit(node)) {
1813 DCHECK_GE(arc, graph.start_[node]);
1816 bool Ok()
const {
return index_ < limit_; }
1817 ArcIndexType
Index()
const {
return index_; }
1828 ArcIndexType index_;
1829 const ArcIndexType limit_;
1832 template <
typename NodeIndexType,
typename ArcIndexType>
1839 limit_(graph.ReverseArcLimit(node)),
1840 index_(graph.reverse_start_[node]) {
1842 DCHECK_LE(index_, limit_);
1845 NodeIndexType node, ArcIndexType arc)
1846 : graph_(graph), limit_(graph.ReverseArcLimit(node)), index_(arc) {
1848 DCHECK_GE(index_, graph.reverse_start_[node]);
1849 DCHECK_LE(index_, limit_);
1852 bool Ok()
const {
return index_ < limit_; }
1853 ArcIndexType
Index()
const {
return index_; }
1867 template <
typename NodeIndexType,
typename ArcIndexType>
1876 arc == graph.ReverseArcLimit(node)
1877 ? graph.ReverseArcLimit(node)
1881 return this->index_ == this->limit_
1883 : this->graph_.OppositeArc(this->index_);
1889 template <
typename NodeIndexType,
typename ArcIndexType>
1895 : index_(graph.reverse_start_[node]),
1896 first_limit_(graph.ReverseArcLimit(node)),
1897 next_start_(graph.start_[node]),
1898 limit_(graph.DirectArcLimit(node)) {
1899 if (index_ == first_limit_) index_ = next_start_;
1901 DCHECK((index_ < first_limit_) || (index_ >= next_start_));
1904 NodeIndexType node, ArcIndexType arc)
1906 first_limit_(graph.ReverseArcLimit(node)),
1907 next_start_(graph.start_[node]),
1908 limit_(graph.DirectArcLimit(node)) {
1910 DCHECK((index_ >= graph.reverse_start_[node] && index_ < first_limit_) ||
1911 (index_ >= next_start_));
1914 ArcIndexType
Index()
const {
return index_; }
1915 bool Ok()
const {
return index_ < limit_; }
1919 if (index_ == first_limit_) {
1920 index_ = next_start_;
1927 ArcIndexType index_;
1928 const ArcIndexType first_limit_;
1929 const ArcIndexType next_start_;
1930 const ArcIndexType limit_;
1936 DirectArcLimit(node));
1939 OutgoingOrOppositeIncoming,
1940 DirectArcLimit(node));
1944 template <
typename NodeIndexType,
typename ArcIndexType>
1946 NodeIndexType node)
const {
1947 return DirectArcLimit(node) - start_[node];
1950 template <
typename NodeIndexType,
typename ArcIndexType>
1952 NodeIndexType node)
const {
1953 ArcIndexType degree(0);
1954 for (
auto arc ABSL_ATTRIBUTE_UNUSED : OppositeIncomingArcs(node)) ++degree;
1958 template <
typename NodeIndexType,
typename ArcIndexType>
1961 NodeIndexType node)
const {
1963 head_.data() + start_[node], head_.data() + DirectArcLimit(node));
1966 template <
typename NodeIndexType,
typename ArcIndexType>
1968 ArcIndexType arc)
const {
1969 DCHECK(IsArcValid(arc));
1973 template <
typename NodeIndexType,
typename ArcIndexType>
1975 ArcIndexType arc)
const {
1977 DCHECK(IsArcValid(arc));
1981 template <
typename NodeIndexType,
typename ArcIndexType>
1983 ArcIndexType arc)
const {
1985 return head_[OppositeArc(arc)];
1988 template <
typename NodeIndexType,
typename ArcIndexType>
1990 ArcIndexType bound) {
1991 Base::ReserveArcs(bound);
1992 if (bound <= num_arcs_)
return;
1993 head_.reserve(bound);
1996 template <
typename NodeIndexType,
typename ArcIndexType>
1998 NodeIndexType node) {
1999 if (node < num_nodes_)
return;
2000 DCHECK(!const_capacities_ || node < node_capacity_);
2001 num_nodes_ = node + 1;
2004 template <
typename NodeIndexType,
typename ArcIndexType>
2006 NodeIndexType tail, NodeIndexType head) {
2009 AddNode(tail > head ? tail : head);
2013 head_.grow(head, tail);
2014 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);
2018 template <
typename NodeIndexType,
typename ArcIndexType>
2020 std::vector<ArcIndexType>* permutation) {
2022 if (is_built_)
return;
2024 node_capacity_ = num_nodes_;
2025 arc_capacity_ = num_arcs_;
2026 this->FreezeCapacities();
2027 this->BuildStartAndForwardHead(&head_, &start_, permutation);
2030 for (
const NodeIndexType node : Base::AllNodes()) {
2031 for (
const ArcIndexType arc : OutgoingArcs(node)) {
2037 reverse_start_.assign(num_nodes_, Base::kNilArc);
2038 next_.reserve(num_arcs_);
2039 for (
const ArcIndexType arc : Base::AllForwardArcs()) {
2040 next_.push_back(reverse_start_[Head(arc)]);
2041 reverse_start_[Head(arc)] = -next_.size();
2045 template <
typename NodeIndexType,
typename ArcIndexType>
2049 : index_(graph.start_[node]), limit_(graph.DirectArcLimit(node)) {}
2052 : index_(arc), limit_(graph.DirectArcLimit(node)) {
2053 DCHECK_GE(arc, graph.start_[node]);
2056 bool Ok()
const {
return index_ < limit_; }
2057 ArcIndexType
Index()
const {
return index_; }
2068 ArcIndexType index_;
2069 const ArcIndexType limit_;
2072 template <
typename NodeIndexType,
typename ArcIndexType>
2079 DCHECK(graph.is_built_);
2081 index_ = graph.reverse_start_[node];
2084 NodeIndexType node, ArcIndexType arc)
2085 : graph_(&graph), index_(arc) {
2086 DCHECK(graph.is_built_);
2092 ArcIndexType
Index()
const {
return index_; }
2095 index_ = graph_->next_[~index_];
2105 template <
typename NodeIndexType,
typename ArcIndexType>
2118 : this->graph_->OppositeArc(this->index_);
2124 template <
typename NodeIndexType,
typename ArcIndexType>
2131 limit_ = graph.DirectArcLimit(node);
2132 index_ = graph.reverse_start_[node];
2133 restart_ = graph.start_[node];
2139 NodeIndexType node, ArcIndexType arc)
2141 limit_ = graph.DirectArcLimit(node);
2143 restart_ = graph.start_[node];
2148 return index_ < limit_;
2150 ArcIndexType
Index()
const {
return index_; }
2154 index_ = graph_->next_[graph_->OppositeArc(index_)];
2167 ArcIndexType index_;
2168 ArcIndexType restart_;
2169 ArcIndexType limit_;
2175 template <
typename NodeIndexType =
int32,
typename ArcIndexType =
int32>
2193 NodeIndexType
Head(ArcIndexType arc)
const;
2194 NodeIndexType
Tail(ArcIndexType arc)
const;
2195 ArcIndexType
OutDegree(NodeIndexType node)
const;
2198 ArcIndexType from)
const;
2202 template <
typename NodeIndexType,
typename ArcIndexType>
2204 ArcIndexType arc)
const {
2205 DCHECK(this->IsArcValid(arc));
2206 return arc % num_nodes_;
2209 template <
typename NodeIndexType,
typename ArcIndexType>
2211 ArcIndexType arc)
const {
2212 DCHECK(this->IsArcValid(arc));
2213 return arc / num_nodes_;
2216 template <
typename NodeIndexType,
typename ArcIndexType>
2218 NodeIndexType node)
const {
2222 template <
typename NodeIndexType,
typename ArcIndexType>
2225 NodeIndexType node)
const {
2226 DCHECK_LT(node, num_nodes_);
2228 static_cast<ArcIndexType
>(num_nodes_) * node,
2229 static_cast<ArcIndexType
>(num_nodes_) * (node + 1));
2232 template <
typename NodeIndexType,
typename ArcIndexType>
2235 NodeIndexType node, ArcIndexType from)
const {
2236 DCHECK_LT(node, num_nodes_);
2238 from,
static_cast<ArcIndexType
>(num_nodes_) * (node + 1));
2241 template <
typename NodeIndexType,
typename ArcIndexType>
2244 NodeIndexType node)
const {
2245 DCHECK_LT(node, num_nodes_);
2252 template <
typename NodeIndexType =
int32,
typename ArcIndexType =
int32>
2254 :
public BaseGraph<NodeIndexType, ArcIndexType, false> {
2268 : left_nodes_(left_nodes), right_nodes_(right_nodes) {
2269 this->
Reserve(left_nodes + right_nodes, left_nodes * right_nodes);
2271 num_nodes_ = left_nodes + right_nodes;
2272 num_arcs_ = left_nodes * right_nodes;
2275 NodeIndexType
Head(ArcIndexType arc)
const;
2276 NodeIndexType
Tail(ArcIndexType arc)
const;
2277 ArcIndexType
OutDegree(NodeIndexType node)
const;
2280 ArcIndexType from)
const;
2287 : index_(graph.right_nodes_ * node),
2288 limit_(node >= graph.left_nodes_ ? index_
2289 : graph.right_nodes_ * (node + 1)) {}
2291 bool Ok()
const {
return index_ < limit_; }
2292 ArcIndexType
Index()
const {
return index_; }
2296 ArcIndexType index_;
2297 const ArcIndexType limit_;
2301 const NodeIndexType left_nodes_;
2302 const NodeIndexType right_nodes_;
2305 template <
typename NodeIndexType,
typename ArcIndexType>
2307 ArcIndexType arc)
const {
2308 DCHECK(this->IsArcValid(arc));
2309 return left_nodes_ + arc % right_nodes_;
2312 template <
typename NodeIndexType,
typename ArcIndexType>
2314 ArcIndexType arc)
const {
2315 DCHECK(this->IsArcValid(arc));
2316 return arc / right_nodes_;
2319 template <
typename NodeIndexType,
typename ArcIndexType>
2321 NodeIndexType node)
const {
2322 return (node < left_nodes_) ? right_nodes_ : 0;
2325 template <
typename NodeIndexType,
typename ArcIndexType>
2328 NodeIndexType node)
const {
2329 if (node < left_nodes_) {
2331 right_nodes_ * (node + 1));
2337 template <
typename NodeIndexType,
typename ArcIndexType>
2340 NodeIndexType node, ArcIndexType from)
const {
2341 if (node < left_nodes_) {
2348 template <
typename NodeIndexType,
typename ArcIndexType>
2351 NodeIndexType node)
const {
2352 if (node < left_nodes_) {
2364 #undef DEFINE_RANGE_BASED_ARC_ITERATION
2365 #undef DEFINE_STL_ITERATOR_FUNCTIONS
ArcIndexType arc_capacity_
static const NodeIndexType kNilNode
IntegerRange< ArcIndex > AllForwardArcs() const
void GroupForwardArcsByFunctor(const A &a, B *b)
bool IsNodeValid(NodeIndexType node) const
virtual void ReserveArcs(ArcIndexType bound)
void Reserve(NodeIndexType node_capacity, ArcIndexType arc_capacity)
NodeIndexType node_capacity_
ArcIndexType num_arcs() const
void BuildStartAndForwardHead(SVector< NodeIndexType > *head, std::vector< ArcIndexType > *start, std::vector< ArcIndexType > *permutation)
NodeIndexType num_nodes() const
ArcIndexType arc_capacity() const
IntegerRange< NodeIndex > AllNodes() const
static const ArcIndexType kNilArc
void ComputeCumulativeSum(std::vector< ArcIndexType > *v)
ArcIndexType max_end_arc_index() const
NodeIndexType node_capacity() const
bool IsArcValid(ArcIndexType arc) const
virtual void ReserveNodes(NodeIndexType bound)
OutgoingArcIterator(const CompleteBipartiteGraph &graph, NodeIndexType node)
ArcIndexType Index() const
IntegerRange< ArcIndexType > OutgoingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
ArcIndexType OutDegree(NodeIndexType node) const
CompleteBipartiteGraph(NodeIndexType left_nodes, NodeIndexType right_nodes)
IntegerRange< NodeIndexType > operator[](NodeIndexType node) const
IntegerRange< ArcIndexType > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
IntegerRange< ArcIndexType > OutgoingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
CompleteGraph(NodeIndexType num_nodes)
ArcIndexType OutDegree(NodeIndexType node) const
IntegerRange< NodeIndexType > operator[](NodeIndexType node) const
IntegerRange< ArcIndexType > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingArcIterator)
OutgoingArcIterator(const ListGraph &graph, NodeIndexType node, ArcIndexType arc)
OutgoingArcIterator(const ListGraph &graph, NodeIndexType node)
ArcIndexType Index() const
const NodeIndexType * pointer
NodeIndexType Index() const
const NodeIndexType & reference
bool operator!=(const typename ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator &other) const
NodeIndexType operator*() const
std::input_iterator_tag iterator_category
OutgoingHeadIterator(const ListGraph &graph, NodeIndexType node, ArcIndexType arc)
ptrdiff_t difference_type
OutgoingHeadIterator(const ListGraph &graph, NodeIndexType node)
BeginEndWrapper< OutgoingHeadIterator > operator[](NodeIndexType node) const
ListGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
NodeIndexType Tail(ArcIndexType arc) const
void ReserveArcs(ArcIndexType bound) override
void ReserveNodes(NodeIndexType bound) override
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
void AddNode(NodeIndexType node)
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
ArcIndexType OutDegree(NodeIndexType node) const
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
IncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
IncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
DEFINE_STL_ITERATOR_FUNCTIONS(IncomingArcIterator)
ArcIndexType Index() const
OppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
const ReverseArcListGraph & graph_
DEFINE_STL_ITERATOR_FUNCTIONS(OppositeIncomingArcIterator)
OppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
ArcIndexType Index() const
OutgoingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
OutgoingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingArcIterator)
ArcIndexType Index() const
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingHeadIterator)
OutgoingHeadIterator(const ReverseArcListGraph &graph, NodeIndexType node)
ArcIndexType Index() const
OutgoingHeadIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
OutgoingOrOppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node)
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingOrOppositeIncomingArcIterator)
ArcIndexType Index() const
OutgoingOrOppositeIncomingArcIterator(const ReverseArcListGraph &graph, NodeIndexType node, ArcIndexType arc)
ArcIndexType OppositeArc(ArcIndexType arc) const
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
void ReserveArcs(ArcIndexType bound) override
BeginEndWrapper< IncomingArcIterator > IncomingArcs(NodeIndexType node) const
void ReserveNodes(NodeIndexType bound) override
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
ArcIndexType InDegree(NodeIndexType node) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
void AddNode(NodeIndexType node)
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
ReverseArcListGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs(NodeIndexType node) const
ArcIndexType OutDegree(NodeIndexType node) const
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
BeginEndWrapper< OutgoingHeadIterator > operator[](NodeIndexType node) const
IncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
IncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
DEFINE_STL_ITERATOR_FUNCTIONS(IncomingArcIterator)
ArcIndexType Index() const
DEFINE_STL_ITERATOR_FUNCTIONS(OppositeIncomingArcIterator)
OppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
const ReverseArcMixedGraph * graph_
OppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
ArcIndexType Index() const
OutgoingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
OutgoingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingArcIterator)
ArcIndexType Index() const
OutgoingOrOppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node)
OutgoingOrOppositeIncomingArcIterator(const ReverseArcMixedGraph &graph, NodeIndexType node, ArcIndexType arc)
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingOrOppositeIncomingArcIterator)
ArcIndexType Index() const
ArcIndexType OppositeArc(ArcIndexType arc) const
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
void ReserveArcs(ArcIndexType bound) override
BeginEndWrapper< IncomingArcIterator > IncomingArcs(NodeIndexType node) const
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
ArcIndexType InDegree(NodeIndexType node) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< NodeIndexType const * > operator[](NodeIndexType node) const
void AddNode(NodeIndexType node)
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs(NodeIndexType node) const
ArcIndexType OutDegree(NodeIndexType node) const
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
ReverseArcMixedGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
IncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
IncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
DEFINE_STL_ITERATOR_FUNCTIONS(IncomingArcIterator)
ArcIndexType Index() const
OppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
const ReverseArcStaticGraph & graph_
OppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
DEFINE_STL_ITERATOR_FUNCTIONS(OppositeIncomingArcIterator)
const ArcIndexType limit_
ArcIndexType Index() const
OutgoingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
OutgoingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingArcIterator)
ArcIndexType Index() const
OutgoingOrOppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node)
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingOrOppositeIncomingArcIterator)
OutgoingOrOppositeIncomingArcIterator(const ReverseArcStaticGraph &graph, NodeIndexType node, ArcIndexType arc)
ArcIndexType Index() const
ArcIndexType OppositeArc(ArcIndexType arc) const
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcs(NodeIndexType node) const
NodeIndexType Tail(ArcIndexType arc) const
ReverseArcStaticGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
void ReserveArcs(ArcIndexType bound) override
BeginEndWrapper< IncomingArcIterator > IncomingArcs(NodeIndexType node) const
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
ArcIndexType InDegree(NodeIndexType node) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< NodeIndexType const * > operator[](NodeIndexType node) const
void AddNode(NodeIndexType node)
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs(NodeIndexType node) const
ArcIndexType OutDegree(NodeIndexType node) const
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
SVector(const SVector &other)
const T & operator[](int n) const
SVector & operator=(const SVector &other)
SVector & operator=(SVector &&other)
void grow(const T &left=T(), const T &right=T())
void swap(SVector< T > &x)
OutgoingArcIterator(const StaticGraph &graph, NodeIndexType node, ArcIndexType arc)
DEFINE_STL_ITERATOR_FUNCTIONS(OutgoingArcIterator)
OutgoingArcIterator(const StaticGraph &graph, NodeIndexType node)
ArcIndexType Index() const
NodeIndexType Tail(ArcIndexType arc) const
void ReserveArcs(ArcIndexType bound) override
void ReserveNodes(NodeIndexType bound) override
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< NodeIndexType const * > operator[](NodeIndexType node) const
void AddNode(NodeIndexType node)
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
StaticGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)
ArcIndexType OutDegree(NodeIndexType node) const
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
DEFINE_RANGE_BASED_ARC_ITERATION(ListGraph, Outgoing, Base::kNilArc)
void Permute(const IntVector &permutation, Array *array_to_permute)
void PermuteWithExplicitElementType(const IntVector &permutation, Array *array_to_permute, ElementType unused)