Changeset 060fc3 for src/Graph/BreadthFirstSearchGatherer.cpp

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.

File:

• src/Graph/BreadthFirstSearchGatherer.cpp (modified) (5 diffs)

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);