Aufgrund einer Wartung wird GitLab am 18.01. zwischen 8:00 und 9:00 Uhr kurzzeitig nicht zur Verfügung stehen. / Due to maintenance, GitLab will be temporarily unavailable on 18.01. between 8:00 and 9:00 am.

random_graph_generator.cpp 15.4 KB
Newer Older
Jonas Seidel's avatar
Jonas Seidel committed
1
2
3
4
5
6
#include "random_graph_generator.h"

random_graph_generator::random_graph_generator(
  size_t number_of_edges, size_t number_of_nodes,
  random_attribute_generator edge_generator,
  random_attribute_generator node_generator,
7
8
  std::unordered_map<std::string, Attribute> default_values_edge_attributes,
  std::unordered_map<std::string, Attribute> default_values_node_attributes
Jonas Seidel's avatar
Jonas Seidel committed
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
)
  : _template_node_attributes(default_values_node_attributes), _template_edge_attributes(default_values_edge_attributes), _number_of_nodes(number_of_nodes), _number_of_edges(number_of_edges), _node_generator(node_generator), _edge_generator(edge_generator) {}

Graph random_graph_generator::next_acyclic(){
  Graph g (this->_template_edge_attributes, this->_template_node_attributes);
  while(!random_graph_generator::grow_random_acyclic(g, this->_number_of_nodes, this->_number_of_edges, this->_edge_generator, this->_node_generator).first){
    std::cout << "generation failed; retrying!" << std::endl;
  }
  return g;
}

Graph random_graph_generator::next(){
  Graph g (this->_template_edge_attributes, this->_template_node_attributes);
  while(!random_graph_generator::grow_random(g, this->_number_of_nodes, this->_number_of_edges, this->_edge_generator, this->_node_generator).first){
    std::cout << "generation failed; retrying!" << std::endl;
  }
  return g;
}

28
std::tuple<std::pair<Node*, Node*>, std::unordered_set<Edge*>, Graph> random_graph_generator::next_acyclic_2_tips(){
Jonas Seidel's avatar
Jonas Seidel committed
29
30
31
32
  Graph g (this->_template_edge_attributes, this->_template_node_attributes);
  while(!random_graph_generator::grow_random_acyclic(g, this->_number_of_nodes, this->_number_of_edges, this->_edge_generator, this->_node_generator).first){
    std::cout << "generation failed; retrying!" << std::endl;
  }
33
  std::unordered_set<Edge*> core_network = g.export_edges();
34

35
36
37
38
39
  auto [source, target] = g.tip_fringes(this->_edge_generator, this->_node_generator);

  source->add_attribute("Source", Attribute({fix, 1, Integral}) );
  target->add_attribute("Target", Attribute({fix, 1, Integral}) );

40
  return {std::pair{source, target}, std::move(core_network), std::move(g)};
Jonas Seidel's avatar
Jonas Seidel committed
41
42
}

43
std::tuple<std::pair<Node*, Node*>, std::unordered_set<Edge*>, Graph> random_graph_generator::next_acyclic_in_steps_2_tips(size_t steps, size_t fuzzing, bool only_tip_fringes, bool only_tip_extreme_layer, bool shelter_orphans, random_attribute_generator* connector_generator, random_attribute_generator* terminal_generator){
44
  Graph g (this->_template_edge_attributes, this->_template_node_attributes);
45

46
47
48
49
50
51
52
53
54
55
  auto graph_generation_data = random_graph_generator::grow_random_acyclic_in_steps(
    g,
    this->_number_of_nodes/steps,
    this->_number_of_edges/steps,
    steps,
    0, // fuzzing start
    fuzzing,
    this->_edge_generator,
    this->_node_generator
  );
56

57
  std::unordered_set<Edge*> core_network = g.export_edges();
58
59
60

  if(connector_generator == nullptr) connector_generator = &this->_edge_generator;
  if(terminal_generator == nullptr) terminal_generator = &this->_node_generator;
61

62
63
64
65
66
67
68
69
  Node* source;
  Node* target;
  if(only_tip_fringes){
    // connect those nodes to start that have no incoming edges / connect those nodes to target that have no outgoing edges

    if(only_tip_extreme_layer){
      // tips first and last layer

70
      auto [source_, target_] = g.tip_fringes(std::get<0>(graph_generation_data).front(), std::get<0>(graph_generation_data).back(), *connector_generator, *terminal_generator, shelter_orphans);
71
72
73
74
75
76
77
78
79
80
81
82
83
84
      source = source_;
      target = target_;
    }else{
      // tips all fringes

      auto [source_, target_] = g.tip_fringes(*connector_generator, *terminal_generator, shelter_orphans);
      source = source_;
      target = target_;
    }
  }else{
    // tips nodes regardless of if they have incoming or outgoing edges
    assert(only_tip_extreme_layer);
    // only those nodes of the first and last generated layers (tipping just everything doesn't make sense)

85
86
    Node* s = g.add_node(std::to_string(g.size().nodes), terminal_generator->next());
    for(Node* n : std::get<0>(graph_generation_data).front()){
87
88
89
90
91
      if(!shelter_orphans && n->incident().size() == 0) continue;
      std::stringstream name;
      name << s->description() << "_" << n->description();
      g.add_edge(s, n, name.str(), connector_generator->next());
    }
92
93
    Node* t = g.add_node(std::to_string(g.size().nodes), terminal_generator->next());
    for(Node* n : std::get<0>(graph_generation_data).back()){
94
95
96
97
98
99
100
101
102
      if(!shelter_orphans && n->incident().size() == 0) continue;
      std::stringstream name;
      name << n->description() << "_" << t->description();
      g.add_edge(n, t, name.str(), connector_generator->next());
    }

    source = s;
    target = t;
  }
103
104
105
106

  source->add_attribute("Source", Attribute({fix, 1, Integral}) );
  target->add_attribute("Target", Attribute({fix, 1, Integral}) );

107
  return {std::pair{source, target}, std::move(core_network), std::move(g)};
108
109
110
}


