Index: test/Makefile.am
===================================================================
--- test/Makefile.am	(revision 1711)
+++ test/Makefile.am	(revision 1728)
@@ -23,4 +23,5 @@
 	max_matching_test \
 	maps_test \
+	matrix_maps_test \
 	min_cost_flow_test \
 	suurballe_test \
@@ -55,4 +56,5 @@
 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
Index: test/graph_test.h
===================================================================
--- test/graph_test.h	(revision 1435)
+++ test/graph_test.h	(revision 1728)
@@ -17,5 +17,5 @@
 #define LEMON_TEST_GRAPH_TEST_H
 
-
+#include <lemon/graph_utils.h>
 #include "test_tools.h"
 
@@ -81,4 +81,17 @@
   }
 
+  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;
Index: test/graph_utils_test.cc
===================================================================
--- test/graph_utils_test.cc	(revision 1568)
+++ test/graph_utils_test.cc	(revision 1728)
@@ -78,4 +78,44 @@
   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
Index: test/heap_test.cc
===================================================================
--- test/heap_test.cc	(revision 1435)
+++ test/heap_test.cc	(revision 1728)
@@ -16,4 +16,5 @@
 #include <lemon/fib_heap.h>
 #include <lemon/radix_heap.h>
+#include <lemon/linear_heap.h>
 
 #include "test_tools.h"
@@ -21,4 +22,5 @@
 #include "heap_test.h"
 
+#include <lemon/time_measure.h>
 
 using namespace lemon;
@@ -66,5 +68,7 @@
     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,5 +82,7 @@
     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,5 +96,22 @@
     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;
   }
 
Index: test/heap_test.h
===================================================================
--- test/heap_test.h	(revision 1435)
+++ test/heap_test.h	(revision 1728)
@@ -1,3 +1,3 @@
-// -+- c++ -+-
+// -*- c++ -*-
 
 #include <vector>
@@ -66,9 +66,4 @@
 
 
-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,7 +79,6 @@
   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,5 +89,5 @@
     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!");
     }
   }
Index: test/matrix_maps_test.cc
===================================================================
--- test/matrix_maps_test.cc	(revision 1728)
+++ test/matrix_maps_test.cc	(revision 1728)
@@ -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;
+}
Index: test/test_tools.h
===================================================================
--- test/test_tools.h	(revision 1716)
+++ test/test_tools.h	(revision 1728)
@@ -21,5 +21,9 @@
 #include <vector>
 
+#include <cstdlib>
+#include <ctime>
+
 #include <lemon/invalid.h>
+#include <lemon/concept_check.h>
 
 using namespace lemon;
@@ -171,3 +175,15 @@
 }
 
+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
