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

#include "pgr_mst.hpp"

Inheritance diagram for pgrouting::functions::Pgr_mst< G >:

Collaboration diagram for pgrouting::functions::Pgr_mst< G >:

Classes
struct	InSpanning

Protected Types
typedef G::B_G	B_G
typedef G::E	E
typedef G::E_i	E_i
typedef G::V	V

Protected Member Functions
std::vector< pgr_mst_rt >	bfs_order (const G &graph)
void	clear ()
std::vector< pgr_mst_rt >	dfs_order (const G &graph)
virtual void	generate_mst (const G &graph)=0
std::vector< pgr_mst_rt >	mst (const G &graph)
std::vector< pgr_mst_rt >	mstBFS (const G &graph, std::vector< int64_t > roots, int64_t max_depth)
std::vector< pgr_mst_rt >	mstDD (const G &graph, std::vector< int64_t > roots, double distance)
std::vector< pgr_mst_rt >	mstDFS (const G &graph, std::vector< int64_t > roots, int64_t max_depth)
std::vector< pgr_mst_rt >	no_order (const G &graph)

Protected Attributes
std::vector< size_t >	m_components
	m_components[v]: More...
double	m_distance
bool	m_get_component
int64_t	m_max_depth
std::vector< int64_t >	m_roots
struct pgrouting::functions::Pgr_mst::InSpanning	m_spanning_tree
std::string	m_suffix
	Stores which function is being executed. More...
std::vector< int64_t >	m_tree_id
	m_tree_id[v]: More...

Private Member Functions
std::vector< pgr_mst_rt >	bfs_ordering (const G &graph)
void	calculate_component (const G &graph)
std::vector< pgr_mst_rt >	dfs_forest (const G &graph)
std::vector< pgr_mst_rt >	dfs_ordering (const G &graph)
template<typename T >
std::vector< pgr_mst_rt >	get_results (T order, int64_t p_root, const G &graph)
bool	no_neg_costs (const G &graph)
std::vector< pgr_mst_rt >	no_ordering (const G &graph)

Detailed Description

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

Definition at line 48 of file pgr_mst.hpp.

Member Typedef Documentation

B_G

template<class G >

typedef G::B_G pgrouting::functions::Pgr_mst< G >::B_G

protected

Definition at line 50 of file pgr_mst.hpp.

E

template<class G >

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

protected

Definition at line 52 of file pgr_mst.hpp.

E_i

template<class G >

typedef G::E_i pgrouting::functions::Pgr_mst< G >::E_i

protected

Definition at line 53 of file pgr_mst.hpp.

V

template<class G >

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

protected

Definition at line 51 of file pgr_mst.hpp.

Member Function Documentation

bfs_order()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::bfs_order ( const G &  graph )

inlineprotected

Definition at line 76 of file pgr_mst.hpp.

                               {
         return bfs_ordering(graph);
     }

References pgrouting::functions::Pgr_mst< G >::bfs_ordering().

Referenced by pgrouting::functions::Pgr_mst< G >::mstBFS().

bfs_ordering()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::bfs_ordering ( const G &  graph )

inlineprivate

Definition at line 322 of file pgr_mst.hpp.

                                  {
         std::vector<pgr_mst_rt> results;
         /*
          * order by bfs
          */
         boost::filtered_graph<B_G, InSpanning, boost::keep_all>
             mst(graph.graph, m_spanning_tree, {});
 
         calculate_component(graph);
 
         std::vector<int64_t> roots;
         if (!m_roots.empty()) {
             roots = m_roots;
         } else {
             roots =  m_tree_id;
         }
 
         using bfs_visitor = visitors::Edges_order_bfs_visitor<E>;
         for (auto root : roots) {
             std::vector<E> visited_order;
             if (graph.has_vertex(root)) {
                 boost::breadth_first_search(mst,
                         graph.get_V(root),
                         visitor(bfs_visitor(visited_order)));
 
                 auto tree_results = get_results(visited_order, root, graph);
                 results.insert(results.end(), tree_results.begin(), tree_results.end());
             } else {
                 results.push_back({root, 0, root, -1, 0.0, 0.0});
             }
             /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
             CHECK_FOR_INTERRUPTS();
         }
 
         return results;
     }

References pgrouting::functions::Pgr_mst< G >::calculate_component(), pgrouting::functions::Pgr_mst< G >::get_results(), pgrouting::functions::Pgr_mst< G >::m_roots, pgrouting::functions::Pgr_mst< G >::m_spanning_tree, pgrouting::functions::Pgr_mst< G >::m_tree_id, and pgrouting::functions::Pgr_mst< G >::mst().

