GraphBuilder.h
Go to the documentation of this file.
1 /*
2  * GraphBuilder.h
3  *
4  * Created on: 15.07.2014
5  * Author: Marvin Ritter (marvin.ritter@gmail.com)
6  */
7
8 #ifndef GRAPH_BUILDER_H
9 #define GRAPH_BUILDER_H
10
11 #include <vector>
12
13 #include "../Globals.h"
14 #include "Graph.h"
15
16 namespace NetworKit {
17
18 /*
19  * The GraphBuilder helps to speed up graph generation by minimizing the number of checks on addEdge/setWeight/increaseWeight. Further more it delays the construction of some internal data structures of the Graph class until you call toGraph(). toGraph() can only be called once.
20  * In the Graph class for an edge u -> v, v is stored in the adjacent array of u (first half) and u in the adjacent array of v (second half). (For directed graphs these might be in and out adjacent arrays.). So each edge can be seen as a pair of 2 half edges. To allow optimization and mainly parallelization GraphBuilder lets you add both half edges yourself. You are responsible for adding both half edges, otherwise you might end up with an invalid Graph object.
21  * As adding the first half edge of an edge u -> v only requires access to the adjacent array of u, other threads can add edges a -> b as long as a != u. Some goes for the methods setWeight and increaseWeight. Note: If you add the first half edge of u -> v, you can change the weight by calling setWeight(u, v, ew) or increaseWeight(u, v, ew), but calling setWeight(v, u, ew) or increaseWeight(v, u, ew) will add the second half edge.
22  * GraphBuilder allows you to be lazy and only add one half of each edge. Calling toGraph with autoCompleteEdges set to true, will make each half Edge in GraphBuilder to one full edge in Graph.
23  *
24  * So far I didn't came up with a good parallelization for toGraph, so at some point I might omit the parallel parameter for toGraph.
25  */
26
27 class GraphBuilder {
28 private:
29  count n;
30  count selfloops;
31  std::string name;
32
33  bool weighted;
34  bool directed;
35
36  std::vector< std::vector<node> > outEdges;
37  std::vector< std::vector<edgeweight> > outEdgeWeights;
38
39  std::vector< std::vector<node> > inEdges;
40  std::vector< std::vector<edgeweight> > inEdgeWeights;
41
42  index indexInOutEdgeArray(node u, node v) const;
43
44  index indexInInEdgeArray(node u, node v) const;
45
46 public:
47
57  GraphBuilder(count n = 0, bool weighted = false, bool directed = false);
58
59  void reset(count n = 0);
60
65  void setName(std::string name) { this->name = name; }
66
71  inline bool isWeighted() const { return weighted; }
72
77  inline bool isDirected() const { return directed; }
78
83  inline bool isEmpty() const { return n == 0; }
84
89  count numberOfNodes() const { return n; }
90
95  index upperNodeIdBound() const { return n; }
96
102
113
114  void swapNeighborhood(node u, std::vector<node> &neighbours, std::vector<edgeweight> &weights, bool selfloop);
115
124  void setWeight(node u, node v, edgeweight ew) { setOutWeight(u, v, ew); }
125  void setOutWeight(node u, node v, edgeweight ew);
126  void setInWeight(node u, node v, edgeweight ew);
127
136  void increaseWeight(node u, node v, edgeweight ew) { increaseOutWeight(u, v, ew); }
137  void increaseOutWeight(node u, node v, edgeweight ew);
138  void increaseInWeight(node u, node v, edgeweight ew);
139
143  Graph toGraph(bool autoCompleteEdges, bool parallel = false);
144
150  template<typename L> void forNodes(L handle) const;
151
157  template<typename L> void parallelForNodes(L handle) const;
158
164  template<typename L> void forNodePairs(L handle) const;
165
171  template<typename L> void parallelForNodePairs(L handle) const;
172
173 private:
174  void toGraphDirectSwap(Graph &G);
175  void toGraphSequential(Graph &G);
176  void toGraphParallel(Graph &G);
177
178  template <typename T>
179  static void copyAndClear(std::vector<T>& source, std::vector<T>& target);
180
181  void setDegrees(Graph& G);
182  count numberOfEdges(const Graph& G);
183 };
184
185 template<typename L>
186 void GraphBuilder::forNodes(L handle) const {
187  for (node v = 0; v < n; v++) {
188  handle(v);
189  }
190 }
191
192 template<typename L>
193 void GraphBuilder::parallelForNodes(L handle) const {
194  #pragma omp parallel for schedule(dynamic, 100)
195  for (node v = 0; v < n; v++) {
196  handle(v);
197  }
198 }
199
200 template<typename L>
201 void GraphBuilder::forNodePairs(L handle) const {
202  for (node u = 0; u < n; u++) {
203  for (node v = u + 1; v < n; v++) {
204  handle(u, v);
205  }
206  }
207 }
208
209 template<typename L>
211  #pragma omp parallel for schedule(dynamic, 100)
212  for (node u = 0; u < n; u++) {
213  for (node v = u + 1; v < n; v++) {
214  handle(u, v);
215  }
216  }
217 }
218
219 template <typename T>
220 void GraphBuilder::copyAndClear(std::vector<T>& source, std::vector<T>& target) {
221  std::copy(source.begin(), source.end(), std::back_inserter(target));
222  source.clear();
223 }
224
225 } /* namespace NetworKit */
226
227 #endif /* GRAPH_BUILDER_H */
void addHalfInEdge(node u, node v, edgeweight ew=defaultEdgeWeight)
Definition: GraphBuilder.cpp:85
void increaseOutWeight(node u, node v, edgeweight ew)
Definition: GraphBuilder.cpp:130
bool isDirected() const
Return true if this graph supports directed edges.
Definition: GraphBuilder.h:77
void addHalfEdge(node u, node v, edgeweight ew=defaultEdgeWeight)
Insert an edge between the nodes u and v.
Definition: GraphBuilder.h:110
bool isWeighted() const
Returns true if this graph supports edge weights other than 1.0.
Definition: GraphBuilder.h:71
void swapNeighborhood(node u, std::vector< node > &neighbours, std::vector< edgeweight > &weights, bool selfloop)
Definition: GraphBuilder.cpp:97
bool isEmpty() const
Return true if graph contains no nodes.
Definition: GraphBuilder.h:83
GraphBuilder(count n=0, bool weighted=false, bool directed=false)
Creates a new GraphBuilder.
Definition: GraphBuilder.cpp:15
void increaseWeight(node u, node v, edgeweight ew)
Increase the weight of an edge.
Definition: GraphBuilder.h:136
Graph toGraph(bool autoCompleteEdges, bool parallel=false)
Generates a Graph instance.
Definition: GraphBuilder.cpp:151
count numberOfNodes() const
Return the number of nodes in the graph.
Definition: GraphBuilder.h:89
void setWeight(node u, node v, edgeweight ew)
Set the weight of an edge.
Definition: GraphBuilder.h:124
uint64_t index
Typedefs.
Definition: Globals.h:20
void setOutWeight(node u, node v, edgeweight ew)
Definition: GraphBuilder.cpp:109
void increaseInWeight(node u, node v, edgeweight ew)
Definition: GraphBuilder.cpp:140
index upperNodeIdBound() const
Get an upper bound for the node ids in the graph.
Definition: GraphBuilder.h:95
void setInWeight(node u, node v, edgeweight ew)
Definition: GraphBuilder.cpp:119
void forNodes(L handle) const
Iterate over all nodes of the graph and call handle (lambda closure).
Definition: GraphBuilder.h:186
void forNodePairs(L handle) const
Iterate over all undirected pairs of nodes and call handle (lambda closure).
Definition: GraphBuilder.h:201
void parallelForNodes(L handle) const
Iterate randomly over all nodes of the graph and call handle (lambda closure).
Definition: GraphBuilder.h:193
void addHalfOutEdge(node u, node v, edgeweight ew=defaultEdgeWeight)
Definition: GraphBuilder.cpp:73
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
Definition: GraphBuilder.h:27
constexpr edgeweight defaultEdgeWeight
Definition: Globals.h:29
void reset(count n=0)
Definition: GraphBuilder.cpp:28
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
void setName(std::string name)
Set name of graph to name.
Definition: GraphBuilder.h:65