-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrwgraph.h
More file actions
157 lines (136 loc) · 5.82 KB
/
rwgraph.h
File metadata and controls
157 lines (136 loc) · 5.82 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#ifndef _RWGRAPH_H
#define _RWGRAPH_H
#include <vector>
#include <random>
#include "sfmt/SFMT.h"
#include "mappedHeap.hpp"
#include "HeapData.hpp"
#include "StepwiseHeap.h"
#include <ctime>
#include <cmath>
#include <functional>
typedef uint32_t UI;
// typedef uint64_t ULL;
#if defined(_OPENMP)
#include <omp.h>
#else
typedef int omp_int_t;
inline omp_int_t omp_set_num_threads(int t) { return 1;}
inline omp_int_t omp_get_thread_num() { return 0;}
#endif
// Graph class defines fundamental operators on graph
class Graph
{
friend class IM_ICSampler;
friend class IM_LTSampler;
private:
UI UI_MAX = 4294967295U;
// ULL ULL_MAX = 18446744073709551615ULL;
// number of nodes
unsigned int numNodes;
// number of edges
unsigned int numEdges;
// adjacency list
std::vector<std::vector<int> > adjList;
std::vector<int> node_deg;
std::vector<std::vector<UI> > weights;
public:
Graph();
// get a vector of neighbours of node u
const std::vector<int> & operator [] (int u) const;
// return weights of neighbours of node u
const std::vector<UI> & getWeight(int u) const;
// get a vector of neighbours of node u
const std::vector<int> & operator [] (int u);
// return weights of neighbours of node u
const std::vector<UI> & getWeight(int u);
// get degree of node u
int getDegree(int u) const;
// get size of the graph
int getSize() const;
// get number of edges
int getEdge() const;
// read graph from a file
void readGraphLT(const char * filename);
// read graph from a file
void readGraphIC(const char * filename);
// write the graph to file
void writeToFile(const char * filename);
};
class HyperGraph
{
private:
// store the edges that a node is incident to
std::vector<std::vector<int> > node_edge;
// store hyperedges
std::vector<std::vector<int> > edge_node;
// complete copy of all generated hyperedge
std::vector<std::vector<int> > all_edge_node;
std::vector<std::vector<int> > all_node_edge;
unsigned int numNodes;
std::vector<bool> markRemovedEdges;
int deletedSize, totalSize, fullSize, maxSize;
bool do_check;
public:
Stepwise_heap sheap;
HyperGraph();
void reinitialize(unsigned int k, unsigned int b);
HyperGraph(unsigned int n, bool c, unsigned int k, unsigned int b);
void addHyperedge(std::vector<int> &e);
void addHyperedge_all(std::vector<int> &e);
void updateDeg();
void updateEdge();
void addEdge(std::vector<int> & edge);
void addEdgeD(std::vector<int> & edge);
const std::vector<int> & getEdge(int e) const;
const std::vector<int> & getEdge(int e);
const std::vector<int> & getNode(int n) const;
const std::vector<int> & getNode(int n);
void clearEdges();
int getSketchSize();
double increaseT(std::vector<int> & seeds, int k, std::vector<double> &ve, double alpha);
double decreaseT(std::vector<int> & seeds, int k, std::vector<double> &ve, double alpha);
double dualBound(std::vector<int> & seeds, int k);
double ILPBound(std::vector<int> & seeds, int k);
void selectNode(int v);
int getMaxDegree();
int getMaxDegreeNode();
int getSumK();
void cleanRemovedEdges();
void checkErrors(){
int tsize=0,dsize=0;
std::vector<int> ldegree(numNodes+1,0);
for (int i = 1; i < numNodes+1; ++i){
tsize += node_edge[i].size();
ldegree[i] = node_edge[i].size();
for (unsigned int j = 0; j < node_edge[i].size(); ++j){
if (markRemovedEdges[node_edge[i][j]]){
dsize++;
ldegree[i]--;
}
}
}
if (dsize != deletedSize){
cout << "Error deleted size: " << dsize << " " << deletedSize << endl;
exit(0);
}
if (tsize != totalSize){
cout << "Error total edge size: " << tsize << " " << totalSize << endl;
exit(0);
}
if (!sheap.checkDegree(ldegree)){
cout << "Error matching degree " << endl;
exit(0);
}
}
// bool calculateInfluence(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &) > sampler, std::vector<int> & seeds, int t, double deg, float epsilon, float delta, long long int numSuccessSamples, long long int numTotalSamples, int iter, double normalized);
// bool MSz(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &, std::vector<bool>&) > sampler, std::vector<int> & seeds, int t, double & deg, float epsilon, float delta, long long int & numSuccessSamples, long long int & numTotalSamples, double normalized, double c, double thresholdz, std::vector<bool> &cseedmark);
// void DTA(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &, std::vector<bool> &) > sampler, std::vector<int> & seeds, int t, float epsilon, float delta, double normalized);
// void SRA(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &, std::vector<bool> &) > sampler, std::vector<int> & seeds, int t, float epsilon, float delta, double normalized);
// long long addHyperedge(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &) > sampler, int t, long long num);
void buildSeedSet(std::vector<int> & seeds, int k, std::vector<double> °ree);
// void runMaxCover_SRA(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &) > sampler, double epsilon, double delta, int k, int t, double normalized, int zscale);
// bool runMaxCover_SSAz(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &) > sampler, double epsilon, double delta, int k, int t, double normalized, int zscale);
// void generateSamplesToBuffer(std::function< std::vector<int32_t>(int32_t &,int &, std::vector<bool> &) > sampler, int id);
};
#endif