All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CoreDecomposition.h
Go to the documentation of this file.
1 /*
2  * CoreDecomposition.h
3  *
4  * Created on: Oct 28, 2013
5  * Author: Lukas Barth, David Weiss, Christian Staudt
6  */
7 
8 #ifndef COREDECOMPOSITION_H_
9 #define COREDECOMPOSITION_H_
10 
11 #include <vector>
12 #include <fstream>
13 #include <string>
14 #include <list>
15 #include "../graph/Graph.h"
16 #include "../centrality/Centrality.h"
17 #include "../structures/Partition.h"
18 #include "../structures/Cover.h"
19 
20 
21 namespace NetworKit {
22 
28 
29 public:
30 
43  CoreDecomposition(const Graph& G, bool normalized=false, bool enforceBucketQueueAlgorithm = false, bool storeNodeOrder = false);
44 
48  void run();
49 
55  Cover getCover() const;
56 
62  Partition getPartition() const;
63 
69  index maxCoreNumber() const;
70 
76  double maximum();
77 
85  const std::vector<node>& getNodeOrder() const;
86 
91  virtual bool isParallel() const {
92  return canRunInParallel;
93  }
94 
95 private:
96 
97  index maxCore; // maximum core number of any node in the graph
98 
99  bool enforceBucketQueueAlgorithm; // in case one wants to switch to the alternative algorithm
100 
101  bool canRunInParallel; // signifies if a parallel algorithm can be used
102 
103  bool storeNodeOrder; // signifies if the node order shall be stored
104 
105  std::vector<node> nodeOrder; // Stores the node order, i.e., all nodes sorted by core number
106 
112  void runWithParK();
113 
119  void runWithBucketQueues();
120 
127  void scan(index level, const std::vector<count>& degrees, std::vector<node>& curr);
128 
135  void scanParallel(index level, const std::vector<count>& degrees, std::vector<node>& curr, std::vector<char>& active);
136 
144  void processSublevel(index level, std::vector<count>& degrees, const std::vector<node>& curr, std::vector<node>& next);
145 
153  void processSublevelParallel(index level, std::vector<count>& degrees, const std::vector<node>& curr, std::vector<node>& next, std::vector<char>& active);
154 };
155 
156 } /* namespace NetworKit */
157 #endif /* COREDECOMPOSITION_H_ */
const std::vector< node > & getNodeOrder() const
Get the node order.
Definition: CoreDecomposition.cpp:320
void run()
Perform k-core decomposition of graph passed in constructor.
Definition: CoreDecomposition.cpp:27
bool normalized
Definition: Centrality.h:94
Computes k-core decomposition of a graph.
Definition: CoreDecomposition.h:27
double maximum()
Get the theoretical maximum of centrality score in the given graph.
Definition: CoreDecomposition.cpp:332
uint64_t index
Typedefs.
Definition: Globals.h:20
Implements a cover of a set, i.e.
Definition: Cover.h:27
const Graph & G
Definition: Centrality.h:91
index maxCoreNumber() const
Get maximum core number.
Definition: CoreDecomposition.cpp:327
Implements a partition of a set, i.e.
Definition: Partition.h:31
Abstract base class for centrality measures.
Definition: Centrality.h:20
Partition getPartition() const
Get the k-shells as a partition object.
Definition: CoreDecomposition.cpp:304
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
CoreDecomposition(const Graph &G, bool normalized=false, bool enforceBucketQueueAlgorithm=false, bool storeNodeOrder=false)
Create CoreDecomposition class for graph G.
Definition: CoreDecomposition.cpp:18
Cover getCover() const
Get the k-cores as a graph cover object.
Definition: CoreDecomposition.cpp:284
virtual bool isParallel() const
The algorithm ParK can run in parallel under certain conditions, the bucket PQ based one cannot...
Definition: CoreDecomposition.h:91