Changeset 2247:269a0dcee70b in lemon-0.x for test

Timestamp:

10/17/06 12:50:57 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2997

Message:

Update the Path concept
Concept check for paths

DirPath? renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed

I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation

Location:

test

Files:

• bfs_test.cc (modified) (2 diffs)
• dfs_test.cc (modified) (2 diffs)
• dijkstra_test.cc (modified) (2 diffs)
• path_test.cc (modified) (1 diff)

test/bfs_test.cc

@@ -60 +60 @@
   b  = bfs_test.reached(n);
 
-  DirPath<Graph> pp(G);
+  Path<Graph> pp(G);
   bfs_test.getPath(pp,n);
 }
@@ -110 +110 @@
   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
 
-  DirPath<Graph> p(G);
+  Path<Graph> p(G);
   check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
   check(p.length()==3,"getPath() found a wrong path.");

test/dfs_test.cc

@@ -60 +60 @@
   b  = dfs_test.reached(n);
 
-  DirPath<Graph> pp(G);
+  Path<Graph> pp(G);
   dfs_test.getPath(pp,n);
 }
@@ -109 +109 @@
   dfs_test.run(s);  
   
-  DirPath<Graph> p(G);
+  Path<Graph> p(G);
   check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
   check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");

test/dijkstra_test.cc

@@ -64 +64 @@
   b  = dijkstra_test.reached(n);
 
-  DirPath<Graph> pp(G);
+  Path<Graph> pp(G);
   dijkstra_test.getPath(pp,n);
 }
@@ -121 +121 @@
 
 
-  DirPath<Graph> p(G);
+  Path<Graph> p(G);
   check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
   check(p.length()==4,"getPath() found a wrong path.");

test/path_test.cc

@@ -19 +19 @@
 #include <string>
 #include <iostream>
+
 #include <lemon/concept/path.h>
+#include <lemon/concept/graph.h>
+
 #include <lemon/path.h>
 #include <lemon/list_graph.h>
 
+#include "test_tools.h"
+
 using namespace std;
 using namespace lemon;
-using namespace lemon::concept;
 
-template<class Path> void checkCompilePath(Path &P) 
-{
-  typedef typename Path::EdgeIt EdgeIt;
-  typedef typename Path::NodeIt NodeIt;
-  typedef typename Path::GraphNode GraphNode;
-  typedef typename Path::GraphEdge GraphEdge;
-  //typedef typename Path::Builder Builder;
-  //??? ha csinalok ilyet es siman Builderrel peldanyositok, akkor warningol. Talan friend miatt? De ki az?
-
-  EdgeIt ei;
-  NodeIt ni;
-  GraphNode gn;
-  GraphEdge ge;
-
-  size_t st;
-  bool b;
-
-  //Path(const Graph &_G) {}      //the constructor has been already called
-
-  st=P.length();                  //size_t length() const {return 0;}
-  b=P.empty();                    //bool empty() const {}
-  P.clear();                      //void clear() {}
-
-  gn=P.target();                    //GraphNode/*It*/ target() const {return INVALID;}
-  gn=P.source();                    //GraphNode/*It*/ source() const {return INVALID;}
-
-  ei=P.first(ei);                 //It& first(It &i) const { return i=It(*this); }
-
-  ni=P.target(ei);                  //NodeIt target(const EdgeIt& e) const {}
-  ni=P.source(ei);                  //NodeIt source(const EdgeIt& e) const {}
-
-
-  ListGraph lg;
-  Path p(lg);
-
-  EdgeIt i;                       //EdgeIt() {}
-  EdgeIt j(INVALID);              //EdgeIt(Invalid) {}
-  EdgeIt k(p);                    //EdgeIt(const Path &_p) {}
-
-  i=++j;                          //EdgeIt& operator++() {}
-  ++k;
-  b=(i==j);                       //bool operator==(const EdgeIt& e) const {return true;}
-  b=(i!=j);                       //bool operator!=(const EdgeIt& e) const {return true;}
-
-
-  NodeIt l;                       //NodeIt() {}
-  NodeIt m(INVALID);              //NodeIt(Invalid) {}
-  NodeIt n(p);                    //NodeIt(const Path &_p) {}
-
-  l=++m;                          //NodeIt& operator++() {}
-  b=(m==n);                       //bool operator==(const NodeIt& e) const {}
-  b=(m!=n);                       //bool operator!=(const NodeIt& e) const {}
-
-  typename Path::Builder builder(p);     //Builder(Path &_P) : P(_P) {}
-  builder.setStartNode(gn);              //void setStartNode(const GraphNode &) {}
-  builder.pushFront(ge);                 //void pushFront(const GraphEdge& e) {}
-  builder.pushBack(ge);                  //void pushBack(const GraphEdge& e) {}
-  builder.commit();                      //void commit() {}
-  builder.reserveFront(st);              //void reserveFront(size_t r) {}
-  builder.reserveBack(st);               //void reserveBack(size_t r) {}
-
+void check_concepts() {
+  checkConcept<concept::Path<concept::Graph>, 
+    concept::Path<concept::Graph> >();
+  checkConcept<concept::Path<concept::Graph>, 
+    Path<concept::Graph> >();
+  checkConcept<concept::Path<ListGraph>, Path<ListGraph> >();
 }
 
-template void checkCompilePath< concept::Path<ListGraph> >(concept::Path<ListGraph> &);
-template void checkCompilePath< DirPath<ListGraph> >(DirPath<ListGraph> &);
-template void checkCompilePath< UPath<ListGraph> >(UPath<ListGraph> &);
+int main() {
+  check_concepts();
+  
+  ListGraph g;
+  
+  ListGraph::Node n1 = g.addNode();
+  ListGraph::Node n2 = g.addNode();
+  ListGraph::Node n3 = g.addNode();
+  ListGraph::Node n4 = g.addNode();
+  ListGraph::Node n5 = g.addNode();
+ 
+  ListGraph::Edge e1 = g.addEdge(n1, n2);
+  ListGraph::Edge e2 = g.addEdge(n2, n3);
+  ListGraph::Edge e3 = g.addEdge(n3, n4);
+  ListGraph::Edge e4 = g.addEdge(n4, n5);
+  ListGraph::Edge e5 = g.addEdge(n5, n1);
 
-int main() 
-{
+  {
+    Path<ListGraph> p(g);
+
+    check(p.empty(), "Wrong Path");
+    check(p.length() == 0, "Wrong Path");
+    
+    {
+      Path<ListGraph>::Builder b(p);
+      b.setStartNode(n3);
+      b.commit();
+    }
+
+    check(!p.empty(), "Wrong Path");
+    check(p.length() == 0, "Wrong Path");
+    check(p.source() == n3, "Wrong Path");
+    check(p.target() == n3, "Wrong Path");
+
+    {
+      Path<ListGraph>::Builder b(p);
+      b.pushBack(e3);
+      b.pushBack(e4);
+      b.pushFront(e2);
+      b.commit();
+    }
+
+    check(!p.empty(), "Wrong Path");
+    check(p.length() == 3, "Wrong Path");
+    check(p.source() == n2, "Wrong Path");
+    check(p.target() == n5, "Wrong Path");
+    
+    {
+      Path<ListGraph>::NodeIt it(p);
+      check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
+      check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
+      check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
+      check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
+      check((ListGraph::Node)it == INVALID, "Wrong Path");
+    }
+
+    {
+      Path<ListGraph>::EdgeIt it(p);
+      check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
+      check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
+      check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
+      check((ListGraph::Edge)it == INVALID, "Wrong Path");
+    }
+    
+  }
+  
+  return 0;
 }