# HG changeset patch
# User deba
# Date 1129287820 0
# Node ID eb8bb91ba9e29a2a4a0f488eda81c7ebe8a9699a
# Parent  0c7d717b953833864c1b332d70b270361cfd54c8
Updating tests

diff -r 0c7d717b9538 -r eb8bb91ba9e2 test/Makefile.am
--- a/test/Makefile.am	Fri Oct 14 11:02:34 2005 +0000
+++ b/test/Makefile.am	Fri Oct 14 11:03:40 2005 +0000
@@ -22,6 +22,7 @@
 	kruskal_test \
 	max_matching_test \
 	maps_test \
+	matrix_maps_test \
 	min_cost_flow_test \
 	suurballe_test \
 	path_test \
@@ -54,6 +55,7 @@
 graph_adaptor_test_SOURCES = graph_adaptor_test.cc
 kruskal_test_SOURCES = kruskal_test.cc
 maps_test_SOURCES = maps_test.cc
+matrix_maps_test_SOURCES = matrix_maps_test.cc
 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
 max_matching_test_SOURCES = max_matching_test.cc
 suurballe_test_SOURCES = suurballe_test.cc
diff -r 0c7d717b9538 -r eb8bb91ba9e2 test/graph_test.h
--- a/test/graph_test.h	Fri Oct 14 11:02:34 2005 +0000
+++ b/test/graph_test.h	Fri Oct 14 11:03:40 2005 +0000
@@ -16,7 +16,7 @@
 #ifndef LEMON_TEST_GRAPH_TEST_H
 #define LEMON_TEST_GRAPH_TEST_H
 
-
+#include <lemon/graph_utils.h>
 #include "test_tools.h"
 
 //! \ingroup misc
@@ -80,6 +80,19 @@
     checkBidirPetersen(G, num);
   }
 
+  template <class Graph> 
+  void checkGraphIterators(const Graph& graph) {
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef ConEdgeIt<Graph> ConEdgeIt;
+    
+    for (NodeIt it(graph); it != INVALID; ++it) {}
+  }
+
   ///\file
   ///\todo Check target(), source() as well;
 
diff -r 0c7d717b9538 -r eb8bb91ba9e2 test/graph_utils_test.cc
--- a/test/graph_utils_test.cc	Fri Oct 14 11:02:34 2005 +0000
+++ b/test/graph_utils_test.cc	Fri Oct 14 11:03:40 2005 +0000
@@ -77,6 +77,46 @@
   checkSnapDeg<ListGraph>();
   checkSnapDeg<SmartGraph>();
   
+  {
+    const int nodeNum = 10;
+    const int edgeNum = 100;
+    ListGraph graph;
+    InDegMap<ListGraph> inDeg(graph);
+    std::vector<ListGraph::Node> nodes(nodeNum);
+    for (int i = 0; i < nodeNum; ++i) {
+      nodes[i] = graph.addNode();
+    }
+    std::vector<ListGraph::Edge> edges(edgeNum);
+    for (int i = 0; i < edgeNum; ++i) {
+      edges[i] = 
+	graph.addEdge(nodes[urandom(nodeNum)], nodes[urandom(nodeNum)]);
+    }
+    for (int i = 0; i < nodeNum; ++i) {
+      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]), 
+	    "Wrong in degree map");
+    }
+    for (int i = 0; i < edgeNum; ++i) {
+      graph.changeTarget(edges[i], nodes[urandom(nodeNum)]);
+    }
+    for (int i = 0; i < nodeNum; ++i) {
+      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
+	    "Wrong in degree map");
+    }
+    for (int i = 0; i < edgeNum; ++i) {
+      graph.changeSource(edges[i], nodes[urandom(nodeNum)]);
+    }
+    for (int i = 0; i < nodeNum; ++i) {
+      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]), 
+	    "Wrong in degree map");
+    }
+    for (int i = 0; i < edgeNum; ++i) {
+      graph.reverseEdge(edges[i]);
+    }
+    for (int i = 0; i < nodeNum; ++i) {
+      check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]), 
+	    "Wrong in degree map");
+    }
+  }
 
   ///Everything is OK
   std::cout << __FILE__ ": All tests passed.\n";
