LEMON/LEMON-main Changeset - r522:22f932bbb305

Repositories » LEMON » LEMON-main

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

Changeset - r522:22f932bbb305

« 521:3af83b

523:d9e435 »

r522:22f932bbb305

Mon, 03 Nov 2008 12:59:54

[Not Reviewed]

0 comments (0 inline)

ladanyi@tmit.bme.hu
ladanyi@tmit.bme.hu

Test for euler.h (#65)

0 4 1

default

5 files changed with 157 insertions and 3 deletions:

test/euler_test.cc

153

lemon/Makefile.am

lemon/euler.h

test/CMakeLists.txt

test/Makefile.am

↑ Collapse diff ↑

test/euler_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 <lemon/euler.h>
 		#include <lemon/list_graph.h>
 		#include <test/test_tools.h>
 		using namespace lemon;
 		template <typename Digraph>
 		void checkDiEulerIt(const Digraph& g)
+		{
 		  typename Digraph::template ArcMap<int> visitationNumber(g);
 		  DiEulerIt<Digraph> e(g);
 		  typename Digraph::Node firstNode = g.source(e);
 		  typename Digraph::Node lastNode;
 		  for (; e != INVALID; ++e)
+		  {
 		    if (e != INVALID)
+		    {
 		      lastNode = g.target(e);
+		    }
 		    ++visitationNumber[e];
+		  }
 		  check(firstNode == lastNode,
 		      "checkDiEulerIt: first and last node are not the same");
 		  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
+		  {
 		    check(visitationNumber[a] == 1,
 		        "checkDiEulerIt: not visited or multiple times visited arc found");
+		  }
+		}
 		template <typename Graph>
 		void checkEulerIt(const Graph& g)
+		{
 		  typename Graph::template EdgeMap<int> visitationNumber(g);
 		  EulerIt<Graph> e(g);
 		  typename Graph::Node firstNode = g.u(e);
 		  typename Graph::Node lastNode;
 		  for (; e != INVALID; ++e)
+		  {
 		    if (e != INVALID)
+		    {
 		      lastNode = g.v(e);
+		    }
 		    ++visitationNumber[e];
+		  }
 		  check(firstNode == lastNode,
 		      "checkEulerIt: first and last node are not the same");
 		  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
+		  {
 		    check(visitationNumber[e] == 1,
 		        "checkEulerIt: not visited or multiple times visited edge found");
+		  }
+		}
 		int main()
+		{
 		  typedef ListDigraph Digraph;
 		  typedef ListGraph Graph;
 		  Digraph digraphWithEulerianCircuit;
+		  {
 		    Digraph& g = digraphWithEulerianCircuit;
 		    Digraph::Node n0 = g.addNode();
 		    Digraph::Node n1 = g.addNode();
 		    Digraph::Node n2 = g.addNode();
 		    g.addArc(n0, n1);
 		    g.addArc(n1, n0);
 		    g.addArc(n1, n2);
 		    g.addArc(n2, n1);
+		  }
 		  Digraph digraphWithoutEulerianCircuit;
+		  {
 		    Digraph& g = digraphWithoutEulerianCircuit;
 		    Digraph::Node n0 = g.addNode();
 		    Digraph::Node n1 = g.addNode();
 		    Digraph::Node n2 = g.addNode();
 		    g.addArc(n0, n1);
 		    g.addArc(n1, n0);
 		    g.addArc(n1, n2);
+		  }
 		  Graph graphWithEulerianCircuit;
+		  {
 		    Graph& g = graphWithEulerianCircuit;
 		    Graph::Node n0 = g.addNode();
 		    Graph::Node n1 = g.addNode();
 		    Graph::Node n2 = g.addNode();
 		    g.addEdge(n0, n1);
 		    g.addEdge(n1, n2);
 		    g.addEdge(n2, n0);
+		  }
 		  Graph graphWithoutEulerianCircuit;
+		  {
 		    Graph& g = graphWithoutEulerianCircuit;
 		    Graph::Node n0 = g.addNode();
 		    Graph::Node n1 = g.addNode();
 		    Graph::Node n2 = g.addNode();
 		    g.addEdge(n0, n1);
 		    g.addEdge(n1, n2);
+		  }
 		  checkDiEulerIt(digraphWithEulerianCircuit);
 		  checkEulerIt(graphWithEulerianCircuit);
 		  check(eulerian(digraphWithEulerianCircuit),
 		      "this graph should have an Eulerian circuit");
 		  check(!eulerian(digraphWithoutEulerianCircuit),
 		      "this graph should not have an Eulerian circuit");
 		  check(eulerian(graphWithEulerianCircuit),
 		      "this graph should have an Eulerian circuit");
 		  check(!eulerian(graphWithoutEulerianCircuit),
 		      "this graph should have an Eulerian circuit");
 		  return 0;
+		}

lemon/Makefile.am

Show inline comments

@@ -33,48 +33,49 @@
 		endif
 		if HAVE_CPLEX
 		lemon_libemon_la_SOURCES += lemon/cplex.cc
 		endif
 		if HAVE_SOPLEX
 		lemon_libemon_la_SOURCES += lemon/soplex.cc
 		endif
 		if HAVE_CLP
 		lemon_libemon_la_SOURCES += lemon/clp.cc
 		endif
 		lemon_HEADERS += \
 			lemon/adaptors.h \
 			lemon/arg_parser.h \
 			lemon/assert.h \
 			lemon/bfs.h \
 			lemon/bin_heap.h \
 			lemon/circulation.h \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
 			lemon/connectivity.h \
 			lemon/counter.h \
 			lemon/core.h \
 			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/euler.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hypercube_graph.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \

lemon/euler.h

Show inline comments

@@ -33,49 +33,48 @@
 		namespace lemon {
 		  ///Euler iterator for digraphs.
 		  /// \ingroup graph_prop
 		  ///This iterator converts to the \c Arc type of the digraph and using
 		  ///operator ++, it provides an Euler tour of a \e directed
 		  ///graph (if there exists).
 		  ///
 		  ///For example
 		  ///if the given digraph is Euler (i.e it has only one nontrivial component
 		  ///and the in-degree is equal to the out-degree for all nodes),
 		  ///the following code will put the arcs of \c g
 		  ///to the vector \c et according to an
 		  ///Euler tour of \c g.
 		  ///\code
 		  ///  std::vector<ListDigraph::Arc> et;
 		  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
 		  ///    et.push_back(e);
 		  ///\endcode
 		  ///If \c g is not Euler then the resulted tour will not be full or closed.
 		  ///\sa EulerIt
 		  ///\todo Test required
 		  template<class Digraph>
 		  class DiEulerIt
+		  {
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    typedef typename Digraph::InArcIt InArcIt;
 		    const Digraph &g;
 		    typename Digraph::template NodeMap<OutArcIt> nedge;
 		    std::list<Arc> euler;
 		  public:
 		    ///Constructor
 		    ///\param _g A digraph.
 		    ///\param start The starting point of the tour. If it is not given
 		    ///       the tour will start from the first node.
 		    DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
 		      : g(_g), nedge(g)
+		    {
@@ -125,49 +124,48 @@
 		  ///Euler iterator for graphs.
 		  /// \ingroup graph_prop
 		  ///This iterator converts to the \c Arc (or \c Edge)
 		  ///type of the digraph and using
 		  ///operator ++, it provides an Euler tour of an undirected
 		  ///digraph (if there exists).
 		  ///
 		  ///For example
 		  ///if the given digraph if Euler (i.e it has only one nontrivial component
 		  ///and the degree of each node is even),
 		  ///the following code will print the arc IDs according to an
 		  ///Euler tour of \c g.
 		  ///\code
 		  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
 		  ///    std::cout << g.id(Edge(e)) << std::eol;
 		  ///  }
 		  ///\endcode
 		  ///Although the iterator provides an Euler tour of an graph,
 		  ///it still returns Arcs in order to indicate the direction of the tour.
 		  ///(But Arc will convert to Edges, of course).
 		  ///
 		  ///If \c g is not Euler then the resulted tour will not be full or closed.
 		  ///\sa EulerIt
 		  ///\todo Test required
 		  template<class Digraph>
 		  class EulerIt
+		  {
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::Edge Edge;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    typedef typename Digraph::InArcIt InArcIt;
 		    const Digraph &g;
 		    typename Digraph::template NodeMap<OutArcIt> nedge;
 		    typename Digraph::template EdgeMap<bool> visited;
 		    std::list<Arc> euler;
 		  public:
 		    ///Constructor
 		    ///\param _g An graph.
 		    ///\param start The starting point of the tour. If it is not given
 		    ///       the tour will start from the first node.
 		    EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
@@ -219,49 +217,48 @@
 		    ///\warning This incrementation
 		    ///returns an \c Arc, not an \ref EulerIt, as one may
 		    ///expect.
 		    Arc operator++(int)
+		    {
 		      Arc e=*this;
 		      ++(*this);
 		      return e;
+		    }
 		  };
 		  ///Checks if the graph is Eulerian
 		  /// \ingroup graph_prop
 		  ///Checks if the graph is Eulerian. It works for both directed and undirected
 		  ///graphs.
 		  ///\note By definition, a digraph is called \e Eulerian if
 		  ///and only if it is connected and the number of its incoming and outgoing
 		  ///arcs are the same for each node.
 		  ///Similarly, an undirected graph is called \e Eulerian if
 		  ///and only if it is connected and the number of incident arcs is even
 		  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
 		  ///but still have an Euler tour</em>.
 		  ///\todo Test required
 		  template<class Digraph>
 		#ifdef DOXYGEN
 		  bool
 		#else
 		  typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
 		  eulerian(const Digraph &g)
+		  {
 		    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
 		      if(countIncEdges(g,n)%2) return false;
 		    return connected(g);
+		  }
 		  template<class Digraph>
 		  typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
 		#endif
 		  eulerian(const Digraph &g)
+		  {
 		    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
 		      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
 		    return connected(Undirector<const Digraph>(g));
+		  }
+		}
 		#endif

test/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${CMAKE_SOURCE_DIR}
 		  ${CMAKE_BINARY_DIR}
+		)
 		IF(HAVE_GLPK)
 		  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
 		ENDIF(HAVE_GLPK)
 		LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
 		SET(TESTS
 		  adaptors_test
 		  bfs_test
 		  circulation_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  edge_set_test
 		  error_test
 		  euler_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test
 		  hao_orlin_test
 		  heap_test
 		  kruskal_test
 		  maps_test
 		  max_matching_test
 		  path_test
 		  preflow_test
 		  radix_sort_test
 		  random_test
 		  suurballe_test
 		  time_measure_test
 		  unionfind_test)
 		IF(HAVE_LP)
 		  ADD_EXECUTABLE(lp_test lp_test.cc)
 		  IF(HAVE_GLPK)
 		    TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
 		  ENDIF(HAVE_GLPK)
 		  ADD_TEST(lp_test lp_test)
 		  IF(WIN32 AND HAVE_GLPK)

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/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/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/hao_orlin_test \
 			test/heap_test \
 			test/kruskal_test \
 			test/maps_test \
 			test/max_matching_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
 		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_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_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_max_matching_test_SOURCES = test/max_matching_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

0 comments (0 inline)

RhodeCode

Login to your account