PandA-2024.02
generate.c
Go to the documentation of this file.
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <sys/types.h>
5 #include <sys/stat.h>
6 #include <fcntl.h>
7 #include <unistd.h>
8 #include <assert.h>
9 
10 // R-MAT parameters (*100)
11 #if 1
12 // Scale-free, small-world graph
13 #define A 57
14 #define B 19
15 #define C 19
16 #define D 5
17 #else
18 // Erdos-Renyi, uniform random graph
19 // For reference. Do not use.
20 #define A 25
21 #define B 25
22 #define C 25
23 #define D 25
24 #endif
25 
26 #include "bfs.h"
27 
28 int main(int argc, char **argv)
29 {
30  struct bench_args_t data;
31  int fd;
32  node_index_t adjmat[N_NODES][N_NODES]; // This is small enough to be fine.
33  node_index_t r,c,s,temp;
34  edge_index_t e;
35  int scale;
36  long int rint;
37  struct prng_rand_t state;
38 
39  // Generate dense R-MAT matrix
40  memset(adjmat, 0, N_NODES*N_NODES*sizeof(node_index_t));
41  prng_srand(1, &state);
42 
43  e = 0;
44  while( e<N_EDGES/2 ) { // generate N_EDGES/2 undirected edges (N_EDGES directed)
45  r = 0;
46  c = 0;
47  // Pick a random edge according to R-MAT parameters
48  for( scale=SCALE; scale>0; scale-- ) { // each level of the quadtree
49  rint = prng_rand(&state)%100;
50  if( rint>=(A+B) ) // C or D (bottom half)
51  r += 1<<(scale-1);
52  if( (rint>=A && rint<A+B) || (rint>=A+B+C) ) // B or D (right half)
53  c += 1<<(scale-1);
54  }
55  if( adjmat[r][c]==0 && r!=c ) { // ignore self-edges, they're irrelevant
56  // We make undirected edges
57  adjmat[r][c]=1;
58  adjmat[c][r]=1;
59  ++e;
60  }
61  }
62 
63  // Shuffle matrix (to eliminate degree locality)
64  for( s=0; s<N_NODES; s++ ) {
65  rint = prng_rand(&state)%N_NODES;
66  // Swap row s with row rint
67  for( r=0; r<N_NODES; r++ ) {
68  for( c=0; c<N_NODES; c++ ) {
69  temp = adjmat[r][c];
70  adjmat[r][c] = adjmat[rint][c];
71  adjmat[rint][c] = temp;
72  }
73  }
74  // Swap col s with col rint (to keep symmetry)
75  for( c=0; c<N_NODES; c++ ) {
76  for( r=0; r<N_NODES; r++ ) {
77  temp = adjmat[r][c];
78  adjmat[r][c] = adjmat[r][rint];
79  adjmat[r][rint] = temp;
80  }
81  }
82  }
83 
84  // Scan rows for edge list lengths, and fill edges while we're at it
85  e = 0;
86  for( r=0; r<N_NODES; r++ ) { // count first
87  data.nodes[r].edge_begin = 0;
88  data.nodes[r].edge_end = 0;
89  for( c=0; c<N_NODES; c++ ) {
90  if( adjmat[r][c] ) {
91  ++data.nodes[r].edge_end;
92  data.edges[e].dst = c;
93  //data.edges[e].weight = prng_rand(&state)%(MAX_WEIGHT-MIN_WEIGHT)+MIN_WEIGHT;
94  ++e;
95  }
96  }
97  }
98 
99  for( r=1; r<N_NODES; r++ ) { // now scan
100  data.nodes[r].edge_begin = data.nodes[r-1].edge_end;
101  data.nodes[r].edge_end += data.nodes[r-1].edge_end;
102  }
103 
104  // Pick starting node
105  do {
106  rint = prng_rand(&state)%N_NODES;
107  } while( (data.nodes[rint].edge_end-data.nodes[rint].edge_begin)<2 );
108  data.starting_node = rint;
109 
110  // Open and write
111  fd = open("input.data", O_WRONLY|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR|S_IRGRP|S_IWGRP|S_IROTH|S_IWOTH);
112  assert( fd>0 && "Couldn't open input data file" );
113  data_to_input(fd, &data);
114 
115  return 0;
116 }
static uint64_t prng_rand(struct prng_rand_t *state)
Definition: support.h:85
#define N_NODES
Definition: bfs.h:18
node_index_t starting_node
Definition: bfs.h:49
void data_to_input(int fd, void *vdata)
Definition: local_support.c:34
#define C
Definition: generate.c:15
uint_fast16_t c
Definition: support.h:79
uint64_t node_index_t
Definition: bfs.h:26
node_index_t dst
Definition: bfs.h:32
#define A
Definition: generate.c:13
edge_t edges[N_EDGES]
Definition: bfs.h:48
node_t nodes[N_NODES]
Definition: bfs.h:47
edge_index_t edge_begin
Definition: bfs.h:36
uint64_t edge_index_t
Definition: bfs.h:25
int main(int argc, char **argv)
Definition: generate.c:12
double c[TESTS_COUNT]
Definition: add.h:16
static void prng_srand(uint64_t seed, struct prng_rand_t *state)
Definition: support.h:106
#define B
Definition: generate.c:14
#define N_EDGES
Definition: bfs.h:19
#define SCALE
Definition: cordic.h:53
edge_index_t edge_end
Definition: bfs.h:37

Generated on Mon Feb 12 2024 13:02:49 for PandA-2024.02 by doxygen 1.8.13