pgr_depthFirstSearch.hpp

Go to the documentation of this file.

/*PGR-GNU*****************************************************************
File: pgr_depthFirstSearch.hpp
 
Copyright (c) 2020 pgRouting developers
Mail: [email protected]
 
Copyright (c) 2020 Ashish Kumar
Mail: [email protected]
 
------
This program 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.
This program 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 this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
********************************************************************PGR-GNU*/
 
#ifndef INCLUDE_TRAVERSAL_PGR_DEPTHFIRSTSEARCH_HPP_
#define INCLUDE_TRAVERSAL_PGR_DEPTHFIRSTSEARCH_HPP_
#pragma once
 
 
#include <visitors/dfs_visitor.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/undirected_dfs.hpp>
 
#include <vector>
#include <map>
 
#include "cpp_common/pgr_base_graph.hpp"
#include "cpp_common/interruption.h"
 
 
namespace pgrouting {
namespace functions {
 
//*************************************************************
 
template < class G >
class Pgr_depthFirstSearch {
 public:
     typedef typename G::V V;
     typedef typename G::E E;
 
     std::vector < pgr_mst_rt > depthFirstSearch(
             G &graph,
             std::vector < int64_t > roots,
             bool directed,
             int64_t max_depth) {
         std::vector < pgr_mst_rt > results;
 
         for (auto root : roots) {
             std::vector < E > visited_order;
             results.push_back({root, 0, root, -1, 0.0, 0.0});
 
             if (graph.has_vertex(root)) {
                 auto v_root(graph.get_V(root));
 
                 depthFirstSearch_single_vertex(graph, v_root, visited_order, directed, max_depth);
 
                 auto result = get_results(visited_order, root, max_depth, graph);
                 results.insert(results.end(), result.begin(), result.end());
             }
         }
 
         return results;
     }
 
 
 private:
     bool depthFirstSearch_single_vertex(
                 G &graph,
                 V root,
                 std::vector < E > &visited_order,
                 bool directed,
                 int64_t max_depth) {
         using dfs_visitor = visitors::Dfs_visitor < V, E, G >;
 
         // Exterior property storage containers
         std::vector < boost::default_color_type > colors(boost::num_vertices(graph.graph));
         std::map < E, boost::default_color_type > edge_color;
 
         auto i_map = boost::get(boost::vertex_index, graph.graph);
 
         // Iterator property maps which record the color of each vertex and edge, respectively
         auto vertex_color_map = boost::make_iterator_property_map(colors.begin(), i_map);
         auto edge_color_map = boost::make_assoc_property_map(edge_color);
 
         auto vis =  dfs_visitor(root, visited_order, max_depth, colors, graph);
 
         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
         CHECK_FOR_INTERRUPTS();
 
         try {
             if (directed) {
                 boost::depth_first_search(graph.graph, vis, vertex_color_map, root);
             } else {
                 boost::undirected_dfs(graph.graph, vis, vertex_color_map, edge_color_map, root);
             }
         } catch(found_goals &) {
             {}
         } catch (boost::exception const& ex) {
             (void)ex;
             throw;
         } catch (std::exception &e) {
             (void)e;
             throw;
         } catch (...) {
             throw;
         }
         return true;
     }
 
     template < typename T >
     std::vector < pgr_mst_rt > get_results(
             T visited_order,
             int64_t root,
             int64_t max_depth,
             const G &graph) {
         std::vector < pgr_mst_rt > results;
 
         std::vector < double > agg_cost(graph.num_vertices(), 0);
         std::vector < int64_t > depth(graph.num_vertices(), 0);
 
         for (const auto edge : visited_order) {
             auto u = graph.source(edge);
             auto v = graph.target(edge);
 
             agg_cost[v] = agg_cost[u] + graph[edge].cost;
             depth[v] = depth[u] + 1;
 
             if (max_depth >= depth[v]) {
                 results.push_back({
                     root,
                     depth[v],
                     graph[v].id,
                     graph[edge].id,
                     graph[edge].cost,
                     agg_cost[v]
                 });
             }
         }
         return results;
     }
};
}  // namespace functions
}  // namespace pgrouting
 
#endif  // INCLUDE_TRAVERSAL_PGR_DEPTHFIRSTSEARCH_HPP_