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 <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";
kpeter@999:
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;
kpeter@999:
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");
kpeter@999:
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();
kpeter@999:
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;
kpeter@999:
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);
kpeter@1022:
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);
kpeter@999:
kpeter@1022: checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
kpeter@1022: checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
kpeter@1022: checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
kpeter@999:
kpeter@999: return 0;
kpeter@999: }