# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 1216650628 -7200
# Node ID b6732e0d38c5c5e6b21123d8425a62591491e391
# Parent  33f8d69e642a7c456c127282bc420a2703fb14c1
Reworking graph testing

 - The graph tests check more graph functionality.
 - The petersen graph is too regular, therefore special graphs are used.
 - The graph_test.h contains just general tools to test graphs.

diff -r 33f8d69e642a -r b6732e0d38c5 test/Makefile.am
--- a/test/Makefile.am	Fri Jul 18 17:26:12 2008 +0100
+++ b/test/Makefile.am	Mon Jul 21 16:30:28 2008 +0200
@@ -3,7 +3,6 @@
 
 noinst_HEADERS += \
 	test/graph_test.h \
-	test/graph_maps_test.h \
         test/test_tools.h
 
 check_PROGRAMS += \
diff -r 33f8d69e642a -r b6732e0d38c5 test/bfs_test.cc
--- a/test/bfs_test.cc	Fri Jul 18 17:26:12 2008 +0100
+++ b/test/bfs_test.cc	Mon Jul 21 16:30:28 2008 +0200
@@ -19,6 +19,7 @@
 #include <lemon/concepts/digraph.h>
 #include <lemon/smart_graph.h>
 #include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
 #include <lemon/bfs.h>
 #include <lemon/path.h>
 
@@ -27,6 +28,28 @@
 
 using namespace lemon;
 
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "@arcs\n"
+  "     label\n"
+  "0 1  0\n"
+  "1 2  1\n"
+  "2 3  2\n"
+  "3 4  3\n"
+  "0 3  4\n"
+  "0 3  5\n"
+  "5 2  6\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 4\n";
+
 void checkBfsCompile()
 {
   typedef concepts::Digraph Digraph;
@@ -49,6 +72,7 @@
   e  = bfs_test.predArc(n);
   n  = bfs_test.predNode(n);
   d  = bfs_test.distMap();
+
   p  = bfs_test.predMap();
   //  pn = bfs_test.predNodeMap();
   b  = bfs_test.reached(n);
@@ -80,41 +104,45 @@
 
   Digraph G;
   Node s, t;
-  PetStruct<Digraph> ps = addPetersen(G, 5);
 
-  s=ps.outer[2];
-  t=ps.inner[0];
+  std::istringstream input(test_lgf);
+  digraphReader(input, G).
+    node("source", s).
+    node("target", t).
+    run();
 
   Bfs<Digraph> bfs_test(G);
   bfs_test.run(s);
 
-  check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
+  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
 
   Path<Digraph> p = bfs_test.path(t);
-  check(p.length()==3,"path() found a wrong path.");
+  check(p.length()==2,"path() found a wrong path.");
   check(checkPath(G, p),"path() found a wrong path.");
   check(pathSource(G, p) == s,"path() found a wrong path.");
   check(pathTarget(G, p) == t,"path() found a wrong path.");
 
 
-  for(ArcIt e(G); e!=INVALID; ++e) {
-    Node u=G.source(e);
-    Node v=G.target(e);
+  for(ArcIt a(G); a!=INVALID; ++a) {
+    Node u=G.source(a);
+    Node v=G.target(a);
     check( !bfs_test.reached(u) ||
            (bfs_test.dist(v) <= bfs_test.dist(u)+1),
-           "Wrong output.");
+           "Wrong output." << G.id(v) << ' ' << G.id(u));
   }
 
   for(NodeIt v(G); v!=INVALID; ++v) {
-    check(bfs_test.reached(v),"Each node should be reached.");
-    if ( bfs_test.predArc(v)!=INVALID ) {
-      Arc e=bfs_test.predArc(v);
-      Node u=G.source(e);
-      check(u==bfs_test.predNode(v),"Wrong tree.");
-      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
-            "Wrong distance. Difference: "
-            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
-                        - 1));
+    if (bfs_test.reached(v)) {
+      check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
+      if (bfs_test.predArc(v)!=INVALID ) {
+        Arc a=bfs_test.predArc(v);
+        Node u=G.source(a);
+        check(u==bfs_test.predNode(v),"Wrong tree.");
+        check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
+              "Wrong distance. Difference: "
+              << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
+                          - 1));
+      }
     }
   }
 }
