Changeset 353:37557a46e298 in lemon-main

Timestamp:

08/14/08 21:49:39 (16 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Porting full graphs from svn 3498

• the FullGraph? is redesigned in implementation
• some improvemnts in documentation

Files:

• lemon/Makefile.am (modified) (1 diff)
• lemon/full_graph.h (added)
• test/digraph_test.cc (modified) (3 diffs)
• test/graph_test.cc (modified) (4 diffs)

lemon/Makefile.am

@@ -30 +30 @@
         lemon/dim2.h \
         lemon/error.h \
+        lemon/full_graph.h \
         lemon/graph_to_eps.h \
         lemon/kruskal.h \

test/digraph_test.cc

@@ -20 +20 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
-//#include <lemon/full_graph.h>
+#include <lemon/full_graph.h>
 //#include <lemon/hypercube_graph.h>
 
@@ -80 +80 @@
 }
 
+void checkFullDigraph(int num) {
+  typedef FullDigraph Digraph;
+  DIGRAPH_TYPEDEFS(Digraph);
+  Digraph G(num);
+
+  checkGraphNodeList(G, num);
+  checkGraphArcList(G, num * num);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphOutArcList(G, n, num);
+    checkGraphInArcList(G, n, num);
+  }
+
+  checkGraphConArcList(G, num * num);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+
+  for (int i = 0; i < G.nodeNum(); ++i) {
+    check(G.index(G(i)) == i, "Wrong index");
+  }
+
+  for (NodeIt s(G); s != INVALID; ++s) {
+    for (NodeIt t(G); t != INVALID; ++t) {
+      Arc a = G.arc(s, t);
+      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
+    }
+  }
+
+}
+
 
 void checkConcepts() {
@@ -177 +210 @@
     checkDigraphValidity<SmartDigraph>();
   }
+  { // Checking FullDigraph
+    checkFullDigraph(8);
+  }
 }
 

test/graph_test.cc

@@ -20 +20 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
-// #include <lemon/full_graph.h>
+#include <lemon/full_graph.h>
 // #include <lemon/grid_graph.h>
 
@@ -96 +96 @@
 }
 
+void checkFullGraph(int num) {
+  typedef FullGraph Graph;
+  GRAPH_TYPEDEFS(Graph);
+
+  Graph G(num);
+  checkGraphNodeList(G, num);
+  checkGraphEdgeList(G, num * (num - 1) / 2);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphOutArcList(G, n, num - 1);    
+    checkGraphInArcList(G, n, num - 1);    
+    checkGraphIncEdgeList(G, n, num - 1);    
+  }
+
+  checkGraphConArcList(G, num * (num - 1));
+  checkGraphConEdgeList(G, num * (num - 1) / 2);
+
+  checkArcDirections(G);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+
+  
+  for (int i = 0; i < G.nodeNum(); ++i) {
+    check(G.index(G(i)) == i, "Wrong index");
+  }
+
+  for (NodeIt u(G); u != INVALID; ++u) {
+    for (NodeIt v(G); v != INVALID; ++v) {
+      Edge e = G.edge(u, v);
+      Arc a = G.arc(u, v);
+      if (u == v) {
+        check(e == INVALID, "Wrong edge lookup");
+        check(a == INVALID, "Wrong arc lookup");
+      } else {
+        check((G.u(e) == u && G.v(e) == v) ||
+              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
+        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
+      }
+    }
+  }
+}
+
 void checkConcepts() {
   { // Checking graph components
@@ -125 +172 @@
     checkConcept<ClearableGraphComponent<>, SmartGraph>();
   }
-//  { // Checking FullGraph
-//    checkConcept<Graph, FullGraph>();
-//    checkGraphIterators<FullGraph>();
-//  }
-//  { // Checking GridGraph
-//    checkConcept<Graph, GridGraph>();
-//    checkGraphIterators<GridGraph>();
-//  }
+  { // Checking FullGraph
+    checkConcept<Graph, FullGraph>();
+  }
+//   { // Checking GridGraph
+//     checkConcept<Graph, GridGraph>();
+//   }
 }
 
@@ -242 +287 @@
     checkGraphValidity<SmartGraph>();
   }
-//   { // Checking FullGraph
-//     FullGraph g(5);
-//     checkGraphNodeList(g, 5);
-//     checkGraphEdgeList(g, 10);
-//   }
+  { // Checking FullGraph   
+    checkFullGraph(7);
+    checkFullGraph(8);
+  }
 //   { // Checking GridGraph
 //     GridGraph g(5, 6);