All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ConnectedComponents.h
Go to the documentation of this file.
1 /*
2  * ConnectedComponents.cpp
3  *
4  * Created on: Dec 16, 2013
5  * Author: cls
6  */
7 
8 #ifndef CONNECTEDCOMPONENTS_H_
9 #define CONNECTEDCOMPONENTS_H_
10 
11 #include "../graph/Graph.h"
12 #include "../distance/BFS.h"
13 #include "../structures/Partition.h"
14 #include "../base/Algorithm.h"
15 #include <unordered_set>
16 
17 namespace NetworKit {
18 
24 public:
30  ConnectedComponents(const Graph& G);
31 
35  void run();
36 
43 
50 
51 
58 
62  std::map<index, count> getComponentSizes();
63 
67  std::vector<std::vector<node> > getComponents();
68 
69 
70 private:
71  const Graph& G;
72  Partition component;
73  count numComponents;
74  bool hasRun;
75 };
76 
78  assert (component[u] != none);
79  if (!hasRun) throw std::runtime_error("run method has not been called");
80  return component[u];
81 }
82 
84  if (!hasRun) throw std::runtime_error("run method has not been called");
85  return this->numComponents;
86 }
87 
88 }
89 
90 
91 #endif /* CONNECTEDCOMPONENTS_H_ */
std::map< index, count > getComponentSizes()
Return the map from component to size.
Definition: ConnectedComponents.cpp:79
Determines the connected components of an undirected graph.
Definition: ConnectedComponents.h:23
count componentOfNode(node u)
Get the the component in which node u is situated.
Definition: ConnectedComponents.h:77
ConnectedComponents(const Graph &G)
Create ConnectedComponents class for Graph G.
Definition: ConnectedComponents.cpp:16
Implements a partition of a set, i.e.
Definition: Partition.h:31
Partition getPartition()
Get a Partition that represents the components.
Definition: ConnectedComponents.cpp:58
uint64_t count
Definition: Globals.h:21
constexpr index none
Constants.
Definition: Globals.h:28
void run()
This method determines the connected components for the graph given in the constructor.
Definition: ConnectedComponents.cpp:22
index node
Definition: Globals.h:23
count numberOfComponents()
Get the number of connected components.
Definition: ConnectedComponents.h:83
Definition: Algorithm.h:9
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
std::vector< std::vector< node > > getComponents()
Definition: ConnectedComponents.cpp:64