diff -r 33f8d69e642a -r b6732e0d38c5 test/dfs_test.cc
--- a/test/dfs_test.cc	Fri Jul 18 17:26:12 2008 +0100
+++ b/test/dfs_test.cc	Mon Jul 21 16:30:28 2008 +0200
@@ -19,6 +19,8 @@
 #include <lemon/concepts/digraph.h>
 #include <lemon/smart_graph.h>
 #include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+
 #include <lemon/dfs.h>
 #include <lemon/path.h>
 
@@ -27,6 +29,30 @@
 
 using namespace lemon;
 
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "@arcs\n"
+  "     label\n"
+  "0 1  0\n"
+  "1 2  1\n"
+  "2 3  2\n"
+  "1 4  3\n"
+  "4 2  4\n"
+  "4 5  5\n"
+  "5 0  6\n"
+  "6 3  7\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 5\n";
+
 void checkDfsCompile()
 {
   typedef concepts::Digraph Digraph;
@@ -39,7 +65,6 @@
   bool b;
   DType::DistMap d(G);
   DType::PredMap p(G);
-  //  DType::PredNodeMap pn(G);
 
   DType dfs_test(G);
 
@@ -50,7 +75,6 @@
   n  = dfs_test.predNode(n);
   d  = dfs_test.distMap();
   p  = dfs_test.predMap();
-  //  pn = dfs_test.predNodeMap();
   b  = dfs_test.reached(n);
 
   Path<Digraph> pp = dfs_test.path(n);
@@ -80,10 +104,12 @@
 
   Digraph G;
   Node s, t;
-  PetStruct<Digraph> ps = addPetersen(G, 5);
 
-  s=ps.outer[2];
-  t=ps.inner[0];
+  std::istringstream input(test_lgf);
+  digraphReader(input, G).
+    node("source", s).
+    node("target", t).
+    run();
 
   Dfs<Digraph> dfs_test(G);
   dfs_test.run(s);
@@ -95,14 +121,16 @@
   check(pathTarget(G, p) == t,"path() found a wrong path.");
 
   for(NodeIt v(G); v!=INVALID; ++v) {
-    check(dfs_test.reached(v),"Each node should be reached.");
-    if ( dfs_test.predArc(v)!=INVALID ) {
-      Arc e=dfs_test.predArc(v);
-      Node u=G.source(e);
-      check(u==dfs_test.predNode(v),"Wrong tree.");
-      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
-            "Wrong distance. (" << dfs_test.dist(u) << "->"
-            <<dfs_test.dist(v) << ')');
+    if (dfs_test.reached(v)) {
+      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
+      if (dfs_test.predArc(v)!=INVALID ) {
+        Arc e=dfs_test.predArc(v);
+        Node u=G.source(e);
+        check(u==dfs_test.predNode(v),"Wrong tree.");
+        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
+              "Wrong distance. (" << dfs_test.dist(u) << "->"
+              <<dfs_test.dist(v) << ')');
+      }
     }
   }
 }
diff -r 33f8d69e642a -r b6732e0d38c5 test/digraph_test.cc
--- a/test/digraph_test.cc	Fri Jul 18 17:26:12 2008 +0100
+++ b/test/digraph_test.cc	Mon Jul 21 16:30:28 2008 +0200
@@ -24,12 +24,63 @@
 
 #include "test_tools.h"
 #include "graph_test.h"
-#include "graph_maps_test.h"
 
 using namespace lemon;
 using namespace lemon::concepts;
 
