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