All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynConnectedComponents.h
Go to the documentation of this file.
1 /*
2 * DynConnectedComponents.cpp
3 *
4 * Created on: June 2017
5 * Author: Eugenio Angriman
6 */
7 
8 #ifndef DYNCONNECTEDCOMPONENTS_H_
9 #define DYNCONNECTEDCOMPONENTS_H_
10 
11 #include "../graph/Graph.h"
12 #include "../distance/BFS.h"
13 #include "../base/Algorithm.h"
14 #include "../base/DynAlgorithm.h"
15 #include "../dynamics/GraphEvent.h"
16 
17 namespace NetworKit {
18 
24 
25  public:
31  DynConnectedComponents(const Graph& G);
32 
37  void run() override;
38 
45  void update(GraphEvent e) override;
46 
54  void updateBatch(const std::vector<GraphEvent>& batch) override;
55 
62 
69 
73  std::map<index, count> getComponentSizes();
74 
78  std::vector<std::vector<node>> getComponents();
79 
80  private:
81  void addEdge(node u, node v);
82  void removeEdge(node u, node v);
83  void addEdgeDirected(node u, node v);
84  void removeEdgeDirected(node u, node v);
85  void reverseBFS(node u, node v);
86  index nextAvailableComponentId(bool eraseId = true);
87  void indexEdges();
88  void insertEdgeIntoMap(node u, node v, edgeid eid);
89  index getEdgeId(node u, node v);
90  // Returns true and the corresponding edge id if the new edge was not
91  // into the original graph.
92  std::pair<bool, edgeid> updateMapAfterAddition(node u, node v);
93  void init();
94  std::pair<node, node> makePair(node u, node v);
95  const Graph& G;
96  std::vector<bool> isTree;
97  std::vector<index> components;
98  std::map<index, count> compSize;
99  std::map<std::pair<node, node>, index> edgesMap;
100  std::vector<count> tmpDistances;
101  std::queue<index> componentIds;
102  bool distancesInit;
103  bool hasRun;
104  };
105 
107  assert(u <= G.upperNodeIdBound());
108  assert (components[u] != none);
109  if (!hasRun) throw std::runtime_error("run method has not been called");
110  return components[u];
111  }
112 
114  if (!hasRun) throw std::runtime_error("run method has not been called");
115  return this->compSize.size();
116  }
117 
118  inline std::map<index, count> DynConnectedComponents::getComponentSizes() {
119  if (!hasRun){
120  throw std::runtime_error("run method has not been called");
121  }
122  return compSize;
123  }
124 
125 }
126 
127 #endif /* DYNCONNECTEDCOMPONENTS_H_ */
void run() override
This method determines the connected components for the graph given in the constructor.
Definition: DynConnectedComponents.cpp:29
index edgeid
Definition: Globals.h:25
std::map< index, count > getComponentSizes()
Returns the map from component to size.
Definition: DynConnectedComponents.h:118
uint64_t index
Typedefs.
Definition: Globals.h:20
Definition: DynAlgorithm.h:10
void update(GraphEvent e) override
Updates the connected components after an edge insertion or deletion.
Definition: DynConnectedComponents.cpp:80
Determines and updates the connected components of an undirected graph.
Definition: DynConnectedComponents.h:23
Definition: GraphEvent.h:19
index upperNodeIdBound() const
Get an upper bound for the node ids in the graph.
Definition: Graph.h:749
count componentOfNode(node u)
Returns the the component in which node u is.
Definition: DynConnectedComponents.h:106
count numberOfComponents()
Get the number of connected components.
Definition: DynConnectedComponents.h:113
void updateBatch(const std::vector< GraphEvent > &batch) override
Updates the connected components after a batch of edge insertions or deletions.
Definition: DynConnectedComponents.cpp:94
uint64_t count
Definition: Globals.h:21
constexpr index none
Constants.
Definition: Globals.h:28
index node
Definition: Globals.h:23
DynConnectedComponents(const Graph &G)
Create ConnectedComponents class for Graph G.
Definition: DynConnectedComponents.cpp:12
Definition: Algorithm.h:9
std::vector< std::vector< node > > getComponents()
Definition: DynConnectedComponents.cpp:271
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79