COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/min_cut_graphs.h @ 2341:46a6311ceffa

Last change on this file since 2341:46a6311ceffa was 2341:46a6311ceffa, checked in by Balazs Dezso, 13 years ago

Undirected minimum cut benchmarking

File size: 2.3 KB
Line 
1// -*- C++ -*-
2#include <lemon/random.h>
3
4
5template <typename UGraph, typename CapacityMap>
6void genNoiUGraph(UGraph& g, CapacityMap& c,
7                  int n, int d, int k, int p) {
8  std::vector<typename UGraph::Node> nodes(n);
9  for (int i = 0; i < n; ++i) {
10    nodes[i] = g.addNode();
11  }
12  typename UGraph::template NodeMap<int> comp(g);
13  for (int i = 0; i < n; ++i) {
14    comp[nodes[i]] = rnd[k];
15  }
16  int m = (n * (n - 1) * d) / 200;
17  for (int i = 0; i < m; ++i) {
18    int s = rnd[n], t = rnd[n];
19    c[g.addEdge(nodes[s], nodes[t])] =
20      rnd[(comp[nodes[s]] == comp[nodes[t]] ? p : 1) * 100];
21  }
22}
23
24template <typename UGraph, typename CapacityMap>
25void genBikeWheelUGraph(UGraph& g, CapacityMap& c, int n) {
26  std::vector<typename UGraph::Node> nodes(n);
27  for (int i = 0; i < n; ++i) {
28    nodes[i] = g.addNode();
29  }
30  for (int i = 0; i < n - 2; ++i) {
31    c[g.addEdge(nodes[i], nodes[n - 1 - (i % 2)])] = 2;
32  }
33  for (int i = 1; i < n - 2; ++i) {
34    c[g.addEdge(nodes[i - 1], nodes[i])] = n - 1;
35  }
36  c[g.addEdge(nodes[n - 3], nodes[0])] = n - 1;
37  c[g.addEdge(nodes[n - 2], nodes[n - 1])] = 2;
38}
39
40template <typename UGraph, typename CapacityMap>
41void genRegUGraph(UGraph& g, CapacityMap& c, int n, int d) {
42  std::vector<typename UGraph::Node> nodes(n);
43  for (int i = 0; i < n; ++i) {
44    nodes[i] = g.addNode();
45  }
46  for (int k = 0; k < d; ++k) {
47    for (int i = 0; i < n; ++i) {
48      int r = rnd[n];
49      typename UGraph::Node t = nodes[r];
50      nodes[r] = nodes[i];
51      nodes[i] = t;
52    }
53    for (int i = 1; i < n; ++i) {
54      c[g.addEdge(nodes[i - 1], nodes[i])] = 1;
55    }
56    c[g.addEdge(nodes[n - 1], nodes[0])] = 1;
57  }
58}
59
60template <typename UGraph, typename CapacityMap>
61void genCdgUGraph(UGraph& g, CapacityMap& c, int n, int d) {
62  std::vector<typename UGraph::Node> nodes(n);
63  for (int i = 0; i < n; ++i) {
64    nodes[i] = g.addNode();
65  }
66  std::vector<typename UGraph::Node> mix(n * d);
67  for (int i = 0; i < n; ++i) {
68    for (int j = 0; j < d; ++j) {
69      mix[i * d + j] = nodes[i];
70    }
71  }
72  while (mix.size() >= 2) {
73    int r;
74    r = rnd[mix.size()];
75    typename UGraph::Node s = mix[r];
76    mix[r] = mix.back(); mix.pop_back();
77    r = rnd[mix.size()];
78    typename UGraph::Node t = mix[r];
79    mix[r] = mix.back(); mix.pop_back();
80    c[g.addEdge(s, t)] = 1;
81  }
82}
Note: See TracBrowser for help on using the repository browser.