Google OR-Tools: ortools/graph/graph.h Source File

970 ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head);

971

972 private:

977};

978

979

980

981

982

983

984

985

986

987

988template <typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

990 : public BaseGraph<ReverseArcStaticGraph<NodeIndexType, ArcIndexType>,

991 NodeIndexType, ArcIndexType, true> {

993 "ArcIndexType must be signed");

994

996 NodeIndexType, ArcIndexType, true>

997 Base;

1003

1004 public:

1008 : is_built_(false) {

1011 if (num_nodes > NodeIndexType(0)) {

1012 this->AddNode(num_nodes - NodeIndexType(1));

1013 }

1014 }

1015

1017

1018 NodeIndexType Head(ArcIndexType arc) const;

1019 NodeIndexType Tail(ArcIndexType arc) const;

1020

1021

1022 ArcIndexType OutDegree(NodeIndexType node) const;

1023 ArcIndexType InDegree(NodeIndexType node) const;

1024

1025

1026 class OutgoingOrOppositeIncomingArcIterator;

1032

1037 ArcIndexType from) const {

1038 DCHECK_GE(from, start_[node]);

1039 const ArcIndexType limit = DirectArcLimit(node);

1041 limit);

1042 }

1043

1046 ReverseArcLimit(node));

1047 }

1049 NodeIndexType node, ArcIndexType from) const {

1050 DCHECK_GE(from, reverse_start_[node]);

1051 const ArcIndexType limit = ReverseArcLimit(node);

1053 limit);

1054 }

1055

1061

1063 NodeIndexType node, ArcIndexType from) const {

1069 }

1070

1073

1076 ArcIndexType from) const;

1077

1078

1079

1080

1081 absl::Span<const NodeIndexType> operator[](NodeIndexType node) const;

1082

1085 ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head);

1086

1087 void Build(std::vector<ArcIndexType>* permutation) final;

1089 bool IsBuilt() const final { return is_built_; }

1090

1091 private:

1092 ArcIndexType DirectArcLimit(NodeIndexType node) const {

1093 DCHECK(is_built_);

1095 return start_[node + NodeIndexType(1)];

1096 }

1097 ArcIndexType ReverseArcLimit(NodeIndexType node) const {

1098 DCHECK(is_built_);

1100 return reverse_start_[node + NodeIndexType(1)];

1101 }

1102

1103 bool is_built_;

1104

1105

1106 internal::Vector<NodeIndexType, ArcIndexType> start_;

1107

1108

1109 internal::Vector<NodeIndexType, ArcIndexType> reverse_start_;

1110 internal::SVector<ArcIndexType, NodeIndexType> head_;

1111 internal::SVector<ArcIndexType, ArcIndexType> opposite_;

1112};

1113

1114

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124template <class IntVector, class Array>

1125void Permute(const IntVector& permutation, Array* array_to_permute) {

1126 if (permutation.empty()) {

1127 return;

1128 }

1129 const auto size = permutation.size();

1130 auto& array = *array_to_permute;

1131 using ElementType =

1132 typename std::iterator_traits<decltype(std::begin(array))>::value_type;

1133 std::vector<ElementType> temp(size);

1134 auto array_begin = std::begin(array);

1135 std::copy_n(array_begin, size, temp.begin());

1136 for (size_t i = 0; i < permutation.size(); ++i) {

1137 *(array_begin + static_cast<size_t>(permutation[i])) = temp[i];

1138 }

1139}

1140

1141

1142

1143template <typename Impl, typename NodeIndexType, typename ArcIndexType,

1144 bool HasNegativeReverseArcs>

1145IntegerRange<NodeIndexType>

1150

1151template <typename Impl, typename NodeIndexType, typename ArcIndexType,

1152 bool HasNegativeReverseArcs>

1158

1159template <typename Impl, typename NodeIndexType, typename ArcIndexType,

1160 bool HasNegativeReverseArcs>

1161NodeIndexType BaseGraph<Impl, NodeIndexType, ArcIndexType,

1167

1168template <typename Impl, typename NodeIndexType, typename ArcIndexType,

1169 bool HasNegativeReverseArcs>

1170ArcIndexType BaseGraph<Impl, NodeIndexType, ArcIndexType,