-void check_concepts() {
+template <class Digraph>
+void checkDigraph() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+  Digraph G;
+
+  checkGraphNodeList(G, 0);
+  checkGraphArcList(G, 0);
+
+  Node
+    n1 = G.addNode(),
+    n2 = G.addNode(),
+    n3 = G.addNode();
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 0);
+
+  Arc a1 = G.addArc(n1, n2);
+  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 1);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 0);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 0);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 0);
+
+  checkGraphConArcList(G, 1);
+
+  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 4);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 2);
+
+  checkGraphConArcList(G, 4);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+
+}
+
+
+void checkConcepts() {
   { // Checking digraph components
     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
 
@@ -51,27 +102,23 @@
     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
-    checkDigraphIterators<ListDigraph>();
   }
   { // Checking SmartDigraph
     checkConcept<Digraph, SmartDigraph>();
     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
-    checkDigraphIterators<SmartDigraph>();
   }
 //  { // Checking FullDigraph
 //    checkConcept<Digraph, FullDigraph>();
-//    checkDigraphIterators<FullDigraph>();
 //  }
 //  { // Checking HyperCubeDigraph
 //    checkConcept<Digraph, HyperCubeDigraph>();
-//    checkDigraphIterators<HyperCubeDigraph>();
 //  }
 }
 
 template <typename Digraph>