Referenced by pgrouting::functions::Pgr_mst< G >::bfs_order().

calculate_component()

template<class G >

void pgrouting::functions::Pgr_mst< G >::calculate_component ( const G &  graph )

inlineprivate

Definition at line 225 of file pgr_mst.hpp.

                                              {
         if (!m_get_component) return;
 
         m_components.resize(num_vertices(graph.graph));
 
         /*
          * Calculate connected components
          *
          * Number of components of graph: num_comps components
          */
         auto num_comps = boost::connected_components(
                 graph.graph,
                 &m_components[0]);
 
         m_tree_id.resize(num_comps, 0);
 
         for (const auto v : boost::make_iterator_range(vertices(graph.graph))) {
             m_tree_id[m_components[v]] =
                 (m_tree_id[m_components[v]] == 0
                  || m_tree_id[m_components[v]] >= graph[v].id) ?
                 graph[v].id : m_tree_id[m_components[v]];
         }
     }

References pgrouting::functions::Pgr_mst< G >::m_components, pgrouting::functions::Pgr_mst< G >::m_get_component, and pgrouting::functions::Pgr_mst< G >::m_tree_id.

Referenced by pgrouting::functions::Pgr_mst< G >::bfs_ordering().

clear()

template<class G >

void pgrouting::functions::Pgr_mst< G >::clear ( )

inlineprotected

Definition at line 59 of file pgr_mst.hpp.

                  {
         this->m_spanning_tree.clear();
         this->m_components.clear();
         this->m_tree_id.clear();
     }

References pgrouting::functions::Pgr_mst< G >::InSpanning::clear(), pgrouting::functions::Pgr_mst< G >::m_components, pgrouting::functions::Pgr_mst< G >::m_spanning_tree, and pgrouting::functions::Pgr_mst< G >::m_tree_id.

dfs_forest()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::dfs_forest ( const G &  graph )

inlineprivate

Definition at line 255 of file pgr_mst.hpp.

                                    {
             boost::filtered_graph<B_G, InSpanning, boost::keep_all>
                 mstGraph(graph.graph, m_spanning_tree, {});
             std::vector<E> visited_order;
 
             using dfs_visitor = visitors::Edges_order_dfs_visitor<E>;
             /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
             CHECK_FOR_INTERRUPTS();
             try {
                 boost::depth_first_search(mstGraph, visitor(dfs_visitor(visited_order)));
             } catch (boost::exception const& ex) {
                 (void)ex;
                 throw;
             } catch (std::exception &e) {
                 (void)e;
                 throw;
             } catch (...) {
                 throw;
             }
 
             return get_results(visited_order, 0, graph);
         }

References pgrouting::functions::Pgr_mst< G >::get_results(), and pgrouting::functions::Pgr_mst< G >::m_spanning_tree.

Referenced by pgrouting::functions::Pgr_mst< G >::dfs_ordering().

dfs_order()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::dfs_order ( const G &  graph )

inlineprotected

Definition at line 71 of file pgr_mst.hpp.

                               {
         return dfs_ordering(graph);
     }

References pgrouting::functions::Pgr_mst< G >::dfs_ordering().

Referenced by pgrouting::functions::Pgr_mst< G >::mstDD(), and pgrouting::functions::Pgr_mst< G >::mstDFS().

dfs_ordering()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::dfs_ordering ( const G &  graph )

inlineprivate

Definition at line 280 of file pgr_mst.hpp.

                                      {
             boost::filtered_graph<B_G, InSpanning, boost::keep_all>
                 mstGraph(graph.graph, m_spanning_tree, {});
 
             if (m_roots.empty()) {
                 return dfs_forest(graph);
             } else {
                 std::vector<pgr_mst_rt> results;
                 for (const auto root : m_roots) {
                     std::vector<E> visited_order;
 
                     using dfs_visitor = visitors::Dfs_visitor_with_root<V, E>;
                     if (graph.has_vertex(root)) {
                         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
                         CHECK_FOR_INTERRUPTS();
                         try {
                             boost::depth_first_search(
                                     mstGraph,
                                     visitor(dfs_visitor(graph.get_V(root), visited_order))
                                     .root_vertex(graph.get_V(root)));
                         } catch(found_goals &) {
                             {}
                         } catch (boost::exception const& ex) {
                             (void)ex;
                             throw;
                         } catch (std::exception &e) {
                             (void)e;
                             throw;
                         } catch (...) {
                             throw;
                         }
                         auto result = get_results(visited_order, root, graph);
                         results.insert(results.end(), result.begin(), result.end());
                     } else {
                         results.push_back({root, 0, root, -1, 0.0, 0.0});
                     }
                 }
                 return results;
             }
         }

