Changeset e3ec8a8 for src/Graph/BreadthFirstSearchGatherer.cpp

Timestamp:

Jul 12, 2017, 7:10:32 PM (8 years ago)

Author:

Frederik Heber <frederik.heber@…>

Branches:

Action_Thermostats, Adding_Graph_to_ChangeBondActions, Adding_MD_integration_tests, Adding_StructOpt_integration_tests, AutomationFragmentation_failures, Candidate_v1.6.1, ChemicalSpaceEvaluator, Enhanced_StructuralOptimization, Enhanced_StructuralOptimization_continued, Exclude_Hydrogens_annealWithBondGraph, Fix_Verbose_Codepatterns, ForceAnnealing_with_BondGraph, ForceAnnealing_with_BondGraph_continued, ForceAnnealing_with_BondGraph_continued_betteresults, ForceAnnealing_with_BondGraph_contraction-expansion, Gui_displays_atomic_force_velocity, JobMarket_RobustOnKillsSegFaults, JobMarket_StableWorkerPool, PythonUI_with_named_parameters, Recreated_GuiChecks, StoppableMakroAction, TremoloParser_IncreasedPrecision

Children:

966ce7

Parents:

0dc8bf2

git-author:

Frederik Heber <frederik.heber@…> (05/19/17 09:27:11)

git-committer:

Frederik Heber <frederik.heber@…> (07/12/17 19:10:32)

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 int _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 int 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 int &_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);