deba@2341: // -*- C++ -*-
deba@2341: #include <lemon/random.h>
deba@2341: 
deba@2341: 
deba@2341: template <typename UGraph, typename CapacityMap>
deba@2341: void genNoiUGraph(UGraph& g, CapacityMap& c, 
deba@2341:                   int n, int d, int k, int p) {
deba@2341:   std::vector<typename UGraph::Node> nodes(n);
deba@2341:   for (int i = 0; i < n; ++i) {
deba@2341:     nodes[i] = g.addNode();
deba@2341:   }
deba@2341:   typename UGraph::template NodeMap<int> comp(g);
deba@2341:   for (int i = 0; i < n; ++i) {
deba@2341:     comp[nodes[i]] = rnd[k];
deba@2341:   }
deba@2341:   int m = (n * (n - 1) * d) / 200;
deba@2341:   for (int i = 0; i < m; ++i) {
deba@2341:     int s = rnd[n], t = rnd[n];
deba@2341:     c[g.addEdge(nodes[s], nodes[t])] =
deba@2341:       rnd[(comp[nodes[s]] == comp[nodes[t]] ? p : 1) * 100]; 
deba@2341:   }
deba@2341: }
deba@2341: 
deba@2341: template <typename UGraph, typename CapacityMap>
deba@2341: void genBikeWheelUGraph(UGraph& g, CapacityMap& c, int n) {
deba@2341:   std::vector<typename UGraph::Node> nodes(n);
deba@2341:   for (int i = 0; i < n; ++i) {
deba@2341:     nodes[i] = g.addNode();
deba@2341:   }
deba@2341:   for (int i = 0; i < n - 2; ++i) {
deba@2341:     c[g.addEdge(nodes[i], nodes[n - 1 - (i % 2)])] = 2;
deba@2341:   }
deba@2341:   for (int i = 1; i < n - 2; ++i) {
deba@2341:     c[g.addEdge(nodes[i - 1], nodes[i])] = n - 1;
deba@2341:   }
deba@2341:   c[g.addEdge(nodes[n - 3], nodes[0])] = n - 1;
deba@2341:   c[g.addEdge(nodes[n - 2], nodes[n - 1])] = 2;
deba@2341: }
deba@2341: 
deba@2341: template <typename UGraph, typename CapacityMap>
deba@2341: void genRegUGraph(UGraph& g, CapacityMap& c, int n, int d) {
deba@2341:   std::vector<typename UGraph::Node> nodes(n);
deba@2341:   for (int i = 0; i < n; ++i) {
deba@2341:     nodes[i] = g.addNode();
deba@2341:   }
deba@2341:   for (int k = 0; k < d; ++k) {
deba@2341:     for (int i = 0; i < n; ++i) {
deba@2341:       int r = rnd[n];
deba@2341:       typename UGraph::Node t = nodes[r];
deba@2341:       nodes[r] = nodes[i];
deba@2341:       nodes[i] = t;
deba@2341:     }
deba@2341:     for (int i = 1; i < n; ++i) {
deba@2341:       c[g.addEdge(nodes[i - 1], nodes[i])] = 1;
deba@2341:     }
deba@2341:     c[g.addEdge(nodes[n - 1], nodes[0])] = 1;
deba@2341:   }
deba@2341: }
deba@2341: 
deba@2341: template <typename UGraph, typename CapacityMap>
deba@2341: void genCdgUGraph(UGraph& g, CapacityMap& c, int n, int d) {
deba@2341:   std::vector<typename UGraph::Node> nodes(n);
deba@2341:   for (int i = 0; i < n; ++i) {
deba@2341:     nodes[i] = g.addNode();
deba@2341:   }
deba@2341:   std::vector<typename UGraph::Node> mix(n * d);
deba@2341:   for (int i = 0; i < n; ++i) {
deba@2341:     for (int j = 0; j < d; ++j) {
deba@2341:       mix[i * d + j] = nodes[i];
deba@2341:     }
deba@2341:   }
deba@2341:   while (mix.size() >= 2) {
deba@2341:     int r;
deba@2341:     r = rnd[mix.size()];
deba@2341:     typename UGraph::Node s = mix[r];
deba@2341:     mix[r] = mix.back(); mix.pop_back();
deba@2341:     r = rnd[mix.size()];
deba@2341:     typename UGraph::Node t = mix[r];
deba@2341:     mix[r] = mix.back(); mix.pop_back();
deba@2341:     c[g.addEdge(s, t)] = 1;
deba@2341:   }
deba@2341: }