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

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

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2007

     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  */

    19 #include <lemon/random.h>

    22 template <typename UGraph, typename CapacityMap>

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

    41 template <typename UGraph, typename CapacityMap>

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

    57 template <typename UGraph, typename CapacityMap>

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

    77 template <typename UGraph, typename CapacityMap>

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

author	ladanyi
	Sat, 13 Oct 2007 08:48:07 +0000
changeset 2495	e4f8367beb41
parent 2341	46a6311ceffa
child 2553	bfced05fa852
permissions	-rw-r--r--