1175

1176template <typename Impl, typename NodeIndexType, typename ArcIndexType,

1177 bool HasNegativeReverseArcs>

1178void BaseGraph<Impl, NodeIndexType, ArcIndexType,

1186

1187

1188

1189template <typename Impl, typename NodeIndexType, typename ArcIndexType,

1190 bool HasNegativeReverseArcs>

1193 DCHECK_EQ(v->size(), num_nodes_ + NodeIndexType(1));

1194 ArcIndexType sum(0);

1195 for (NodeIndexType i(0); i < num_nodes_; ++i) {

1196 ArcIndexType temp = (*v)[i];

1197 (*v)[i] = sum;

1198 sum += temp;

1199 }

1201 (*v)[num_nodes_] = sum;

1202}

1203

1204

1205

1206

1207

1208

1209template <typename Impl, typename NodeIndexType, typename ArcIndexType,

1210 bool HasNegativeReverseArcs>

1215 std::vector<ArcIndexType>* permutation) {

1216

1217

1218

1219 start->assign(num_nodes_ + NodeIndexType(1), ArcIndexType(0));

1220 NodeIndexType last_tail_seen(0);

1221 bool permutation_needed = false;

1222 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1223 NodeIndexType tail = (*head)[i];

1224 if (!permutation_needed) {

1225 permutation_needed = tail < last_tail_seen;

1226 last_tail_seen = tail;

1227 }

1228 (*start)[tail]++;

1229 }

1231

1232

1233

1234 if (!permutation_needed) {

1235 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1236 (*head)[i] = (*head)[~i];

1237 }

1238 if (permutation != nullptr) {

1239 permutation->clear();

1240 }

1241 return;

1242 }

1243

1244

1245

1246 std::vector<ArcIndexType> perm(static_cast<size_t>(num_arcs_));

1247 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1248 perm[static_cast<size_t>(i)] = (*start)[(*head)[i]]++;

1249 }

1250

1251

1252 DCHECK_GE(num_nodes_, NodeIndexType(1));

1253 for (NodeIndexType i = num_nodes_ - NodeIndexType(1); i > NodeIndexType(0);

1254 --i) {

1255 (*start)[i] = (*start)[i - NodeIndexType(1)];

1256 }

1257 (*start)[NodeIndexType(0)] = ArcIndexType(0);

1258

1259

1260

1261 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1262 (*head)[perm[static_cast<size_t>(i)]] = (*head)[~i];

1263 }

1264 if (permutation != nullptr) {

1265 permutation->swap(perm);

1266 }

1267}

1268

1269

1270

1271

1272

1273

1274

1275

1276

1277

1278#define DEFINE_RANGE_BASED_ARC_ITERATION(c, t) \

1279 template <typename NodeIndexType, typename ArcIndexType> \

1280 BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \

1281 c<NodeIndexType, ArcIndexType>::t##Arcs(NodeIndexType node) const { \

1282 return BeginEndWrapper<t##ArcIterator>( \

1283 t##ArcIterator(*this, node), \

1284 t##ArcIterator(*this, node, Base::kNilArc)); \

1285 } \

1286 template <typename NodeIndexType, typename ArcIndexType> \

1287 BeginEndWrapper<typename c<NodeIndexType, ArcIndexType>::t##ArcIterator> \

1288 c<NodeIndexType, ArcIndexType>::t##ArcsStartingFrom( \

1289 NodeIndexType node, ArcIndexType from) const { \

1290 return BeginEndWrapper<t##ArcIterator>( \

1291 t##ArcIterator(*this, node, from), \

1292 t##ArcIterator(*this, node, Base::kNilArc)); \

1293 }

1294

1295

1296

1297#define DEFINE_STL_ITERATOR_FUNCTIONS(iterator_class_name) \

1298 using iterator_category = std::input_iterator_tag; \

1299 using difference_type = ptrdiff_t; \

1300 using pointer = const ArcIndexType*; \

1301 using value_type = ArcIndexType; \

1302 using reference = value_type; \

1303 bool operator!=(const iterator_class_name& other) const { \

1304 return this->index_ != other.index_; \

1305 } \

