test/max_clique_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 21:56:21 +0200
changeset 1098 cf6084618b1b
parent 918 8583fb74238c
permissions -rw-r--r--
Merge headmerge to the default branch
kpeter@904
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@904
     2
 *
kpeter@904
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@904
     4
 *
alpar@1092
     5
 * Copyright (C) 2003-2013
kpeter@904
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@904
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@904
     8
 *
kpeter@904
     9
 * Permission to use, modify and distribute this software is granted
kpeter@904
    10
 * provided that this copyright notice appears in all copies. For
kpeter@904
    11
 * precise terms see the accompanying LICENSE file.
kpeter@904
    12
 *
kpeter@904
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@904
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@904
    15
 * purpose.
kpeter@904
    16
 *
kpeter@904
    17
 */
kpeter@904
    18
kpeter@904
    19
#include <sstream>
kpeter@904
    20
#include <lemon/list_graph.h>
kpeter@904
    21
#include <lemon/full_graph.h>
kpeter@904
    22
#include <lemon/grid_graph.h>
kpeter@904
    23
#include <lemon/lgf_reader.h>
kpeter@904
    24
#include <lemon/grosso_locatelli_pullan_mc.h>
kpeter@904
    25
kpeter@904
    26
#include "test_tools.h"
kpeter@904
    27
kpeter@904
    28
using namespace lemon;
kpeter@904
    29
kpeter@904
    30
char test_lgf[] =
kpeter@904
    31
  "@nodes\n"
kpeter@904
    32
  "label max_clique\n"
kpeter@904
    33
  "1     0\n"
kpeter@904
    34
  "2     0\n"
kpeter@904
    35
  "3     0\n"
kpeter@904
    36
  "4     1\n"
kpeter@904
    37
  "5     1\n"
kpeter@904
    38
  "6     1\n"
kpeter@904
    39
  "7     1\n"
kpeter@904
    40
  "@edges\n"
kpeter@904
    41
  "    label\n"
kpeter@904
    42
  "1 2     1\n"
kpeter@904
    43
  "1 3     2\n"
kpeter@904
    44
  "1 4     3\n"
kpeter@904
    45
  "1 6     4\n"
kpeter@904
    46
  "2 3     5\n"
kpeter@904
    47
  "2 5     6\n"
kpeter@904
    48
  "2 7     7\n"
kpeter@904
    49
  "3 4     8\n"
kpeter@904
    50
  "3 5     9\n"
kpeter@904
    51
  "4 5    10\n"
kpeter@904
    52
  "4 6    11\n"
kpeter@904
    53
  "4 7    12\n"
kpeter@904
    54
  "5 6    13\n"
kpeter@904
    55
  "5 7    14\n"
kpeter@904
    56
  "6 7    15\n";
alpar@1092
    57
kpeter@904
    58
kpeter@904
    59
// Check with general graphs
kpeter@904
    60
template <typename Param>
kpeter@918
    61
void checkMaxCliqueGeneral(Param rule) {
kpeter@904
    62
  typedef ListGraph GR;
kpeter@904
    63
  typedef GrossoLocatelliPullanMc<GR> McAlg;
kpeter@904
    64
  typedef McAlg::CliqueNodeIt CliqueIt;
alpar@1092
    65
kpeter@904
    66
  // Basic tests
kpeter@904
    67
  {
kpeter@904
    68
    GR g;
kpeter@904
    69
    GR::NodeMap<bool> map(g);
kpeter@904
    70
    McAlg mc(g);
kpeter@918
    71
    mc.iterationLimit(50);
kpeter@918
    72
    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@904
    73
    check(mc.cliqueSize() == 0, "Wrong clique size");
kpeter@904
    74
    check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
kpeter@904
    75
kpeter@904
    76
    GR::Node u = g.addNode();
kpeter@918
    77
    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@904
    78
    check(mc.cliqueSize() == 1, "Wrong clique size");
kpeter@904
    79
    mc.cliqueMap(map);
kpeter@904
    80
    check(map[u], "Wrong clique map");
kpeter@904
    81
    CliqueIt it1(mc);
kpeter@904
    82
    check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
kpeter@904
    83
          "Wrong CliqueNodeIt");
alpar@1092
    84
kpeter@904
    85
    GR::Node v = g.addNode();
kpeter@918
    86
    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
kpeter@904
    87
    check(mc.cliqueSize() == 1, "Wrong clique size");
kpeter@904
    88
    mc.cliqueMap(map);
kpeter@904
    89
    check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
kpeter@904
    90
    CliqueIt it2(mc);
kpeter@904
    91
    check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
kpeter@904
    92
kpeter@904
    93
    g.addEdge(u, v);
kpeter@918
    94
    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@904
    95
    check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@904
    96
    mc.cliqueMap(map);
kpeter@904
    97
    check(map[u] && map[v], "Wrong clique map");
kpeter@904
    98
    CliqueIt it3(mc);
kpeter@904
    99
    check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
kpeter@904
   100
          "Wrong CliqueNodeIt");
