kpeter@763: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@763: *
kpeter@763: * This file is a part of LEMON, a generic C++ optimization library.
kpeter@763: *
alpar@877: * Copyright (C) 2003-2010
kpeter@763: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@763: * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@763: *
kpeter@763: * Permission to use, modify and distribute this software is granted
kpeter@763: * provided that this copyright notice appears in all copies. For
kpeter@763: * precise terms see the accompanying LICENSE file.
kpeter@763: *
kpeter@763: * This software is provided "AS IS" with no warranty of any kind,
kpeter@763: * express or implied, and with no claim as to its suitability for any
kpeter@763: * purpose.
kpeter@763: *
kpeter@763: */
kpeter@763:
kpeter@763: #include <iostream>
kpeter@763: #include <sstream>
kpeter@763:
kpeter@763: #include <lemon/smart_graph.h>
kpeter@763: #include <lemon/lgf_reader.h>
kpeter@763: #include <lemon/path.h>
kpeter@763: #include <lemon/concepts/digraph.h>
kpeter@763: #include <lemon/concept_check.h>
kpeter@763:
kpeter@864: #include <lemon/karp_mmc.h>
kpeter@864: #include <lemon/hartmann_orlin_mmc.h>
kpeter@864: #include <lemon/howard_mmc.h>
kpeter@765:
kpeter@763: #include "test_tools.h"
kpeter@763:
kpeter@763: using namespace lemon;
kpeter@763:
kpeter@763: char test_lgf[] =
kpeter@763: "@nodes\n"
kpeter@763: "label\n"
kpeter@763: "1\n"
kpeter@763: "2\n"
kpeter@763: "3\n"
kpeter@763: "4\n"
kpeter@763: "5\n"
kpeter@763: "6\n"
kpeter@763: "7\n"
kpeter@763: "@arcs\n"
kpeter@763: " len1 len2 len3 len4 c1 c2 c3 c4\n"
kpeter@763: "1 2 1 1 1 1 0 0 0 0\n"
kpeter@763: "2 4 5 5 5 5 1 0 0 0\n"
kpeter@763: "2 3 8 8 8 8 0 0 0 0\n"
kpeter@763: "3 2 -2 0 0 0 1 0 0 0\n"
kpeter@763: "3 4 4 4 4 4 0 0 0 0\n"
kpeter@763: "3 7 -4 -4 -4 -4 0 0 0 0\n"
kpeter@763: "4 1 2 2 2 2 0 0 0 0\n"
kpeter@763: "4 3 3 3 3 3 1 0 0 0\n"
kpeter@763: "4 4 3 3 0 0 0 0 1 0\n"
kpeter@763: "5 2 4 4 4 4 0 0 0 0\n"
kpeter@763: "5 6 3 3 3 3 0 1 0 0\n"
kpeter@763: "6 5 2 2 2 2 0 1 0 0\n"
kpeter@763: "6 4 -1 -1 -1 -1 0 0 0 0\n"
kpeter@763: "6 7 1 1 1 1 0 0 0 0\n"
kpeter@763: "7 7 4 4 4 -1 0 0 0 1\n";
kpeter@763:
alpar@877:
kpeter@763: // Check the interface of an MMC algorithm
kpeter@864: template <typename GR, typename Cost>
kpeter@763: struct MmcClassConcept
kpeter@763: {
kpeter@763: template <typename MMC>
kpeter@763: struct Constraints {
kpeter@763: void constraints() {
kpeter@763: const Constraints& me = *this;
kpeter@763:
kpeter@763: typedef typename MMC
kpeter@763: ::template SetPath<ListPath<GR> >
kpeter@864: ::template SetLargeCost<Cost>
kpeter@763: ::Create MmcAlg;
kpeter@864: MmcAlg mmc(me.g, me.cost);
kpeter@763: const MmcAlg& const_mmc = mmc;
alpar@877:
kpeter@769: typename MmcAlg::Tolerance tol = const_mmc.tolerance();
kpeter@769: mmc.tolerance(tol);
alpar@877:
kpeter@763: b = mmc.cycle(p).run();
kpeter@864: b = mmc.findCycleMean();
kpeter@763: b = mmc.findCycle();
kpeter@763:
kpeter@864: v = const_mmc.cycleCost();
kpeter@864: i = const_mmc.cycleSize();
kpeter@763: d = const_mmc.cycleMean();
kpeter@763: p = const_mmc.cycle();
kpeter@763: }
kpeter@763:
kpeter@864: typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
alpar@877:
kpeter@763: GR g;
kpeter@864: CM cost;
kpeter@763: ListPath<GR> p;
kpeter@864: Cost v;
kpeter@763: int i;
kpeter@763: double d;
kpeter@763: bool b;
kpeter@763: };
kpeter@763: };
kpeter@763:
kpeter@763: // Perform a test with the given parameters
kpeter@763: template <typename MMC>
kpeter@763: void checkMmcAlg(const SmartDigraph& gr,
kpeter@763: const SmartDigraph::ArcMap<int>& lm,
kpeter@763: const SmartDigraph::ArcMap<int>& cm,
kpeter@864: int cost, int size) {
kpeter@763: MMC alg(gr, lm);
kpeter@864: alg.findCycleMean();
kpeter@864: check(alg.cycleMean() == static_cast<double>(cost) / size,
kpeter@763: "Wrong cycle mean");
kpeter@763: alg.findCycle();
kpeter@864: check(alg.cycleCost() == cost && alg.cycleSize() == size,
kpeter@763: "Wrong path");
kpeter@763: SmartDigraph::ArcMap<int> cycle(gr, 0);
kpeter@763: for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
kpeter@763: ++cycle[a];
kpeter@763: }
kpeter@763: for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
kpeter@763: check(cm[a] == cycle[a], "Wrong path");
kpeter@763: }
kpeter@763: }
kpeter@763:
kpeter@763: // Class for comparing types
kpeter@763: template <typename T1, typename T2>
kpeter@763: struct IsSameType {
kpeter@763: static const int result = 0;
kpeter@763: };
kpeter@763:
kpeter@763: template <typename T>
kpeter@763: struct IsSameType<T,T> {
kpeter@763: static const int result = 1;
kpeter@763: };
kpeter@763:
kpeter@763:
kpeter@763: int main() {
kpeter@763: #ifdef LEMON_HAVE_LONG_LONG
kpeter@763: typedef long long long_int;
kpeter@763: #else
kpeter@763: typedef long long_int;
kpeter@763: #endif
kpeter@763:
kpeter@763: // Check the interface
kpeter@763: {
kpeter@763: typedef concepts::Digraph GR;
kpeter@765:
kpeter@864: // KarpMmc
kpeter@765: checkConcept< MmcClassConcept<GR, int>,
kpeter@864: KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765: checkConcept< MmcClassConcept<GR, float>,
kpeter@864: KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
alpar@877:
kpeter@864: // HartmannOrlinMmc
kpeter@766: checkConcept< MmcClassConcept<GR, int>,
kpeter@864: HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@766: checkConcept< MmcClassConcept<GR, float>,
kpeter@864: HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
alpar@877:
kpeter@864: // HowardMmc
kpeter@765: checkConcept< MmcClassConcept<GR, int>,
kpeter@864: HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765: checkConcept< MmcClassConcept<GR, float>,
kpeter@864: HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@765:
kpeter@864: check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
kpeter@864: ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
kpeter@864: check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
kpeter@864: ::LargeCost, double>::result == 1), "Wrong LargeCost type");
kpeter@763: }
kpeter@763:
kpeter@763: // Run various tests
kpeter@763: {
kpeter@763: typedef SmartDigraph GR;
kpeter@763: DIGRAPH_TYPEDEFS(GR);
alpar@877:
kpeter@763: GR gr;
kpeter@763: IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
kpeter@763: IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
alpar@877:
kpeter@763: std::istringstream input(test_lgf);
kpeter@763: digraphReader(gr, input).
kpeter@763: arcMap("len1", l1).
kpeter@763: arcMap("len2", l2).
kpeter@763: arcMap("len3", l3).
kpeter@763: arcMap("len4", l4).
kpeter@763: arcMap("c1", c1).
kpeter@763: arcMap("c2", c2).
kpeter@763: arcMap("c3", c3).
kpeter@763: arcMap("c4", c4).
kpeter@763: run();
kpeter@763:
kpeter@765: // Karp
kpeter@864: checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3);
kpeter@864: checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2);
kpeter@864: checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1);
kpeter@864: checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@765:
kpeter@766: // HartmannOrlin
kpeter@864: checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3);
kpeter@864: checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2);
kpeter@864: checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1);
kpeter@864: checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@766:
kpeter@765: // Howard
kpeter@864: checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3);
kpeter@864: checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2);
kpeter@864: checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1);
kpeter@864: checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@763: }
kpeter@763:
kpeter@763: return 0;
kpeter@763: }