1306 bool operator==(const iterator_class_name& other) const { \

1307 return this->index_ == other.index_; \

1308 } \

1309 ArcIndexType operator*() const { return this->Index(); } \

1310 iterator_class_name& operator++() { \

1311 this->Next(); \

1312 return *this; \

1313 } \

1314 iterator_class_name operator++(int) { \

1315 auto tmp = *this; \

1316 this->Next(); \

1317 return tmp; \

1318 }

1319

1320

1321

1322template <typename NodeIndexType, typename ArcIndexType>

1324 ArcIndexType arc) const {

1326 return tail_[arc];

1327}

1328

1329template <typename NodeIndexType, typename ArcIndexType>

1331 ArcIndexType arc) const {

1333 return head_[arc];

1334}

1335

1336template <typename NodeIndexType, typename ArcIndexType>

1338 NodeIndexType node) const {

1339 ArcIndexType degree(0);

1340 for (auto arc ABSL_ATTRIBUTE_UNUSED : OutgoingArcs(node)) ++degree;

1341 return degree;

1342}

1343

1344template <typename NodeIndexType, typename ArcIndexType>

1346 if (node < num_nodes_) return;

1347 DCHECK(!const_capacities_ || node < node_capacity_);

1348 num_nodes_ = node + NodeIndexType(1);

1350}

1351

1352template <typename NodeIndexType, typename ArcIndexType>

1354 NodeIndexType tail, NodeIndexType head) {

1355 DCHECK_GE(tail, NodeIndexType(0));

1356 DCHECK_GE(head, NodeIndexType(0));

1357 AddNode(tail > head ? tail : head);

1358 head_.push_back(head);

1359 tail_.push_back(tail);

1360 next_.push_back(start_[tail]);

1361 start_[tail] = num_arcs_;

1362 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);

1363 return num_arcs_++;

1364}

1365

1366template <typename NodeIndexType, typename ArcIndexType>

1368 Base::ReserveNodes(bound);

1369 if (bound <= num_nodes_) return;

1370 start_.reserve(bound);

1371}

1372

1373template <typename NodeIndexType, typename ArcIndexType>

1375 Base::ReserveArcs(bound);

1376 if (bound <= num_arcs_) return;

1377 head_.reserve(bound);

1378 tail_.reserve(bound);

1379 next_.reserve(bound);

1380}

1381

1382

1383

1384template <typename NodeIndexType, typename ArcIndexType>

1385template <class ArcContainer>

1388 const ArcContainer& arcs) {

1390 for (const auto& [from, to] : arcs) g.AddArc(from, to);

1391 g.Build();

1392 return g;

1393}

1394

1395template <typename NodeIndexType, typename ArcIndexType>

1396absl::Span<const NodeIndexType>

1398 return absl::Span<const NodeIndexType>(

1399 head_.data() + static_cast<size_t>(start_[node]),

1400 static_cast<size_t>(DirectArcLimit(node) - start_[node]));

1401}

1402

1403template <typename NodeIndexType, typename ArcIndexType>

1405 NodeIndexType node) const {

1406 return DirectArcLimit(node) - start_[node];

1407}

1408

1409template <typename NodeIndexType, typename ArcIndexType>

1411 NodeIndexType bound) {

1413 if (bound <= num_nodes_) return;

1414 start_.reserve(bound + NodeIndexType(1));

1415}

1416

1417template <typename NodeIndexType, typename ArcIndexType>

1419 Base::ReserveArcs(bound);

1420 if (bound <= num_arcs_) return;

1421 head_.reserve(bound);

1422 tail_.reserve(bound);

1423}

1424

1425template <typename NodeIndexType, typename ArcIndexType>

1427 if (node < num_nodes_) return;

1428 DCHECK(!const_capacities_ || node < node_capacity_) << node;

1429 num_nodes_ = node + NodeIndexType(1);

1430 start_.resize(num_nodes_ + NodeIndexType(1), ArcIndexType(0));

1431}

1432

1433template <typename NodeIndexType, typename ArcIndexType>