kpeter@904
   101
  }
kpeter@904
   102
kpeter@904
   103
  // Test graph
kpeter@904
   104
  {
kpeter@904
   105
    GR g;
kpeter@904
   106
    GR::NodeMap<bool> max_clique(g);
kpeter@904
   107
    GR::NodeMap<bool> map(g);
kpeter@904
   108
    std::istringstream input(test_lgf);
kpeter@904
   109
    graphReader(g, input)
kpeter@904
   110
      .nodeMap("max_clique", max_clique)
kpeter@904
   111
      .run();
alpar@1092
   112
kpeter@904
   113
    McAlg mc(g);
kpeter@918
   114
    mc.iterationLimit(50);
kpeter@918
   115
    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
kpeter@904
   116
    check(mc.cliqueSize() == 4, "Wrong clique size");
kpeter@904
   117
    mc.cliqueMap(map);
kpeter@904
   118
    for (GR::NodeIt n(g); n != INVALID; ++n) {
kpeter@904
   119
      check(map[n] == max_clique[n], "Wrong clique map");
kpeter@904
   120
    }
kpeter@904
   121
    int cnt = 0;
kpeter@904
   122
    for (CliqueIt n(mc); n != INVALID; ++n) {
kpeter@904
   123
      cnt++;
kpeter@904
   124
      check(map[n] && max_clique[n], "Wrong CliqueNodeIt");
kpeter@904
   125
    }
kpeter@904
   126
    check(cnt == 4, "Wrong CliqueNodeIt");
kpeter@904
   127
  }
kpeter@904
   128
}
kpeter@904
   129
kpeter@904
   130
// Check with full graphs
kpeter@904
   131
template <typename Param>
kpeter@918
   132
void checkMaxCliqueFullGraph(Param rule) {
kpeter@904
   133
  typedef FullGraph GR;
kpeter@904
   134
  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
kpeter@904
   135
  typedef McAlg::CliqueNodeIt CliqueIt;
alpar@1092
   136
kpeter@904
   137
  for (int size = 0; size <= 40; size = size * 3 + 1) {
kpeter@904
   138
    GR g(size);
kpeter@904
   139
    GR::NodeMap<bool> map(g);
kpeter@904
   140
    McAlg mc(g);
kpeter@918
   141
    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@904
   142
    check(mc.cliqueSize() == size, "Wrong clique size");
kpeter@904
   143
    mc.cliqueMap(map);
kpeter@904
   144
    for (GR::NodeIt n(g); n != INVALID; ++n) {
kpeter@904
   145
      check(map[n], "Wrong clique map");
kpeter@904
   146
    }
kpeter@904
   147
    int cnt = 0;
kpeter@904
   148
    for (CliqueIt n(mc); n != INVALID; ++n) cnt++;
kpeter@904
   149
    check(cnt == size, "Wrong CliqueNodeIt");
kpeter@904
   150
  }
kpeter@904
   151
}
kpeter@904
   152
kpeter@904
   153
// Check with grid graphs
kpeter@904
   154
template <typename Param>
kpeter@918
   155
void checkMaxCliqueGridGraph(Param rule) {
kpeter@904
   156
  GridGraph g(5, 7);
kpeter@904
   157
  GridGraph::NodeMap<char> map(g);
kpeter@904
   158
  GrossoLocatelliPullanMc<GridGraph> mc(g);
alpar@1092
   159
kpeter@918
   160
  mc.iterationLimit(100);
kpeter@918
   161
  check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
kpeter@918
   162
  check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@918
   163
kpeter@918
   164
  mc.stepLimit(100);
kpeter@918
   165
  check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
kpeter@918
   166
  check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@918
   167
kpeter@918
   168
  mc.sizeLimit(2);
kpeter@918
   169
  check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
kpeter@904
   170
  check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@904
   171
}
kpeter@904
   172
kpeter@904
   173
kpeter@904
   174
int main() {
kpeter@918
   175
  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
kpeter@918
   176
  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
kpeter@918
   177
  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
kpeter@904
   178
kpeter@918
   179
  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
kpeter@918
   180
  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
kpeter@918
   181
  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
alpar@1092
   182
kpeter@918
   183
  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
kpeter@918
   184
  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
kpeter@918
   185
  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
alpar@1092
   186
kpeter@904
   187
  return 0;
kpeter@904
   188
}