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 kpeter@904: #include kpeter@904: #include kpeter@904: #include kpeter@904: #include kpeter@904: #include 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 kpeter@918: void checkMaxCliqueGeneral(Param rule) { kpeter@904: typedef ListGraph GR; kpeter@904: typedef GrossoLocatelliPullanMc McAlg; kpeter@904: typedef McAlg::CliqueNodeIt CliqueIt; kpeter@904: kpeter@904: // Basic tests kpeter@904: { kpeter@904: GR g; kpeter@904: GR::NodeMap 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(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 max_clique(g); kpeter@904: GR::NodeMap 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 kpeter@918: void checkMaxCliqueFullGraph(Param rule) { kpeter@904: typedef FullGraph GR; kpeter@904: typedef GrossoLocatelliPullanMc 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 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 kpeter@918: void checkMaxCliqueGridGraph(Param rule) { kpeter@904: GridGraph g(5, 7); kpeter@904: GridGraph::NodeMap map(g); kpeter@904: GrossoLocatelliPullanMc 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::RANDOM); kpeter@918: checkMaxCliqueGeneral(GrossoLocatelliPullanMc::DEGREE_BASED); kpeter@918: checkMaxCliqueGeneral(GrossoLocatelliPullanMc::PENALTY_BASED); kpeter@904: kpeter@918: checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::RANDOM); kpeter@918: checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::DEGREE_BASED); kpeter@918: checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::PENALTY_BASED); kpeter@904: kpeter@918: checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::RANDOM); kpeter@918: checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::DEGREE_BASED); kpeter@918: checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::PENALTY_BASED); kpeter@904: kpeter@904: return 0; kpeter@904: }