source: src/Graph/BreadthFirstSearchGatherer.cpp@ 1e06ed

/*
 * Project: MoleCuilder
 * Description: creates and alters molecular systems
 * Copyright (C)  2017 Frederik Heber. All rights reserved.
 *
 *
 *   This file is part of MoleCuilder.
 *
 *    MoleCuilder is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    MoleCuilder is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoleCuilder.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 * BreadthFirstSearchGatherer.cpp
 *
 *  Created on: May 17, 2017
 *      Author: heber
 */


// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

//#include "CodePatterns/MemDebug.hpp"

#include "BreadthFirstSearchGatherer.hpp"

#include "CodePatterns/Log.hpp"

#include "Graph/BoostGraphCreator.hpp"

#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 ...
 *
 * This is taken from the book "The Boost Graph Library: User Guide and Reference Manual, Portable Documents",
 * chapter "Basic Graph Algorithms", example on calculating the bacon number.
 */
template <typename DistanceMap>
class distance_recorder : public boost::default_bfs_visitor
{
public:
  distance_recorder(
      DistanceMap dist,
      const int _max_distance) : d(dist), max_distance(_max_distance) {}

  template <typename Edge, typename Graph>
  void tree_edge(Edge e, const Graph &g) const {
    typename boost::graph_traits<Graph>::vertex_descriptor u = source(e,g), v = target(e,g);
    d[v] = d[u] + 1;
  }

  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, const size_t _max_distance)
{
  return distance_recorder<DistanceMap>(d, _max_distance);
}

BreadthFirstSearchGatherer::BreadthFirstSearchGatherer(BoostGraphCreator &_BGcreator) :
    BGcreator(_BGcreator)
{}

std::vector<atomId_t> BreadthFirstSearchGatherer::operator()(
    const atomId_t &_discoverfrom,
    const int &_max_distance)
{
  std::vector<atomId_t> returnids;

  // Do BFS through graph from given vertex
  const size_t num_vertices = BGcreator.getNumVertices();
  distances_t distances(num_vertices, num_vertices+1); // set distance to num+1
  const BoostGraphCreator::UndirectedGraph &BGgraph = BGcreator.get();
  const BoostGraphCreator::nodeId_t discoverfrom_nodeid = BGcreator.getNodeId(_discoverfrom);
  distances[ boost::vertex(discoverfrom_nodeid, BGgraph) ] = 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);

  // any node was discovered whose distances is less than num_vertices+1
  distance_map.clear();
  const BoostGraphCreator::const_name_map_t name_map = boost::get(boost::vertex_name, BGgraph);
  BoostGraphCreator::vertex_iter vp, vpend;
  for (boost::tie(vp, vpend) = vertices(BGgraph); vp != vpend; ++vp) {
    BoostGraphCreator::Vertex v = *vp;
    if (distances[v] != (num_vertices+1)) {
      returnids.push_back( boost::get(name_map, v) );
      distance_map.insert( std::make_pair(boost::get(name_map, v), distances[v]) );
    }
  }

  return returnids;
}