// -*- C++ -*-

#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;

  }

}