OR-Tools  8.1
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 
34 #include "ortools/base/stl_util.h"
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);
56  DCHECK_LT(node, GetNumberOfNodes());
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 
96 void 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 
133 bool DenseConnectedComponentsFinder::Connected(int node1, int node2) {
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 }
DenseConnectedComponentsFinder::GetComponentRoots
const std::vector< int > & GetComponentRoots()
Definition: connected_components.cc:73
DCHECK_LT
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
DenseConnectedComponentsFinder::SetNumberOfNodes
void SetNumberOfNodes(int num_nodes)
Definition: connected_components.cc:36
max
int64 max
Definition: alldiff_cst.cc:139
DenseConnectedComponentsFinder::FindRoot
int FindRoot(int node)
Definition: connected_components.cc:54
CHECK_GT
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
DenseConnectedComponentsFinder::GetSize
int GetSize(int node)
Definition: connected_components.cc:141
connected_components.h
DenseConnectedComponentsFinder::AddEdge
void AddEdge(int node1, int node2)
Definition: connected_components.cc:96
DCHECK_GE
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
DenseConnectedComponentsFinder::GetNumberOfNodes
int GetNumberOfNodes() const
Definition: connected_components.h:96
stl_util.h
DenseConnectedComponentsFinder::GetComponentIds
std::vector< int > GetComponentIds()
Definition: connected_components.cc:148
DenseConnectedComponentsFinder::Connected
bool Connected(int node1, int node2)
Definition: connected_components.cc:133
gtl::STLEraseAllFromSequenceIf
void STLEraseAllFromSequenceIf(T *v, P pred)
Definition: stl_util.h:107