Changeset 171:02f4d5d9bfd7 in lemon-1.0 for test/graph_utils_test.cc

Timestamp:

06/15/08 22:05:23 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Children:

172:c94a80f38d7f, 173:b026e9779b28, 175:4eb8900a865c

Phase:

public

Message:

Improve and redesign test programs + unify their output (ticket #25)

• Move graph related utilities form test_tools.h to graph_test.h.
• Move the contents of graph_utils_test.h to graph_utils_test.cc.
• Rename map_test.h -> graph_maps_test.h.
• Rename digraph_test.h -> graph_test.h.
• Many improvements in the following files:
  • digraph_test.cc
  • graph_test.cc
  • graph_test.h
  • graph_maps_test.h
  • graph_utils_test.cc
  • bfs_test.cc
  • dfs_test.cc
  • counter_test.cc
• Test programs print messages only if it really seems necessary.
• Remove \file commands form .cc test files.

File:

• test/graph_utils_test.cc (modified) (3 diffs)

test/graph_utils_test.cc

@@ -17 +17 @@
  */
 
-#include <iostream>
-#include <vector>
-
+#include <cstdlib>
+#include <ctime>
+
+#include <lemon/random.h>
 #include <lemon/graph_utils.h>
-
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
 
+#include "graph_test.h"
 #include "test_tools.h"
-#include "graph_utils_test.h"
-
 
 using namespace lemon;
 
-template <class Graph>
-void checkSnapDeg() 
+template <typename Digraph>
+void checkFindArcs() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  {
+    Digraph digraph;
+    for (int i = 0; i < 10; ++i) {
+      digraph.addNode();
+    }
+    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) {
+          check(digraph.source(con) == src, "Wrong source.");
+          check(digraph.target(con) == trg, "Wrong target.");
+          check(found[con] == false, "The arc found already.");
+          found[con] = true;
+        }
+      }
+    }
+    for (ArcIt it(digraph); it != INVALID; ++it) {
+      check(found[it] == true, "The arc is not found.");
+    }
+  }
+
+  {
+    int num = 5;
+    Digraph fg;
+    std::vector<Node> nodes;
+    for (int i = 0; i < num; ++i) {
+      nodes.push_back(fg.addNode());
+    }
+    for (int i = 0; i < num * num; ++i) {
+      fg.addArc(nodes[i / num], nodes[i % num]);
+    }
+    check(countNodes(fg) == num, "Wrong node number.");
+    check(countArcs(fg) == num*num, "Wrong arc number.");
+    for (NodeIt src(fg); src != INVALID; ++src) {
+      for (NodeIt trg(fg); trg != INVALID; ++trg) {
+        ConArcIt<Digraph> con(fg, src, trg);
+        check(con != INVALID, "There is no connecting arc.");
+        check(fg.source(con) == src, "Wrong source.");
+        check(fg.target(con) == trg, "Wrong target.");
+        check(++con == INVALID, "There is more connecting arc.");
+      }
+    }
+    ArcLookUp<Digraph> al1(fg);
+    DynArcLookUp<Digraph> al2(fg);
+    AllArcLookUp<Digraph> al3(fg);
+    for (NodeIt src(fg); src != INVALID; ++src) {
+      for (NodeIt trg(fg); trg != INVALID; ++trg) {
+        Arc con1 = al1(src, trg);
+        Arc con2 = al2(src, trg);
+        Arc con3 = al3(src, trg);
+        Arc con4 = findArc(fg, src, trg);
+        check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.")
+        check(con1 != INVALID, "There is no connecting arc.");
+        check(fg.source(con1) == src, "Wrong source.");
+        check(fg.target(con1) == trg, "Wrong target.");
+        check(al3(src, trg, con3) == INVALID, "There is more connecting arc.");
+        check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc.");
+      }
+    }
+  }
+}
+
+template <typename Graph>
+void checkFindEdges() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+  Graph graph;
+  for (int i = 0; i < 10; ++i) {
+    graph.addNode();
+  }
+  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) {
+        check( (graph.u(con) == src && graph.v(con) == trg) ||
+               (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes.");
+        ++found[con];
+        check(found[con] <= 2, "The edge found more than twice.");
+      }
+    }
+  }
+  for (EdgeIt it(graph); it != INVALID; ++it) {
+    check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
+           (graph.u(it) == graph.v(it) && found[it] == 1),
+           "The edge is not found correctly.");
+  }
+}
+
+template <class Digraph>
+void checkDeg()
 {
-  Graph g;
-  typename Graph::Node n1=g.addNode();
-  typename Graph::Node n2=g.addNode();
-   
-  InDegMap<Graph> ind(g);
- 
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+  
+  const int nodeNum = 10;
+  const int arcNum = 100;
+  Digraph digraph;
+  InDegMap<Digraph> inDeg(digraph);
+  OutDegMap<Digraph> outDeg(digraph);
+  std::vector<Node> nodes(nodeNum);
+  for (int i = 0; i < nodeNum; ++i) {
+    nodes[i] = digraph.addNode();
+  }
+  std::vector<Arc> arcs(arcNum);
+  for (int i = 0; i < arcNum; ++i) {
+    arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
+  }
+  for (int i = 0; i < nodeNum; ++i) {
+    check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
+          "Wrong in degree map");
+  }
+  for (int i = 0; i < nodeNum; ++i) {
+    check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
+          "Wrong out degree map");
+  }
+}
+
+template <class Digraph>
+void checkSnapDeg()
+{
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph g;
+  Node n1=g.addNode();
+  Node n2=g.addNode();
+  
+  InDegMap<Digraph> ind(g);
+  
   g.addArc(n1,n2);
   
-  typename Graph::Snapshot snap(g);
-  
-  OutDegMap<Graph> outd(g);
+  typename Digraph::Snapshot snap(g);
+  
+  OutDegMap<Digraph> outd(g);
   
   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
@@ -51 +187 @@
   g.addArc(n1,n2);
   g.addArc(n2,n1);
- 
+
   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
@@ -59 +195 @@
   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
-  
 }
 
 int main() {
-  ///\file
-  { // checking list graph
-    checkDigraphCounters<ListDigraph>();
-    checkFindArc<ListDigraph>();
-  }
-  { // checking smart graph
-    checkDigraphCounters<SmartDigraph>();
-    checkFindArc<SmartDigraph>();
-  }
-  {
-    int num = 5;
-    SmartDigraph fg;
-    std::vector<SmartDigraph::Node> nodes;
-    for (int i = 0; i < num; ++i) {
-      nodes.push_back(fg.addNode());
-    }
-    for (int i = 0; i < num * num; ++i) {
-      fg.addArc(nodes[i / num], nodes[i % num]);
-    }
-    check(countNodes(fg) == num, "FullGraph: wrong node number.");
-    check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
-    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
-      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
-        ConArcIt<SmartDigraph> con(fg, src, trg);
-        check(con != INVALID, "There is no connecting arc.");
-        check(fg.source(con) == src, "Wrong source.");
-        check(fg.target(con) == trg, "Wrong target.");
-        check(++con == INVALID, "There is more connecting arc.");
-      }
-    }
-    AllArcLookUp<SmartDigraph> el(fg);
-    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
-      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
-        SmartDigraph::Arc con = el(src, trg);
-        check(con != INVALID, "There is no connecting arc.");
-        check(fg.source(con) == src, "Wrong source.");
-        check(fg.target(con) == trg, "Wrong target.");
-        check(el(src,trg,con) == INVALID, "There is more connecting arc.");
-      }
-    }
-  }
-
-  //check In/OutDegMap (and Snapshot feature)
-
+  // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
+  checkFindArcs<ListDigraph>();
+  checkFindArcs<SmartDigraph>();
+  checkFindEdges<ListGraph>();
+  checkFindEdges<SmartGraph>();
+
+  // Checking In/OutDegMap (and Snapshot feature)
+  checkDeg<ListDigraph>();
+  checkDeg<SmartDigraph>();
   checkSnapDeg<ListDigraph>();
   checkSnapDeg<SmartDigraph>();
-  
-  {
-    const int nodeNum = 10;
-    const int arcNum = 100;
-    ListDigraph digraph;
-    InDegMap<ListDigraph> inDeg(digraph);
-    OutDegMap<ListDigraph> outDeg(digraph);
-    std::vector<ListDigraph::Node> nodes(nodeNum);
-    for (int i = 0; i < nodeNum; ++i) {
-      nodes[i] = digraph.addNode();
-    }
-    std::vector<ListDigraph::Arc> arcs(arcNum);
-    for (int i = 0; i < arcNum; ++i) {
-      arcs[i] = 
-        digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
-    }
-    for (int i = 0; i < nodeNum; ++i) {
-      check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
-            "Wrong in degree map");
-    }
-    for (int i = 0; i < nodeNum; ++i) {
-      check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
-            "Wrong in degree map");
-    }
-  }
-
-  ///Everything is OK
-  std::cout << __FILE__ ": All tests passed.\n";
 
   return 0;