1435 NodeIndexType tail, NodeIndexType head) {

1436 DCHECK_GE(tail, NodeIndexType(0));

1437 DCHECK_GE(head, NodeIndexType(0));

1438 DCHECK(!is_built_);

1439 AddNode(tail > head ? tail : head);

1440 if (arc_in_order_) {

1441 if (tail >= last_tail_seen_) {

1442 start_[tail]++;

1443 last_tail_seen_ = tail;

1444 } else {

1445 arc_in_order_ = false;

1446 }

1447 }

1448 tail_.push_back(tail);

1449 head_.push_back(head);

1450 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);

1451 return num_arcs_++;

1452}

1453

1454template <typename NodeIndexType, typename ArcIndexType>

1456 ArcIndexType arc) const {

1458 return tail_[arc];

1459}

1460

1461template <typename NodeIndexType, typename ArcIndexType>

1463 ArcIndexType arc) const {

1465 return head_[arc];

1466}

1467

1468

1469

1470

1471

1472

1473

1474

1475

1476

1477

1478

1479

1480template <typename NodeIndexType, typename ArcIndexType>

1482 std::vector<ArcIndexType>* permutation) {

1483 DCHECK(!is_built_);

1484 if (is_built_) return;

1485 is_built_ = true;

1486 node_capacity_ = num_nodes_;

1487 arc_capacity_ = num_arcs_;

1489 if (num_nodes_ == NodeIndexType(0)) {

1490 return;

1491 }

1492

1493

1494 if (arc_in_order_) {

1495 if (permutation != nullptr) {

1496 permutation->clear();

1497 }

1498 this->ComputeCumulativeSum(&start_);

1499 return;

1500 }

1501

1502

1503

1504 start_.assign(num_nodes_ + NodeIndexType(1), ArcIndexType(0));

1505 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1506 start_[tail_[i]]++;

1507 }

1508 this->ComputeCumulativeSum(&start_);

1509

1510

1511

1512 std::vector<ArcIndexType> perm(static_cast<size_t>(num_arcs_));

1513 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1514 perm[static_cast<size_t>(i)] = start_[tail_[i]]++;

1515 }

1516

1517

1518 CHECK_EQ(tail_.size(), num_arcs_);

1519 tail_.swap(head_);

1520 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1521 head_[perm[static_cast<size_t>(i)]] = tail_[i];

1522 }

1523

1524 if (permutation != nullptr) {

1525 permutation->swap(perm);

1526 }

1527

1528

1529 DCHECK_GE(num_nodes_, NodeIndexType(1));

1530 for (NodeIndexType i = num_nodes_ - NodeIndexType(1); i > NodeIndexType(0);

1531 --i) {

1532 start_[i] = start_[i - NodeIndexType(1)];

1533 }

1534 start_[NodeIndexType(0)] = ArcIndexType(0);

1535

1536

1537 for (const NodeIndexType node : Base::AllNodes()) {

1538 for (const ArcIndexType arc : OutgoingArcs(node)) {

1539 tail_[arc] = node;

1540 }

1541 }

1542}

1543

1544

1546 OutgoingOrOppositeIncoming);

1548template <typename NodeIndexType, typename ArcIndexType>

1550 NodeIndexType, ArcIndexType>::OutgoingHeadIterator>

1552 NodeIndexType node) const {

1554

1555

1559}

1560

1561template <typename NodeIndexType, typename ArcIndexType>

1563 NodeIndexType node) const {

1564 ArcIndexType degree(0);

1565 for (auto arc ABSL_ATTRIBUTE_UNUSED : OutgoingArcs(node)) ++degree;

1566 return degree;

1567}

1568

1569template <typename NodeIndexType, typename ArcIndexType>

1571 NodeIndexType node) const {

1572 ArcIndexType degree(0);

1574 return degree;

1575}

1576

1577template <typename NodeIndexType, typename ArcIndexType>

1579 ArcIndexType arc) const {

1581 return ~arc;

1582}

1583

1584template <typename NodeIndexType, typename ArcIndexType>

1586 ArcIndexType arc) const {

1588 return head_[arc];

1589}

1590

1591template <typename NodeIndexType, typename ArcIndexType>

1593 ArcIndexType arc) const {

1595}

1596

1597template <typename NodeIndexType, typename ArcIndexType>