Jonas Seidel's avatar
Jonas Seidel committed
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
std::pair<bool, Attribute> random_graph_generator::node_template(const std::string& attr) const{
  auto search = this->_template_node_attributes.find(attr);
  if(search == this->_template_node_attributes.end()){
    return {false, {fix, 0}};
  }
  return {true, search->second};
}

std::pair<bool, Attribute> random_graph_generator::edge_template(const std::string& attr) const {
  auto search = this->_template_edge_attributes.find(attr);
  if(search == this->_template_edge_attributes.end()){
    return {false, {fix, 0}};
  }
  return {true, search->second};
}

Attribute random_graph_generator::edge_template_throwing(const std::string& attr){
  auto search = this->_template_edge_attributes.find(attr);
  if(search == this->_template_edge_attributes.end()){
    std::stringstream text;
    text << "\"" << attr << "\" is not defined by default for Edges generated by this Generator";
    throw std::range_error(text.str());
  }
  return search->second;
}

Attribute random_graph_generator::node_template_throwing(const std::string& attr){
  auto search = this->_template_node_attributes.find(attr);
  if(search == this->_template_node_attributes.end()){
    std::stringstream text;
    text << "\"" << attr << "\" is not defined by default for Nodes generated by this Generator";
    throw std::range_error(text.str());
  }
  return search->second;
}

147
148
149
150
151
152
153
154
155
random_attribute_generator& random_graph_generator::edge_generator(){
  return this->_edge_generator;
}

random_attribute_generator& random_graph_generator::node_generator(){
  return this->_node_generator;
}


156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
std::unordered_set<Edge*> random_graph_generator::connect_random(
  SubGraph& graph_superunion,
  SubGraph& subgraph_from,
  SubGraph& subgraph_to,
  random_attribute_generator& edge_attribute_generator,
  bool at_least_strongly_connected,
  bool at_least_weakly_connected,
  bool acyclic,
  bool simple,
  bool anti_reflexive,
  size_t at_least_number_of_edges
) {
  if(at_least_strongly_connected && acyclic) throw std::logic_error("can't generate strongly connected acyclic graph");

  std::unordered_set<Edge*> added_edges;
  added_edges.reserve(at_least_number_of_edges);
  random_set_element_generator<Node*> rand_stream_from(subgraph_from.export_nodes(), random_all_static);
  random_set_element_generator<Node*> rand_stream_to(subgraph_to.export_nodes(), random_all_static);

  /**
    We opt for brute force because resticting the generation to only edges that conform to generation parameters while also keeping the distribution uniform is connected with considerable overhead.

    DO NOT ATTEMPT TO GENERATE (close to) FULL GRAPHS OF ANY SIGNIFICANT SIZE WITH THIS!!!
  */

  Node* from;
  Node* to;
  bool warned = false;
  while(
      (added_edges.size() < at_least_number_of_edges)
      || (at_least_strongly_connected && !graph_superunion.is_strongly_connected())
      || (at_least_weakly_connected && !graph_superunion.is_weakly_connected())
    ) {
    size_t attempt = 0;
    redo:
    {
      size_t problem_size_coeff = subgraph_from.size().nodes + subgraph_to.size().nodes;
      if(attempt > problem_size_coeff && !warned){
        warned = true;
        std::cerr << "bad performance when generating graph" << std::endl;
      }
      if(attempt > problem_size_coeff*problem_size_coeff*problem_size_coeff){
        std::cerr << "giving up on graph generation" << std::endl;
        goto failed;
      };
    }

    try{
      rand_stream_from >> from;
      rand_stream_to >> to;
    }catch (std::range_error& e){
      goto failed;
    }

    if(
      ( (simple && ((from == to) || (graph_superunion.directed_admissible_st_path(from, to).number_of_edges()) == 1)) )
      || (anti_reflexive && (from == to))
      || (acyclic && graph_superunion.directed_admissible_st_path(to, from).exists())
    ) {
      attempt++;
      goto redo;
    }

    std::stringstream name;
    name << from->description() << "_" << to->description();
    added_edges.insert(graph_superunion.add_edge(from, to, name.str(), edge_attribute_generator.next()));
  }
  return added_edges;

  failed:
  /*
    cleanup: restore state; due to failure: remove the already added components
  */
  for(Edge* e : added_edges){
    graph_superunion.remove_edge(e);
  }

  throw excessive_graph_generation_runtime();
  assert(false);
  return {};
}

