pgrouting::functions::Pgr_depthFirstSearch< G > Class Template Reference

#include "pgr_depthFirstSearch.hpp"

Public Types
typedef G::E	E
typedef G::V	V

DepthFirstSearch
std::vector< pgr_mst_rt >	depthFirstSearch (G &graph, std::vector< int64_t > roots, bool directed, int64_t max_depth)
	depthFirstSearch function More...
bool	depthFirstSearch_single_vertex (G &graph, V root, std::vector< E > &visited_order, bool directed, int64_t max_depth)
	Calls the Boost function. More...
template<typename T >
std::vector< pgr_mst_rt >	get_results (T visited_order, int64_t root, int64_t max_depth, const G &graph)
	to get the results More...

Detailed Description

template<class G>
class pgrouting::functions::Pgr_depthFirstSearch< G >

Definition at line 54 of file pgr_depthFirstSearch.hpp.

Member Typedef Documentation

E

template<class G >

typedef G::E pgrouting::functions::Pgr_depthFirstSearch< G >::E

Definition at line 57 of file pgr_depthFirstSearch.hpp.

V

template<class G >

typedef G::V pgrouting::functions::Pgr_depthFirstSearch< G >::V

Definition at line 56 of file pgr_depthFirstSearch.hpp.

Member Function Documentation

depthFirstSearch()

template<class G >

std::vector< pgr_mst_rt > pgrouting::functions::Pgr_depthFirstSearch< G >::depthFirstSearch ( G &  graph, std::vector< int64_t >  roots, bool  directed, int64_t  max_depth  )

inline

depthFirstSearch function

It does all the processing and returns the results.

Parameters

graph	the graph containing the edges
roots	the root vertices
max_depth	the maximum depth of traversal
directed	whether the graph is directed or undirected

Returns

results, when results are found

See also

boost::depth_first_search

boost::undirected_dfs

Definition at line 80 of file pgr_depthFirstSearch.hpp.

                                {
         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;
     }

References pgrouting::functions::Pgr_depthFirstSearch< G >::depthFirstSearch_single_vertex(), and pgrouting::functions::Pgr_depthFirstSearch< G >::get_results().

Referenced by pgr_depthFirstSearch().

depthFirstSearch_single_vertex()

template<class G >

bool pgrouting::functions::Pgr_depthFirstSearch< G >::depthFirstSearch_single_vertex ( G &  graph, V  root, std::vector< E > &  visited_order, bool  directed, int64_t  max_depth  )

inlineprivate

Calls the Boost function.

Calls boost::depth_first_search and boost::undirected_dfs for directed graphs and undirected graphs, respectively.

Parameters

graph	the graph containing the edges
root	the root vertex
visited_order	vector which will contain the edges of the resulting traversal
directed	whether the graph is directed or undirected

Returns

bool true, when results are found

Definition at line 122 of file pgr_depthFirstSearch.hpp.

                                    {
         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;
     }

Referenced by pgrouting::functions::Pgr_depthFirstSearch< G >::depthFirstSearch().

get_results()

template<class G >

template<typename T >

std::vector< pgr_mst_rt > pgrouting::functions::Pgr_depthFirstSearch< G >::get_results ( T  visited_order, int64_t  root, int64_t  max_depth, const G &  graph  )

inlineprivate

to get the results

Uses the visited_order of vertices to get the results. Selects only those nodes in the final result whose depth is less than the max_depth.

Parameters

visited_order	vector which contains the edges of the resulting traversal
root	the root vertex
max_depth	the maximum depth of traversal
graph	the graph containing the edges

Returns

results vector

Definition at line 179 of file pgr_depthFirstSearch.hpp.

                             {
         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;
     }

Referenced by pgrouting::functions::Pgr_depthFirstSearch< G >::depthFirstSearch().

---

The documentation for this class was generated from the following file:

• pgr_depthFirstSearch.hpp