Google OR-Tools: ortools/graph/connected

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

25#ifndef UTIL_GRAPH_CONNECTED_COMPONENTS_H_

26#define UTIL_GRAPH_CONNECTED_COMPONENTS_H_

28#include <functional>

29#include <map>

30#include <memory>

31#include <set>

32#include <type_traits>

33#include <vector>

35#include "absl/container/flat_hash_map.h"

36#include "absl/container/flat_hash_set.h"

37#include "absl/hash/hash.h"

38#include "absl/meta/type_traits.h"

42namespace util {

45template <class UndirectedGraph, class NodeType>

47 const UndirectedGraph& graph);

64template <class UndirectedGraph>

66 const UndirectedGraph& graph) {

68}

69}

76 public:

81 default;

86 default;

90 bool AddEdge(int node1, int node2);

91 bool Connected(int node1, int node2);

100

101

102

103

105

106

107

108

110

111

112

113 int GetParent(int node) const { return parent_[node]; }

114

115

117

118 private:

119

120

121 std::vector<int> parent_;

122

123

124 std::vector<int> component_size_;

125

126 std::vector<int> rank_;

127

128 int num_components_ = 0;

129

130 std::vector<int> roots_;

131

132

133 int num_nodes_at_last_get_roots_call_ = 0;

134};

135

137

138

139template <typename T, typename CompareOrHashT, typename Eq>

141

142

143 template <typename U, typename V, typename E = void>

145 using Set = std::set<T, CompareOrHashT>;

146 using Map = std::map<T, int, CompareOrHashT>;

147 };

148

149

150

151

152

153

154

155 template <typename U, typename V>

157 U, V,

158 absl::enable_if_t<std::is_integral<decltype(std::declval<const U&>()(

159 std::declval<const T&>()))>::value &&

160 std::is_same_v<V, void>>> {

161 using Set = absl::flat_hash_set<T, CompareOrHashT>;

162 using Map = absl::flat_hash_map<T, int, CompareOrHashT>;

163 };

164

165

166 template <typename U, typename V>

168 U, V,

169 absl::enable_if_t<std::is_integral<decltype(std::declval<const U&>()(

170 std::declval<const T&>()))>::value &&

171 !std::is_same_v<V, void>>> {

172 using Set = absl::flat_hash_set<T, CompareOrHashT, Eq>;

173 using Map = absl::flat_hash_map<T, int, CompareOrHashT, Eq>;

174 };

175

178};

179

180}

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218template <typename T, typename CompareOrHashT = std::less<T>,

219 typename Eq = void>

221 public:

225

226

228

231 delete;

232

233

234

235 void AddNode(T node) { LookupOrInsertNode<true>(node); }

236

237

238

239

240

242 return delegate_.AddEdge(LookupOrInsertNode<false>(node1),

243 LookupOrInsertNode<false>(node2));

244 }

245

246

247

252

253

254

255

259

260

261

262

263

264

265

266

267

268

270 const auto component_ids = delegate_.GetComponentIds();

271 std::vector<std::vector<T>> components(delegate_.GetNumberOfComponents());

272 for (const auto& elem_id : index_) {

273 components[component_ids[elem_id.second]].push_back(elem_id.first);

274 }

275 return components;

276 }

278 const auto component_ids = delegate_.GetComponentIds();

279 components->clear();

280 components->resize(delegate_.GetNumberOfComponents());

281 for (const auto& elem_id : index_) {

282 components->at(component_ids[elem_id.second]).insert(elem_id.first);

283 }

284 }

285

286

287

289 return delegate_.GetNumberOfComponents();

290 }

291

292

293

294

295

297

298 private:

299

300

301 template <bool update_delegate>

302 int LookupOrInsertNode(T node) {

303 const auto result = index_.emplace(node, index_.size());

304 const int node_id = result.first->second;

305 if (update_delegate && result.second) {

306

308 }

309 return node_id;

310 }

311

312 DenseConnectedComponentsFinder delegate_;

314 index_;

