All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynWeaklyConnectedComponents.h
Go to the documentation of this file.
1 /*
2 * DynWeaklyConnectedComponents.h
3 *
4 * Created on: June 20, 2017
5 * Author: Eugenio Angriman
6 */
7 
8 #ifndef DYNWEAKLYCONNECTEDCOMPONENTS_H_
9 #define DYNWEAKLYCONNECTEDCOMPONENTS_H_
10 
11 #include "../graph/Graph.h"
12 #include "../base/Algorithm.h"
13 #include "../base/DynAlgorithm.h"
14 #include "../dynamics/GraphEvent.h"
15 
16 namespace NetworKit {
17 
24 
25  public:
32 
37  void run() override;
38 
46  void update(GraphEvent event) override;
47 
55  void updateBatch(const std::vector<GraphEvent>& batch) override;
56 
63 
70 
74  std::map<index, count> getComponentSizes();
75 
79  std::vector<std::vector<node>> getComponents();
80 
81 
82  private:
83  void init();
84  void addEdge(node u, node v);
85  void removeEdge(node u, node v);
86  void updateComponent(index c, node w, std::queue<node>& q, node v);
87  void indexEdges();
88  void insertEdgeIntoMap(node u, node v, edgeid eid);
89  edgeid updateMapAfterAddition(node u, node v);
90  void updateTreeAfterAddition(edgeid eid, bool partOfTree);
91  void reverseBFS(node u, node v);
92  index getEdgeId(node u, node v);
93  index nextAvailableComponentId(bool eraseId = true);
94  bool visitNodeReversed(
95  node u,
96  node s,
97  node w,
98  node v,
99  count d,
100  std::queue<node>& q,
101  bool& nextEdgeFound,
102  count level
103  );
104  std::pair<node, node> makePair(node u, node v);
105 
106  // Pointer to the graph
107  const Graph& G;
108 
109  // This vector associates each node to a component
110  std::vector<index> components;
111 
112  // Whether each edge is part of a spanning tree. If an edge is removed
113  // then a components could split.
114  std::vector<bool> isTree;
115 
116  // Maps the edges to their IDs
117  std::map<std::pair<node, node>, edgeid> edgesMap;
118 
119  // Temporary distances used for BFSs after edge updates.
120  std::vector<count> tmpDistances;
121 
122  // Stores all components <Key: component ID, Value: component size>
123  std::map<index, count> compSize;
124 
125  // Stores available component IDs.
126  std::queue<index> componentIds;
127 
128  // Whether the run() method has been called
129  bool hasRun = false;
130  };
131 
132 
134  assert (components[u] != none);
135  if (!hasRun) throw std::runtime_error("run method has not been called");
136  return components[u];
137  }
138 
140  if (!hasRun) throw std::runtime_error("run method has not been called");
141  return this->compSize.size();
142  }
143 
144  inline std::map<index, count> DynWeaklyConnectedComponents::getComponentSizes() {
145  if (!hasRun) {
146  throw std::runtime_error("run method has not been called");
147  }
148  return compSize;
149  }
150 
151 }
152 
153 
154 #endif /* DynWeaklyConnectedComponents_H_ */
index edgeid
Definition: Globals.h:25
DynWeaklyConnectedComponents(const Graph &G)
Create DynWeaklyConnectedComponents class for Graph G.
Definition: DynWeaklyConnectedComponents.cpp:12
count componentOfNode(node u)
Get the the component in which node u is.
Definition: DynWeaklyConnectedComponents.h:133
void run() override
This method determines the weakly connected components for the graph given in the constructor...
Definition: DynWeaklyConnectedComponents.cpp:31
uint64_t index
Typedefs.
Definition: Globals.h:20
Determines and updates the weakly connected components of a directed graph.
Definition: DynWeaklyConnectedComponents.h:23
void updateBatch(const std::vector< GraphEvent > &batch) override
Updates the weakly connected components after a batch of edge events (insertions or deletions)...
Definition: DynWeaklyConnectedComponents.cpp:143
count numberOfComponents()
Get the number of weakly connected components.
Definition: DynWeaklyConnectedComponents.h:139
Definition: DynAlgorithm.h:10
Definition: GraphEvent.h:19
std::map< index, count > getComponentSizes()
Definition: DynWeaklyConnectedComponents.h:144
uint64_t count
Definition: Globals.h:21
constexpr index none
Constants.
Definition: Globals.h:28
index node
Definition: Globals.h:23
void update(GraphEvent event) override
Updates the weakly connected components after an edge insertion or deletion.
Definition: DynWeaklyConnectedComponents.cpp:128
Definition: Algorithm.h:9
std::vector< std::vector< node > > getComponents()
Definition: DynWeaklyConnectedComponents.cpp:387
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79