-
Notifications
You must be signed in to change notification settings - Fork 3
/
Calc_Inf_IC.cpp
122 lines (106 loc) · 2.26 KB
/
Calc_Inf_IC.cpp
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
#include <cstdio>
#include <queue>
#include <cstring>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <cmath>
//#include <windows.h>
using namespace std;
#define NODE 100000
#define EDGE 1000000
#define MAXK 60
#define T 10000
FILE* fp;
FILE* fs;
struct edge
{
int v, next;
};
edge E[EDGE];
int firstedge[NODE] = {0},
deg[NODE] = {0},
degin[NODE] = {0},
seed[MAXK] = {0};
bool visit[NODE] = {0};
int n, m,
TOPK = 20,
DIR = 0;
float delta[NODE] = {0};
int Simulate(int topk)
{
queue <int> Q;
int x,y,i,
tot = 0;
float prob;
memset(visit,0,sizeof(visit));
for (i = 0; i < topk; i++){
Q.push(seed[i]);
visit[seed[i]] = 1;
tot++;
}
while (!Q.empty()){
x = Q.front();
Q.pop();
for (i = firstedge[x]; i != 0; i = E[i].next){
y = E[i].v;
prob = (float)rand()/RAND_MAX;
if (prob < (float)1/degin[y] && !visit[y]){
Q.push(y);
visit[y] = 1;
tot++;
}
}
}
return tot;
}
int main(int argc, char* argv[])
{
int x, y,
tot = 0;
float z,
totnum = 0;
fp = fopen(argv[1], "r");
fs = fopen(argv[2], "r");
srand(time(NULL));
if (argc >= 4){
TOPK = atoi(argv[3]);
}
if (argc >= 5 && argv[4][0] == 'D'){
DIR = 1;
}
time_t start,end;
start = clock();
fscanf(fp, "%d %d", &n, &m);
for (int i = 0; i < m; i++){
fscanf(fp, "%d %d", &x, &y);
tot++;
E[tot].v = y;
E[tot].next = firstedge[x];
firstedge[x] = tot;
deg[x]++;
degin[y]++;
if (DIR == 0){
tot++;
E[tot].v = x;
E[tot].next = firstedge[y];
firstedge[y] = tot;
deg[y]++;
degin[x]++;
}
}
fclose(fp);
for (int i = 0; i < TOPK; i++){
fscanf(fs, "%d %f", &x, &z);
seed[i] = x;
}
fclose(fs);
for (int i = 1; i <= T; i++){
totnum += Simulate(TOPK);
//cout<<totnum<<endl;
}
printf("Expected Influence: %d\n", (int)totnum/T);
end = clock();
printf("%lfs\n", double(end-start)/CLOCKS_PER_SEC);
return 0;
}