std::pair<bool, std::pair<std::unordered_set<Node*>, std::unordered_set<Edge*>>> random_graph_generator::grow_random(Graph& g, size_t number_of_nodes, size_t number_of_edges, random_attribute_generator& edge_attribute_generator, random_attribute_generator& node_attribute_generator){
  std::unordered_set<Node*> added_nodes;
  std::unordered_set<Edge*> added_edges;
Jonas Seidel's avatar
Jonas Seidel committed
241
242
243
244
245
  added_nodes.reserve(number_of_nodes);
  added_edges.reserve(number_of_edges);

  for(size_t i = 0; i < number_of_nodes; ++i){
    std::stringstream name;
246
247
    name << g.size().nodes;
    added_nodes.insert(g.add_node(name.str(), node_attribute_generator.next()));
Jonas Seidel's avatar
Jonas Seidel committed
248
  }
249
  random_set_element_generator<Node*> rand_stream (&g.nodes(), random_all_dynamic);
Jonas Seidel's avatar
Jonas Seidel committed
250
251
252
253
254
255

  Node* n1;
  Node* n2;
  for(size_t i = 0; i < number_of_edges; ++i){
    size_t attempt = 0;
    redo:
256
    if(attempt > g.size().nodes*g.size().nodes*g.size().nodes){
Jonas Seidel's avatar
Jonas Seidel committed
257
258
259
260
261
262
263
264
265
266
267
      goto failed;
    };

    try{
      rand_stream >> n1;
      rand_stream >> n2;
    }catch (std::range_error& e){
      goto failed;
    }

    {
268
269
270
      Path path = g.directed_admissible_st_path(n1, n2);
      //                  unique paths?
      if(path.exists() && path.number_of_edges() <= 1) {
Jonas Seidel's avatar
Jonas Seidel committed
271
272
273
274
275
276
277
        attempt++;
        goto redo;
      }
    }

    std::stringstream name;
    name << n1->description() << "_" << n2->description();
278
    added_edges.insert(g.add_edge(n1, n2, name.str(), edge_attribute_generator.next()));
Jonas Seidel's avatar
Jonas Seidel committed
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
  }
  return {true,{added_nodes, added_edges}};

  failed:
  /*
    cleanup: restore state; due to failure: remove the already added components
  */
  for(Edge* e : added_edges){
    g.remove_edge(e);
  }
  for(Node* n : added_nodes){
    g.remove_node(n);
  }
  return {false,{{},{}}};
}

//TODO: add generate_random_edge and random node to node, edge and use additional parameters to generate random attributes for edges, nodes
296
297
298
std::pair<bool, std::pair<std::unordered_set<Node*>, std::unordered_set<Edge*>>> random_graph_generator::grow_random_acyclic(Graph& g, size_t number_of_nodes, size_t number_of_edges, random_attribute_generator& edge_attribute_generator, random_attribute_generator& node_attribute_generator){
  std::unordered_set<Node*> added_nodes;
  std::unordered_set<Edge*> added_edges;
Jonas Seidel's avatar
Jonas Seidel committed
299
300
301
302
303
  added_nodes.reserve(number_of_nodes);
  added_edges.reserve(number_of_edges);

  for(size_t i = 0; i < number_of_nodes; ++i){
    std::stringstream name;
304
305
    name << g.size().nodes;
    added_nodes.insert(g.add_node(name.str(), node_attribute_generator.next()));
Jonas Seidel's avatar
Jonas Seidel committed
306
  }
307
308

  random_set_element_generator<Node*> rand_stream (&g.nodes(), random_all_dynamic);
Jonas Seidel's avatar
Jonas Seidel committed
309
310
311
312
313
314

  Node* n1;
  Node* n2;
  for(size_t i = 0; i < number_of_edges; ++i){
    size_t attempt = 0;
    redo:
315
    if(attempt > g.size().nodes*g.size().nodes*g.size().nodes){
Jonas Seidel's avatar
Jonas Seidel committed
316
317
318
319
320
321
322
323
324
325
      goto failed;
    };

    try{
      rand_stream >> n1;
      rand_stream >> n2;
    }catch (std::range_error& e){
      goto failed;
    }

326
    if(n1 == n2 || g.directed_admissible_st_path(n2, n1).exists() || g.directed_admissible_st_path(n1, n2).number_of_edges() == 1) {
Jonas Seidel's avatar
Jonas Seidel committed
327
328
329
330
331
332
      attempt++;
      goto redo;
    }

    std::stringstream name;
    name << n1->description() << "_" << n2->description();
333
    added_edges.insert(g.add_edge(n1, n2, name.str(), edge_attribute_generator.next()));
Jonas Seidel's avatar
Jonas Seidel committed
334
335
336
  }
  return {true,{added_nodes, added_edges}};

337
338
339
340
341
342
343
344
345
346
347
348
349
350
  failed:
  /*
    cleanup: restore state; due to failure: remove the already added components
  */
  for(Edge* e : added_edges){
    g.remove_edge(e);
  }
  for(Node* n : added_nodes){
    g.remove_node(n);
  }
  return {false,{{},{}}};
}

