lemon-0.x: benchmark/min_cut_graphs.h@eb371753e814

     1 // -*- C++ -*-

     2 #include <lemon/random.h>

     5 template <typename UGraph, typename CapacityMap>

     6 void 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 }

    24 template <typename UGraph, typename CapacityMap>

    25 void 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 }

    40 template <typename UGraph, typename CapacityMap>

    41 void 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 }

    60 template <typename UGraph, typename CapacityMap>

    61 void 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 }

author	alpar
	Tue, 23 Jan 2007 12:51:39 +0000
changeset 2350	eb371753e814
child 2391	14a343be7a5a
permissions	-rw-r--r--