FilesExpand file tree

 chivector-with-header

/

erdosrenyi.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

61 lines (46 loc) · 1.46 KB

 chivector-with-header

/

erdosrenyi.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

61 lines (46 loc) · 1.46 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Simple utility to generate Erdos-Renyi G(n, p) graphs.

* n = number of vertices, p = probability for each edge.

* This requires O(n^2) time, so not good idea to define very large n.

* Edge direction is randomized.

*/

#include <stdlib.h>

#include <cstdio>

#include <sys/time.h>

#include <time.h>

int main(int argc, const char ** argv) {

if (argc < 4) {

printf("Usage: erdosrenyi nameprefix n p\n");

return 1;

}

const char * nameprefix = argv[1];

int n = atoi(argv[2]);

double p = atof(argv[3]);

printf("Number of vertices=%d, edge probability=%lf\n", n, p);

char filename[1024];

sprintf(filename, "erdosrenyi_%s_%d_%.4f.edgelist", nameprefix, n, p);

timeval tt;

gettimeofday(&tt, NULL);

srandom(time(NULL) + (int)tt.tv_usec);

size_t K = 10000;

FILE * f = fopen(filename, "w");

size_t count = 0;

size_t accepted = 0;

size_t lim = (size_t) (p * K);

for(int i=0; i < n; i++) {

for(int j=i+1; j < n; j++) {

count++;

size_t r = random();

if (r % K < lim) {

accepted++;

if (rand() % 2 == 0) {

fprintf(f, "%d\t%d\n", i, j);

} else {

fprintf(f, "%d\t%d\n", j, i);

}

}

}

}

fclose(f);

printf("count: %lu, accepted: %lf\n", count, double(accepted)/double(count));

}