diff -r 0c7d717b9538 -r eb8bb91ba9e2 test/heap_test.cc
--- a/test/heap_test.cc	Fri Oct 14 11:02:34 2005 +0000
+++ b/test/heap_test.cc	Fri Oct 14 11:03:40 2005 +0000
@@ -15,11 +15,13 @@
 #include <lemon/bin_heap.h>
 #include <lemon/fib_heap.h>
 #include <lemon/radix_heap.h>
+#include <lemon/linear_heap.h>
 
 #include "test_tools.h"
 
 #include "heap_test.h"
 
+#include <lemon/time_measure.h>
 
 using namespace lemon;
 using namespace lemon::concept;
@@ -65,7 +67,9 @@
     
     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
+    std::cout << timer << std::endl;
   }
   {
     std::cerr << "Checking Fib Heap" << std::endl;
@@ -77,7 +81,9 @@
 
     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
+    std::cout << timer << std::endl;
   }
   {
     std::cerr << "Checking Radix Heap" << std::endl;
@@ -89,7 +95,24 @@
 
     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
+    std::cout << timer << std::endl;
+  }
+
+  {
+    std::cerr << "Checking Linear Heap" << std::endl;
+
+    typedef LinearHeap<Item, ItemIntMap> IntHeap;
+    checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
+    heapSortTest<IntHeap>(100);
+    heapIncreaseTest<IntHeap>(100);
+
+    typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
+    checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
+    Timer timer;
+    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
+    std::cout << timer << std::endl;
   }
 
   std::cout << __FILE__ ": All tests passed.\n";
diff -r 0c7d717b9538 -r eb8bb91ba9e2 test/heap_test.h
--- a/test/heap_test.h	Fri Oct 14 11:02:34 2005 +0000
+++ b/test/heap_test.h	Fri Oct 14 11:03:40 2005 +0000
@@ -1,4 +1,4 @@
-// -+- c++ -+-
+// -*- c++ -*-
 
 #include <vector>
 #include <algorithm>
@@ -65,11 +65,6 @@
 
 
 
-template <typename _Traits, typename _Heap>
-struct DefHeapTraits : public _Traits {
-  typedef _Heap Heap;
-};
-
 template <typename _Graph, typename _LengthMap, typename _Heap>
 void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
 		      typename _Graph::Node& start) {
@@ -83,9 +78,8 @@
   typedef typename Graph::NodeIt NodeIt;
   typedef typename Graph::EdgeIt EdgeIt;
 
-  Dijkstra<Graph, LengthMap, 
-    DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> > 
-    dijkstra(graph, length);
+  typename Dijkstra<Graph, LengthMap>::template DefHeap<Heap>::
+    Create dijkstra(graph, length);
 
   dijkstra.run(start);
 
@@ -94,7 +88,7 @@
     Node v=graph.target(e);
     if (dijkstra.reached(u)) {
       check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
-	     "Error in a shortest path tree edge!");
+      	     "Error in a shortest path tree edge!");
     }
   }
 