-void check_graph_validity() {
+void checkDigraphValidity() {
   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   Digraph g;
 
@@ -92,7 +139,7 @@
 }
 
 template <typename Digraph>
-void check_graph_validity_erase() {
+void checkDigraphValidityErase() {
   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   Digraph g;
 
@@ -120,25 +167,19 @@
   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
 }
 
-void check_digraphs() {
+void checkDigraphs() {
   { // Checking ListDigraph
     checkDigraph<ListDigraph>();
-    checkGraphNodeMap<ListDigraph>();
-    checkGraphArcMap<ListDigraph>();
-
-    check_graph_validity_erase<ListDigraph>();
+    checkDigraphValidityErase<ListDigraph>();
   }
   { // Checking SmartDigraph
     checkDigraph<SmartDigraph>();
-    checkGraphNodeMap<SmartDigraph>();
-    checkGraphArcMap<SmartDigraph>();
-
-    check_graph_validity<SmartDigraph>();
+    checkDigraphValidity<SmartDigraph>();
   }
 }
 
 int main() {
-  check_concepts();
-  check_digraphs();
+  checkDigraphs();
+  checkConcepts();
   return 0;
 }
diff -r 33f8d69e642a -r b6732e0d38c5 test/dijkstra_test.cc
--- a/test/dijkstra_test.cc	Fri Jul 18 17:26:12 2008 +0100
+++ b/test/dijkstra_test.cc	Mon Jul 21 16:30:28 2008 +0200
@@ -19,6 +19,8 @@
 #include <lemon/concepts/digraph.h>
 #include <lemon/smart_graph.h>
 #include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+
 #include <lemon/dijkstra.h>
 #include <lemon/path.h>
 
@@ -27,6 +29,27 @@
 
 using namespace lemon;
 
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "@arcs\n"
+  "     label length\n"
+  "0 1  0     1\n"
+  "1 2  1     1\n"
+  "2 3  2     1\n"
+  "0 3  4     5\n"
+  "0 3  5     10\n"
+  "0 3  6     7\n"
+  "4 2  7     1\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 3\n";
+
 void checkDijkstraCompile()
 {
   typedef int VType;
@@ -84,24 +107,22 @@
   Digraph G;
   Node s, t;
   LengthMap length(G);
-  PetStruct<Digraph> ps = addPetersen(G, 5);
 
-  for(int i=0;i<5;i++) {
-    length[ps.outcir[i]]=4;
-    length[ps.incir[i]]=1;
-    length[ps.chords[i]]=10;
-  }
-  s=ps.outer[0];
-  t=ps.inner[1];
+  std::istringstream input(test_lgf);
+  digraphReader(input, G).
+    arcMap("length", length).
+    node("source", s).
+    node("target", t).
+    run();
 
   Dijkstra<Digraph, LengthMap>
         dijkstra_test(G, length);
   dijkstra_test.run(s);
 
-  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
+  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
 
   Path<Digraph> p = dijkstra_test.path(t);
-  check(p.length()==4,"getPath() found a wrong path.");
+  check(p.length()==3,"getPath() found a wrong path.");
   check(checkPath(G, p),"path() found a wrong path.");
   check(pathSource(G, p) == s,"path() found a wrong path.");
   check(pathTarget(G, p) == t,"path() found a wrong path.");
@@ -115,15 +136,17 @@
            dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
   }
 
-  for(NodeIt v(G); v!=INVALID; ++v){
-    check(dijkstra_test.reached(v),"Each node should be reached.");
-    if ( dijkstra_test.predArc(v)!=INVALID ) {
-      Arc e=dijkstra_test.predArc(v);
-      Node u=G.source(e);
-      check(u==dijkstra_test.predNode(v),"Wrong tree.");
-      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
-            "Wrong distance! Difference: " <<
-            std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+  for(NodeIt v(G); v!=INVALID; ++v) {
+    if (dijkstra_test.reached(v)) {
+      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
+      if (dijkstra_test.predArc(v)!=INVALID ) {
+        Arc e=dijkstra_test.predArc(v);
+        Node u=G.source(e);
+        check(u==dijkstra_test.predNode(v),"Wrong tree.");
+        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
+              "Wrong distance! Difference: " <<
+              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+      }
     }
   }
 
diff -r 33f8d69e642a -r b6732e0d38c5 test/graph_maps_test.h
--- a/test/graph_maps_test.h	Fri Jul 18 17:26:12 2008 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,144 +0,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2008
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_TEST_MAP_TEST_H
-#define LEMON_TEST_MAP_TEST_H
-
-#include <vector>
-#include <lemon/maps.h>
-
-#include "test_tools.h"
-
-namespace lemon {
-
-  template <typename Graph>
-  void checkGraphNodeMap() {
-    Graph graph;
-    const int num = 16;
-
-    typedef typename Graph::Node Node;
-
-    std::vector<Node> nodes;
-    for (int i = 0; i < num; ++i) {
-      nodes.push_back(graph.addNode());
-    }
-    typedef typename Graph::template NodeMap<int> IntNodeMap;
-    IntNodeMap map(graph, 42);
-    for (int i = 0; i < int(nodes.size()); ++i) {
-      check(map[nodes[i]] == 42, "Wrong map constructor.");
-    }
-    for (int i = 0; i < num; ++i) {
-      nodes.push_back(graph.addNode());
-      map[nodes.back()] = 23;
-      check(map[nodes.back()] == 23, "Wrong operator[].");
-    }
-    map = constMap<Node>(12);
-    for (int i = 0; i < int(nodes.size()); ++i) {
-      check(map[nodes[i]] == 12, "Wrong map constructor.");
-    }
-    graph.clear();
-    nodes.clear();
-  }
-
-  template <typename Graph>
-  void checkGraphArcMap() {
-    Graph graph;
-    const int num = 16;
-
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Arc Arc;
-
-    std::vector<Node> nodes;
-    for (int i = 0; i < num; ++i) {
-      nodes.push_back(graph.addNode());
-    }
-
-    std::vector<Arc> arcs;
-    for (int i = 0; i < num; ++i) {
-      for (int j = 0; j < i; ++j) {
-        arcs.push_back(graph.addArc(nodes[i], nodes[j]));
-      }
-    }
-
-    typedef typename Graph::template ArcMap<int> IntArcMap;
-    IntArcMap map(graph, 42);
-
-    for (int i = 0; i < int(arcs.size()); ++i) {
-      check(map[arcs[i]] == 42, "Wrong map constructor.");
-    }
-
-    for (int i = 0; i < num; ++i) {
-      for (int j = i + 1; j < num; ++j) {
-        arcs.push_back(graph.addArc(nodes[i], nodes[j]));
-        map[arcs.back()] = 23;
-        check(map[arcs.back()] == 23, "Wrong operator[].");
-      }
-    }
-    map = constMap<Arc>(12);
-    for (int i = 0; i < int(arcs.size()); ++i) {
-      check(map[arcs[i]] == 12, "Wrong map constructor.");
-    }
-    graph.clear();
-    arcs.clear();
-  }
-
-  template <typename Graph>
-  void checkGraphEdgeMap() {
-    Graph graph;
-    const int num = 16;
-
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Edge Edge;
-
-    std::vector<Node> nodes;
-    for (int i = 0; i < num; ++i) {
-      nodes.push_back(graph.addNode());
-    }
-
-    std::vector<Edge> edges;
-    for (int i = 0; i < num; ++i) {
-      for (int j = 0; j < i; ++j) {
-        edges.push_back(graph.addEdge(nodes[i], nodes[j]));
-      }
-    }
-
-    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
-    IntEdgeMap map(graph, 42);
-
-    for (int i = 0; i < int(edges.size()); ++i) {
-      check(map[edges[i]] == 42, "Wrong map constructor.");
-    }
-
-    for (int i = 0; i < num; ++i) {
-      for (int j = i + 1; j < num; ++j) {
-        edges.push_back(graph.addEdge(nodes[i], nodes[j]));
-        map[edges.back()] = 23;
-        check(map[edges.back()] == 23, "Wrong operator[].");
-      }
-    }
-    map = constMap<Edge>(12);
-    for (int i = 0; i < int(edges.size()); ++i) {
-      check(map[edges[i]] == 12, "Wrong map constructor.");
-    }
-    graph.clear();
-    edges.clear();
-  }
-
-}
-
-#endif
diff -r 33f8d69e642a -r b6732e0d38c5 test/graph_test.cc
--- a/test/graph_test.cc	Fri Jul 18 17:26:12 2008 +0100
+++ b/test/graph_test.cc	Mon Jul 21 16:30:28 2008 +0200
@@ -24,12 +24,78 @@
 
 #include "test_tools.h"
 #include "graph_test.h"
-#include "graph_maps_test.h"
 
 using namespace lemon;
 using namespace lemon::concepts;
 
-void check_concepts() {
+template <class Graph>
+void checkGraph() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  checkGraphNodeList(G, 0);
+  checkGraphEdgeList(G, 0);
+
+  Node
+    n1 = G.addNode(),
+    n2 = G.addNode(),
+    n3 = G.addNode();
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 0);
+
+  Edge e1 = G.addEdge(n1, n2);
+  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
+        "Wrong edge");
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 2);
+  checkGraphEdgeList(G, 1);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 0);
+
+  checkGraphIncEdgeList(G, n1, 1);
+  checkGraphIncEdgeList(G, n2, 1);
+  checkGraphIncEdgeList(G, n3, 0);
+
+  checkGraphConArcList(G, 2);
+  checkGraphConEdgeList(G, 1);
+
+  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 6);
+  checkGraphEdgeList(G, 3);
+
+  checkGraphOutArcList(G, n1, 2);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 1);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 3);
+  checkGraphInArcList(G, n3, 1);
+
+  checkGraphIncEdgeList(G, n1, 2);
+  checkGraphIncEdgeList(G, n2, 3);
+  checkGraphIncEdgeList(G, n3, 1);
+
+  checkGraphConArcList(G, 6);
+  checkGraphConEdgeList(G, 3);
+
+  checkArcDirections(G);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+}
+
+void checkConcepts() {
   { // Checking graph components
     checkConcept<BaseGraphComponent, BaseGraphComponent >();
 
@@ -51,14 +117,12 @@
     checkConcept<ExtendableGraphComponent<>, ListGraph>();
     checkConcept<ClearableGraphComponent<>, ListGraph>();
     checkConcept<ErasableGraphComponent<>, ListGraph>();
-    checkGraphIterators<ListGraph>();
   }
   { // Checking SmartGraph
     checkConcept<Graph, SmartGraph>();
     checkConcept<AlterableGraphComponent<>, SmartGraph>();
     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
     checkConcept<ClearableGraphComponent<>, SmartGraph>();
-    checkGraphIterators<SmartGraph>();
   }
 //  { // Checking FullGraph
 //    checkConcept<Graph, FullGraph>();
@@ -71,7 +135,7 @@
 }
 
 template <typename Graph>