1599 NodeIndexType bound) {

1601 if (bound <= num_nodes_) return;

1602 start_.reserve(bound);

1603 reverse_start_.reserve(bound);

1604}

1605

1606template <typename NodeIndexType, typename ArcIndexType>

1608 ArcIndexType bound) {

1610 if (bound <= num_arcs_) return;

1611 head_.reserve(bound);

1612 next_.reserve(bound);

1613}

1614

1615template <typename NodeIndexType, typename ArcIndexType>

1617 NodeIndexType node) {

1618 if (node < num_nodes_) return;

1619 DCHECK(!const_capacities_ || node < node_capacity_);

1620 num_nodes_ = node + NodeIndexType(1);

1622 reverse_start_.resize(num_nodes_, Base::kNilArc);

1623}

1624

1625template <typename NodeIndexType, typename ArcIndexType>

1627 NodeIndexType tail, NodeIndexType head) {

1628 DCHECK_GE(tail, NodeIndexType(0));

1629 DCHECK_GE(head, NodeIndexType(0));

1630 AddNode(tail > head ? tail : head);

1631 head_.grow(tail, head);

1632 next_.grow(reverse_start_[head], start_[tail]);

1633 start_[tail] = num_arcs_;

1634 reverse_start_[head] = ~num_arcs_;

1635 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);

1636 return num_arcs_++;

1637}

1638

1639template <typename NodeIndexType, typename ArcIndexType>

1644 NodeIndexType node)

1645 : graph_(&graph), index_(graph.reverse_start_[node]), node_(node) {

1646 DCHECK(graph.IsNodeValid(node));

1648 }

1650 NodeIndexType node, ArcIndexType arc)

1651 : graph_(&graph), index_(arc), node_(node) {

1652 DCHECK(graph.IsNodeValid(node));

1654 }

1655

1656 bool Ok() const { return index_ != Base::kNilArc; }

1657 ArcIndexType Index() const { return index_; }

1660 if (index_ < ArcIndexType(0)) {

1661 index_ = graph_->next_[index_];

1663 index_ = graph_->start_[node_];

1664 }

1665 } else {

1666 index_ = graph_->next_[index_];

1667 }

1668 }

1669

1671

1674 ArcIndexType index_;

1675 NodeIndexType node_;

1676};

1677

1678

1686 return DirectArcLimit(node) - start_[node];

1687}

1688

1689template <typename NodeIndexType, typename ArcIndexType>

1692 return ReverseArcLimit(node) - reverse_start_[node];

1693}

1694

1695template <typename NodeIndexType, typename ArcIndexType>

1699 return absl::Span<const NodeIndexType>(

1700 head_.data() + static_cast<size_t>(start_[node]),

1701 static_cast<size_t>(DirectArcLimit(node) - start_[node]));

1702}

1703

1704template <typename NodeIndexType, typename ArcIndexType>

1707 DCHECK(is_built_);

1709 return opposite_[arc];

1710}

1711

1712template <typename NodeIndexType, typename ArcIndexType>

1715 DCHECK(is_built_);

1717 return head_[arc];

1718}

1719

1720template <typename NodeIndexType, typename ArcIndexType>

1723 DCHECK(is_built_);

1725}

1726

1727template <typename NodeIndexType, typename ArcIndexType>

1731 if (bound <= num_arcs_) return;

1732 head_.reserve(bound);

1733}

1734

1735template <typename NodeIndexType, typename ArcIndexType>

1738 if (node < num_nodes_) return;

1739 DCHECK(!const_capacities_ || node < node_capacity_);

1740 num_nodes_ = node + NodeIndexType(1);

1741}

1742

1743template <typename NodeIndexType, typename ArcIndexType>

1746 DCHECK_GE(tail, NodeIndexType(0));

1747 DCHECK_GE(head, NodeIndexType(0));

1748 AddNode(tail > head ? tail : head);

1749

1750

1751

1752 head_.grow(head, tail);

1753 DCHECK(!const_capacities_ || num_arcs_ < arc_capacity_);

1754 return num_arcs_++;

1755}

1756

1757template <typename NodeIndexType, typename ArcIndexType>

1760 DCHECK(!is_built_);

1761 if (is_built_) return;

