LEMON/LEMON-main Changeset - r203:215bfc30b14f

Repositories » LEMON » LEMON-main

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

Changeset - r203:215bfc30b14f

« 202:a5ee72

205:436fe7 »

r203:215bfc30b14f

Fri, 11 Jul 2008 15:01:49

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Cleaning of heap test and bug fix in heap concept check (ticket #100) * The dijkstra heap test's digraph is inlined into the source file * The random sequences are fixed * The content of the header is moved to the source file * Only the binary heap is checked

1 4 0

default

5 files changed with 143 insertions and 220 deletions:

lemon/concepts/heap.h

test/CMakeLists.txt

test/Makefile.am

test/heap_test.cc

137

test/heap_test.h

123

↑ Collapse diff ↑

lemon/concepts/heap.h

Show inline comments

@@ -160,92 +160,87 @@
 		      /// to the heap again.
 		      /// \param i The item.
 		      State state(const Item &i) const {}
 		      /// \brief Sets the state of an item in the heap.
 		      ///
 		      /// Sets the state of the given item in the heap. It can be used
 		      /// to manually clear the heap when it is important to achive the
 		      /// better time complexity.
 		      /// \param i The item.
 		      /// \param st The state. It should not be \c IN_HEAP.
 		      void state(const Item& i, State st) {}
 		      template <typename _Heap>
 		      struct Constraints {
 		      public:
 			void constraints() {
 			  typedef typename _Heap::Item OwnItem;
 			  typedef typename _Heap::Prio OwnPrio;
 			  typedef typename _Heap::State OwnState;
 			  Item item;
 			  Prio prio;
 			  State state;
 			  item=Item();
 			  prio=Prio();
 			  ignore_unused_variable_warning(item);
 			  ignore_unused_variable_warning(prio);
 			  ignore_unused_variable_warning(state);
 			  OwnItem own_item;
 			  OwnPrio own_prio;
 			  OwnState own_state;
 			  own_item=Item();
 			  own_prio=Prio();
 			  ignore_unused_variable_warning(own_item);
 			  ignore_unused_variable_warning(own_prio);
 			  ignore_unused_variable_warning(own_state);
 			  _Heap heap1(map);
 			  _Heap heap2 = heap1;
 			  ignore_unused_variable_warning(heap1);
 			  ignore_unused_variable_warning(heap2);
 			  int s = heap.size();
 			  ignore_unused_variable_warning(s);
 			  bool e = heap.empty();
 			  ignore_unused_variable_warning(e);
 			  prio = heap.prio();
 			  item = heap.top();
 			  prio = heap[item];
 			  own_prio = heap.prio();
 			  own_item = heap.top();
 			  own_prio = heap[own_item];
 			  heap.push(item, prio);
 			  heap.push(own_item, own_prio);
 			  heap.pop();
 			  heap.set(item, prio);
 			  heap.decrease(item, prio);
 			  heap.increase(item, prio);
 			  heap.set(own_item, own_prio);
 			  heap.decrease(own_item, own_prio);
 			  heap.increase(own_item, own_prio);
 			  heap.erase(item);
 			  heap.erase(own_item);
 			  heap.clear();
 			  state = heap.state(item);
 			  heap.state(item, state);
-			  state = heap.state(own_item);
+			  own_state = heap.state(own_item);
 			  heap.state(own_item, own_state);
 			  state = _Heap::PRE_HEAP;
 			  state = _Heap::IN_HEAP;
 			  state = _Heap::POST_HEAP;
 			  own_state = _Heap::PRE_HEAP;
 			  own_state = _Heap::IN_HEAP;
 			  own_state = _Heap::POST_HEAP;
+			}
 			_Heap& heap;
 			ItemIntMap& map;
 		      };
 		    };
 		    /// @}
 		  } // namespace lemon
+		}
 		#endif // LEMON_CONCEPT_PATH_H

test/CMakeLists.txt