References pgrouting::functions::Pgr_mst< G >::dfs_forest(), pgrouting::functions::Pgr_mst< G >::get_results(), pgrouting::functions::Pgr_mst< G >::m_roots, and pgrouting::functions::Pgr_mst< G >::m_spanning_tree.

Referenced by pgrouting::functions::Pgr_mst< G >::dfs_order().

generate_mst()

template<class G >

virtual void pgrouting::functions::Pgr_mst< G >::generate_mst ( const G &  graph )

protectedpure virtual

Implemented in pgrouting::functions::Pgr_prim< G >, and pgrouting::functions::Pgr_kruskal< G >.

Referenced by pgrouting::functions::Pgr_mst< G >::mst(), pgrouting::functions::Pgr_mst< G >::mstBFS(), pgrouting::functions::Pgr_mst< G >::mstDD(), and pgrouting::functions::Pgr_mst< G >::mstDFS().

get_results()

template<class G >

template<typename T >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::get_results ( T  order, int64_t  p_root, const G &  graph  )

inlineprivate

Definition at line 170 of file pgr_mst.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);
         int64_t root(p_root);
 
         for (const auto edge : order) {
             auto u = graph.source(edge);
             auto v = graph.target(edge);
             if (depth[u] == 0 && depth[v] != 0) {
                 std::swap(u, v);
             }
 
             auto component = m_get_component? m_tree_id[m_components[u]] : 0;
             if (m_suffix != "" && depth[u] == 0 && depth[v] == 0) {
                 if (!m_roots.empty() && graph[u].id != root) std::swap(u, v);
                 if (m_roots.empty() && graph[u].id != component) std::swap(u, v);
                 if (!p_root && graph[u].id > graph[v].id) std::swap(u, v);
 
                 root = p_root? p_root: graph[u].id;
                 depth[u] = -1;
                 results.push_back({
                     root,
                         0,
                         graph[u].id,
                         -1,
                         0.0,
                         0.0 });
             }
 
             agg_cost[v] = agg_cost[u] + graph[edge].cost;
             depth[v] = depth[u] == -1? 1 : depth[u] + 1;
 
             if ((m_suffix == "")
                     || ((m_suffix == "BFS")   && (m_max_depth >= depth[v]))
                     || ((m_suffix == "DFS")  && m_max_depth >= depth[v])
                     || ((m_suffix == "DD")  && m_distance >= agg_cost[v])) {
                 results.push_back({
                     root,
                         m_suffix != ""? depth[v] : 0,
                         graph[v].id,
                         graph[edge].id,
                         graph[edge].cost,
                         m_suffix != ""? agg_cost[v] : 0.0
                 });
             }
         }
         return results;
     }

References pgrouting::functions::Pgr_mst< G >::m_components, pgrouting::functions::Pgr_mst< G >::m_distance, pgrouting::functions::Pgr_mst< G >::m_get_component, pgrouting::functions::Pgr_mst< G >::m_max_depth, pgrouting::functions::Pgr_mst< G >::m_roots, pgrouting::functions::Pgr_mst< G >::m_suffix, and pgrouting::functions::Pgr_mst< G >::m_tree_id.

Referenced by pgrouting::functions::Pgr_mst< G >::bfs_ordering(), pgrouting::functions::Pgr_mst< G >::dfs_forest(), pgrouting::functions::Pgr_mst< G >::dfs_ordering(), and pgrouting::functions::Pgr_mst< G >::no_ordering().

mst()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::mst ( const G &  graph )

inlineprotected

Definition at line 80 of file pgr_mst.hpp.

                                               {
         m_suffix = "";
         m_get_component = false;
         m_distance = -1;
         m_max_depth = -1;
         m_roots.clear();
 
         no_neg_costs(graph);
         this->generate_mst(graph);
         return no_order(graph);
     }

References pgrouting::functions::Pgr_mst< G >::generate_mst(), pgrouting::functions::Pgr_mst< G >::m_distance, pgrouting::functions::Pgr_mst< G >::m_get_component, pgrouting::functions::Pgr_mst< G >::m_max_depth, pgrouting::functions::Pgr_mst< G >::m_roots, pgrouting::functions::Pgr_mst< G >::m_suffix, pgrouting::functions::Pgr_mst< G >::no_neg_costs(), and pgrouting::functions::Pgr_mst< G >::no_order().