diff -r 0c7d717b9538 -r eb8bb91ba9e2 test/matrix_maps_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/matrix_maps_test.cc	Fri Oct 14 11:03:40 2005 +0000
@@ -0,0 +1,114 @@
+// -*- c++ -*-
+
+#include <iostream>
+#include <vector>
+
+#include <lemon/concept_check.h>
+
+#include <lemon/concept/matrix_maps.h>
+#include <lemon/concept/maps.h>
+#include <lemon/concept/graph.h>
+
+#include <lemon/matrix_maps.h>
+
+#include <lemon/smart_graph.h>
+
+#include "test_tools.h"
+#include "graph_test.h"
+#include "map_test.h"
+
+
+using namespace lemon;
+using namespace lemon::concept;
+
+int main() {
+  typedef SmartGraph Graph;
+  typedef Graph::Node Node;
+
+  { // checking MatrixMap for int
+    typedef DynamicMatrixMap<Graph, Node, int> IntMatrixMap;
+    checkConcept<ReferenceMatrixMap<Node, Node, int, 
+      IntMatrixMap::Reference, IntMatrixMap::ConstReference>,
+      IntMatrixMap>();
+
+  }
+
+  { // checking MatrixMap for bool
+    typedef DynamicMatrixMap<Graph, Node, bool> BoolMatrixMap;
+    checkConcept<ReferenceMatrixMap<Node, Node, bool, 
+      BoolMatrixMap::Reference, BoolMatrixMap::ConstReference>,
+      BoolMatrixMap>();
+
+  }
+
+  {
+    Graph graph;
+    typedef DynamicMatrixMap<Graph, Node, int> IntMatrixMap;
+    IntMatrixMap matrix(graph);
+    for (int i = 0; i < 10; ++i) {
+      graph.addNode();
+    }
+    for (Graph::NodeIt it(graph); it != INVALID; ++it) {
+      for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
+	int val = urandom(100);
+	matrix.set(it, jt, val);
+	check(matrix(it, jt) == val, "Wrong assign");
+	check(matrix(it, jt) == matrixColMap(matrix, it)[jt], "Wrong colMap");
+	check(matrix(it, jt) == matrixRowMap(matrix, jt)[it], "Wrong rowMap");
+      }
+    }
+    const IntMatrixMap& cm = matrix;
+    for (Graph::NodeIt it(graph); it != INVALID; ++it) {
+      for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
+	check(cm(it, jt) == matrixColMap(cm, it)[jt], "Wrong colMap");
+	check(cm(it, jt) == matrixRowMap(cm, jt)[it], "Wrong rowMap");
+      }
+    }
+  }
+
+  { // checking MatrixMap for int
+    typedef DynamicSymMatrixMap<Graph, Node, int> IntMatrixMap;
+    checkConcept<ReferenceMatrixMap<Node, Node, int, 
+      IntMatrixMap::Reference, IntMatrixMap::ConstReference>,
+      IntMatrixMap>();
+
+  }
+
+  { // checking MatrixMap for bool
+    typedef DynamicSymMatrixMap<Graph, Node, bool> BoolMatrixMap;
+    checkConcept<ReferenceMatrixMap<Node, Node, bool, 
+      BoolMatrixMap::Reference, BoolMatrixMap::ConstReference>,
+      BoolMatrixMap>();
+
+  }
+
+  {
+    Graph graph;
+    typedef DynamicSymMatrixMap<Graph, Node, int> IntMatrixMap;
+    IntMatrixMap matrix(graph);
+    for (int i = 0; i < 10; ++i) {
+      graph.addNode();
+    }
+    for (Graph::NodeIt it(graph); it != INVALID; ++it) {
+      for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
+	int val = urandom(100);
+	matrix.set(it, jt, val);
+	check(matrix(it, jt) == val, "Wrong assign");
+	check(matrix(jt, it) == val, "Wrong assign");
+	check(matrix(it, jt) == matrixColMap(matrix, it)[jt], "Wrong colMap");
+	check(matrix(it, jt) == matrixRowMap(matrix, jt)[it], "Wrong rowMap");
+      }
+    }
+    const IntMatrixMap& cm = matrix;
+    for (Graph::NodeIt it(graph); it != INVALID; ++it) {
+      for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
+	check(cm(it, jt) == matrixColMap(cm, it)[jt], "Wrong colMap");
+	check(cm(it, jt) == matrixRowMap(cm, jt)[it], "Wrong rowMap");
+      }
+    }
+  }
+
+  std::cout << __FILE__ ": All tests passed.\n";
+
+  return 0;
+}
diff -r 0c7d717b9538 -r eb8bb91ba9e2 test/test_tools.h
--- a/test/test_tools.h	Fri Oct 14 11:02:34 2005 +0000
+++ b/test/test_tools.h	Fri Oct 14 11:03:40 2005 +0000
@@ -20,7 +20,11 @@
 #include <iostream>
 #include <vector>
 
+#include <cstdlib>
+#include <ctime>
+
 #include <lemon/invalid.h>
+#include <lemon/concept_check.h>
 
 using namespace lemon;
 
@@ -170,4 +174,16 @@
  return n;
 }
 
+int _urandom_init() {
+  int seed = time(0);
+  srand(seed);
+  return seed;
+}
+
+int urandom(int n) {
+  static int seed = _urandom_init();
+  ignore_unused_variable_warning(seed);
+  return (int)(rand() / (1.0 + RAND_MAX) * n);
+}
+
 #endif