source: lemon-0.x/benchmark/min_cut_graphs.h @ 2592:f1fb0c31f952

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/random.h>


template <typename UGraph, typename CapacityMap>
void genNoiUGraph(UGraph& g, CapacityMap& c, 
                  int n, int d, int k, int p) {
  std::vector<typename UGraph::Node> nodes(n);
  for (int i = 0; i < n; ++i) {
    nodes[i] = g.addNode();
  }
  typename UGraph::template NodeMap<int> comp(g);
  for (int i = 0; i < n; ++i) {
    comp[nodes[i]] = rnd[k];
  }
  int m = (n * (n - 1) * d) / 200;
  for (int i = 0; i < m; ++i) {
    int s = rnd[n], t = rnd[n];
    c[g.addEdge(nodes[s], nodes[t])] =
      rnd[(comp[nodes[s]] == comp[nodes[t]] ? p : 1) * 100]; 
  }
}

template <typename UGraph, typename CapacityMap>
void genBikeWheelUGraph(UGraph& g, CapacityMap& c, int n) {
  std::vector<typename UGraph::Node> nodes(n);
  for (int i = 0; i < n; ++i) {
    nodes[i] = g.addNode();
  }
  for (int i = 0; i < n - 2; ++i) {
    c[g.addEdge(nodes[i], nodes[n - 1 - (i % 2)])] = 2;
  }
  for (int i = 1; i < n - 2; ++i) {
    c[g.addEdge(nodes[i - 1], nodes[i])] = n - 1;
  }
  c[g.addEdge(nodes[n - 3], nodes[0])] = n - 1;
  c[g.addEdge(nodes[n - 2], nodes[n - 1])] = 2;
}

template <typename UGraph, typename CapacityMap>
void genRegUGraph(UGraph& g, CapacityMap& c, int n, int d) {
  std::vector<typename UGraph::Node> nodes(n);
  for (int i = 0; i < n; ++i) {
    nodes[i] = g.addNode();
  }
  for (int k = 0; k < d; ++k) {
    for (int i = 0; i < n; ++i) {
      int r = rnd[n];
      typename UGraph::Node t = nodes[r];
      nodes[r] = nodes[i];
      nodes[i] = t;
    }
    for (int i = 1; i < n; ++i) {
      c[g.addEdge(nodes[i - 1], nodes[i])] = 1;
    }
    c[g.addEdge(nodes[n - 1], nodes[0])] = 1;
  }
}

template <typename UGraph, typename CapacityMap>
void genCdgUGraph(UGraph& g, CapacityMap& c, int n, int d) {
  std::vector<typename UGraph::Node> nodes(n);
  for (int i = 0; i < n; ++i) {
    nodes[i] = g.addNode();
  }
  std::vector<typename UGraph::Node> mix(n * d);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < d; ++j) {
      mix[i * d + j] = nodes[i];
    }
  }
  while (mix.size() >= 2) {
    int r;
    r = rnd[mix.size()];
    typename UGraph::Node s = mix[r];
    mix[r] = mix.back(); mix.pop_back();
    r = rnd[mix.size()];
    typename UGraph::Node t = mix[r];
    mix[r] = mix.back(); mix.pop_back();
    c[g.addEdge(s, t)] = 1;
  }
}