Referenced by pgrouting::functions::Pgr_mst< G >::bfs_ordering().

mstBFS()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::mstBFS ( const G &  graph, std::vector< int64_t >  roots, int64_t  max_depth  )

inlineprotected

Definition at line 93 of file pgr_mst.hpp.

                                {
         m_suffix = "BFS";
         m_get_component = true;
         m_distance = -1;
         m_max_depth = max_depth;
         m_roots = details::clean_vids(roots);
 
         this->generate_mst(graph);
         return bfs_order(graph);
     }

References pgrouting::functions::Pgr_mst< G >::bfs_order(), pgrouting::details::clean_vids(), pgrouting::functions::Pgr_mst< G >::generate_mst(), pgrouting::functions::Pgr_mst< G >::m_distance, pgrouting::functions::Pgr_mst< G >::m_get_component, pgrouting::functions::Pgr_mst< G >::m_max_depth, pgrouting::functions::Pgr_mst< G >::m_roots, and pgrouting::functions::Pgr_mst< G >::m_suffix.

mstDD()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::mstDD ( const G &  graph, std::vector< int64_t >  roots, double  distance  )

inlineprotected

Definition at line 121 of file pgr_mst.hpp.

                              {
         m_suffix = "DD";
         m_get_component = false;
         m_distance = distance;
         m_max_depth = -1;
         m_roots = details::clean_vids(roots);
 
         this->generate_mst(graph);
         return dfs_order(graph);
     }

References pgrouting::details::clean_vids(), pgrouting::functions::Pgr_mst< G >::dfs_order(), pgrouting::functions::Pgr_mst< G >::generate_mst(), pgrouting::functions::Pgr_mst< G >::m_distance, pgrouting::functions::Pgr_mst< G >::m_get_component, pgrouting::functions::Pgr_mst< G >::m_max_depth, pgrouting::functions::Pgr_mst< G >::m_roots, and pgrouting::functions::Pgr_mst< G >::m_suffix.

mstDFS()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::mstDFS ( const G &  graph, std::vector< int64_t >  roots, int64_t  max_depth  )

inlineprotected

Definition at line 107 of file pgr_mst.hpp.

                                {
         m_suffix = "DFS";
         m_get_component = false;
         m_distance = -1;
         m_max_depth = max_depth;
         m_roots = details::clean_vids(roots);
 
         this->generate_mst(graph);
         return dfs_order(graph);
     }

References pgrouting::details::clean_vids(), pgrouting::functions::Pgr_mst< G >::dfs_order(), pgrouting::functions::Pgr_mst< G >::generate_mst(), pgrouting::functions::Pgr_mst< G >::m_distance, pgrouting::functions::Pgr_mst< G >::m_get_component, pgrouting::functions::Pgr_mst< G >::m_max_depth, pgrouting::functions::Pgr_mst< G >::m_roots, and pgrouting::functions::Pgr_mst< G >::m_suffix.

no_neg_costs()

template<class G >

bool pgrouting::functions::Pgr_mst< G >::no_neg_costs ( const G &  graph )

inlineprivate

Definition at line 359 of file pgr_mst.hpp.

                                       {
         E_i  ei, ei_end;
         for (boost::tie(ei, ei_end) = edges(graph.graph); ei != ei_end; ++ei)
             pgassert(graph[*ei].cost > 0);
         return true;
     }

References pgassert.

Referenced by pgrouting::functions::Pgr_mst< G >::mst().

no_order()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::no_order ( const G &  graph )

inlineprotected

Definition at line 66 of file pgr_mst.hpp.

                              {
         return no_ordering(graph);
     }

References pgrouting::functions::Pgr_mst< G >::no_ordering().

Referenced by pgrouting::functions::Pgr_mst< G >::mst().

no_ordering()

template<class G >

std::vector<pgr_mst_rt> pgrouting::functions::Pgr_mst< G >::no_ordering ( const G &  graph )

inlineprivate

Definition at line 250 of file pgr_mst.hpp.

                                     {
             return get_results(m_spanning_tree.edges, 0, graph);
         }

References pgrouting::functions::Pgr_mst< G >::InSpanning::edges, pgrouting::functions::Pgr_mst< G >::get_results(), and pgrouting::functions::Pgr_mst< G >::m_spanning_tree.

Referenced by pgrouting::functions::Pgr_mst< G >::no_order().

Member Data Documentation

m_components

template<class G >