315};

316

317

318

319

320namespace util {

321template <class UndirectedGraph, typename NodeType>

323 const UndirectedGraph& graph) {

324

325

326 std::vector<NodeType> component_of_node(num_nodes, num_nodes);

327 std::vector<NodeType> bfs_queue;

328 NodeType num_components = 0;

329 for (NodeType src = 0; src < num_nodes; ++src) {

330 if (component_of_node[src] != num_nodes) continue;

331 bfs_queue.push_back(src);

332 component_of_node[src] = num_components;

333 for (size_t num_visited = 0; num_visited < bfs_queue.size();

334 ++num_visited) {

335 const NodeType node = bfs_queue[num_visited];

336 for (const NodeType neighbor : graph[node]) {

337 if (component_of_node[neighbor] != num_nodes) continue;

338 component_of_node[neighbor] = num_components;

339 bfs_queue.push_back(neighbor);

340 }

341 }

342 ++num_components;

343 bfs_queue.clear();

344 }

345 return component_of_node;

346}

347

348}

349

350#endif

int GetSize(T node)

Definition connected_components.h:256

ConnectedComponentsFinder()=default

ConnectedComponentsFinder(const ConnectedComponentsFinder &)=delete

int GetNumberOfComponents() const

Definition connected_components.h:288

typename internal::ConnectedComponentsTypeHelper< T, CompareOrHashT, Eq >::Set Set

Definition connected_components.h:222

int GetNumberOfNodes() const

Definition connected_components.h:296

bool Connected(T node1, T node2)

Definition connected_components.h:248

void FindConnectedComponents(std::vector< Set > *components)

Definition connected_components.h:277

std::vector< std::vector< T > > FindConnectedComponents()

Definition connected_components.h:269

bool AddEdge(T node1, T node2)

Definition connected_components.h:241

ConnectedComponentsFinder & operator=(const ConnectedComponentsFinder &)=delete

void AddNode(T node)

Definition connected_components.h:235

bool Connected(int node1, int node2)

DenseConnectedComponentsFinder()=default

bool AddEdge(int node1, int node2)

int GetNumberOfNodes() const

Definition connected_components.h:94

void SetNumberOfNodes(int num_nodes)

int GetNumberOfComponents() const

Definition connected_components.h:93

int GetParent(int node) const

Definition connected_components.h:113

DenseConnectedComponentsFinder(const DenseConnectedComponentsFinder &)=default

std::vector< int > GetComponentIds()

DenseConnectedComponentsFinder & operator=(DenseConnectedComponentsFinder &&)=default

DenseConnectedComponentsFinder & operator=(const DenseConnectedComponentsFinder &)=default

const std::vector< int > & GetComponentRoots()

DenseConnectedComponentsFinder(DenseConnectedComponentsFinder &&)=default

const MapUtilMappedT< Collection > & FindWithDefault(const Collection &collection, const KeyType &key, const MapUtilMappedT< Collection > &value)

std::vector< int > GetConnectedComponents(int num_nodes, const UndirectedGraph &graph)

Definition connected_components.h:65

std::vector< NodeType > GetConnectedComponentsTpl(NodeType num_nodes, const UndirectedGraph &graph)

Definition connected_components.h:324

absl::flat_hash_set< T, CompareOrHashT > Set

Definition connected_components.h:161

absl::flat_hash_map< T, int, CompareOrHashT > Map

Definition connected_components.h:162

absl::flat_hash_map< T, int, CompareOrHashT, Eq > Map

Definition connected_components.h:173

absl::flat_hash_set< T, CompareOrHashT, Eq > Set

Definition connected_components.h:172

std::set< T, CompareOrHashT > Set

Definition connected_components.h:145

std::map< T, int, CompareOrHashT > Map

Definition connected_components.h:146

typename SelectContainer< CompareOrHashT, Eq >::Set Set

Definition connected_components.h:176

typename SelectContainer< CompareOrHashT, Eq >::Map Map

Definition connected_components.h:177