Changeset 100:4f754b4cf82b in lemon-main for test

Timestamp:

02/07/08 22:37:07 (17 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Phase:

public

Message:

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

Location:

test

Files:

• Makefile.am (modified) (2 diffs)
• bfs_test.cc (added)
• dfs_test.cc (added)
• heap_test.cc (added)
• heap_test.h (added)
• test_tools.h (modified) (3 diffs)

test/Makefile.am

@@ -4 +4 @@
 noinst_HEADERS += \
         test/digraph_test.h \
+        test/heap_test.h \
         test/map_test.h \
         test/test_tools.h
 
 check_PROGRAMS += \
+        test/bfs_test \
+        test/dfs_test \
         test/digraph_test \
         test/dim_test \
@@ -20 +23 @@
 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 
+test_bfs_test_SOURCES = test/bfs_test.cc
+test_dfs_test_SOURCES = test/dfs_test.cc
 test_digraph_test_SOURCES = test/digraph_test.cc
 test_dim_test_SOURCES = test/dim_test.cc
 #test_error_test_SOURCES = test/error_test.cc
 test_graph_test_SOURCES = test/graph_test.cc
+# test_heap_test_SOURCES = test/heap_test.cc
 test_maps_test_SOURCES = test/maps_test.cc
 test_path_test_SOURCES = test/path_test.cc

test/test_tools.h

@@ -21 +21 @@
 
 #include <iostream>
+#include <vector>
+
+#include <cstdlib>
+#include <ctime>
+
+#include <lemon/concept_check.h>
+#include <lemon/concepts/digraph.h>
+
+#include <lemon/random.h>
+
+using namespace lemon;
 
 //! \ingroup misc
@@ -37 +48 @@
 ///\code check(0==1,"This is obviously false.");\endcode will
 ///print this (and then exits).
-///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
+///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
 ///
 ///\todo It should be in \c error.h
@@ -46 +57 @@
   } else { } \
 
+///Structure returned by \ref addPetersen().
+
+///Structure returned by \ref 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 a Petersen digraph to \c G.
+
+///Adds a Petersen digraph to \c G.
+///\return 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;
+}
+
+/// \brief Adds to the digraph the reverse pair of all arcs.
+///
+/// Adds to the digraph the reverse pair of all arcs.
+///
+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(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
+    G.addArc(G.target(*p),G.source(*p));
+}
+
+
+/// \brief Checks the bidirectioned Petersen digraph.
+///
+///  Checks the bidirectioned Petersen digraph.
+///
+template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
+{
+  typedef typename Digraph::Node Node;
+
+  typedef typename Digraph::ArcIt ArcIt;
+  typedef typename Digraph::NodeIt NodeIt;
+
+  checkDigraphNodeList(G, 2 * num);
+  checkDigraphArcList(G, 6 * num);
+
+  for(NodeIt n(G);n!=INVALID;++n) {
+    checkDigraphInArcList(G, n, 3);
+    checkDigraphOutArcList(G, n, 3);
+  }  
+}
+
+///Structure returned by \ref addUPetersen().
+
+///Structure returned by \ref addUPetersen().
+///
+template<class Digraph> struct UPetStruct
+{
+  ///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::Edge> incir;
+  ///Vector containing the arcs of the outer circle.
+  std::vector<typename Digraph::Edge> outcir;
+  ///Vector containing the chord arcs.
+  std::vector<typename Digraph::Edge> chords;
+};
+
+///Adds a Petersen digraph to the undirected \c G.
+
+///Adds a Petersen digraph to the undirected \c G.
+///\return The nodes and arcs of the generated digraph.
+
+template<typename Digraph>
+UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
+{
+  UPetStruct<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)%5]));
+   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
+ }
+ return n;
+}
+
 #endif