//TODO: add generate_random_edge and random node to node, edge and use additional parameters to generate random attributes for edges, nodes
351
352
std::tuple<std::vector<std::unordered_set<Node*>>, std::unordered_set<Node*>, std::unordered_set<Edge*>> random_graph_generator::grow_random_acyclic_in_steps(Graph& g, size_t number_of_nodes_per_step, size_t number_of_nodes_between_node_step_pairs, size_t number_of_steps, size_t fuzzing_distance_from, size_t fuzzing_distance_to, random_attribute_generator& edge_attribute_generator, random_attribute_generator& node_attribute_generator){
  if( fuzzing_distance_from > fuzzing_distance_to ) throw std::invalid_argument("fuzzing_distance_from needs to be \"<= fuzzing_distance_to\"");
353

354
355
356
  std::unordered_set<Node*> added_nodes;
  std::unordered_set<Edge*> added_edges;
  added_nodes.reserve(number_of_nodes_per_step*number_of_steps);
357

358
359
  std::vector<std::unordered_set<Node*>> node_steps;
  node_steps.reserve(number_of_steps);
360

361
362
363
364
365
  bool at_least_strongly_connected = false;
  bool at_least_weakly_connected = false;
  bool acyclic = true;
  bool simple = true;
  bool anti_reflexive = true;
366
367

  for(int curr_step = 0; curr_step < number_of_steps; ++curr_step){
368
369
    node_steps.push_back(std::unordered_set<Node*>());
    node_steps[curr_step].reserve(number_of_nodes_per_step);
370
371
372

    for(size_t i = 0; i < number_of_nodes_per_step; ++i){
      std::stringstream name;
373
      name << g.size().nodes;
374
      Node* new_node = g.add_node(name.str(), node_attribute_generator.next());
375
376
      added_nodes.insert(new_node);
      node_steps[curr_step].insert(new_node);
377
378
379
    }
  }

380
381
382
383
384
385
386
387
388
  SubGraph subgraph_superunion(g);
  for(size_t step_from = 0; step_from < number_of_steps; ++step_from){
    for(size_t step_to = step_from+fuzzing_distance_from; (step_to <= step_from+fuzzing_distance_to) && (step_to < number_of_steps); ++step_to){
      SubGraph subgraph_from (subgraph_superunion, node_steps[step_from]);
      SubGraph* subgraph_to;
      if(step_from == step_to){
        subgraph_to = new SubGraph(subgraph_from, node_steps[step_to]);
      }else{
        subgraph_to = new SubGraph(subgraph_superunion, node_steps[step_to]);
389
390
      }

391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
      try{
        auto last_added_edges = random_graph_generator::connect_random(
          subgraph_superunion,
          subgraph_from,
          *subgraph_to,
          edge_attribute_generator,
          at_least_strongly_connected,
          at_least_weakly_connected,
          acyclic,
          simple,
          anti_reflexive,
          number_of_nodes_between_node_step_pairs
        );
        added_edges.insert(last_added_edges.begin(), last_added_edges.end());
      }catch(excessive_graph_generation_runtime& except){
        for(Edge* e : added_edges){
          g.remove_edge(e);
        }
        for(Node* n : added_nodes){
          g.remove_node(n);
        }
        throw except;
413
414
      }

415
      delete subgraph_to;
416
417
418
    }
  }

419
  return {node_steps, added_nodes, added_edges};
Jonas Seidel's avatar
Jonas Seidel committed
420
}