COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/min_cut_graphs.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 2.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <lemon/random.h>
20
21
22template <typename UGraph, typename CapacityMap>
23void genNoiUGraph(UGraph& g, CapacityMap& c,
24                  int n, int d, int k, int p) {
25  std::vector<typename UGraph::Node> nodes(n);
26  for (int i = 0; i < n; ++i) {
27    nodes[i] = g.addNode();
28  }
29  typename UGraph::template NodeMap<int> comp(g);
30  for (int i = 0; i < n; ++i) {
31    comp[nodes[i]] = rnd[k];
32  }
33  int m = (n * (n - 1) * d) / 200;
34  for (int i = 0; i < m; ++i) {
35    int s = rnd[n], t = rnd[n];
36    c[g.addEdge(nodes[s], nodes[t])] =
37      rnd[(comp[nodes[s]] == comp[nodes[t]] ? p : 1) * 100];
38  }
39}
40
41template <typename UGraph, typename CapacityMap>
42void genBikeWheelUGraph(UGraph& g, CapacityMap& c, int n) {
43  std::vector<typename UGraph::Node> nodes(n);
44  for (int i = 0; i < n; ++i) {
45    nodes[i] = g.addNode();
46  }
47  for (int i = 0; i < n - 2; ++i) {
48    c[g.addEdge(nodes[i], nodes[n - 1 - (i % 2)])] = 2;
49  }
50  for (int i = 1; i < n - 2; ++i) {
51    c[g.addEdge(nodes[i - 1], nodes[i])] = n - 1;
52  }
53  c[g.addEdge(nodes[n - 3], nodes[0])] = n - 1;
54  c[g.addEdge(nodes[n - 2], nodes[n - 1])] = 2;
55}
56
57template <typename UGraph, typename CapacityMap>
58void genRegUGraph(UGraph& g, CapacityMap& c, int n, int d) {
59  std::vector<typename UGraph::Node> nodes(n);
60  for (int i = 0; i < n; ++i) {
61    nodes[i] = g.addNode();
62  }
63  for (int k = 0; k < d; ++k) {
64    for (int i = 0; i < n; ++i) {
65      int r = rnd[n];
66      typename UGraph::Node t = nodes[r];
67      nodes[r] = nodes[i];
68      nodes[i] = t;
69    }
70    for (int i = 1; i < n; ++i) {
71      c[g.addEdge(nodes[i - 1], nodes[i])] = 1;
72    }
73    c[g.addEdge(nodes[n - 1], nodes[0])] = 1;
74  }
75}
76
77template <typename UGraph, typename CapacityMap>
78void genCdgUGraph(UGraph& g, CapacityMap& c, int n, int d) {
79  std::vector<typename UGraph::Node> nodes(n);
80  for (int i = 0; i < n; ++i) {
81    nodes[i] = g.addNode();
82  }
83  std::vector<typename UGraph::Node> mix(n * d);
84  for (int i = 0; i < n; ++i) {
85    for (int j = 0; j < d; ++j) {
86      mix[i * d + j] = nodes[i];
87    }
88  }
89  while (mix.size() >= 2) {
90    int r;
91    r = rnd[mix.size()];
92    typename UGraph::Node s = mix[r];
93    mix[r] = mix.back(); mix.pop_back();
94    r = rnd[mix.size()];
95    typename UGraph::Node t = mix[r];
96    mix[r] = mix.back(); mix.pop_back();
97    c[g.addEdge(s, t)] = 1;
98  }
99}
Note: See TracBrowser for help on using the repository browser.