1 #ifndef GRAPH_CONNECTED_COMPONENTS_H 2 #define GRAPH_CONNECTED_COMPONENTS_H 4 #include "UndirectedGraph.h" 5 #include <KrisLibrary/utils/unionfind.h> 13 template <
class Node,
class Edge>
16 for(
size_t i=0;i<G.nodes.size();i++) {
17 for(
const auto& e:G.edges[i]) {
18 sets.
Union(i,e.first);
22 void Resize(
int numNodes) { sets.
Initialize(numNodes); }
23 void Clear() { Resize(0); }
24 void AddEdge(
int i,
int j) { sets.
Union(i,j); }
26 int GetComponent(
int i) {
return sets.
FindSet(i); }
27 int GetComponent(
int i)
const {
return sets.FindRoot(i); }
28 bool SameComponent(
int i,
int j) {
return sets.
FindSet(i)==sets.
FindSet(j); }
29 bool SameComponent(
int i,
int j)
const {
return sets.FindRoot(i)==sets.FindRoot(j); }
30 void GetRepresentatives(std::vector<int>& reps)
const { sets.
GetRoots(reps); }
31 size_t NumComponents()
const {
return sets.
CountSets(); }
32 void EnumerateComponent(
int node,std::vector<int>& items)
const {
return sets.
EnumerateSet(node,items); }
From an indexed set of elments, allows fast unioning of the elements into sets.
Definition: unionfind.h:18
Definition: ConnectedComponents.h:9
void GetRoots(std::vector< int > &roots) const
Returns the roots of all sets.
Definition: unionfind.cpp:66
size_t CountSets() const
Counts the number of sets.
Definition: unionfind.cpp:58
void EnumerateSet(int i, std::vector< int > &s) const
Returns the entire set for item i.
Definition: unionfind.cpp:86
int AddEntry()
Increment the size of X by 1, sets Sn={xn}.
Definition: unionfind.cpp:20
Namespace for all classes and functions in the Graph subdirectory.
Definition: ApproximateShortestPaths.h:7
int Union(const int i, const int j)
Unions the sets to which xi and xj belong.
Definition: unionfind.cpp:34
int FindSet(const int i)
Returns the id of the set to which xi belongs.
Definition: unionfind.cpp:26
void Initialize(const int entries)
Resize X to size entries, sets all sets Si={xi}.
Definition: unionfind.cpp:9
A specialization of a Graph to be an undirected graph.
Definition: UndirectedGraph.h:17