Changeset 060fc3 for src

Timestamp:

May 19, 2017, 9:27:11 AM (8 years ago)

Author:

Frederik Heber <frederik.heber@…>

Branches:

ForceAnnealing_goodresults, ForceAnnealing_tocheck

Children:

adbeca

Parents:

6370f9

Message:

Extended BreadthFirstSearchGatherer to allow BFS with limited discovery horizon.

• TESTS: extended unit test as well.

Location:

src/Graph

Files:

• BoostGraphCreator.hpp (modified) (1 diff)
• BreadthFirstSearchGatherer.cpp (modified) (5 diffs)
• BreadthFirstSearchGatherer.hpp (modified) (1 diff)
• unittests/BreadthFirstSearchGathererUnitTest.cpp (modified) (1 diff)
• unittests/BreadthFirstSearchGathererUnitTest.hpp (modified) (2 diffs)

src/Graph/BoostGraphCreator.hpp

@@ -38 +38 @@
 
 public:
+
   //!> typedef for an undirected graph using boost::graph
   typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS,
-      boost::property<boost::vertex_name_t, atomId_t>, boost::no_property > UndirectedGraph;
+      boost::property<boost::vertex_name_t, atomId_t>,
+      boost::property<boost::vertex_color_t, boost::default_color_type> /* needed for limited-depth DFS,
+      otherwise the property_map gets full size of graph */
+  > UndirectedGraph;
+
   //!> typedef for a map of graph node indices
   typedef boost::property_map < UndirectedGraph, boost::vertex_index_t >::type index_map_t;

src/Graph/BreadthFirstSearchGatherer.cpp

@@ -44 +44 @@
 #include <boost/graph/breadth_first_search.hpp>
 
+struct found_max_distance {}; // exception when doing limited BFS
+
 /**
  * I have no idea why this is so complicated with BGL ...
@@ -54 +56 @@
 {
 public:
-  distance_recorder(DistanceMap dist) : d(dist) {}
+  distance_recorder(
+      DistanceMap dist,
+      const size_t _max_distance) : d(dist), max_distance(_max_distance) {}
 
   template <typename Edge, typename Graph>
@@ -62 +66 @@
   }
 
+  template <typename Vertex, typename Graph>
+  void discover_vertex(Vertex u, const Graph &g) const {
+    if ((max_distance > 0) && (d[u] >= max_distance))
+      throw found_max_distance();
+  }
+
 private:
   DistanceMap d;
+  const size_t max_distance;
 };
 
 template <typename DistanceMap>
-distance_recorder<DistanceMap> record_distance(DistanceMap d)
+distance_recorder<DistanceMap> record_distance(DistanceMap d, const size_t _max_distance)
 {
-  return distance_recorder<DistanceMap>(d);
+  return distance_recorder<DistanceMap>(d, _max_distance);
 }
 
@@ -76 +87 @@
 {}
 
-std::vector<atomId_t> BreadthFirstSearchGatherer::operator()(const atomId_t &_discoverfrom)
+std::vector<atomId_t> BreadthFirstSearchGatherer::operator()(
+    const atomId_t &_discoverfrom,
+    const size_t &_max_distance)
 {
   std::vector<atomId_t> returnids;
@@ -86 +99 @@
   const BoostGraphCreator::nodeId_t discoverfrom_nodeid = BGcreator.getNodeId(_discoverfrom);
   distances[ boost::vertex(discoverfrom_nodeid, BGgraph) ] = 0;
-  boost::breadth_first_search(
-      BGgraph,
-      boost::vertex(discoverfrom_nodeid, BGgraph),
-      boost::visitor(record_distance(&distances[0])));
+  try {
+    boost::breadth_first_search(
+        BGgraph,
+        boost::vertex(discoverfrom_nodeid, BGgraph),
+        boost::visitor(record_distance(&distances[0], _max_distance)));
+  } catch (found_max_distance &e) {
+    // where are at discovery horizon
+  }
   LOG(3, "DEBUG: From atom #" << _discoverfrom
       << " BFS discovered the following distances " << distances);

src/Graph/BreadthFirstSearchGatherer.hpp

@@ -35 +35 @@
   /** Discovers all nodes from the given \a _discoverfrom and returns
    * the vector of ids.
+   *
+   * \param _discoverfrom node to start BFS from
+   * \param _max_distance max distance to discover (0 means all)
    */
-  std::vector<atomId_t> operator()(const atomId_t &_discoverfrom);
+  std::vector<atomId_t> operator()(
+      const atomId_t &_discoverfrom,
+      const size_t &_max_distance = 0);
 
 private:

src/Graph/unittests/BreadthFirstSearchGathererUnitTest.cpp

@@ -105 +105 @@
   CPPUNIT_ASSERT_EQUAL (compareids, atomids);
 };
+
+/** Tests whether operator() with limited distance works.
+ */
+void BreadthFirstSearchGathererTest::limitedDistanceTest()
+{
+  // create linear test graph
+  prepareLinearGraph();
+
+  // call operator
+  BreadthFirstSearchGatherer gatherer(*BGCreator);
+  std::vector<atomId_t> atomids = gatherer(0, 3);
+
+  // create comparator set
+  std::vector<atomId_t> compareids;
+  compareids += 0,1,2,3;
+  CPPUNIT_ASSERT_EQUAL ((size_t)4, atomids.size());
+  CPPUNIT_ASSERT_EQUAL (compareids, atomids);
+};

src/Graph/unittests/BreadthFirstSearchGathererUnitTest.hpp

@@ -25 +25 @@
     CPPUNIT_TEST_SUITE( BreadthFirstSearchGathererTest) ;
     CPPUNIT_TEST ( operatorTest );
+    CPPUNIT_TEST ( limitedDistanceTest );
     CPPUNIT_TEST_SUITE_END();
 
@@ -31 +32 @@
       void tearDown();
       void operatorTest();
+      void limitedDistanceTest();
 
 private: