diff --git a/test/graph_utils_test.cc b/test/graph_utils_test.cc
--- a/test/graph_utils_test.cc
+++ b/test/graph_utils_test.cc
@@ -35,18 +35,18 @@
 
   {
     Digraph digraph;
+    typename Digraph::template NodeMap<int> nodes(digraph);
+    std::vector<Node> invNodes;
     for (int i = 0; i < 10; ++i) {
-      digraph.addNode();
+      invNodes.push_back(digraph.addNode());
+      nodes[invNodes.back()]=invNodes.size()-1;
     }
-    DescriptorMap<Digraph, Node> nodes(digraph);
-    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
     for (int i = 0; i < 100; ++i) {
       int src = rnd[invNodes.size()];
       int trg = rnd[invNodes.size()];
       digraph.addArc(invNodes[src], invNodes[trg]);
     }
     typename Digraph::template ArcMap<bool> found(digraph, false);
-    DescriptorMap<Digraph, Arc> arcs(digraph);
     for (NodeIt src(digraph); src != INVALID; ++src) {
       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
         for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
@@ -110,18 +110,18 @@
 void checkFindEdges() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   Graph graph;
+  typename Graph::template NodeMap<int> nodes(graph);
+  std::vector<Node> invNodes;
   for (int i = 0; i < 10; ++i) {
-    graph.addNode();
+    invNodes.push_back(graph.addNode());
+    nodes[invNodes.back()]=invNodes.size()-1;
   }
-  DescriptorMap<Graph, Node> nodes(graph);
-  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
   for (int i = 0; i < 100; ++i) {
     int src = rnd[invNodes.size()];
     int trg = rnd[invNodes.size()];
     graph.addEdge(invNodes[src], invNodes[trg]);
   }
   typename Graph::template EdgeMap<int> found(graph, 0);
-  DescriptorMap<Graph, Edge> edges(graph);
   for (NodeIt src(graph); src != INVALID; ++src) {
     for (NodeIt trg(graph); trg != INVALID; ++trg) {
       for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {