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: *
kpeter@763: * Copyright (C) 2003-2009
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@765: #include <lemon/karp.h>
kpeter@766: #include <lemon/hartmann_orlin.h>
kpeter@765: #include <lemon/howard.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:
kpeter@763:
kpeter@763: // Check the interface of an MMC algorithm
kpeter@763: template <typename GR, typename Value>
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@763: ::template SetLargeValue<Value>
kpeter@763: ::Create MmcAlg;
kpeter@763: MmcAlg mmc(me.g, me.length);
kpeter@763: const MmcAlg& const_mmc = mmc;
kpeter@763:
kpeter@769: typename MmcAlg::Tolerance tol = const_mmc.tolerance();
kpeter@769: mmc.tolerance(tol);
kpeter@769:
kpeter@763: b = mmc.cycle(p).run();
kpeter@763: b = mmc.findMinMean();
kpeter@763: b = mmc.findCycle();
kpeter@763:
kpeter@763: v = const_mmc.cycleLength();
kpeter@763: i = const_mmc.cycleArcNum();
kpeter@763: d = const_mmc.cycleMean();
kpeter@763: p = const_mmc.cycle();
kpeter@763: }
kpeter@763:
kpeter@763: typedef concepts::ReadMap<typename GR::Arc, Value> LM;
kpeter@763:
kpeter@763: GR g;
kpeter@763: LM length;
kpeter@763: ListPath<GR> p;
kpeter@763: Value 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@763: int length, int size) {
kpeter@763: MMC alg(gr, lm);
kpeter@763: alg.findMinMean();
kpeter@763: check(alg.cycleMean() == static_cast<double>(length) / size,
kpeter@763: "Wrong cycle mean");
kpeter@763: alg.findCycle();
kpeter@763: check(alg.cycleLength() == length && alg.cycleArcNum() == 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@765: // Karp
kpeter@765: checkConcept< MmcClassConcept<GR, int>,
kpeter@765: Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765: checkConcept< MmcClassConcept<GR, float>,
kpeter@765: Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@763:
kpeter@766: // HartmannOrlin
kpeter@766: checkConcept< MmcClassConcept<GR, int>,
kpeter@766: HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@766: checkConcept< MmcClassConcept<GR, float>,
kpeter@766: HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@766:
kpeter@765: // Howard
kpeter@765: checkConcept< MmcClassConcept<GR, int>,
kpeter@765: Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
kpeter@765: checkConcept< MmcClassConcept<GR, float>,
kpeter@765: Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
kpeter@765:
kpeter@765: if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
kpeter@765: long_int>::result == 0) check(false, "Wrong LargeValue type");
kpeter@765: if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
kpeter@765: double>::result == 0) check(false, "Wrong LargeValue type");
kpeter@763: }
kpeter@763:
kpeter@763: // Run various tests
kpeter@763: {
kpeter@763: typedef SmartDigraph GR;
kpeter@763: DIGRAPH_TYPEDEFS(GR);
kpeter@763:
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);
kpeter@763:
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@765: checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1, 6, 3);
kpeter@765: checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2, 5, 2);
kpeter@765: checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3, 0, 1);
kpeter@765: checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@765:
kpeter@766: // HartmannOrlin
kpeter@766: checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1, 6, 3);
kpeter@766: checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2, 5, 2);
kpeter@766: checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3, 0, 1);
kpeter@766: checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@766:
kpeter@765: // Howard
kpeter@764: checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1, 6, 3);
kpeter@764: checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2, 5, 2);
kpeter@764: checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3, 0, 1);
kpeter@764: checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
kpeter@763: }
kpeter@763:
kpeter@763: return 0;
kpeter@763: }