LEMON/LEMON-main Changeset - r763:93cd93e82f9b

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r763:93cd93e82f9b

« 762:03887b

764:1fac51 »

r763:93cd93e82f9b

Fri, 07 Aug 2009 14:52:40

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Add a detailed test file for MinMeanCycle and fix test_tools.h (#179)

0 4 1

default

5 files changed with 193 insertions and 1 deletions:

test/min_mean_cycle_test.cc

184

lemon/min_mean_cycle.h

test/CMakeLists.txt

test/Makefile.am

test/test_tools.h

↑ Collapse diff ↑

test/min_mean_cycle_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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/min_mean_cycle.h>
 		#include <lemon/path.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concept_check.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 Value>
 		struct MmcClassConcept
+		{
 		  template <typename MMC>
 		  struct Constraints {
 		    void constraints() {
 		      const Constraints& me = *this;
 		      typedef typename MMC
 		        ::template SetPath<ListPath<GR> >
 		        ::template SetLargeValue<Value>
 		        ::Create MmcAlg;
 		      MmcAlg mmc(me.g, me.length);
 		      const MmcAlg& const_mmc = mmc;
 		      b = mmc.cycle(p).run();
 		      b = mmc.findMinMean();
 		      b = mmc.findCycle();
 		      v = const_mmc.cycleLength();
 		      i = const_mmc.cycleArcNum();
 		      d = const_mmc.cycleMean();
 		      p = const_mmc.cycle();
+		    }
 		    typedef concepts::ReadMap<typename GR::Arc, Value> LM;
 		    GR g;
 		    LM length;
 		    ListPath<GR> p;
 		    Value 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 length, int size) {
 		  MMC alg(gr, lm);
 		  alg.findMinMean();
 		  check(alg.cycleMean() == static_cast<double>(length) / size,
 		        "Wrong cycle mean");
 		  alg.findCycle();
 		  check(alg.cycleLength() == length && alg.cycleArcNum() == 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;
 		    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
 		    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
 		    checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
 		    checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();
 		    if (IsSameType<IntMmcAlg::LargeValue, long_int>::result == 0)
 		      check(false, "Wrong LargeValue type");
 		    if (IsSameType<FloatMmcAlg::LargeValue, double>::result == 0)
 		      check(false, "Wrong LargeValue 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();
 		    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l1, c1,  6, 3);
 		    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l2, c2,  5, 2);
 		    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l3, c3,  0, 1);
 		    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+		  }
 		  return 0;
+		}

lemon/min_mean_cycle.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_MIN_MEAN_CYCLE_H
 		#define LEMON_MIN_MEAN_CYCLE_H
 		/// \ingroup shortest_path
 		///
 		/// \file
 		/// \brief Howard's algorithm for finding a minimum mean cycle.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
 		  /// \brief Default traits class of MinMeanCycle class.
 		  ///
 		  /// Default traits class of MinMeanCycle class.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN>
 		#else
 		  template <typename GR, typename LEN,
 		    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 		#endif
 		  struct MinMeanCycleDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the length map
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths
 		    typedef typename LengthMap::Value Value;
 		    /// \brief The large value type used for internal computations
 		    ///
 		    /// The large value type used for internal computations.
 		    /// It is \c long \c long if the \c Value type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Value must be convertible to \c LargeValue.
 		    typedef double LargeValue;
 		    /// The tolerance type used for internal computations
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    /// \brief The path type of the found cycles
 		    ///
 		    /// The path type of the found cycles.
 		    /// It must conform to the \ref lemon::concepts::Path "Path" concept
 		    /// and it must have an \c addBack() function.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  // Default traits class for integer value types

