Graph.h
Go to the documentation of this file.
1 /*
2  * Graph.h
3  *
4  * Created on: 01.06.2014
5  * Author: Christian Staudt (christian.staudt@kit.edu), Klara Reichard (klara.reichard@gmail.com), Marvin Ritter (marvin.ritter@gmail.com)
6  */
7
8 #ifndef GRAPH_H_
9 #define GRAPH_H_
10
11 #include <algorithm>
12 #include <vector>
13 #include <stack>
14 #include <queue>
15 #include <utility>
16 #include <stdexcept>
17 #include <functional>
18 #include <unordered_set>
19
20 #include "../Globals.h"
21 #include "Coordinates.h"
22 #include "../viz/Point.h"
23 #include "../auxiliary/Random.h"
24 #include "../auxiliary/FunctionTraits.h"
25 #include "../auxiliary/Log.h"
26
27 namespace NetworKit {
28
29
34 struct WeightedEdge {
35  node u, v;
37
38  WeightedEdge(node u, node v, edgeweight w) : u(u), v(v), weight(w) {
39  }
40 };
41 inline bool operator<(const WeightedEdge& e1, const WeightedEdge& e2) {
42  return e1.weight < e2.weight;
43 }
44 struct Edge {
45  node u, v;
46
47  Edge(node _u, node _v, bool sorted = false) {
48  if (sorted) {
49  u = std::min(_u, _v);
50  v = std::max(_u, _v);
51  } else {
52  u = _u;
53  v = _v;
54  }
55  }
56 };
57 inline bool operator==(const Edge& e1, const Edge& e2) {
58  return e1.u == e2.u && e1.v == e2.v;
59 }
60 }
61
62 namespace std {
63  template<>
64  struct hash<NetworKit::Edge> {
65  size_t operator()(const NetworKit::Edge& e) const {
66  return hash_node(e.u) ^ hash_node(e.v);
67  }
68
69  hash<NetworKit::node> hash_node;
70  };
71 }
72
73 namespace NetworKit {
74
79 class Graph final {
80
82  friend class GraphBuilder;
83
84 private:
85  // graph attributes
86  count id;
87  std::string name;
88
89  // scalars
90  count n;
91  count m;
92  count storedNumberOfSelfLoops;
93  node z;
94  edgeid omega;
95  count t;
96
97  bool weighted;
98  bool directed;
99  bool edgesIndexed;
100
101  // per node data
102  std::vector<bool> exists;
103  Coordinates<float> coordinates;
104
105  std::vector<count> inDeg;
106  std::vector<count> outDeg;
107
108  std::vector< std::vector<node> > inEdges;
109  std::vector< std::vector<node> > outEdges;
110
111  std::vector< std::vector<edgeweight> > inEdgeWeights;
112  std::vector< std::vector<edgeweight> > outEdgeWeights;
113
114  std::vector< std::vector<edgeid> > inEdgeIds;
115  std::vector< std::vector<edgeid> > outEdgeIds;
116
120  count getNextGraphId();
121
125  index indexInInEdgeArray(node v, node u) const;
126
130  index indexInOutEdgeArray(node u, node v) const;
131
138  template<bool hasWeights>
139  inline edgeweight getOutEdgeWeight(node u, index i) const;
140
148  template<bool hasWeights>
149  inline edgeweight getInEdgeWeight(node u, index i) const;
150
158  template<bool graphHasEdgeIds>
159  inline edgeid getOutEdgeId(node u, index i) const;
160
168  template<bool graphHasEdgeIds>
169  inline edgeid getInEdgeId(node u, index i) const;
170
178  template<bool graphIsDirected>
179  inline bool useEdgeInIteration(node u, node v) const;
180
190  template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
191  inline void forOutEdgesOfImpl(node u, L handle) const;
192
202  template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
203  inline void forInEdgesOfImpl(node u, L handle) const;
204
211  template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
212  inline void forEdgeImpl(L handle) const;
213
220  template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
221  inline void parallelForEdgesImpl(L handle) const;
222
229  template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
230  inline double parallelSumForEdgesImpl(L handle) const;
231
232  /*
233  * In the following definition, Aux::FunctionTraits is used in order to only execute lambda functions
234  * with the appropriate parameters. The decltype-return type is used for determining the return type of
235  * the lambda (needed for summation) but also determines if the lambda accepts the correct number of parameters.
236  * Otherwise the return type declaration fails and the function is excluded from overload resoluation.
237  * Then there are multiple possible lambdas with three (third parameter id or weight) and two (second parameter
238  * can be second node id or edge weight for neighbor iterators). This is checked using Aux::FunctionTraits and
239  * std::enable_if. std::enable_if only defines the type member when the given bool is true, this bool comes from
240  * std::is_same which compares two types. The function traits give either the parameter type or if it is out of bounds
241  * they define type as void.
242  */
243
249  template<class F, void* = (void*)0>
250  typename Aux::FunctionTraits<F>::result_type edgeLambda(F&, ...) const {
251  // the strange condition is used in order to delay the eveluation of the static assert to the moment when this function is actually used
252  static_assert(! std::is_same<F, F>::value, "Your lambda does not support the required parameters or the parameters have the wrong type.");
253  return std::declval<typename Aux::FunctionTraits<F>::result_type>(); // use the correct return type (this won't compile)
254  }
255
260  template < class F,
261  typename std::enable_if <
263  std::is_same<edgeweight, typename Aux::FunctionTraits<F>::template arg<2>::type>::value &&
264  std::is_same<edgeid, typename Aux::FunctionTraits<F>::template arg<3>::type>::value
265  >::type * = (void*)0 >
266  auto edgeLambda(F &f, node u, node v, edgeweight ew, edgeid id) const -> decltype(f(u, v, ew, id)) {
267  return f(u, v, ew, id);
268  }
269
270
275  template<class F,
276  typename std::enable_if<
278  std::is_same<edgeid, typename Aux::FunctionTraits<F>::template arg<2>::type>::value &&
279  std::is_same<node, typename Aux::FunctionTraits<F>::template arg<1>::type>::value /* prevent f(v, weight, eid) */
280  >::type* = (void*)0>
281  auto edgeLambda(F&f, node u, node v, edgeweight, edgeid id) const -> decltype(f(u, v, id)) {
282  return f(u, v, id);
283  }
284
289  template<class F,
290  typename std::enable_if<
292  std::is_same<edgeweight, typename Aux::FunctionTraits<F>::template arg<2>::type>::value
293  >::type* = (void*)0>
294  auto edgeLambda(F&f, node u, node v, edgeweight ew, edgeid /*id*/) const -> decltype(f(u, v, ew)) {
295  return f(u, v, ew);
296  }
297
298
304  template<class F,
305  typename std::enable_if<
307  std::is_same<node, typename Aux::FunctionTraits<F>::template arg<1>::type>::value
308  >::type* = (void*)0>
309  auto edgeLambda(F&f, node u, node v, edgeweight /*ew*/, edgeid /*id*/) const -> decltype(f(u, v)) {
310  return f(u, v);
311  }
312
318  template<class F,
319  typename std::enable_if<
321  std::is_same<edgeweight, typename Aux::FunctionTraits<F>::template arg<1>::type>::value
322  >::type* = (void*)0>
323  auto edgeLambda(F&f, node u, node v, edgeweight ew, edgeid /*id*/) const -> decltype(f(u, ew)) {
324  return f(v, ew);
325  }
326
327
332  template<class F,
333  void* = (void*)0>
334  auto edgeLambda(F&f, node, node v, edgeweight, edgeid) const -> decltype(f(v)) {
335  return f(v);
336  }
337
338
342  template <class F>
343  auto callBFSHandle(F &f, node u, count dist) const -> decltype(f(u, dist)) {
344  return f(u, dist);
345  }
346
350  template <class F>
351  auto callBFSHandle(F &f, node u, count) const -> decltype(f(u)) {
352  return f(u);
353  }
354
355 public:
356
365  Graph(count n = 0, bool weighted = false, bool directed = false);
366
367  Graph(const Graph& G, bool weighted, bool directed);
368
375  Graph(std::initializer_list<WeightedEdge> edges);
376
377
382  Graph(const Graph& other) = default;
383
385  Graph(Graph&& other) = default;
386
388  ~Graph() = default;
389
391  Graph& operator=(Graph&& other) = default;
392
394  Graph& operator=(const Graph& other) = default;
395
403  void indexEdges(bool force = false);
404
410  bool hasEdgeIds() const { return edgesIndexed; }
411
415  edgeid edgeId(node u, node v) const;
416
421  index upperEdgeIdBound() const { return omega; }
422
423
430  count getId() const { return id; }
431
439  std::string typ() const;
440
446  void shrinkToFit();
447
451  void compactEdges();
452
457  void sortEdges();
458
463  void setName(std::string name) { this->name = name; }
464
465  /*
466  * Returns the name of the graph.
467  * @return The name of the graph.
468  */
469  std::string getName() const { return name; }
470
471
476  std::string toString() const;
477
478
479  /* COPYING */
480
481  /*
482  * Copies all nodes to a new graph
483  * @return graph with the same nodes.
484  */
485  Graph copyNodes() const;
486
487
488  /* NODE MODIFIERS */
489
495
502  // TODO: remove method
503  // [[deprecated("Deprecated: Node coordinates should be stored externally like any other node attribute")]]
504  node addNode(float x, float y);
505
513  void removeNode(node v);
514
522  bool hasNode(node v) const { return (v < z) && this->exists[v]; }
523
524
532  void restoreNode(node v);
533
534
535  // SET OPERATIONS
536
542  void append(const Graph& G);
543
549  void merge(const Graph& G);
550
551
552  // SUBGRAPHS
553
554  Graph subgraphFromNodes(const std::unordered_set<node>& nodes) const;
555
556
565  count degree(node v) const { return outDeg[v]; }
566
574  count degreeIn(node v) const { return directed ? inDeg[v] : outDeg[v]; }
575
582  count degreeOut(node v) const { return outDeg[v]; }
583
589  bool isIsolated(node v) const { return outDeg[v] == 0 && (!directed || inDeg[v] == 0); }
590
591
599  edgeweight weightedDegree(node v) const;
600
607  edgeweight volume(node v) const;
608
613  node randomNode() const;
614
621  node randomNeighbor(node u) const;
622
623
624  /* EDGE MODIFIERS */
625
635  void addEdge(node u, node v, edgeweight ew = defaultEdgeWeight);
636
642  void removeEdge(node u, node v);
643
647  void removeSelfLoops();
648
660
667  bool hasEdge(node u, node v) const;
668
675  std::pair<node, node> randomEdge(bool uniformDistribution = false) const;
676
680  std::vector< std::pair<node, node> > randomEdges(count nr) const;
681
682  /* GLOBAL PROPERTIES */
683
688  bool isWeighted() const { return weighted; }
689
694  bool isDirected() const { return directed; }
695
700  bool isEmpty() const { return n == 0; }
701
706  count numberOfNodes() const { return n; }
707
712  count numberOfEdges() const { return m; }
713
714
718  std::pair<count, count> const size() const { return {n, m}; };
719
720
724  double density() const {
725  count n = numberOfNodes();
726  count m = numberOfEdges();
727  count loops = numberOfSelfLoops();
728  m -= loops;
729  double d;
730  if (isDirected()) {
731  d = m / (double) (n * (n-1));
732  } else {
733  d = (2 * m) / (double) (n * (n-1));
734  }
735  return d;
736  }
737
743  count numberOfSelfLoops() const;
744
749  index upperNodeIdBound() const { return z; }
750
755  bool checkConsistency() const;
756
757
758  /* DYNAMICS */
759
763  void timeStep() { t++; }
764
769  count time() { return t; }
770
771
772  /* COORDINATES */
773
783  // TODO: remove method
784  // [[deprecated("Deprecated: Node coordinates should be stored externally like any other node attribute")]]
785  void setCoordinate(node v, Point<float> value) { coordinates.setCoordinate(v, value); }
786
787
796  // TODO: remove method
797  // [[deprecated("Deprecated: Node coordinates should be stored externally like any other node attribute")]]
798  Point<float>& getCoordinate(node v) { return coordinates.getCoordinate(v); }
799
808  // TODO: remove method
809  // [[deprecated("Deprecated: Node coordinates should be stored externally like any other node attribute")]]
810  float minCoordinate(count dim) { return coordinates.minCoordinate(dim); }
811
820  // TODO: remove method
821  // [[deprecated("Deprecated: Node coordinates should be stored externally like any other node attribute")]]
822  float maxCoordinate(count dim) { return coordinates.maxCoordinate(dim); }
823
832  // TODO: remove method
833  // [[deprecated("Deprecated: Node coordinates should be stored externally like any other node attribute")]]
834  void initCoordinates() { coordinates.init(z); }
835
836
837  /* EDGE ATTRIBUTES */
838
847  edgeweight weight(node u, node v) const;
848
857  void setWeight(node u, node v, edgeweight ew);
858
867  void increaseWeight(node u, node v, edgeweight ew);
868
869
870
871  /* SUMS */
872
877  edgeweight totalEdgeWeight() const;
878
879
880  /* Collections */
881
886  std::vector<node> nodes() const;
887
892  std::vector<std::pair<node, node> > edges() const;
893
900  std::vector<node> neighbors(node u) const;
901
911  template<bool graphIsDirected>
913  node v = outEdges[u][i];
914  if (useEdgeInIteration<graphIsDirected>(u, v))
915  return v;
916  else
917  return none;
918  }
919
920
921  /* Derivative Graphs */
922
928  Graph toUndirected() const;
929
930
936  Graph toUnweighted() const;
937
943  Graph transpose() const;
944
945  /* NODE ITERATORS */
946
952  template<typename L> void forNodes(L handle) const;
953
959  template<typename L> void parallelForNodes(L handle) const;
960
967  template<typename C, typename L> void forNodesWhile(C condition, L handle) const;
968
974  template<typename L> void forNodesInRandomOrder(L handle) const;
975
982  template<typename L> void balancedParallelForNodes(L handle) const;
983
984
990  template<typename L> void forNodePairs(L handle) const;
991
992
998  template<typename L> void parallelForNodePairs(L handle) const;
999
1000
1001  /* EDGE ITERATORS */
1002
1008  template<typename L> void forEdges(L handle) const;
1009
1015  template<typename L> void parallelForEdges(L handle) const;
1016
1017
1018  /* NEIGHBORHOOD ITERATORS */
1019
1029  template<typename L> void forNeighborsOf(node u, L handle) const;
1030
1038  template<typename L> void forEdgesOf(node u, L handle) const;
1039
1044  template<typename L> void forInNeighborsOf(node u, L handle) const;
1045
1052  template<typename L> void forInEdgesOf(node u, L handle) const;
1053
1054  /* REDUCTION ITERATORS */
1055
1059  template<typename L> double parallelSumForNodes(L handle) const;
1060
1064  template<typename L> double parallelSumForEdges(L handle) const;
1065
1066
1067  /* GRAPH SEARCHES */
1068
1076  template<typename L> void BFSfrom(node r, L handle) const;
1077  template<typename L> void BFSfrom(const std::vector<node> &startNodes, L handle) const;
1078
1079  template<typename L> void BFSEdgesFrom(node r, L handle) const;
1080
1088  template<typename L> void DFSfrom(node r, L handle) const;
1089
1090
1091  template<typename L> void DFSEdgesFrom(node r, L handle) const;
1092 };
1093
1094 /* NODE ITERATORS */
1095
1096 template<typename L>
1097 void Graph::forNodes(L handle) const {
1098  for (node v = 0; v < z; ++v) {
1099  if (exists[v]) {
1100  handle(v);
1101  }
1102  }
1103 }
1104
1105 template<typename L>
1106 void Graph::parallelForNodes(L handle) const {
1107  #pragma omp parallel for
1108  for (node v = 0; v < z; ++v) {
1109  if (exists[v]) {
1110  handle(v);
1111  }
1112  }
1113 }
1114
1115 template<typename C, typename L>
1116 void Graph::forNodesWhile(C condition, L handle) const {
1117  for (node v = 0; v < z; ++v) {
1118  if (exists[v]) {
1119  if (!condition()) {
1120  break;
1121  }
1122  handle(v);
1123  }
1124  }
1125 }
1126
1127 template<typename L>
1128 void Graph::forNodesInRandomOrder(L handle) const {
1129  std::vector<node> randVec = nodes();
1130  std::shuffle(randVec.begin(), randVec.end(), Aux::Random::getURNG());
1131  for (node v : randVec) {
1132  handle(v);
1133  }
1134 }
1135
1136 template<typename L>
1137 void Graph::balancedParallelForNodes(L handle) const {
1138  #pragma omp parallel for schedule(guided) // TODO: define min block size (and test it!)
1139  for (node v = 0; v < z; ++v) {
1140  if (exists[v]) {
1141  handle(v);
1142  }
1143  }
1144 }
1145
1146 template<typename L>
1147 void Graph::forNodePairs(L handle) const {
1148  for (node u = 0; u < z; ++u) {
1149  if (exists[u]) {
1150  for (node v = u + 1; v < z; ++v) {
1151  if (exists[v]) {
1152  handle(u, v);
1153  }
1154  }
1155  }
1156  }
1157 }
1158
1159 template<typename L>
1160 void Graph::parallelForNodePairs(L handle) const {
1161  #pragma omp parallel for schedule(guided)
1162  for (node u = 0; u < z; ++u) {
1163  if (exists[u]) {
1164  for (node v = u + 1; v < z; ++v) {
1165  if (exists[v]) {
1166  handle(u, v);
1167  }
1168  }
1169  }
1170  }
1171 }
1172
1173
1174 /* EDGE ITERATORS */
1175
1176 /* HELPERS */
1177
1178 template<bool hasWeights> // implementation for weighted == true
1179 inline edgeweight Graph::getOutEdgeWeight(node u, index i) const {
1180  return outEdgeWeights[u][i];
1181 }
1182
1183 template<> // implementation for weighted == false
1184 inline edgeweight Graph::getOutEdgeWeight<false>(node, index) const {
1185  return defaultEdgeWeight;
1186 }
1187
1188 template<bool hasWeights> // implementation for weighted == true
1189 inline edgeweight Graph::getInEdgeWeight(node u, index i) const {
1190  return inEdgeWeights[u][i];
1191 }
1192
1193 template<> // implementation for weighted == false
1194 inline edgeweight Graph::getInEdgeWeight<false>(node, index) const {
1195  return defaultEdgeWeight;
1196 }
1197
1198
1199 template<bool graphHasEdgeIds> // implementation for hasEdgeIds == true
1200 inline edgeid Graph::getOutEdgeId(node u, index i) const {
1201  return outEdgeIds[u][i];
1202 }
1203
1204 template<> // implementation for hasEdgeIds == false
1205 inline edgeid Graph::getOutEdgeId<false>(node, index) const {
1206  return 0;
1207 }
1208
1209 template<bool graphHasEdgeIds> // implementation for hasEdgeIds == true
1210 inline edgeid Graph::getInEdgeId(node u, index i) const {
1211  return inEdgeIds[u][i];
1212 }
1213
1214 template<> // implementation for hasEdgeIds == false
1215 inline edgeid Graph::getInEdgeId<false>(node, index) const {
1216  return 0;
1217 }
1218
1219
1220 template<bool graphIsDirected> // implementation for graphIsDirected == true
1221 inline bool Graph::useEdgeInIteration(node /* u */, node v) const {
1222  return v != none;
1223 }
1224
1225 template<> // implementation for graphIsDirected == false
1226 inline bool Graph::useEdgeInIteration<false>(node u, node v) const {
1227  return u >= v;
1228 }
1229
1230 template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
1231 inline void Graph::forOutEdgesOfImpl(node u, L handle) const {
1232  for (index i = 0; i < outEdges[u].size(); ++i) {
1233  node v = outEdges[u][i];
1234
1235  if (useEdgeInIteration<graphIsDirected>(u, v)) {
1236  edgeLambda<L>(handle, u, v, getOutEdgeWeight<hasWeights>(u, i), getOutEdgeId<graphHasEdgeIds>(u, i));
1237  }
1238  }
1239 }
1240
1241 template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
1242 inline void Graph::forInEdgesOfImpl(node u, L handle) const {
1243  if (graphIsDirected) {
1244  for (index i = 0; i < inEdges[u].size(); i++) {
1245  node v = inEdges[u][i];
1246
1247  if (useEdgeInIteration<true>(u, v)) {
1248  edgeLambda<L>(handle, u, v, getInEdgeWeight<hasWeights>(u, i), getInEdgeId<graphHasEdgeIds>(u, i));
1249  }
1250  }
1251  } else {
1252  for (index i = 0; i < outEdges[u].size(); ++i) {
1253  node v = outEdges[u][i];
1254
1255  if (useEdgeInIteration<true>(u, v)) {
1256  edgeLambda<L>(handle, u, v, getOutEdgeWeight<hasWeights>(u, i), getOutEdgeId<graphHasEdgeIds>(u, i));
1257  }
1258  }
1259  }
1260 }
1261
1262 template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
1263 inline void Graph::forEdgeImpl(L handle) const {
1264  for (node u = 0; u < z; ++u) {
1265  forOutEdgesOfImpl<graphIsDirected, hasWeights, graphHasEdgeIds, L>(u, handle);
1266  }
1267 }
1268
1269 template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
1270 inline void Graph::parallelForEdgesImpl(L handle) const {
1271  #pragma omp parallel for schedule(guided)
1272  for (node u = 0; u < z; ++u) {
1273  forOutEdgesOfImpl<graphIsDirected, hasWeights, graphHasEdgeIds, L>(u, handle);
1274  }
1275 }
1276
1277 template<bool graphIsDirected, bool hasWeights, bool graphHasEdgeIds, typename L>
1278 inline double Graph::parallelSumForEdgesImpl(L handle) const {
1279  double sum = 0.0;
1280
1281  #pragma omp parallel for reduction(+:sum)
1282
1283  for (node u = 0; u < z; ++u) {
1284  for (index i = 0; i < outEdges[u].size(); ++i) {
1285  node v = outEdges[u][i];
1286
1287  // undirected, do not iterate over edges twice
1288  // {u, v} instead of (u, v); if v == none, u > v is not fulfilled
1289  if (useEdgeInIteration<graphIsDirected>(u, v)) {
1290  sum += edgeLambda<L>(handle, u, v, getOutEdgeWeight<hasWeights>(u, i), getOutEdgeId<graphHasEdgeIds>(u, i));
1291  }
1292  }
1293  }
1294
1295  return sum;
1296 }
1297
1298 template<typename L>
1299 void Graph::forEdges(L handle) const {
1300  switch (weighted + 2 * directed + 4 * edgesIndexed) {
1301  case 0: // unweighted, undirected, no edgeIds
1302  forEdgeImpl<false, false, false, L>(handle);
1303  break;
1304
1305  case 1: // weighted, undirected, no edgeIds
1306  forEdgeImpl<false, true, false, L>(handle);
1307  break;
1308
1309  case 2: // unweighted, directed, no edgeIds
1310  forEdgeImpl<true, false, false, L>(handle);
1311  break;
1312
1313  case 3: // weighted, directed, no edgeIds
1314  forEdgeImpl<true, true, false, L>(handle);
1315  break;
1316
1317  case 4: // unweighted, undirected, with edgeIds
1318  forEdgeImpl<false, false, true, L>(handle);
1319  break;
1320
1321  case 5: // weighted, undirected, with edgeIds
1322  forEdgeImpl<false, true, true, L>(handle);
1323  break;
1324
1325  case 6: // unweighted, directed, with edgeIds
1326  forEdgeImpl<true, false, true, L>(handle);
1327  break;
1328
1329  case 7: // weighted, directed, with edgeIds
1330  forEdgeImpl<true, true, true, L>(handle);
1331  break;
1332  }
1333 }
1334
1335
1336 template<typename L>
1337 void Graph::parallelForEdges(L handle) const {
1338  switch (weighted + 2 * directed + 4 * edgesIndexed) {
1339  case 0: // unweighted, undirected, no edgeIds
1340  parallelForEdgesImpl<false, false, false, L>(handle);
1341  break;
1342
1343  case 1: // weighted, undirected, no edgeIds
1344  parallelForEdgesImpl<false, true, false, L>(handle);
1345  break;
1346
1347  case 2: // unweighted, directed, no edgeIds
1348  parallelForEdgesImpl<true, false, false, L>(handle);
1349  break;
1350
1351  case 3: // weighted, directed, no edgeIds
1352  parallelForEdgesImpl<true, true, false, L>(handle);
1353  break;
1354
1355  case 4: // unweighted, undirected, with edgeIds
1356  parallelForEdgesImpl<false, false, true, L>(handle);
1357  break;
1358
1359  case 5: // weighted, undirected, with edgeIds
1360  parallelForEdgesImpl<false, true, true, L>(handle);
1361  break;
1362
1363  case 6: // unweighted, directed, with edgeIds
1364  parallelForEdgesImpl<true, false, true, L>(handle);
1365  break;
1366
1367  case 7: // weighted, directed, with edgeIds
1368  parallelForEdgesImpl<true, true, true, L>(handle);
1369  break;
1370  }
1371 }
1372
1373
1374
1375 /* NEIGHBORHOOD ITERATORS */
1376
1377 template<typename L>
1378 void Graph::forNeighborsOf(node u, L handle) const {
1379  forEdgesOf(u, handle);
1380 }
1381
1382 template<typename L>
1383 void Graph::forEdgesOf(node u, L handle) const {
1384  switch (weighted + 2 * edgesIndexed) {
1385  case 0: //not weighted, no edge ids
1386  forOutEdgesOfImpl<true, false, false, L>(u, handle);
1387  break;
1388
1389  case 1: //weighted, no edge ids
1390  forOutEdgesOfImpl<true, true, false, L>(u, handle);
1391  break;
1392
1393  case 2: //not weighted, with edge ids
1394  forOutEdgesOfImpl<true, false, true, L>(u, handle);
1395  break;
1396
1397  case 3: //weighted, with edge ids
1398  forOutEdgesOfImpl<true, true, true, L>(u, handle);
1399  break;
1400  }
1401 }
1402
1403 template<typename L>
1404 void Graph::forInNeighborsOf(node u, L handle) const {
1405  forInEdgesOf(u, handle);
1406 }
1407
1408 template<typename L>
1409 void Graph::forInEdgesOf(node u, L handle) const {
1410  switch (weighted + 2 * directed + 4 * edgesIndexed) {
1411  case 0: //unweighted, undirected, no edge ids
1412  forInEdgesOfImpl<false, false, false, L>(u, handle);
1413  break;
1414
1415  case 1: //weighted, undirected, no edge ids
1416  forInEdgesOfImpl<false, true, false, L>(u, handle);
1417  break;
1418
1419  case 2: //unweighted, directed, no edge ids
1420  forInEdgesOfImpl<true, false, false, L>(u, handle);
1421  break;
1422
1423  case 3: //weighted, directed, no edge ids
1424  forInEdgesOfImpl<true, true, false, L>(u, handle);
1425  break;
1426
1427  case 4: //unweighted, undirected, with edge ids
1428  forInEdgesOfImpl<false, false, true, L>(u, handle);
1429  break;
1430
1431  case 5: //weighted, undirected, with edge ids
1432  forInEdgesOfImpl<false, true, true, L>(u, handle);
1433  break;
1434
1435  case 6: //unweighted, directed, with edge ids
1436  forInEdgesOfImpl<true, false, true, L>(u, handle);
1437  break;
1438
1439  case 7: //weighted, directed, with edge ids
1440  forInEdgesOfImpl<true, true, true, L>(u, handle);
1441  break;
1442  }
1443 }
1444
1445 /* REDUCTION ITERATORS */
1446
1447 template<typename L>
1448 double Graph::parallelSumForNodes(L handle) const {
1449  double sum = 0.0;
1450  #pragma omp parallel for reduction(+:sum)
1451
1452  for (node v = 0; v < z; ++v) {
1453  if (exists[v]) {
1454  sum += handle(v);
1455  }
1456  }
1457
1458  return sum;
1459 }
1460
1461 template<typename L>
1462 double Graph::parallelSumForEdges(L handle) const {
1463  double sum = 0.0;
1464
1465  switch (weighted + 2 * directed + 4 * edgesIndexed) {
1466  case 0: // unweighted, undirected, no edge ids
1467  sum = parallelSumForEdgesImpl<false, false, false, L>(handle);
1468  break;
1469
1470  case 1: // weighted, undirected, no edge ids
1471  sum = parallelSumForEdgesImpl<false, true, false, L>(handle);
1472  break;
1473
1474  case 2: // unweighted, directed, no edge ids
1475  sum = parallelSumForEdgesImpl<true, false, false, L>(handle);
1476  break;
1477
1478  case 3: // weighted, directed, no edge ids
1479  sum = parallelSumForEdgesImpl<true, true, false, L>(handle);
1480  break;
1481
1482  case 4: // unweighted, undirected, with edge ids
1483  sum = parallelSumForEdgesImpl<false, false, true, L>(handle);
1484  break;
1485
1486  case 5: // weighted, undirected, with edge ids
1487  sum = parallelSumForEdgesImpl<false, true, true, L>(handle);
1488  break;
1489
1490  case 6: // unweighted, directed, with edge ids
1491  sum = parallelSumForEdgesImpl<true, false, true, L>(handle);
1492  break;
1493
1494  case 7: // weighted, directed, with edge ids
1495  sum = parallelSumForEdgesImpl<true, true, true, L>(handle);
1496  break;
1497  }
1498
1499  return sum;
1500 }
1501
1502
1503 /* GRAPH SEARCHES */
1504
1505 template<typename L>
1506 void Graph::BFSfrom(node r, L handle) const {
1507  std::vector<node> startNodes(1, r);
1508  BFSfrom(startNodes, handle);
1509 }
1510
1511 template<typename L>
1512 void Graph::BFSfrom(const std::vector<node> &startNodes, L handle) const {
1513  std::vector<bool> marked(z);
1514  std::queue<node> q, qNext;
1515  count dist = 0;
1516  // enqueue start nodes
1517  for (node u : startNodes) {
1518  q.push(u);
1519  marked[u] = true;
1520  }
1521  do {
1522  node u = q.front();
1523  q.pop();
1524  // apply function
1525  callBFSHandle(handle, u, dist);
1526  forNeighborsOf(u, [&](node v) {
1527  if (!marked[v]) {
1528  qNext.push(v);
1529  marked[v] = true;
1530  }
1531  });
1532  if (q.empty() && !qNext.empty()) {
1533  q.swap(qNext);
1534  ++dist;
1535  }
1536  } while (!q.empty());
1537 }
1538
1539 template<typename L>
1540 void Graph::BFSEdgesFrom(node r, L handle) const {
1541  std::vector<bool> marked(z);
1542  std::queue<node> q;
1543  q.push(r); // enqueue root
1544  marked[r] = true;
1545  do {
1546  node u = q.front();
1547  q.pop();
1548  // apply function
1549  forNeighborsOf(u, [&](node, node v, edgeweight w, edgeid eid) {
1550  if (!marked[v]) {
1551  handle(u, v, w, eid);
1552  q.push(v);
1553  marked[v] = true;
1554  }
1555  });
1556  } while (!q.empty());
1557 }
1558
1559 template<typename L>
1560 void Graph::DFSfrom(node r, L handle) const {
1561  std::vector<bool> marked(z);
1562  std::stack<node> s;
1563  s.push(r); // enqueue root
1564  marked[r] = true;
1565  do {
1566  node u = s.top();
1567  s.pop();
1568  // apply function
1569  handle(u);
1570  forNeighborsOf(u, [&](node v) {
1571  if (!marked[v]) {
1572  s.push(v);
1573  marked[v] = true;
1574  }
1575  });
1576  } while (!s.empty());
1577 }
1578
1579 template<typename L>
1580 void Graph::DFSEdgesFrom(node r, L handle) const {
1581  std::vector<bool> marked(z);
1582  std::stack<node> s;
1583  s.push(r); // enqueue root
1584  marked[r] = true;
1585  do {
1586  node u = s.top();
1587  s.pop();
1588  // apply function
1589  forNeighborsOf(u, [&](node v) {
1590  if (!marked[v]) {
1591  handle(u, v);
1592  s.push(v);
1593  marked[v] = true;
1594  }
1595  });
1596  } while (!s.empty());
1597 }
1598
1599
1600
1601
1602 } /* namespace NetworKit */
1603
1604 #endif /* GRAPH_H_ */
float maxCoordinate(count dim)
DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes...
Definition: Graph.h:822
bool checkConsistency() const
Check for invalid graph states, such as multi-edges.
Definition: Graph.cpp:949
count degreeOut(node v) const
Get the number of outgoing neighbors of v.
Definition: Graph.h:582
Definition: ParallelPartitionCoarsening.h:20
edgeweight totalEdgeWeight() const
Returns the sum of all edge weights.
Definition: Graph.cpp:866
void initCoordinates()
DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes...
Definition: Graph.h:834
A weighted edge used for the graph constructor with initializer list syntax.
Definition: Graph.h:34
node u
Definition: Graph.h:35
void forNodes(L handle) const
Iterate over all nodes of the graph and call handle (lambda closure).
Definition: Graph.h:1097
void setWeight(node u, node v, edgeweight ew)
Set the weight of an edge.
Definition: Graph.cpp:816
double parallelSumForNodes(L handle) const
Iterate in parallel over all nodes and sum (reduce +) the values returned by the handler.
Definition: Graph.h:1448
Graph toUnweighted() const
Return an unweighted version of this graph.
Definition: Graph.cpp:941
index edgeid
Definition: Globals.h:25
void BFSEdgesFrom(node r, L handle) const
Definition: Graph.h:1540
Graph(count n=0, bool weighted=false, bool directed=false)
Create a graph of n nodes.
Definition: Graph.cpp:18
void merge(const Graph &G)
Modifies this graph to be the union of it and another graph.
Definition: Graph.cpp:984
Graph & operator=(Graph &&other)=default
Default move assignment operator.
edgeweight weightedDegree(node v) const
Returns the weighted degree of v.
Definition: Graph.cpp:536
Graph transpose() const
Return the transpose of this graph.
Definition: Graph.cpp:910
bool isDirected() const
Return true if this graph supports directed edges.
Definition: Graph.h:694
typename call_type::result_type result_type
Definition: FunctionTraits.h:57
float minCoordinate(count dim)
DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes...
Definition: Graph.h:810
void forEdgesOf(node u, L handle) const
Iterate over all incident edges of a node and call handle (lamdba closure).
Definition: Graph.h:1383
WeightedEdge(node u, node v, edgeweight w)
Definition: Graph.h:38
void parallelForNodePairs(L handle) const
Iterate over all undirected pairs of nodes in parallel and call handle (lambda closure).
Definition: Graph.h:1160
void DFSfrom(node r, L handle) const
Iterate over nodes in depth-first search order starting from r until connected component of r has bee...
Definition: Graph.h:1560
Edge(node _u, node _v, bool sorted=false)
Definition: Graph.h:47
Point< T > & getCoordinate(index v)
Definition: Coordinates.h:50
void init(count numNodes)
Allocates space for numNodes entries.
Definition: Coordinates.h:36
bool hasEdge(node u, node v) const
Checks if undirected edge {u,v} exists in the graph.
Definition: Graph.cpp:745
uint64_t index
Typedefs.
Definition: Globals.h:20
Definition: Graph.h:44
void forInNeighborsOf(node u, L handle) const
Iterate over all neighbors of a node and call handler (lamdba closure).
Definition: Graph.h:1404
void shrinkToFit()
Try to save some memory by shrinking internal data structures of the graph.
Definition: Graph.cpp:298
std::string getName() const
Definition: Graph.h:469
Add a new node to the graph and return it.
Definition: Graph.cpp:475
node randomNode() const
Returns a random node of the graph.
Definition: Graph.cpp:570
void BFSfrom(node r, L handle) const
Iterate over nodes in breadth-first search order starting from r until connected component of r has b...
Definition: Graph.h:1506
void addEdge(node u, node v, edgeweight ew=defaultEdgeWeight)
Insert an edge between the nodes u and v.
Definition: Graph.cpp:600
std::vector< node > neighbors(node u) const
Get list of neighbors of u.
Definition: Graph.cpp:901
node getIthNeighbor(node u, index i) const
Get i-th (outgoing) neighbor of u.
Definition: Graph.h:912
void forEdges(L handle) const
Iterate over all edges of the const graph and call handle (lambda closure).
Definition: Graph.h:1299
edgeweight weight
Definition: Graph.h:36
std::pair< node, node > randomEdge(bool uniformDistribution=false) const
Returns a random edge.
Definition: Graph.cpp:749
index upperEdgeIdBound() const
Get an upper bound for the edge ids in the graph.
Definition: Graph.h:421
edgeweight weight(node u, node v) const
Return edge weight of edge {u,v}.
Definition: Graph.cpp:807
T minCoordinate(count dim)
Definition: Coordinates.h:57
void append(const Graph &G)
Appends another graph to this graph as a new subgraph.
Definition: Graph.cpp:967
count degree(node v) const
NODE PROPERTIES.
Definition: Graph.h:565
void timeStep()
Trigger a time step - increments counter.
Definition: Graph.h:763
index upperNodeIdBound() const
Get an upper bound for the node ids in the graph.
Definition: Graph.h:749
std::pair< count, count > const size() const
Definition: Graph.h:718
void restoreNode(node v)
Restores a previously deleted node v with its previous id in the graph.
Definition: Graph.cpp:525
double density() const
Definition: Graph.h:724
std::vector< std::pair< node, node > > edges() const
Get list of edges as node pairs.
Definition: Graph.cpp:891
double parallelSumForEdges(L handle) const
Iterate in parallel over all edges and sum (reduce +) the values returned by the handler.
Definition: Graph.h:1462
node randomNeighbor(node u) const
Returns a random neighbor of u and none if degree is zero.
Definition: Graph.cpp:583
void compactEdges()
Compacts the adjacency arrays by re-using no longer neede slots from deleted edges.
Definition: Graph.cpp:326
void swapEdge(NetworKit::node s1, NetworKit::node t1, NetworKit::node s2, NetworKit::node t2)
Changes the edges {s1, t1} into {s1, t2} and the edge {s2, t2} into {s2, t1}.
Definition: Graph.cpp:711
void removeEdge(node u, node v)
Removes the undirected edge {u,v}.
Definition: Graph.cpp:653
count numberOfSelfLoops() const
Return the number of loops {v,v} in the graph.
Definition: Graph.cpp:800
void DFSEdgesFrom(node r, L handle) const
Definition: Graph.h:1580
Graph subgraphFromNodes(const std::unordered_set< node > &nodes) const
Definition: Graph.cpp:998
bool isEmpty() const
Return true if graph contains no nodes.
Definition: Graph.h:700
uint64_t count
Definition: Globals.h:21
constexpr index none
Constants.
Definition: Globals.h:28
index node
Definition: Globals.h:23
Point< float > & getCoordinate(node v)
DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes...
Definition: Graph.h:798
void forNodesWhile(C condition, L handle) const
Iterate over all nodes of the graph and call handle (lambda closure) as long as condition remains tru...
Definition: Graph.h:1116
void setCoordinate(index v, const Point< T > &value)
Sets entry at index v to value value.
Definition: Coordinates.h:43
count getId() const
GRAPH INFORMATION.
Definition: Graph.h:430
void forInEdgesOf(node u, L handle) const
Iterate over all incoming edges of a node and call handler (lamdba closure).
Definition: Graph.h:1409
hash< NetworKit::node > hash_node
Definition: Graph.h:69
bool hasNode(node v) const
Check if node v exists in the graph.
Definition: Graph.h:522
void forNodePairs(L handle) const
Iterate over all undirected pairs of nodes and call handle (lambda closure).
Definition: Graph.h:1147
bool isIsolated(node v) const
Check whether v is isolated, i.e.
Definition: Graph.h:589
count numberOfEdges() const
Return the number of edges in the graph.
Definition: Graph.h:712
size_t operator()(const NetworKit::Edge &e) const
Definition: Graph.h:65
void balancedParallelForNodes(L handle) const
Iterate in parallel over all nodes of the graph and call handler (lambda closure).
Definition: Graph.h:1137
bool hasEdgeIds() const
Checks if edges have been indexed.
Definition: Graph.h:410
void sortEdges()
Sorts the adjacency arrays by node id.
Definition: Graph.cpp:381
std::string typ() const
Return the type of the graph.
Definition: Graph.cpp:290
Definition: GraphBuilder.h:27
constexpr edgeweight defaultEdgeWeight
Definition: Globals.h:29
void increaseWeight(node u, node v, edgeweight ew)
Increase the weight of an edge.
Definition: Graph.cpp:839
std::vector< node > nodes() const
Get list of all nodes.
Definition: Graph.cpp:881
void removeSelfLoops()
Removes all self-loops in the graph.
Definition: Graph.cpp:701
count time()
Get time step counter.
Definition: Graph.h:769
void removeNode(node v)
Remove a node v and all incident edges from the graph.
Definition: Graph.cpp:509
bool isWeighted() const
Returns true if this graph supports edge weights other than 1.0.
Definition: Graph.h:688
count numberOfNodes() const
Return the number of nodes in the graph.
Definition: Graph.h:706
bool operator<(const WeightedEdge &e1, const WeightedEdge &e2)
Definition: Graph.h:41
Graph toUndirected() const
Return an undirected version of this graph.
Definition: Graph.cpp:932
void forNodesInRandomOrder(L handle) const
Iterate randomly over all nodes of the graph and call handle (lambda closure).
Definition: Graph.h:1128
void forNeighborsOf(node u, L handle) const
Iterate over all neighbors of a node and call handle (lamdba closure).
Definition: Graph.h:1378
node v
Definition: Graph.h:45
Definition: FunctionTraits.h:12
void parallelForNodes(L handle) const
Iterate randomly over all nodes of the graph and call handle (lambda closure).
Definition: Graph.h:1106
node u
Definition: Graph.h:45
void parallelForEdges(L handle) const
Iterate in parallel over all edges of the const graph and call handle (lambda closure).
Definition: Graph.h:1337
void setCoordinate(node v, Point< float > value)
DEPRECATED: Coordinates should be handled outside the Graph class like general node attributes...
Definition: Graph.h:785
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
Graph copyNodes() const
COPYING.
Definition: Graph.cpp:463
edgeweight volume(node v) const
Returns the volume of the v, which is the weighted degree with self-loops counted twice...
Definition: Graph.cpp:547
T maxCoordinate(count dim)
Definition: Coordinates.h:71
edgeid edgeId(node u, node v) const
Get the id of the given edge.
Definition: Graph.cpp:273
count degreeIn(node v) const
Get the number of incoming neighbors of v.
Definition: Graph.h:574
std::mt19937_64 & getURNG()
Definition: Random.cpp:54
bool operator==(const Edge &e1, const Edge &e2)
Definition: Graph.h:57
std::vector< std::pair< node, node > > randomEdges(count nr) const
Returns a vector with nr random edges.
Definition: Graph.cpp:767
void setName(std::string name)
Set name of graph to name.
Definition: Graph.h:463
double edgeweight
Definition: Globals.h:24
node v
Definition: Graph.h:35
~Graph()=default
Default destructor.
void indexEdges(bool force=false)
EDGE IDS.
Definition: Graph.cpp:216
std::string toString() const
Returns a string representation of the graph.
Definition: Graph.cpp:453