All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
WeaklyConnectedComponents.h
Go to the documentation of this file.
1 /*
2 * WeaklyConnectedComponents.h
3 *
4 * Created on: June 20, 2017
5 * Author: Eugenio Angriman
6 */
7 
8 #ifndef WEAKLYCONNECTEDCOMPONENTS_H_
9 #define WEAKLYCONNECTEDCOMPONENTS_H_
10 
11 #include "../graph/Graph.h"
12 #include "../structures/Partition.h"
13 #include "../base/Algorithm.h"
14 
15 namespace NetworKit {
16 
22  public:
29 
34  void run();
35 
42 
49 
55  std::map<index, count> getComponentSizes();
56 
60  std::vector<std::vector<node>> getComponents();
61 
62 
63  private:
64  void updateComponent(
65  index c, node w, std::queue<node>& q, bool inNeighbor
66  );
67 
68  void init();
69 
70  // Pointer to the graph
71  const Graph& G;
72 
73  // This vector associates each node to a component
74  std::vector<index> components;
75 
76  // This map stores all components
77  // <Key: component ID, Value: component size>
78  std::map<index, count> compSize;
79 
80  // Whether the run() method has been called
81  bool hasRun;
82  };
83 
85  assert (components[u] != none);
86  if (!hasRun) throw std::runtime_error("run method has not been called");
87  return components[u];
88  }
89 
91  if (!hasRun) throw std::runtime_error("run method has not been called");
92  return compSize.size();
93  }
94 
95  inline std::map<index, count> WeaklyConnectedComponents::getComponentSizes() {
96  if (!hasRun){
97  throw std::runtime_error("run method has not been called");
98  }
99  return compSize;
100  }
101 
102 }
103 
104 
105 #endif /* WEAKLYCONNECTEDCOMPONENTS_H_ */
Determines the weakly connected components of a directed graph.
Definition: WeaklyConnectedComponents.h:21
std::map< index, count > getComponentSizes()
Get the map from component to size.
Definition: WeaklyConnectedComponents.h:95
count componentOfNode(node u)
Get the the component in which node u is.
Definition: WeaklyConnectedComponents.h:84
WeaklyConnectedComponents(const Graph &G)
Create WeaklyConnectedComponents class for Graph G.
Definition: WeaklyConnectedComponents.cpp:12
uint64_t index
Typedefs.
Definition: Globals.h:20
count numberOfComponents()
Get the number of weakly connected components.
Definition: WeaklyConnectedComponents.h:90
uint64_t count
Definition: Globals.h:21
constexpr index none
Constants.
Definition: Globals.h:28
void run()
This method determines the weakly connected components for the graph given in the constructor...
Definition: WeaklyConnectedComponents.cpp:32
index node
Definition: Globals.h:23
Definition: Algorithm.h:9
std::vector< std::vector< node > > getComponents()
Definition: WeaklyConnectedComponents.cpp:88
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79