20 #ifndef OR_TOOLS_GRAPH_CONNECTIVITY_H_
21 #define OR_TOOLS_GRAPH_CONNECTIVITY_H_
25 #include "ortools/base/integral_types.h"
26 #include "ortools/base/logging.h"
27 #include "ortools/base/macros.h"
66 template <
typename NodeIndex,
typename ArcIndex>
73 CHECK_GE(num_nodes, 0);
74 num_nodes_ = num_nodes;
75 class_.resize(num_nodes_);
76 class_size_.assign(num_nodes_, 1);
77 for (
NodeIndex node = 0; node < num_nodes_; ++node) {
86 if (tail_class != head_class) {
94 template <
typename Graph>
96 Init(graph.num_nodes());
97 for (
NodeIndex tail = 0; tail < graph.num_nodes(); ++tail) {
98 for (
typename Graph::OutgoingArcIterator it(graph, tail); it.Ok();
100 AddArc(tail, graph.Head(it.Index()));
107 CheckNodeBounds(node);
109 while (parent != class_[parent]) {
110 CheckNodeBounds(class_[parent]);
111 CheckNodeBounds(class_[class_[parent]]);
112 parent = class_[parent];
114 while (node != class_[node]) {
115 const NodeIndex old_parent = class_[node];
116 class_[node] = parent;
131 for (
NodeIndex node = 0; node < num_nodes_; ++node) {
132 if (class_[node] == node) ++number;
141 CheckNodeBounds(node1);
142 CheckNodeBounds(node2);
143 if (class_size_[node1] < class_size_[node2]) {
144 std::swap(node1, node2);
146 class_[node2] = node1;
147 class_size_[node1] += class_size_[node2];
151 void CheckNodeBounds(
NodeIndex node_index) {
152 DCHECK_LE(0, node_index);
153 DCHECK_LT(node_index, num_nodes_);
159 std::vector<NodeIndex> class_;
163 std::vector<NodeIndex> class_size_;
170 #endif // OR_TOOLS_GRAPH_CONNECTIVITY_H_