test/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
+		)
 		LINK_DIRECTORIES(
 		  ${PROJECT_BINARY_DIR}/lemon
+		)
 		SET(TESTS
 		  adaptors_test
 		  bfs_test
 		  circulation_test
 		  connectivity_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  edge_set_test
 		  error_test
 		  euler_test
 		  gomory_hu_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test
 		  hao_orlin_test
 		  heap_test
 		  kruskal_test
 		  maps_test
 		  matching_test
 		  min_cost_arborescence_test
 		  min_cost_flow_test
 		  min_mean_cycle_test
 		  path_test
 		  preflow_test
 		  radix_sort_test
 		  random_test
 		  suurballe_test
 		  time_measure_test
 		  unionfind_test
+		)
 		IF(LEMON_HAVE_LP)
 		  ADD_EXECUTABLE(lp_test lp_test.cc)
 		  SET(LP_TEST_LIBS lemon)
 		  IF(LEMON_HAVE_GLPK)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
 		  ENDIF()
 		  IF(LEMON_HAVE_CPLEX)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
 		  ENDIF()
 		  IF(LEMON_HAVE_CLP)
 		    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
 		  ENDIF()
 		  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
 		  ADD_TEST(lp_test lp_test)
 		  IF(WIN32 AND LEMON_HAVE_GLPK)
 		    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
 		      COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
+		    )
 		  ENDIF()
 		  IF(WIN32 AND LEMON_HAVE_CPLEX)
 		    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
 		    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
 		    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
 		      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
+		    )
 		  ENDIF()
 		ENDIF()
 		IF(LEMON_HAVE_MIP)
 		  ADD_EXECUTABLE(mip_test mip_test.cc)
 		  SET(MIP_TEST_LIBS lemon)

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/test_tools.h
 		check_PROGRAMS += \
 			test/adaptors_test \
 			test/bfs_test \
 			test/circulation_test \
 			test/connectivity_test \
 			test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 			test/dim_test \
 			test/edge_set_test \
 			test/error_test \
 			test/euler_test \
 			test/gomory_hu_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/hao_orlin_test \
 			test/heap_test \
 			test/kruskal_test \
 			test/maps_test \
 			test/matching_test \
 			test/min_cost_arborescence_test \
 			test/min_cost_flow_test \
 			test/min_mean_cycle_test \
 			test/path_test \
 			test/preflow_test \
 			test/radix_sort_test \
 			test/random_test \
 			test/suurballe_test \
 			test/test_tools_fail \
 			test/test_tools_pass \
 			test/time_measure_test \
 			test/unionfind_test
 		test_test_tools_pass_DEPENDENCIES = demo
 		if HAVE_LP
 		check_PROGRAMS += test/lp_test
 		endif HAVE_LP
 		if HAVE_MIP
 		check_PROGRAMS += test/mip_test
 		endif HAVE_MIP
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_adaptors_test_SOURCES = test/adaptors_test.cc
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_circulation_test_SOURCES = test/circulation_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_connectivity_test_SOURCES = test/connectivity_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_edge_set_test_SOURCES = test/edge_set_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_euler_test_SOURCES = test/euler_test.cc
 		test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
 		test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 		test_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 		test_lp_test_SOURCES = test/lp_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_mip_test_SOURCES = test/mip_test.cc
 		test_matching_test_SOURCES = test/matching_test.cc
 		test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 		test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
 		test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
 		test_path_test_SOURCES = test/path_test.cc
 		test_preflow_test_SOURCES = test/preflow_test.cc
 		test_radix_sort_test_SOURCES = test/radix_sort_test.cc
 		test_suurballe_test_SOURCES = test/suurballe_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 		test_time_measure_test_SOURCES = test/time_measure_test.cc
 		test_unionfind_test_SOURCES = test/unionfind_test.cc

test/test_tools.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_TEST_TEST_TOOLS_H
 		#define LEMON_TEST_TEST_TOOLS_H
 		///\ingroup misc
 		///\file
 		///\brief Some utilities to write test programs.
 		#include <iostream>
 		#include <stdlib.h>
 		///If \c rc is fail, writes an error message and exits.
 		///If \c rc is fail, writes an error message and exits.
 		///The error message contains the file name and the line number of the
 		///source code in a standard from, which makes it possible to go there
 		///using good source browsers like e.g. \c emacs.
 		///
 		///For example
 		///\code check(0==1,"This is obviously false.");\endcode will
 		///print something like this (and then exits).
 		///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
 		#define check(rc, msg) \
 		  {                                                                     \
 		  if(!(rc)) { \
-		    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
+		      std::cerr << __FILE__ ":" << __LINE__ << ": error: "              \
 		                << msg << std::endl;                                    \
 		    abort(); \
 		  } else { } \
 		  }                                                                     \
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account