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: * kpeter@999: * Copyright (C) 2003-2010 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 kpeter@999: #include kpeter@999: #include kpeter@999: #include kpeter@999: #include kpeter@999: #include 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"; kpeter@999: kpeter@999: kpeter@999: // Check with general graphs kpeter@999: template kpeter@999: void checkMaxCliqueGeneral(int max_sel, Param rule) { kpeter@999: typedef ListGraph GR; kpeter@999: typedef GrossoLocatelliPullanMc McAlg; kpeter@999: typedef McAlg::CliqueNodeIt CliqueIt; kpeter@999: kpeter@999: // Basic tests kpeter@999: { kpeter@999: GR g; kpeter@999: GR::NodeMap map(g); kpeter@999: McAlg mc(g); kpeter@999: check(mc.run(max_sel, rule) == 0, "Wrong clique size"); 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@999: check(mc.run(max_sel, rule) == 1, "Wrong clique size"); 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(it1) == u && ++it1 == INVALID, kpeter@999: "Wrong CliqueNodeIt"); kpeter@999: kpeter@999: GR::Node v = g.addNode(); kpeter@999: check(mc.run(max_sel, rule) == 1, "Wrong clique size"); 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@999: check(mc.run(max_sel, rule) == 2, "Wrong clique size"); 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 max_clique(g); kpeter@999: GR::NodeMap map(g); kpeter@999: std::istringstream input(test_lgf); kpeter@999: graphReader(g, input) kpeter@999: .nodeMap("max_clique", max_clique) kpeter@999: .run(); kpeter@999: kpeter@999: McAlg mc(g); kpeter@999: check(mc.run(max_sel, rule) == 4, "Wrong clique size"); 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 kpeter@999: void checkMaxCliqueFullGraph(int max_sel, Param rule) { kpeter@999: typedef FullGraph GR; kpeter@999: typedef GrossoLocatelliPullanMc McAlg; kpeter@999: typedef McAlg::CliqueNodeIt CliqueIt; kpeter@999: kpeter@999: for (int size = 0; size <= 40; size = size * 3 + 1) { kpeter@999: GR g(size); kpeter@999: GR::NodeMap map(g); kpeter@999: McAlg mc(g); kpeter@999: check(mc.run(max_sel, rule) == size, "Wrong clique size"); 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 kpeter@999: void checkMaxCliqueGridGraph(int max_sel, Param rule) { kpeter@999: GridGraph g(5, 7); kpeter@999: GridGraph::NodeMap map(g); kpeter@999: GrossoLocatelliPullanMc mc(g); kpeter@999: check(mc.run(max_sel, rule) == 2, "Wrong clique size"); kpeter@999: check(mc.cliqueSize() == 2, "Wrong clique size"); kpeter@999: } kpeter@999: kpeter@999: kpeter@999: int main() { kpeter@999: checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::RANDOM); kpeter@999: checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::DEGREE_BASED); kpeter@999: checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::PENALTY_BASED); kpeter@999: kpeter@999: checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::RANDOM); kpeter@999: checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::DEGREE_BASED); kpeter@999: checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::PENALTY_BASED); kpeter@999: kpeter@999: checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::RANDOM); kpeter@999: checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::DEGREE_BASED); kpeter@999: checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::PENALTY_BASED); kpeter@999: kpeter@999: return 0; kpeter@999: }