1762 is_built_ = true;

1763 node_capacity_ = num_nodes_;

1764 arc_capacity_ = num_arcs_;

1766 if (num_nodes_ == NodeIndexType(0)) {

1767 return;

1768 }

1769 this->BuildStartAndForwardHead(&head_, &start_, permutation);

1770

1771

1772 reverse_start_.assign(num_nodes_ + NodeIndexType(1), ArcIndexType(0));

1773 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1774 reverse_start_[head_[i]]++;

1775 }

1776 this->ComputeCumulativeSum(&reverse_start_);

1777

1778

1779

1780 opposite_.reserve(num_arcs_);

1781 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1782

1783 opposite_.grow(ArcIndexType(0), reverse_start_[head_[i]]++ - num_arcs_);

1784 }

1785

1786

1787 DCHECK_GE(num_nodes_, NodeIndexType(1));

1788 reverse_start_[num_nodes_] = ArcIndexType(0);

1789 for (NodeIndexType i = num_nodes_ - NodeIndexType(1); i > NodeIndexType(0);

1790 --i) {

1791 reverse_start_[i] = reverse_start_[i - NodeIndexType(1)] - num_arcs_;

1792 }

1793 if (num_nodes_ != NodeIndexType(0)) {

1794 reverse_start_[NodeIndexType(0)] = -num_arcs_;

1795 }

1796

1797

1798 for (ArcIndexType i(0); i < num_arcs_; ++i) {

1799 opposite_[opposite_[i]] = i;

1800 }

1801 for (const NodeIndexType node : Base::AllNodes()) {

1802 for (const ArcIndexType arc : OutgoingArcs(node)) {

1803 head_[opposite_[arc]] = node;

1804 }

1805 }

1806}

1807

1808template <typename NodeIndexType, typename ArcIndexType>

1813 NodeIndexType node)

1814 : index_(graph.reverse_start_[node]),

1815 first_limit_(graph.ReverseArcLimit(node)),

1816 next_start_(graph.start_[node]),

1817 limit_(graph.DirectArcLimit(node)) {

1818 if (index_ == first_limit_) index_ = next_start_;

1819 DCHECK(graph.IsNodeValid(node));

1820 DCHECK((index_ < first_limit_) || (index_ >= next_start_));

1821 }

1823 NodeIndexType node, ArcIndexType arc)

1824 : first_limit_(graph.ReverseArcLimit(node)),

1825 next_start_(graph.start_[node]),

1826 limit_(graph.DirectArcLimit(node)) {

1828 DCHECK(graph.IsNodeValid(node));

1829 DCHECK((index_ >= graph.reverse_start_[node] && index_ < first_limit_) ||

1830 (index_ >= next_start_));

1831 }

1832

1833 ArcIndexType Index() const { return index_; }

1834 bool Ok() const { return index_ != limit_; }

1838 if (index_ == first_limit_) {

1839 index_ = next_start_;

1840 }

1841 }

1842

1844

1846 ArcIndexType index_;

1847 const ArcIndexType first_limit_;

1848 const ArcIndexType next_start_;

1849 const ArcIndexType limit_;

1850};

1851

1852

1858 NodeIndexType, ArcIndexType, false> {

1860 ArcIndexType, false>

1861 Base;

1867

1868 public:

1869

1871 :

1872

1878 }

1879

1880 NodeIndexType Head(ArcIndexType arc) const;

1881 NodeIndexType Tail(ArcIndexType arc) const;

1882 ArcIndexType OutDegree(NodeIndexType node) const;

1885 ArcIndexType from) const;

1887

1888 const ::util::math::ConstantDivisor<std::make_unsigned_t<ArcIndexType>>

1890};

1892template <typename NodeIndexType, typename ArcIndexType>

1894 ArcIndexType arc) const {

1897}

1898

1899template <typename NodeIndexType, typename ArcIndexType>

1901 ArcIndexType arc) const {

1904}

1905

1906template <typename NodeIndexType, typename ArcIndexType>

1908 NodeIndexType node) const {

1909 return num_nodes_;

1910}

1911

1912template <typename NodeIndexType, typename ArcIndexType>

