kpeter@999: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@999:  *
kpeter@999:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@999:  *
alpar@1270:  * Copyright (C) 2003-2013
kpeter@999:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@999:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@999:  *
kpeter@999:  * Permission to use, modify and distribute this software is granted
kpeter@999:  * provided that this copyright notice appears in all copies. For
kpeter@999:  * precise terms see the accompanying LICENSE file.
kpeter@999:  *
kpeter@999:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@999:  * express or implied, and with no claim as to its suitability for any
kpeter@999:  * purpose.
kpeter@999:  *
kpeter@999:  */
kpeter@999: 
kpeter@999: #include <sstream>
kpeter@999: #include <lemon/list_graph.h>
kpeter@999: #include <lemon/full_graph.h>
kpeter@999: #include <lemon/grid_graph.h>
kpeter@999: #include <lemon/lgf_reader.h>
kpeter@999: #include <lemon/grosso_locatelli_pullan_mc.h>
kpeter@999: 
kpeter@999: #include "test_tools.h"
kpeter@999: 
kpeter@999: using namespace lemon;
kpeter@999: 
kpeter@999: char test_lgf[] =
kpeter@999:   "@nodes\n"
kpeter@999:   "label max_clique\n"
kpeter@999:   "1     0\n"
kpeter@999:   "2     0\n"
kpeter@999:   "3     0\n"
kpeter@999:   "4     1\n"
kpeter@999:   "5     1\n"
kpeter@999:   "6     1\n"
kpeter@999:   "7     1\n"
kpeter@999:   "@edges\n"
kpeter@999:   "    label\n"
kpeter@999:   "1 2     1\n"
kpeter@999:   "1 3     2\n"
kpeter@999:   "1 4     3\n"
kpeter@999:   "1 6     4\n"
kpeter@999:   "2 3     5\n"
kpeter@999:   "2 5     6\n"
kpeter@999:   "2 7     7\n"
kpeter@999:   "3 4     8\n"
kpeter@999:   "3 5     9\n"
kpeter@999:   "4 5    10\n"
kpeter@999:   "4 6    11\n"
kpeter@999:   "4 7    12\n"
kpeter@999:   "5 6    13\n"
kpeter@999:   "5 7    14\n"
kpeter@999:   "6 7    15\n";
alpar@1270: 
kpeter@999: 
kpeter@999: // Check with general graphs
kpeter@999: template <typename Param>
kpeter@1022: void checkMaxCliqueGeneral(Param rule) {
kpeter@999:   typedef ListGraph GR;
kpeter@999:   typedef GrossoLocatelliPullanMc<GR> McAlg;
kpeter@999:   typedef McAlg::CliqueNodeIt CliqueIt;
alpar@1270: 
kpeter@999:   // Basic tests
kpeter@999:   {
kpeter@999:     GR g;
kpeter@999:     GR::NodeMap<bool> map(g);
kpeter@999:     McAlg mc(g);
kpeter@1022:     mc.iterationLimit(50);
kpeter@1022:     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@999:     check(mc.cliqueSize() == 0, "Wrong clique size");
kpeter@999:     check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
kpeter@999: 
kpeter@999:     GR::Node u = g.addNode();
kpeter@1022:     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@999:     check(mc.cliqueSize() == 1, "Wrong clique size");
kpeter@999:     mc.cliqueMap(map);
kpeter@999:     check(map[u], "Wrong clique map");
kpeter@999:     CliqueIt it1(mc);
kpeter@999:     check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
kpeter@999:           "Wrong CliqueNodeIt");
alpar@1270: 
kpeter@999:     GR::Node v = g.addNode();
kpeter@1022:     check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
kpeter@999:     check(mc.cliqueSize() == 1, "Wrong clique size");
kpeter@999:     mc.cliqueMap(map);
kpeter@999:     check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
kpeter@999:     CliqueIt it2(mc);
kpeter@999:     check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
kpeter@999: 
kpeter@999:     g.addEdge(u, v);
kpeter@1022:     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@999:     check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@999:     mc.cliqueMap(map);
kpeter@999:     check(map[u] && map[v], "Wrong clique map");
kpeter@999:     CliqueIt it3(mc);
kpeter@999:     check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
kpeter@999:           "Wrong CliqueNodeIt");
kpeter@999:   }
kpeter@999: 
kpeter@999:   // Test graph
kpeter@999:   {
kpeter@999:     GR g;
kpeter@999:     GR::NodeMap<bool> max_clique(g);
kpeter@999:     GR::NodeMap<bool> map(g);
kpeter@999:     std::istringstream input(test_lgf);
kpeter@999:     graphReader(g, input)
kpeter@999:       .nodeMap("max_clique", max_clique)
kpeter@999:       .run();
alpar@1270: 
kpeter@999:     McAlg mc(g);
kpeter@1022:     mc.iterationLimit(50);
kpeter@1022:     check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
kpeter@999:     check(mc.cliqueSize() == 4, "Wrong clique size");
kpeter@999:     mc.cliqueMap(map);
kpeter@999:     for (GR::NodeIt n(g); n != INVALID; ++n) {
kpeter@999:       check(map[n] == max_clique[n], "Wrong clique map");
kpeter@999:     }
kpeter@999:     int cnt = 0;
kpeter@999:     for (CliqueIt n(mc); n != INVALID; ++n) {
kpeter@999:       cnt++;
kpeter@999:       check(map[n] && max_clique[n], "Wrong CliqueNodeIt");
kpeter@999:     }
kpeter@999:     check(cnt == 4, "Wrong CliqueNodeIt");
kpeter@999:   }
kpeter@999: }
kpeter@999: 
kpeter@999: // Check with full graphs
kpeter@999: template <typename Param>
kpeter@1022: void checkMaxCliqueFullGraph(Param rule) {
kpeter@999:   typedef FullGraph GR;
kpeter@999:   typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
kpeter@999:   typedef McAlg::CliqueNodeIt CliqueIt;
alpar@1270: 
kpeter@999:   for (int size = 0; size <= 40; size = size * 3 + 1) {
kpeter@999:     GR g(size);
kpeter@999:     GR::NodeMap<bool> map(g);
kpeter@999:     McAlg mc(g);
kpeter@1022:     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
kpeter@999:     check(mc.cliqueSize() == size, "Wrong clique size");
kpeter@999:     mc.cliqueMap(map);
kpeter@999:     for (GR::NodeIt n(g); n != INVALID; ++n) {
kpeter@999:       check(map[n], "Wrong clique map");
kpeter@999:     }
kpeter@999:     int cnt = 0;
kpeter@999:     for (CliqueIt n(mc); n != INVALID; ++n) cnt++;
kpeter@999:     check(cnt == size, "Wrong CliqueNodeIt");
kpeter@999:   }
kpeter@999: }
kpeter@999: 
kpeter@999: // Check with grid graphs
kpeter@999: template <typename Param>
kpeter@1022: void checkMaxCliqueGridGraph(Param rule) {
kpeter@999:   GridGraph g(5, 7);
kpeter@999:   GridGraph::NodeMap<char> map(g);
kpeter@999:   GrossoLocatelliPullanMc<GridGraph> mc(g);
alpar@1270: 
kpeter@1022:   mc.iterationLimit(100);
kpeter@1022:   check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
kpeter@1022:   check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@1022: 
kpeter@1022:   mc.stepLimit(100);
kpeter@1022:   check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
kpeter@1022:   check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@1022: 
kpeter@1022:   mc.sizeLimit(2);
kpeter@1022:   check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
kpeter@999:   check(mc.cliqueSize() == 2, "Wrong clique size");
kpeter@999: }
kpeter@999: 
kpeter@999: 
kpeter@999: int main() {
kpeter@1022:   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
kpeter@1022:   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
kpeter@1022:   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
kpeter@999: 
kpeter@1022:   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
kpeter@1022:   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
kpeter@1022:   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
alpar@1270: 
kpeter@1022:   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
kpeter@1022:   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
kpeter@1022:   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
alpar@1270: 
kpeter@999:   return 0;
kpeter@999: }