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

#include "pgr_prim.hpp"

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

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

Public Member Functions
std::vector< pgr_mst_rt >	prim (G &graph)
std::vector< pgr_mst_rt >	primBFS (G &graph, std::vector< int64_t > roots, int64_t max_depth)
std::vector< pgr_mst_rt >	primDD (G &graph, std::vector< int64_t > roots, double distance)
std::vector< pgr_mst_rt >	primDFS (G &graph, std::vector< int64_t > roots, int64_t max_depth)

Protected Types
typedef G::E_i	E_i

Protected Member Functions
std::vector< pgr_mst_rt >	bfs_order (const G &graph)
std::vector< pgr_mst_rt >	dfs_order (const G &graph)
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 Types
typedef G::B_G	B_G
typedef G::E	E
typedef G::V	V

Private Member Functions
std::vector< pgr_mst_rt >	bfs_ordering (const G &graph)
void	calculate_component (const G &graph)
void	clear ()
std::vector< pgr_mst_rt >	dfs_forest (const G &graph)
std::vector< pgr_mst_rt >	dfs_ordering (const G &graph)
void	generate_mst (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)
void	primTree (const G &graph, int64_t root_vertex)

Private Attributes
std::vector< V >	data
std::vector< double >	distances
std::set< V >	m_unassigned
std::vector< V >	predecessors

Detailed Description

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

Definition at line 47 of file pgr_prim.hpp.

Member Typedef Documentation

B_G

template<class G >

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

private

Definition at line 50 of file pgr_prim.hpp.

E

template<class G >

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

private

Definition at line 49 of file pgr_prim.hpp.

E_i

template<class G >

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

protectedinherited

Definition at line 53 of file pgr_mst.hpp.

V

template<class G >

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

private

Definition at line 48 of file pgr_prim.hpp.

Member Function Documentation

bfs_order()

template<class G >

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

inlineprotectedinherited

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 )

inlineprivateinherited

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 )

inlineprivateinherited

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_prim< G >::clear ( )

inlineprivate

Definition at line 73 of file pgr_prim.hpp.

                  {
         data.clear();
         predecessors.clear();
         distances.clear();
     }

References pgrouting::functions::Pgr_prim< G >::data, pgrouting::functions::Pgr_prim< G >::distances, and pgrouting::functions::Pgr_prim< G >::predecessors.

dfs_forest()

template<class G >

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

inlineprivateinherited

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 )

inlineprotectedinherited

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 )

inlineprivateinherited

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 >

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

privatevirtual

Implements pgrouting::functions::Pgr_mst< G >.

Definition at line 144 of file pgr_prim.hpp.

                                        {
    this->clear();
 
    size_t totalNodes = num_vertices(graph.graph);
 
    m_unassigned.clear();
    for (V v = 0; v < totalNodes; ++v) {
            m_unassigned.insert(m_unassigned.end(), v);
    }
 
    while (!m_unassigned.empty()) {
        auto root = *m_unassigned.begin();
        m_unassigned.erase(m_unassigned.begin());
        primTree(
                graph,
                graph.graph[root].id);
    }
}

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  )

inlineprivateinherited

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 )

inlineprotectedinherited

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  )

inlineprotectedinherited

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  )

inlineprotectedinherited

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  )

inlineprotectedinherited

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 )

inlineprivateinherited

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 )

inlineprotectedinherited

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 )

inlineprivateinherited

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().

prim()

template<class G >

std::vector< pgr_mst_rt > pgrouting::functions::Pgr_prim< G >::prim

(

G &

graph

)

Definition at line 165 of file pgr_prim.hpp.

                  {
    return this->mst(graph);
}

Referenced by do_pgr_prim().

primBFS()

template<class G >

std::vector< pgr_mst_rt > pgrouting::functions::Pgr_prim< G >::primBFS	(	G &	graph,
		std::vector< int64_t >	roots,
		int64_t	max_depth
	)

Definition at line 172 of file pgr_prim.hpp.

                           {
    return this->mstBFS(graph, roots, max_depth);
}

Referenced by do_pgr_prim().

primDD()

template<class G >

std::vector< pgr_mst_rt > pgrouting::functions::Pgr_prim< G >::primDD	(	G &	graph,
		std::vector< int64_t >	roots,
		double	distance
	)

Definition at line 190 of file pgr_prim.hpp.

                         {
    return this->mstDD(graph, roots, distance);
}

Referenced by do_pgr_prim().

primDFS()

template<class G >

std::vector< pgr_mst_rt > pgrouting::functions::Pgr_prim< G >::primDFS	(	G &	graph,
		std::vector< int64_t >	roots,
		int64_t	max_depth
	)

Definition at line 181 of file pgr_prim.hpp.

                           {
    return this->mstDFS(graph, roots, max_depth);
}

Referenced by do_pgr_prim().

primTree()

template<class G >

void pgrouting::functions::Pgr_prim< G >::primTree ( const G &  graph, int64_t  root_vertex  )

private

Definition at line 96 of file pgr_prim.hpp.

                             {
    clear();
 
    predecessors.resize(graph.num_vertices());
    distances.resize(graph.num_vertices());
 
    auto v_root(graph.get_V(root_vertex));
 
    using prim_visitor = visitors::Prim_dijkstra_visitor<V>;
 
    /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
    CHECK_FOR_INTERRUPTS();
 
    boost::prim_minimum_spanning_tree(
            graph.graph,
            &predecessors[0],
            boost::distance_map(&distances[0]).
            weight_map(get(&G::G_T_E::cost, graph.graph))
            .root_vertex(v_root)
            .visitor(prim_visitor(data)));
 
    for (const auto v : data) {
        /*
         * its not a tree, its a forest
         * - v is not on current tree
         */
        if (std::isinf(distances[v])) continue;
        m_unassigned.erase(v);
 
 
        auto u = predecessors[v];
 
        /*
         * Not a valid edge
         */
        if (u == v) continue;
 
        auto cost = distances[u] - distances[v];
        auto edge = graph.get_edge(u, v, cost);
        this->m_spanning_tree.edges.insert(edge);
    }
}

Member Data Documentation

data

template<class G >

std::vector<V> pgrouting::functions::Pgr_prim< G >::data

private

Definition at line 89 of file pgr_prim.hpp.

Referenced by pgrouting::functions::Pgr_prim< G >::clear().

distances

template<class G >

std::vector<double> pgrouting::functions::Pgr_prim< G >::distances

private

Definition at line 88 of file pgr_prim.hpp.

Referenced by pgrouting::functions::Pgr_prim< G >::clear().

m_components

template<class G >

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

protectedinherited

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

protectedinherited

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

protectedinherited

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

protectedinherited

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

protectedinherited

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

protectedinherited

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

protectedinherited

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

protectedinherited

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().

m_unassigned

template<class G >

std::set<V> pgrouting::functions::Pgr_prim< G >::m_unassigned

private

Definition at line 90 of file pgr_prim.hpp.

predecessors

template<class G >

std::vector<V> pgrouting::functions::Pgr_prim< G >::predecessors

private

Definition at line 87 of file pgr_prim.hpp.

Referenced by pgrouting::functions::Pgr_prim< G >::clear().

---

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

• pgr_prim.hpp