Changeset 286:da414906fe21 in lemon for test

Timestamp:

09/26/08 12:40:11 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improvements related to BFS/DFS/Dijkstra (ticket #96)

• Add run(s,t) function to BfsVisit?.
• Modify run(s,t) functions in the class interfaces to return bool value.
• Bug fix in Dijkstra::start(t) function.
• Improve Dijkstra::currentDist().
• Extend test files to check named class template parameters.
• Doc improvements.

Location:

test

Files:

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

test/bfs_test.cc

@@ -55 +55 @@
   typedef concepts::Digraph Digraph;
   typedef Bfs<Digraph> BType;
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
 
   Digraph G;
-  Digraph::Node n;
-  Digraph::Arc e;
+  Node s, t;
+  Arc e;
   int l;
   bool b;
   BType::DistMap d(G);
   BType::PredMap p(G);
+  Path<Digraph> pp;
 
-  BType bfs_test(G);
+  {
+    BType bfs_test(G);
 
-  bfs_test.run(n);
+    bfs_test.run(s);
+    bfs_test.run(s,t);
+    bfs_test.run();
 
-  l  = bfs_test.dist(n);
-  e  = bfs_test.predArc(n);
-  n  = bfs_test.predNode(n);
-  d  = bfs_test.distMap();
-  p  = bfs_test.predMap();
-  b  = bfs_test.reached(n);
+    l  = bfs_test.dist(t);
+    e  = bfs_test.predArc(t);
+    s  = bfs_test.predNode(t);
+    b  = bfs_test.reached(t);
+    d  = bfs_test.distMap();
+    p  = bfs_test.predMap();
+    pp = bfs_test.path(t);
+  }
+  {
+    BType
+      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
+      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
+      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
+      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
+      ::SetStandardProcessedMap
+      ::Create bfs_test(G);
 
-  Path<Digraph> pp = bfs_test.path(n);
+    bfs_test.run(s);
+    bfs_test.run(s,t);
+    bfs_test.run();
+
+    l  = bfs_test.dist(t);
+    e  = bfs_test.predArc(t);
+    s  = bfs_test.predNode(t);
+    b  = bfs_test.reached(t);
+    pp = bfs_test.path(t);
+  }
 }
 

test/dfs_test.cc

@@ -57 +57 @@
   typedef concepts::Digraph Digraph;
   typedef Dfs<Digraph> DType;
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
 
   Digraph G;
-  Digraph::Node n;
-  Digraph::Arc e;
+  Node s, t;
+  Arc e;
   int l;
   bool b;
   DType::DistMap d(G);
   DType::PredMap p(G);
+  Path<Digraph> pp;
 
-  DType dfs_test(G);
+  {
+    DType dfs_test(G);
 
-  dfs_test.run(n);
+    dfs_test.run(s);
+    dfs_test.run(s,t);
+    dfs_test.run();
 
-  l  = dfs_test.dist(n);
-  e  = dfs_test.predArc(n);
-  n  = dfs_test.predNode(n);
-  d  = dfs_test.distMap();
-  p  = dfs_test.predMap();
-  b  = dfs_test.reached(n);
+    l  = dfs_test.dist(t);
+    e  = dfs_test.predArc(t);
+    s  = dfs_test.predNode(t);
+    b  = dfs_test.reached(t);
+    d  = dfs_test.distMap();
+    p  = dfs_test.predMap();
+    pp = dfs_test.path(t);
+  }
+  {
+    DType
+      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
+      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
+      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
+      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
+      ::SetStandardProcessedMap
+      ::Create dfs_test(G);
 
-  Path<Digraph> pp = dfs_test.path(n);
+    dfs_test.run(s);
+    dfs_test.run(s,t);
+    dfs_test.run();
+
+    l  = dfs_test.dist(t);
+    e  = dfs_test.predArc(t);
+    s  = dfs_test.predNode(t);
+    b  = dfs_test.reached(t);
+    pp = dfs_test.path(t);
+  }
 }
 

test/dijkstra_test.cc

@@ -23 +23 @@
 #include <lemon/dijkstra.h>
 #include <lemon/path.h>
+#include <lemon/bin_heap.h>
 
 #include "graph_test.h"
@@ -56 +57 @@
   typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
   typedef Dijkstra<Digraph, LengthMap> DType;
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
 
   Digraph G;
-  Digraph::Node n;
-  Digraph::Arc e;
+  Node s, t;
+  Arc e;
   VType l;
   bool b;
@@ -65 +68 @@
   DType::PredMap p(G);
   LengthMap length;
+  Path<Digraph> pp;
 
-  DType dijkstra_test(G,length);
+  {
+    DType dijkstra_test(G,length);
 
-  dijkstra_test.run(n);
+    dijkstra_test.run(s);
+    dijkstra_test.run(s,t);
 
-  l  = dijkstra_test.dist(n);
-  e  = dijkstra_test.predArc(n);
-  n  = dijkstra_test.predNode(n);
-  d  = dijkstra_test.distMap();
-  p  = dijkstra_test.predMap();
-  b  = dijkstra_test.reached(n);
+    l  = dijkstra_test.dist(t);
+    e  = dijkstra_test.predArc(t);
+    s  = dijkstra_test.predNode(t);
+    b  = dijkstra_test.reached(t);
+    d  = dijkstra_test.distMap();
+    p  = dijkstra_test.predMap();
+    pp = dijkstra_test.path(t);
+  }
+  {
+    DType
+      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
+      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
+      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
+      ::SetStandardProcessedMap
+      ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
+      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
+      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
+      ::Create dijkstra_test(G,length);
 
-  Path<Digraph> pp = dijkstra_test.path(n);
+    dijkstra_test.run(s);
+    dijkstra_test.run(s,t);
+
+    l  = dijkstra_test.dist(t);
+    e  = dijkstra_test.predArc(t);
+    s  = dijkstra_test.predNode(t);
+    b  = dijkstra_test.reached(t);
+    pp = dijkstra_test.path(t);
+  }
+
 }