Changeset e3ec8a8 for src/Graph


Ignore:
Timestamp:
Jul 12, 2017, 7:10:32 PM (7 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.
Location:
src/Graph
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/Graph/BoostGraphCreator.hpp

    r0dc8bf2 re3ec8a8  
    4141
    4242public:
     43
    4344  //!> typedef for an undirected graph using boost::graph
    4445  typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS,
    45       boost::property<boost::vertex_name_t, atomId_t>, boost::no_property > UndirectedGraph;
     46      boost::property<boost::vertex_name_t, atomId_t>,
     47      boost::property<boost::vertex_color_t, boost::default_color_type> /* needed for limited-depth DFS,
     48      otherwise the property_map gets full size of graph */
     49  > UndirectedGraph;
     50
    4651  //!> typedef for a map of graph node indices
    4752  typedef boost::property_map < UndirectedGraph, boost::vertex_index_t >::type index_map_t;
  • src/Graph/BreadthFirstSearchGatherer.cpp

    r0dc8bf2 re3ec8a8  
    4444#include <boost/graph/breadth_first_search.hpp>
    4545
     46struct found_max_distance {}; // exception when doing limited BFS
     47
    4648/**
    4749 * I have no idea why this is so complicated with BGL ...
     
    5456{
    5557public:
    56   distance_recorder(DistanceMap dist) : d(dist) {}
     58  distance_recorder(
     59      DistanceMap dist,
     60      const int _max_distance) : d(dist), max_distance(_max_distance) {}
    5761
    5862  template <typename Edge, typename Graph>
     
    6266  }
    6367
     68  template <typename Vertex, typename Graph>
     69  void discover_vertex(Vertex u, const Graph &g) const {
     70    if ((max_distance >= 0) && (d[u] >= max_distance))
     71      throw found_max_distance();
     72  }
     73
    6474private:
    6575  DistanceMap d;
     76  const int max_distance;
    6677};
    6778
    6879template <typename DistanceMap>
    69 distance_recorder<DistanceMap> record_distance(DistanceMap d)
     80distance_recorder<DistanceMap> record_distance(DistanceMap d, const size_t _max_distance)
    7081{
    71   return distance_recorder<DistanceMap>(d);
     82  return distance_recorder<DistanceMap>(d, _max_distance);
    7283}
    7384
     
    7687{}
    7788
    78 std::vector<atomId_t> BreadthFirstSearchGatherer::operator()(const atomId_t &_discoverfrom)
     89std::vector<atomId_t> BreadthFirstSearchGatherer::operator()(
     90    const atomId_t &_discoverfrom,
     91    const int &_max_distance)
    7992{
    8093  std::vector<atomId_t> returnids;
     
    8699  const BoostGraphCreator::nodeId_t discoverfrom_nodeid = BGcreator.getNodeId(_discoverfrom);
    87100  distances[ boost::vertex(discoverfrom_nodeid, BGgraph) ] = 0;
    88   boost::breadth_first_search(
    89       BGgraph,
    90       boost::vertex(discoverfrom_nodeid, BGgraph),
    91       boost::visitor(record_distance(&distances[0])));
     101  try {
     102    boost::breadth_first_search(
     103        BGgraph,
     104        boost::vertex(discoverfrom_nodeid, BGgraph),
     105        boost::visitor(record_distance(&distances[0], _max_distance)));
     106  } catch (found_max_distance &e) {
     107    // where are at discovery horizon
     108  }
    92109  LOG(3, "DEBUG: From atom #" << _discoverfrom
    93110      << " BFS discovered the following distances " << distances);
  • src/Graph/BreadthFirstSearchGatherer.hpp

    r0dc8bf2 re3ec8a8  
    3535  /** Discovers all nodes from the given \a _discoverfrom and returns
    3636   * the vector of ids.
     37   *
     38   * \param _discoverfrom node to start BFS from
     39   * \param _max_distance max distance to discover (negative means all)
    3740   */
    38   std::vector<atomId_t> operator()(const atomId_t &_discoverfrom);
     41  std::vector<atomId_t> operator()(
     42      const atomId_t &_discoverfrom,
     43      const int &_max_distance = -1);
    3944
    4045private:
  • src/Graph/unittests/BreadthFirstSearchGathererUnitTest.cpp

    r0dc8bf2 re3ec8a8  
    105105  CPPUNIT_ASSERT_EQUAL (compareids, atomids);
    106106};
     107
     108/** Tests whether operator() with limited distance works.
     109 */
     110void BreadthFirstSearchGathererTest::limitedDistanceTest()
     111{
     112  // create linear test graph
     113  prepareLinearGraph();
     114
     115  // call operator
     116  BreadthFirstSearchGatherer gatherer(*BGCreator);
     117  {
     118    std::vector<atomId_t> atomids = gatherer(0, 3);
     119
     120    // create comparator set
     121    std::vector<atomId_t> compareids;
     122    compareids += 1,2,3,4;
     123    CPPUNIT_ASSERT_EQUAL ((size_t)4, atomids.size());
     124    CPPUNIT_ASSERT_EQUAL (compareids, atomids);
     125  }
     126  // zero distance means just find the initial node
     127  {
     128    std::vector<atomId_t> atomids = gatherer(0, 0);
     129
     130    // create comparator set
     131    std::vector<atomId_t> compareids;
     132    compareids += 1;
     133    CPPUNIT_ASSERT_EQUAL ((size_t)1, atomids.size());
     134    CPPUNIT_ASSERT_EQUAL (compareids, atomids);
     135  }
     136  // negative distance means find all
     137  {
     138    std::vector<atomId_t> atomids = gatherer(0, -1);
     139
     140    // create comparator set
     141    std::vector<atomId_t> compareids;
     142    compareids += 1,2,3,4,5;
     143    CPPUNIT_ASSERT_EQUAL ((size_t)5, atomids.size());
     144    CPPUNIT_ASSERT_EQUAL (compareids, atomids);
     145  }
     146};
  • src/Graph/unittests/BreadthFirstSearchGathererUnitTest.hpp

    r0dc8bf2 re3ec8a8  
    2525    CPPUNIT_TEST_SUITE( BreadthFirstSearchGathererTest) ;
    2626    CPPUNIT_TEST ( operatorTest );
     27    CPPUNIT_TEST ( limitedDistanceTest );
    2728    CPPUNIT_TEST_SUITE_END();
    2829
     
    3132      void tearDown();
    3233      void operatorTest();
     34      void limitedDistanceTest();
    3335
    3436private:
Note: See TracChangeset for help on using the changeset viewer.