OR-Tools  8.2
connected_components.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14//
15// Licensed under the Apache License, Version 2.0 (the "License");
16// you may not use this file except in compliance with the License.
17// You may obtain a copy of the License at
18//
19// http://www.apache.org/licenses/LICENSE-2.0
20//
21// Unless required by applicable law or agreed to in writing, software
22// distributed under the License is distributed on an "AS IS" BASIS,
23// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
24// See the License for the specific language governing permissions and
25// limitations under the License.
26
27// The following uses disjoint-sets algorithms, see:
28// https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests
29
31
32#include <numeric>
33
35
37 const int old_num_nodes = GetNumberOfNodes();
38 if (num_nodes == old_num_nodes) {
39 return;
40 }
41 CHECK_GT(num_nodes, old_num_nodes);
42 // Each new node starts as an isolated component:
43 // It has itself as root.
44 parent_.resize(num_nodes);
45 std::iota(parent_.begin() + old_num_nodes, parent_.end(), old_num_nodes);
46 // It's in an isolated component of size 1.
47 component_size_.resize(num_nodes, 1);
48 // Its rank is 0.
49 rank_.resize(num_nodes);
50 // This introduces one extra component per added node.
51 num_components_ += num_nodes - old_num_nodes;
52}
53
55 DCHECK_GE(node, 0);
57
58 // Search the root.
59 int root = parent_[node];
60 while (parent_[root] != root) {
61 root = parent_[root];
62 }
63
64 // Apply path compression.
65 while (node != root) {
66 const int prev_parent = parent_[node];
67 parent_[node] = root;
68 node = prev_parent;
69 }
70 return root;
71}
72
74 const int num_nodes = GetNumberOfNodes();
75 if (num_nodes != num_nodes_at_last_get_roots_call_) {
76 // Add potential roots for each new node that did not exist the last time
77 // GetComponentRoots() was called. The cost here is amortized against
78 // adding the nodes in the first place.
79 const int previous_num_roots = roots_.size();
80 roots_.resize(previous_num_roots + num_nodes -
81 num_nodes_at_last_get_roots_call_);
82 std::iota(roots_.begin() + previous_num_roots, roots_.end(),
83 num_nodes_at_last_get_roots_call_);
84 }
85
86 // Remove the roots that have been merged with other components. Each node
87 // only gets removed once from the roots vector, so the cost of FindRoot() is
88 // amortized against adding the edge.
90 &roots_, [&](const int node) { return node != FindRoot(node); });
91
92 num_nodes_at_last_get_roots_call_ = num_nodes;
93 return roots_;
94}
95
96void DenseConnectedComponentsFinder::AddEdge(int node1, int node2) {
97 // Grow if needed.
98 const int min_num_nodes = std::max(node1, node2) + 1;
99 if (min_num_nodes > GetNumberOfNodes()) {
100 SetNumberOfNodes(min_num_nodes);
101 }
102
103 // Just union the sets for node1 and node2.
104 int root1 = FindRoot(node1);
105 int root2 = FindRoot(node2);
106
107 // Already the same set.
108 if (root1 == root2) {
109 return;
110 }
111
112 DCHECK_GE(num_components_, 2);
113 --num_components_;
114
115 const int component_size = component_size_[root1] + component_size_[root2];
116
117 // Attach the shallowest tree to root of the deepest one. Note that this
118 // operation grows the rank of the new common root by at most one (if the two
119 // trees originally have the same rank).
120 if (rank_[root1] > rank_[root2]) {
121 parent_[root2] = root1;
122 component_size_[root1] = component_size;
123 } else {
124 parent_[root1] = root2;
125 component_size_[root2] = component_size;
126 // If the ranks were the same then attaching just grew the rank by one.
127 if (rank_[root1] == rank_[root2]) {
128 ++rank_[root2];
129 }
130 }
131}
132
134 if (node1 < 0 || node1 >= GetNumberOfNodes() || node2 < 0 ||
135 node2 >= GetNumberOfNodes()) {
136 return false;
137 }
138 return FindRoot(node1) == FindRoot(node2);
139}
140
142 if (node < 0 || node >= GetNumberOfNodes()) {
143 return 0;
144 }
145 return component_size_[FindRoot(node)];
146}
147
149 std::vector<int> component_ids(GetNumberOfNodes(), -1);
150 int current_component = 0;
151 for (int node = 0; node < GetNumberOfNodes(); ++node) {
152 int& root_component = component_ids[FindRoot(node)];
153 if (root_component < 0) {
154 // This is the first node in a yet unseen component.
155 root_component = current_component;
156 ++current_component;
157 }
158 component_ids[node] = root_component;
159 }
160 return component_ids;
161}
int64 max
Definition: alldiff_cst.cc:139
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
void AddEdge(int node1, int node2)
bool Connected(int node1, int node2)
const std::vector< int > & GetComponentRoots()
void STLEraseAllFromSequenceIf(T *v, P pred)
Definition: stl_util.h:107