std::vector<size_t> pgrouting::functions::Pgr_mst< G >::m_components

protected

m_components[v]:

• is empty (when m_get_component = 0)
• has the component number of vertex v (when m_get_component != 0)

Definition at line 152 of file pgr_mst.hpp.

Referenced by pgrouting::functions::Pgr_mst< G >::calculate_component(), pgrouting::functions::Pgr_mst< G >::clear(), and pgrouting::functions::Pgr_mst< G >::get_results().

m_distance

template<class G >

double pgrouting::functions::Pgr_mst< G >::m_distance

protected

Definition at line 139 of file pgr_mst.hpp.

Referenced by pgrouting::functions::Pgr_mst< G >::get_results(), pgrouting::functions::Pgr_mst< G >::mst(), pgrouting::functions::Pgr_mst< G >::mstBFS(), pgrouting::functions::Pgr_mst< G >::mstDD(), and pgrouting::functions::Pgr_mst< G >::mstDFS().

m_get_component

template<class G >

bool pgrouting::functions::Pgr_mst< G >::m_get_component

protected

Definition at line 137 of file pgr_mst.hpp.

Referenced by pgrouting::functions::Pgr_mst< G >::calculate_component(), pgrouting::functions::Pgr_mst< G >::get_results(), pgrouting::functions::Pgr_mst< G >::mst(), pgrouting::functions::Pgr_mst< G >::mstBFS(), pgrouting::functions::Pgr_mst< G >::mstDD(), and pgrouting::functions::Pgr_mst< G >::mstDFS().

m_max_depth

template<class G >

int64_t pgrouting::functions::Pgr_mst< G >::m_max_depth

protected

Definition at line 138 of file pgr_mst.hpp.

Referenced by pgrouting::functions::Pgr_mst< G >::get_results(), pgrouting::functions::Pgr_mst< G >::mst(), pgrouting::functions::Pgr_mst< G >::mstBFS(), pgrouting::functions::Pgr_mst< G >::mstDD(), and pgrouting::functions::Pgr_mst< G >::mstDFS().

m_roots

template<class G >

std::vector<int64_t> pgrouting::functions::Pgr_mst< G >::m_roots

protected

Definition at line 136 of file pgr_mst.hpp.

Referenced by pgrouting::functions::Pgr_mst< G >::bfs_ordering(), pgrouting::functions::Pgr_mst< G >::dfs_ordering(), pgrouting::functions::Pgr_mst< G >::get_results(), pgrouting::functions::Pgr_mst< G >::mst(), pgrouting::functions::Pgr_mst< G >::mstBFS(), pgrouting::functions::Pgr_mst< G >::mstDD(), and pgrouting::functions::Pgr_mst< G >::mstDFS().

m_spanning_tree

template<class G >

struct pgrouting::functions::Pgr_mst::InSpanning pgrouting::functions::Pgr_mst< G >::m_spanning_tree

protected

Referenced by pgrouting::functions::Pgr_mst< G >::bfs_ordering(), pgrouting::functions::Pgr_mst< G >::clear(), pgrouting::functions::Pgr_mst< G >::dfs_forest(), pgrouting::functions::Pgr_mst< G >::dfs_ordering(), and pgrouting::functions::Pgr_mst< G >::no_ordering().

m_suffix

template<class G >

std::string pgrouting::functions::Pgr_mst< G >::m_suffix

protected

Stores which function is being executed.

TODO change to enum

Definition at line 159 of file pgr_mst.hpp.

Referenced by pgrouting::functions::Pgr_mst< G >::get_results(), pgrouting::functions::Pgr_mst< G >::mst(), pgrouting::functions::Pgr_mst< G >::mstBFS(), pgrouting::functions::Pgr_mst< G >::mstDD(), and pgrouting::functions::Pgr_mst< G >::mstDFS().

m_tree_id

template<class G >

std::vector<int64_t> pgrouting::functions::Pgr_mst< G >::m_tree_id

protected

m_tree_id[v]:

• is empty (when m_get_component = 0)
• has the component number of vertex v (when m_get_component = 1)
• has the min vertex id that belongs to the component (when m_get_component = 2)

Definition at line 166 of file pgr_mst.hpp.

Referenced by pgrouting::functions::Pgr_mst< G >::bfs_ordering(), pgrouting::functions::Pgr_mst< G >::calculate_component(), pgrouting::functions::Pgr_mst< G >::clear(), and pgrouting::functions::Pgr_mst< G >::get_results().

---

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

• pgr_mst.hpp