-void check_graph_validity() {
+void checkGraphValidity() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   Graph g;
 
@@ -94,7 +158,7 @@
 }
 
 template <typename Graph>
-void check_graph_validity_erase() {
+void checkGraphValidityErase() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   Graph g;
 
@@ -168,20 +232,14 @@
 //   }
 // }
 
-void check_graphs() {
+void checkGraphs() {
   { // Checking ListGraph
     checkGraph<ListGraph>();
-    checkGraphNodeMap<ListGraph>();
-    checkGraphEdgeMap<ListGraph>();
-
-    check_graph_validity_erase<ListGraph>();
+    checkGraphValidityErase<ListGraph>();
   }
   { // Checking SmartGraph
     checkGraph<SmartGraph>();
-    checkGraphNodeMap<SmartGraph>();
-    checkGraphEdgeMap<SmartGraph>();
-
-    check_graph_validity<SmartGraph>();
+    checkGraphValidity<SmartGraph>();
   }
 //   { // Checking FullGraph
 //     FullGraph g(5);
@@ -197,7 +255,7 @@
 }
 
 int main() {
-  check_concepts();
-  check_graphs();
+  checkConcepts();
+  checkGraphs();
   return 0;
 }
diff -r 33f8d69e642a -r b6732e0d38c5 test/graph_test.h
--- a/test/graph_test.h	Fri Jul 18 17:26:12 2008 +0100
+++ b/test/graph_test.h	Mon Jul 21 16:30:28 2008 +0200
@@ -19,7 +19,11 @@
 #ifndef LEMON_TEST_GRAPH_TEST_H
 #define LEMON_TEST_GRAPH_TEST_H
 
+#include <set>
+
 #include <lemon/core.h>
+#include <lemon/maps.h>
+
 #include "test_tools.h"
 
 namespace lemon {
@@ -42,6 +46,10 @@
     typename Graph::ArcIt e(G);
     for(int i=0;i<cnt;i++) {
       check(e!=INVALID,"Wrong Arc list linking.");
+      check(G.oppositeNode(G.source(e), e) == G.target(e),
+            "Wrong opposite node");
+      check(G.oppositeNode(G.target(e), e) == G.source(e),
+            "Wrong opposite node");
       ++e;
     }
     check(e==INVALID,"Wrong Arc list linking.");
@@ -55,6 +63,8 @@
     for(int i=0;i<cnt;i++) {
       check(e!=INVALID,"Wrong OutArc list linking.");
       check(n==G.source(e),"Wrong OutArc list linking.");
+      check(n==G.baseNode(e),"Wrong OutArc list linking.");
+      check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
       ++e;
     }
     check(e==INVALID,"Wrong OutArc list linking.");
@@ -68,6 +78,8 @@
     for(int i=0;i<cnt;i++) {
       check(e!=INVALID,"Wrong InArc list linking.");
       check(n==G.target(e),"Wrong InArc list linking.");
+      check(n==G.baseNode(e),"Wrong OutArc list linking.");
+      check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
       ++e;
     }
     check(e==INVALID,"Wrong InArc list linking.");
@@ -80,6 +92,8 @@
     typename Graph::EdgeIt e(G);
     for(int i=0;i<cnt;i++) {
       check(e!=INVALID,"Wrong Edge list linking.");
+      check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
+      check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
       ++e;
     }
     check(e==INVALID,"Wrong Edge list linking.");
@@ -93,170 +107,178 @@
     for(int i=0;i<cnt;i++) {
       check(e!=INVALID,"Wrong IncEdge list linking.");
       check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
+      check(n==G.baseNode(e),"Wrong OutArc list linking.");
+      check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
+            "Wrong OutArc list linking.");
       ++e;
     }
     check(e==INVALID,"Wrong IncEdge list linking.");
     check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
   }
 
-  template <class Digraph>
-  void checkDigraphIterators() {
-    typedef typename Digraph::Node Node;
-    typedef typename Digraph::NodeIt NodeIt;
-    typedef typename Digraph::Arc Arc;
-    typedef typename Digraph::ArcIt ArcIt;
-    typedef typename Digraph::InArcIt InArcIt;
-    typedef typename Digraph::OutArcIt OutArcIt;
+  template <class Graph>
+  void checkGraphConArcList(const Graph &G, int cnt) {
+    int i = 0;
+    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
+      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
+        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
+          check(G.source(a) == u, "Wrong iterator.");
+          check(G.target(a) == v, "Wrong iterator.");
+          ++i;
+        }
+      }
+    }
+    check(cnt == i, "Wrong iterator.");
   }
 
   template <class Graph>
