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