1915 NodeIndexType node) const {

1916 DCHECK_LT(node, num_nodes_);

1918 static_cast<ArcIndexType>(num_nodes_) * node,

1919 static_cast<ArcIndexType>(num_nodes_) * (node + 1));

1920}

1921

1922template <typename NodeIndexType, typename ArcIndexType>

1925 NodeIndexType node, ArcIndexType from) const {

1926 DCHECK_LT(node, num_nodes_);

1928 from, static_cast<ArcIndexType>(num_nodes_) * (node + 1));

1929}

1930

1931template <typename NodeIndexType, typename ArcIndexType>

1934 NodeIndexType node) const {

1935 DCHECK_LT(node, num_nodes_);

1937}

1938

1939

1940

1941

1942template <typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

1944 : public BaseGraph<CompleteBipartiteGraph<NodeIndexType, ArcIndexType>,

1945 NodeIndexType, ArcIndexType, false> {

1947 NodeIndexType, ArcIndexType, false>

1948 Base;

1954

1955 public:

1956

1957

1958

1959

1961 : left_nodes_(left_nodes),

1962 right_nodes_(right_nodes),

1963

1964

1965

1966 divisor_(right_nodes > 1 ? right_nodes : 2) {

1967 this->Reserve(left_nodes + right_nodes, left_nodes * right_nodes);

1969 num_nodes_ = left_nodes + right_nodes;

1970 num_arcs_ = left_nodes * right_nodes;

1971 }

1972

1973

1974

1975

1976 ArcIndexType GetArc(NodeIndexType left_node, NodeIndexType right_node) const;

1977

1978 NodeIndexType Head(ArcIndexType arc) const;

1979 NodeIndexType Tail(ArcIndexType arc) const;

1980 ArcIndexType OutDegree(NodeIndexType node) const;

1983 ArcIndexType from) const;

1985

1986 private:

1987 const NodeIndexType left_nodes_;

1988 const NodeIndexType right_nodes_;

1989

1990 const ::util::math::ConstantDivisor<std::make_unsigned_t<ArcIndexType>>

1991 divisor_;

1992};

1993

1994template <typename NodeIndexType, typename ArcIndexType>

1996 NodeIndexType left_node, NodeIndexType right_node) const {

1997 DCHECK_LT(left_node, left_nodes_);

1998 DCHECK_GE(right_node, left_nodes_);

1999 DCHECK_LT(right_node, num_nodes_);

2000 return left_node * static_cast<ArcIndexType>(right_nodes_) +

2001 (right_node - left_nodes_);

2002}

2003

2004template <typename NodeIndexType, typename ArcIndexType>

2006 ArcIndexType arc) const {

2008

2009 return right_nodes_ > 1 ? left_nodes_ + arc % divisor_ : left_nodes_;

2010}

2011

2012template <typename NodeIndexType, typename ArcIndexType>

2014 ArcIndexType arc) const {

2016

2017 return right_nodes_ > 1 ? arc / divisor_ : arc;

2018}

2019

2020template <typename NodeIndexType, typename ArcIndexType>

2022 NodeIndexType node) const {

2023 return (node < left_nodes_) ? right_nodes_ : 0;

2024}

2025

2026template <typename NodeIndexType, typename ArcIndexType>

2029 NodeIndexType node) const {

2030 if (node < left_nodes_) {

2032 static_cast<ArcIndexType>(right_nodes_) * node,

2033 static_cast<ArcIndexType>(right_nodes_) * (node + 1));

2034 } else {

2036 }

2037}

2038

2039template <typename NodeIndexType, typename ArcIndexType>

2042 NodeIndexType node, ArcIndexType from) const {

2043 if (node < left_nodes_) {

2045 from, static_cast<ArcIndexType>(right_nodes_) * (node + 1));

2046 } else {

2048 }

2049}

2050

2051template <typename NodeIndexType, typename ArcIndexType>

2054 NodeIndexType node) const {

2055 if (node < left_nodes_) {

2057 } else {

2059 }

2060}

2061

2062

2064

2065}

2066

2067#undef DEFINE_RANGE_BASED_ARC_ITERATION

2068#undef DEFINE_STL_ITERATOR_FUNCTIONS

2069

2070#endif