1.1 --- a/test/Makefile.am Fri Oct 14 11:02:34 2005 +0000
1.2 +++ b/test/Makefile.am Fri Oct 14 11:03:40 2005 +0000
1.3 @@ -22,6 +22,7 @@
1.4 kruskal_test \
1.5 max_matching_test \
1.6 maps_test \
1.7 + matrix_maps_test \
1.8 min_cost_flow_test \
1.9 suurballe_test \
1.10 path_test \
1.11 @@ -54,6 +55,7 @@
1.12 graph_adaptor_test_SOURCES = graph_adaptor_test.cc
1.13 kruskal_test_SOURCES = kruskal_test.cc
1.14 maps_test_SOURCES = maps_test.cc
1.15 +matrix_maps_test_SOURCES = matrix_maps_test.cc
1.16 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
1.17 max_matching_test_SOURCES = max_matching_test.cc
1.18 suurballe_test_SOURCES = suurballe_test.cc
2.1 --- a/test/graph_test.h Fri Oct 14 11:02:34 2005 +0000
2.2 +++ b/test/graph_test.h Fri Oct 14 11:03:40 2005 +0000
2.3 @@ -16,7 +16,7 @@
2.4 #ifndef LEMON_TEST_GRAPH_TEST_H
2.5 #define LEMON_TEST_GRAPH_TEST_H
2.6
2.7 -
2.8 +#include <lemon/graph_utils.h>
2.9 #include "test_tools.h"
2.10
2.11 //! \ingroup misc
2.12 @@ -80,6 +80,19 @@
2.13 checkBidirPetersen(G, num);
2.14 }
2.15
2.16 + template <class Graph>
2.17 + void checkGraphIterators(const Graph& graph) {
2.18 + typedef typename Graph::Node Node;
2.19 + typedef typename Graph::NodeIt NodeIt;
2.20 + typedef typename Graph::Edge Edge;
2.21 + typedef typename Graph::EdgeIt EdgeIt;
2.22 + typedef typename Graph::InEdgeIt InEdgeIt;
2.23 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.24 + typedef ConEdgeIt<Graph> ConEdgeIt;
2.25 +
2.26 + for (NodeIt it(graph); it != INVALID; ++it) {}
2.27 + }
2.28 +
2.29 ///\file
2.30 ///\todo Check target(), source() as well;
2.31
3.1 --- a/test/graph_utils_test.cc Fri Oct 14 11:02:34 2005 +0000
3.2 +++ b/test/graph_utils_test.cc Fri Oct 14 11:03:40 2005 +0000
3.3 @@ -77,6 +77,46 @@
3.4 checkSnapDeg<ListGraph>();
3.5 checkSnapDeg<SmartGraph>();
3.6
3.7 + {
3.8 + const int nodeNum = 10;
3.9 + const int edgeNum = 100;
3.10 + ListGraph graph;
3.11 + InDegMap<ListGraph> inDeg(graph);
3.12 + std::vector<ListGraph::Node> nodes(nodeNum);
3.13 + for (int i = 0; i < nodeNum; ++i) {
3.14 + nodes[i] = graph.addNode();
3.15 + }
3.16 + std::vector<ListGraph::Edge> edges(edgeNum);
3.17 + for (int i = 0; i < edgeNum; ++i) {
3.18 + edges[i] =
3.19 + graph.addEdge(nodes[urandom(nodeNum)], nodes[urandom(nodeNum)]);
3.20 + }
3.21 + for (int i = 0; i < nodeNum; ++i) {
3.22 + check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
3.23 + "Wrong in degree map");
3.24 + }
3.25 + for (int i = 0; i < edgeNum; ++i) {
3.26 + graph.changeTarget(edges[i], nodes[urandom(nodeNum)]);
3.27 + }
3.28 + for (int i = 0; i < nodeNum; ++i) {
3.29 + check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
3.30 + "Wrong in degree map");
3.31 + }
3.32 + for (int i = 0; i < edgeNum; ++i) {
3.33 + graph.changeSource(edges[i], nodes[urandom(nodeNum)]);
3.34 + }
3.35 + for (int i = 0; i < nodeNum; ++i) {
3.36 + check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
3.37 + "Wrong in degree map");
3.38 + }
3.39 + for (int i = 0; i < edgeNum; ++i) {
3.40 + graph.reverseEdge(edges[i]);
3.41 + }
3.42 + for (int i = 0; i < nodeNum; ++i) {
3.43 + check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]),
3.44 + "Wrong in degree map");
3.45 + }
3.46 + }
3.47
3.48 ///Everything is OK
3.49 std::cout << __FILE__ ": All tests passed.\n";
4.1 --- a/test/heap_test.cc Fri Oct 14 11:02:34 2005 +0000
4.2 +++ b/test/heap_test.cc Fri Oct 14 11:03:40 2005 +0000
4.3 @@ -15,11 +15,13 @@
4.4 #include <lemon/bin_heap.h>
4.5 #include <lemon/fib_heap.h>
4.6 #include <lemon/radix_heap.h>
4.7 +#include <lemon/linear_heap.h>
4.8
4.9 #include "test_tools.h"
4.10
4.11 #include "heap_test.h"
4.12
4.13 +#include <lemon/time_measure.h>
4.14
4.15 using namespace lemon;
4.16 using namespace lemon::concept;
4.17 @@ -65,7 +67,9 @@
4.18
4.19 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
4.20 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
4.21 + Timer timer;
4.22 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
4.23 + std::cout << timer << std::endl;
4.24 }
4.25 {
4.26 std::cerr << "Checking Fib Heap" << std::endl;
4.27 @@ -77,7 +81,9 @@
4.28
4.29 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
4.30 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
4.31 + Timer timer;
4.32 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
4.33 + std::cout << timer << std::endl;
4.34 }
4.35 {
4.36 std::cerr << "Checking Radix Heap" << std::endl;
4.37 @@ -89,7 +95,24 @@
4.38
4.39 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
4.40 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
4.41 + Timer timer;
4.42 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
4.43 + std::cout << timer << std::endl;
4.44 + }
4.45 +
4.46 + {
4.47 + std::cerr << "Checking Linear Heap" << std::endl;
4.48 +
4.49 + typedef LinearHeap<Item, ItemIntMap> IntHeap;
4.50 + checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
4.51 + heapSortTest<IntHeap>(100);
4.52 + heapIncreaseTest<IntHeap>(100);
4.53 +
4.54 + typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
4.55 + checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
4.56 + Timer timer;
4.57 + dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
4.58 + std::cout << timer << std::endl;
4.59 }
4.60
4.61 std::cout << __FILE__ ": All tests passed.\n";
5.1 --- a/test/heap_test.h Fri Oct 14 11:02:34 2005 +0000
5.2 +++ b/test/heap_test.h Fri Oct 14 11:03:40 2005 +0000
5.3 @@ -1,4 +1,4 @@
5.4 -// -+- c++ -+-
5.5 +// -*- c++ -*-
5.6
5.7 #include <vector>
5.8 #include <algorithm>
5.9 @@ -65,11 +65,6 @@
5.10
5.11
5.12
5.13 -template <typename _Traits, typename _Heap>
5.14 -struct DefHeapTraits : public _Traits {
5.15 - typedef _Heap Heap;
5.16 -};
5.17 -
5.18 template <typename _Graph, typename _LengthMap, typename _Heap>
5.19 void dijkstraHeapTest(_Graph& graph, _LengthMap& length,
5.20 typename _Graph::Node& start) {
5.21 @@ -83,9 +78,8 @@
5.22 typedef typename Graph::NodeIt NodeIt;
5.23 typedef typename Graph::EdgeIt EdgeIt;
5.24
5.25 - Dijkstra<Graph, LengthMap,
5.26 - DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> >
5.27 - dijkstra(graph, length);
5.28 + typename Dijkstra<Graph, LengthMap>::template DefHeap<Heap>::
5.29 + Create dijkstra(graph, length);
5.30
5.31 dijkstra.run(start);
5.32
5.33 @@ -94,7 +88,7 @@
5.34 Node v=graph.target(e);
5.35 if (dijkstra.reached(u)) {
5.36 check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e],
5.37 - "Error in a shortest path tree edge!");
5.38 + "Error in a shortest path tree edge!");
5.39 }
5.40 }
5.41
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/test/matrix_maps_test.cc Fri Oct 14 11:03:40 2005 +0000
6.3 @@ -0,0 +1,114 @@
6.4 +// -*- c++ -*-
6.5 +
6.6 +#include <iostream>
6.7 +#include <vector>
6.8 +
6.9 +#include <lemon/concept_check.h>
6.10 +
6.11 +#include <lemon/concept/matrix_maps.h>
6.12 +#include <lemon/concept/maps.h>
6.13 +#include <lemon/concept/graph.h>
6.14 +
6.15 +#include <lemon/matrix_maps.h>
6.16 +
6.17 +#include <lemon/smart_graph.h>
6.18 +
6.19 +#include "test_tools.h"
6.20 +#include "graph_test.h"
6.21 +#include "map_test.h"
6.22 +
6.23 +
6.24 +using namespace lemon;
6.25 +using namespace lemon::concept;
6.26 +
6.27 +int main() {
6.28 + typedef SmartGraph Graph;
6.29 + typedef Graph::Node Node;
6.30 +
6.31 + { // checking MatrixMap for int
6.32 + typedef DynamicMatrixMap<Graph, Node, int> IntMatrixMap;
6.33 + checkConcept<ReferenceMatrixMap<Node, Node, int,
6.34 + IntMatrixMap::Reference, IntMatrixMap::ConstReference>,
6.35 + IntMatrixMap>();
6.36 +
6.37 + }
6.38 +
6.39 + { // checking MatrixMap for bool
6.40 + typedef DynamicMatrixMap<Graph, Node, bool> BoolMatrixMap;
6.41 + checkConcept<ReferenceMatrixMap<Node, Node, bool,
6.42 + BoolMatrixMap::Reference, BoolMatrixMap::ConstReference>,
6.43 + BoolMatrixMap>();
6.44 +
6.45 + }
6.46 +
6.47 + {
6.48 + Graph graph;
6.49 + typedef DynamicMatrixMap<Graph, Node, int> IntMatrixMap;
6.50 + IntMatrixMap matrix(graph);
6.51 + for (int i = 0; i < 10; ++i) {
6.52 + graph.addNode();
6.53 + }
6.54 + for (Graph::NodeIt it(graph); it != INVALID; ++it) {
6.55 + for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
6.56 + int val = urandom(100);
6.57 + matrix.set(it, jt, val);
6.58 + check(matrix(it, jt) == val, "Wrong assign");
6.59 + check(matrix(it, jt) == matrixColMap(matrix, it)[jt], "Wrong colMap");
6.60 + check(matrix(it, jt) == matrixRowMap(matrix, jt)[it], "Wrong rowMap");
6.61 + }
6.62 + }
6.63 + const IntMatrixMap& cm = matrix;
6.64 + for (Graph::NodeIt it(graph); it != INVALID; ++it) {
6.65 + for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
6.66 + check(cm(it, jt) == matrixColMap(cm, it)[jt], "Wrong colMap");
6.67 + check(cm(it, jt) == matrixRowMap(cm, jt)[it], "Wrong rowMap");
6.68 + }
6.69 + }
6.70 + }
6.71 +
6.72 + { // checking MatrixMap for int
6.73 + typedef DynamicSymMatrixMap<Graph, Node, int> IntMatrixMap;
6.74 + checkConcept<ReferenceMatrixMap<Node, Node, int,
6.75 + IntMatrixMap::Reference, IntMatrixMap::ConstReference>,
6.76 + IntMatrixMap>();
6.77 +
6.78 + }
6.79 +
6.80 + { // checking MatrixMap for bool
6.81 + typedef DynamicSymMatrixMap<Graph, Node, bool> BoolMatrixMap;
6.82 + checkConcept<ReferenceMatrixMap<Node, Node, bool,
6.83 + BoolMatrixMap::Reference, BoolMatrixMap::ConstReference>,
6.84 + BoolMatrixMap>();
6.85 +
6.86 + }
6.87 +
6.88 + {
6.89 + Graph graph;
6.90 + typedef DynamicSymMatrixMap<Graph, Node, int> IntMatrixMap;
6.91 + IntMatrixMap matrix(graph);
6.92 + for (int i = 0; i < 10; ++i) {
6.93 + graph.addNode();
6.94 + }
6.95 + for (Graph::NodeIt it(graph); it != INVALID; ++it) {
6.96 + for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
6.97 + int val = urandom(100);
6.98 + matrix.set(it, jt, val);
6.99 + check(matrix(it, jt) == val, "Wrong assign");
6.100 + check(matrix(jt, it) == val, "Wrong assign");
6.101 + check(matrix(it, jt) == matrixColMap(matrix, it)[jt], "Wrong colMap");
6.102 + check(matrix(it, jt) == matrixRowMap(matrix, jt)[it], "Wrong rowMap");
6.103 + }
6.104 + }
6.105 + const IntMatrixMap& cm = matrix;
6.106 + for (Graph::NodeIt it(graph); it != INVALID; ++it) {
6.107 + for (Graph::NodeIt jt(graph); jt != INVALID; ++jt) {
6.108 + check(cm(it, jt) == matrixColMap(cm, it)[jt], "Wrong colMap");
6.109 + check(cm(it, jt) == matrixRowMap(cm, jt)[it], "Wrong rowMap");
6.110 + }
6.111 + }
6.112 + }
6.113 +
6.114 + std::cout << __FILE__ ": All tests passed.\n";
6.115 +
6.116 + return 0;
6.117 +}
7.1 --- a/test/test_tools.h Fri Oct 14 11:02:34 2005 +0000
7.2 +++ b/test/test_tools.h Fri Oct 14 11:03:40 2005 +0000
7.3 @@ -20,7 +20,11 @@
7.4 #include <iostream>
7.5 #include <vector>
7.6
7.7 +#include <cstdlib>
7.8 +#include <ctime>
7.9 +
7.10 #include <lemon/invalid.h>
7.11 +#include <lemon/concept_check.h>
7.12
7.13 using namespace lemon;
7.14
7.15 @@ -170,4 +174,16 @@
7.16 return n;
7.17 }
7.18
7.19 +int _urandom_init() {
7.20 + int seed = time(0);
7.21 + srand(seed);
7.22 + return seed;
7.23 +}
7.24 +
7.25 +int urandom(int n) {
7.26 + static int seed = _urandom_init();
7.27 + ignore_unused_variable_warning(seed);
7.28 + return (int)(rand() / (1.0 + RAND_MAX) * n);
7.29 +}
7.30 +
7.31 #endif