Changeset 1728:eb8bb91ba9e2 in lemon-0.x

Timestamp:

10/14/05 13:03:40 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2255

Message:

Updating tests

Location:

test

Files:

• Makefile.am (modified) (2 diffs)
• graph_test.h (modified) (2 diffs)
• graph_utils_test.cc (modified) (1 diff)
• heap_test.cc (modified) (5 diffs)
• heap_test.h (modified) (4 diffs)
• matrix_maps_test.cc (added)
• test_tools.h (modified) (2 diffs)

test/Makefile.am

@@ -23 +23 @@
         max_matching_test \
         maps_test \
+        matrix_maps_test \
         min_cost_flow_test \
         suurballe_test \
@@ -55 +56 @@
 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

test/graph_test.h

@@ -17 +17 @@
 #define LEMON_TEST_GRAPH_TEST_H
 
-
+#include <lemon/graph_utils.h>
 #include "test_tools.h"
 
@@ -81 +81 @@
   }
 
+  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;

test/graph_utils_test.cc

@@ -78 +78 @@
   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

test/heap_test.cc

@@ -16 +16 @@
 #include <lemon/fib_heap.h>
 #include <lemon/radix_heap.h>
+#include <lemon/linear_heap.h>
 
 #include "test_tools.h"
@@ -21 +22 @@
 #include "heap_test.h"
 
+#include <lemon/time_measure.h>
 
 using namespace lemon;
@@ -66 +68 @@
     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;
   }
   {
@@ -78 +82 @@
     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;
   }
   {
@@ -90 +96 @@
     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;
   }
 

test/heap_test.h

@@ -1 @@
-// -+- c++ -+-
+// -*- c++ -*-
 
 #include <vector>
@@ -66 +66 @@
 
 
-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,
@@ -84 +79 @@
   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);
@@ -95 +89 @@
     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!");
     }
   }

test/test_tools.h

@@ -21 +21 @@
 #include <vector>
 
+#include <cstdlib>
+#include <ctime>
+
 #include <lemon/invalid.h>
+#include <lemon/concept_check.h>
 
 using namespace lemon;
@@ -171 +175 @@
 }
 
+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