Show inline comments

 		include_directories (${LEMON_SOURCE_DIR})
 		link_directories (${LEMON_BINARY_DIR}/lemon)
 		set (TESTS
 		  bfs_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  error_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test
 		  heap_test
 		  kruskal_test
 		  maps_test
 		  path_test
 		  random_test
 		  time_measure_test
 		  unionfind_test)
 		foreach (TEST_NAME ${TESTS})
 		  add_executable (${TEST_NAME} ${TEST_NAME}.cc)
 		  target_link_libraries (${TEST_NAME} lemon)
 		  add_test(${TEST_NAME} ${TEST_NAME})
 		endforeach (TEST_NAME)

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/heap_test.h \
 			test/graph_maps_test.h \
 		        test/test_tools.h
 		check_PROGRAMS += \
 			test/bfs_test \
 		        test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 		        test/dim_test \
 			test/error_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/heap_test \
 			test/kruskal_test \
 		        test/maps_test \
 		        test/random_test \
 		        test/path_test \
 		        test/test_tools_fail \
 		        test/test_tools_pass \
 		        test/time_measure_test \
 			test/unionfind_test
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_bfs_test_SOURCES = test/bfs_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_error_test_SOURCES = test/error_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_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_path_test_SOURCES = test/path_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/heap_test.cc

Show inline comments

@@ -3,135 +3,185 @@
 		 * 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.
+		 *
 		 */
 		#include <iostream>
 		#include <fstream>
 		#include <string>
 		#include <vector>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/heap.h>
-		#include <lemon/list_graph.h>
+		#include <lemon/smart_graph.h>
-		#include <lemon/digraph_reader.h>
+		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/maps.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/fib_heap.h>
 		#include <lemon/radix_heap.h>
 		#include <lemon/bucket_heap.h>
 		#include "test_tools.h"
 		#include "heap_test.h"
 		#include <lemon/time_measure.h>
 		using namespace lemon;
 		using namespace lemon::concepts;
 		typedef ListDigraph Digraph;
 		DIGRAPH_TYPEDEFS(Digraph);
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "7\n"
 		  "8\n"
 		  "9\n"
 		  "@arcs\n"
 		  "		label	capacity\n"
 		  "0	5	0	94\n"
 		  "3	9	1	11\n"
 		  "8	7	2	83\n"
 		  "1	2	3	94\n"
 		  "5	7	4	35\n"
 		  "7	4	5	84\n"
 		  "9	5	6	38\n"
 		  "0	4	7	96\n"
 		  "6	7	8	6\n"
 		  "3	1	9	27\n"
 		  "5	2	10	77\n"
 		  "5	6	11	69\n"
 		  "6	5	12	41\n"
 		  "4	6	13	70\n"
 		  "3	2	14	45\n"
 		  "7	9	15	93\n"
 		  "5	9	16	50\n"
 		  "9	0	17	94\n"
 		  "9	6	18	67\n"
 		  "0	9	19	86\n"
 		  "@attributes\n"
 		  "source 3\n";
 		int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
 		int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
 		int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
 		template <typename Heap>
 		void heapSortTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
 		    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void heapIncreaseTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] += test_inc[i];
 		    heap.increase(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
 		    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
 				      Node source) {
 		  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
 		    Create dijkstra(digraph, length);
 		  dijkstra.run(source);
 		  for(ArcIt a(digraph); a != INVALID; ++a) {
 		    Node s = digraph.source(a);
 		    Node t = digraph.target(a);
 		    if (dijkstra.reached(s)) {
 		      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
 		      	     "Error in a shortest path tree!");
+		    }
+		  }
 		  for(NodeIt n(digraph); n != INVALID; ++n) {
 		    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
 		      Arc a = dijkstra.predArc(n);
 		      Node s = digraph.source(a);
 		      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
 			     "Error in a shortest path tree!");