-  void checkGraphIterators() {
-    checkDigraphIterators<Graph>();
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::IncEdgeIt IncEdgeIt;
+  void checkGraphConEdgeList(const Graph &G, int cnt) {
+    int i = 0;
+    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
+      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
+        for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
+          check((G.u(e) == u && G.v(e) == v) ||
+                (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
+          i += u == v ? 2 : 1;
+        }
+      }
+    }
+    check(2 * cnt == i, "Wrong iterator.");
   }
 
-  // Structure returned by addPetersen()
-  template<class Digraph>
-  struct PetStruct
-  {
-    // Vector containing the outer nodes
-    std::vector<typename Digraph::Node> outer;
-    // Vector containing the inner nodes
-    std::vector<typename Digraph::Node> inner;
-    // Vector containing the arcs of the inner circle
-    std::vector<typename Digraph::Arc> incir;
-    // Vector containing the arcs of the outer circle
-    std::vector<typename Digraph::Arc> outcir;
-    // Vector containing the chord arcs
-    std::vector<typename Digraph::Arc> chords;
-  };
-
-  // Adds the reverse pair of all arcs to a digraph
-  template<class Digraph>
-  void bidirDigraph(Digraph &G)
-  {
-    typedef typename Digraph::Arc Arc;
-    typedef typename Digraph::ArcIt ArcIt;
-
-    std::vector<Arc> ee;
-
-    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
-
-    for(int i=0;i<int(ee.size());++i)
-      G.addArc(G.target(ee[i]),G.source(ee[i]));
-  }
-
-  // Adds a Petersen digraph to G.
-  // Returns the nodes and arcs of the generated digraph.
-  template<typename Digraph>
-  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
-  {
-    PetStruct<Digraph> n;
-
-    for(int i=0;i<num;i++) {
-      n.outer.push_back(G.addNode());
-      n.inner.push_back(G.addNode());
-    }
-
-    for(int i=0;i<num;i++) {
-      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
-      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
-      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
-    }
-
-    return n;
-  }
-
-  // Checks the bidirectioned Petersen digraph
-  template<class Digraph>
-  void checkBidirPetersen(const Digraph &G, int num = 5)
-  {
-    typedef typename Digraph::NodeIt NodeIt;
-
-    checkGraphNodeList(G, 2 * num);
-    checkGraphArcList(G, 6 * num);
-
-    for(NodeIt n(G);n!=INVALID;++n) {
-      checkGraphInArcList(G, n, 3);
-      checkGraphOutArcList(G, n, 3);
+  template <typename Graph>
+  void checkArcDirections(const Graph& G) {
+    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
+      check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
+      check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
+      check(G.direct(a, G.direction(a)) == a, "Wrong direction");
     }
   }
 
-  // Structure returned by addUPetersen()
-  template<class Graph>
-  struct UPetStruct
-  {
-    // Vector containing the outer nodes
-    std::vector<typename Graph::Node> outer;
-    // Vector containing the inner nodes
-    std::vector<typename Graph::Node> inner;
-    // Vector containing the edges of the inner circle
-    std::vector<typename Graph::Edge> incir;
-    // Vector containing the edges of the outer circle
-    std::vector<typename Graph::Edge> outcir;
-    // Vector containing the chord edges
-    std::vector<typename Graph::Edge> chords;
-  };
-
-  // Adds a Petersen graph to \c G.
-  // Returns the nodes and edges of the generated graph.
-  template<typename Graph>
-  UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
-  {
-    UPetStruct<Graph> n;
-
-    for(int i=0;i<num;i++) {
-      n.outer.push_back(G.addNode());
-      n.inner.push_back(G.addNode());
-    }
-
-    for(int i=0;i<num;i++) {
-      n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
-      n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
-      n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
-    }
-
-    return n;
-  }
-
-  // Checks the undirected Petersen graph
-  template<class Graph>
-  void checkUndirPetersen(const Graph &G, int num = 5)
-  {
-    typedef typename Graph::NodeIt NodeIt;
-
-    checkGraphNodeList(G, 2 * num);
-    checkGraphEdgeList(G, 3 * num);
-    checkGraphArcList(G, 6 * num);
-
-    for(NodeIt n(G);n!=INVALID;++n) {
-      checkGraphIncEdgeList(G, n, 3);
+  template <typename Graph>
+  void checkNodeIds(const Graph& G) {
+    std::set<int> values;
+    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
+      check(G.nodeFromId(G.id(n)) == n, "Wrong id");
+      check(values.find(G.id(n)) == values.end(), "Wrong id");
+      check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
+      values.insert(G.id(n));
     }
   }
 
-  template <class Digraph>
-  void checkDigraph() {
-    const int num = 5;
-    Digraph G;
-    checkGraphNodeList(G, 0);
-    checkGraphArcList(G, 0);
-    addPetersen(G, num);
-    bidirDigraph(G);
-    checkBidirPetersen(G, num);
+  template <typename Graph>
+  void checkArcIds(const Graph& G) {
+    std::set<int> values;
+    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
+      check(G.arcFromId(G.id(a)) == a, "Wrong id");
+      check(values.find(G.id(a)) == values.end(), "Wrong id");
+      check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
+      values.insert(G.id(a));
+    }
   }
 
-  template <class Graph>
-  void checkGraph() {
-    const int num = 5;
-    Graph G;
-    checkGraphNodeList(G, 0);
-    checkGraphEdgeList(G, 0);
-    addUPetersen(G, num);
-    checkUndirPetersen(G, num);
+  template <typename Graph>
+  void checkEdgeIds(const Graph& G) {
+    std::set<int> values;
+    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
+      check(G.edgeFromId(G.id(e)) == e, "Wrong id");
+      check(values.find(G.id(e)) == values.end(), "Wrong id");
+      check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
+      values.insert(G.id(e));
+    }
   }
 
+  template <typename Graph>
+  void checkGraphNodeMap(const Graph& G) {
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+
+    typedef typename Graph::template NodeMap<int> IntNodeMap;
+    IntNodeMap map(G, 42);
+    for (NodeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (NodeIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (NodeIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    map = constMap<Node>(12);
+    for (NodeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 12, "Wrong operator[].");
+    }
+  }
+
+  template <typename Graph>
+  void checkGraphArcMap(const Graph& G) {
+    typedef typename Graph::Arc Arc;
+    typedef typename Graph::ArcIt ArcIt;
+
+    typedef typename Graph::template ArcMap<int> IntArcMap;
+    IntArcMap map(G, 42);
+    for (ArcIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (ArcIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (ArcIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    map = constMap<Arc>(12);
+    for (ArcIt it(G); it != INVALID; ++it) {
+      check(map[it] == 12, "Wrong operator[].");
+    }
+  }
+
+  template <typename Graph>
+  void checkGraphEdgeMap(const Graph& G) {
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+
+    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
+    IntEdgeMap map(G, 42);
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    map = constMap<Edge>(12);
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 12, "Wrong operator[].");
+    }
+  }
+
+
 } //namespace lemon
 
 #endif