+		    }
+		  }
+		}
 		int main() {
 		  typedef int Item;
 		  typedef int Prio;
-		  typedef IntIntMap ItemIntMap;
+		  typedef RangeMap<int> ItemIntMap;
 		  Digraph digraph;
 		  IntArcMap length(digraph);
 		  Node source;
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef Digraph::ArcMap<int> LengthMap;
 		  Digraph digraph;
 		  LengthMap length(digraph);
 		  Node start;
 		  /// \todo create own test digraph
 		  std::string f_name;
 		  if( getenv("srcdir") )
 		    f_name = std::string(getenv("srcdir"));
 		  else f_name = ".";
 		  f_name += "/test/dijkstra_test.lgf";
 		  std::ifstream input(f_name.c_str());
 		  check(input, "Input file '" << f_name << "' not found.");
 		  DigraphReader<Digraph>(input, digraph).
 		    readArcMap("capacity", length).
-		    readNode("source", start).
+		  std::istringstream input(test_lgf);
 		  digraphReader(input, digraph).
 		    arcMap("capacity", length).
 		    node("source", source).
 		    run();
+		  {
 		    std::cout << "Checking Bin Heap" << std::endl;
 		    typedef BinHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
+		  }
+		  {
 		    std::cout << "Checking Fib Heap" << std::endl;
 		    typedef FibHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
+		  }
+		  {
 		    std::cout << "Checking Radix Heap" << std::endl;
 		    typedef RadixHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
+		  }
+		  {
 		    std::cout << "Checking Bucket Heap" << std::endl;
 		    typedef BucketHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>(100);
 		    heapIncreaseTest<IntHeap>(100);
 		    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
 		    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
 		    Timer timer;
 		    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
 		    std::cout << timer << std::endl;
 		    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  return 0;
+		}

test/heap_test.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.
+		 *
 		 */
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/dijkstra.h>
 		class IntIntMap : public std::vector<int> {
 		public:
 		  typedef std::vector<int> Parent;
 		  typedef int Key;
 		  typedef int Value;
 		  IntIntMap() : Parent() {}
 		  IntIntMap(int n) : Parent(n) {}
 		  IntIntMap(int n, int v) : Parent(n, v) {}
 		  void set(int key, int value) {
 		    Parent::operator[](key) = value;
+		  }
 		};
 		template <typename _Heap>
 		void heapSortTest(int n) {
 		  typedef _Heap Heap;
 		  IntIntMap map(n, -1);
 		  Heap heap(map);
 		  std::vector<int> v(n);
 		  for (int i = 0; i < n; ++i) {
 		    v[i] = rnd[1000];
 		    heap.push(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < n; ++i) {
 		    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
 		    heap.pop();
+		  }
+		}
 		template <typename _Heap>
 		void heapIncreaseTest(int n) {
 		  typedef _Heap Heap;
 		  IntIntMap map(n, -1);
 		  Heap heap(map);
 		  std::vector<int> v(n);
 		  for (int i = 0; i < n; ++i) {
 		    v[i] = rnd[1000];
 		    heap.push(i, v[i]);
+		  }
 		  for (int i = 0; i < n; ++i) {
 		    v[i] += rnd[1000];
 		    heap.increase(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < n; ++i) {
 		    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
 		    heap.pop();
+		  }
+		}
 		template <typename _Digraph, typename _LengthMap, typename _Heap>
 		void dijkstraHeapTest(_Digraph& digraph, _LengthMap& length,
 				      typename _Digraph::Node& start) {
 		  typedef _Heap Heap;
 		  typedef _Digraph Digraph;
 		  typedef _LengthMap LengthMap;
 		  typedef typename Digraph::Node Node;
 		  typedef typename Digraph::Arc Arc;
 		  typedef typename Digraph::NodeIt NodeIt;
 		  typedef typename Digraph::ArcIt ArcIt;
 		  typename Dijkstra<Digraph, LengthMap>::template DefStandardHeap<Heap>::
 		    Create dijkstra(digraph, length);
 		  dijkstra.run(start);
 		  for(ArcIt e(digraph); e!=INVALID; ++e) {
 		    Node u=digraph.source(e);
 		    Node v=digraph.target(e);
 		    if (dijkstra.reached(u)) {
 		      check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
 		      	     "Error in a shortest path tree arc!");
+		    }
+		  }
 		  for(NodeIt v(digraph); v!=INVALID; ++v) {
 		    if ( dijkstra.reached(v) && dijkstra.predArc(v) != INVALID ) {
 		      Arc e=dijkstra.predArc(v);
 		      Node u=digraph.source(e);
 		      check( dijkstra.dist(v) - dijkstra .dist(u) == length[e],
 			     "Error in a shortest path tree arc!");
+		    }
+		  }
+		}

0 comments (0 inline)

RhodeCode

Login to your account