1 /*PGR-GNU*****************************************************************
2 File: pgr_prim.hpp
3
4 Copyright (c) 2018 pgRouting developers
5 Mail: project@pgrouting.org
6
7 Copyright (c) 2018 Aditya Pratap Singh
8 adityapratap.singh28@gmail.com
9
10 ------
11
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version.
16
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25
26 ********************************************************************PGR-GNU*/
27
28 #ifndef INCLUDE_SPANNINGTREE_PGR_PRIM_HPP_
29 #define INCLUDE_SPANNINGTREE_PGR_PRIM_HPP_
30 #pragma once
31
32 #include <visitors/prim_dijkstra_visitor.hpp>
33 #include <boost/graph/prim_minimum_spanning_tree.hpp>
34
35 #include <vector>
36 #include <set>
37
38 #include "spanningTree/pgr_mst.hpp"
39 #include "cpp_common/interruption.h"
40
41 //******************************************
42
43 namespace pgrouting {
44 namespace functions {
45
46 template <class G>
47 class Pgr_prim : public Pgr_mst<G> {
48 typedef typename G::V V;
49 typedef typename G::E E;
50 typedef typename G::B_G B_G;
51
52 public:
53 std::vector<pgr_mst_rt> prim(G &graph);
54
55 std::vector<pgr_mst_rt> primBFS(
56 G &graph,
57 std::vector<int64_t> roots,
58 int64_t max_depth);
59
60 std::vector<pgr_mst_rt> primDFS(
61 G &graph,
62 std::vector<int64_t> roots,
63 int64_t max_depth);
64
65 std::vector<pgr_mst_rt> primDD(
66 G &graph,
67 std::vector<int64_t> roots,
68 double distance);
69
70
71 private:
72 // Functions
clear()73 void clear() {
74 data.clear();
75 predecessors.clear();
76 distances.clear();
77 }
78
79 void primTree(
80 const G &graph,
81 int64_t root_vertex);
82
83 void generate_mst(const G &graph);
84
85 private:
86 // Member
87 std::vector<V> predecessors;
88 std::vector<double> distances;
89 std::vector<V> data;
90 std::set<V> m_unassigned;
91 };
92
93
94 template <class G>
95 void
primTree(const G & graph,int64_t root_vertex)96 Pgr_prim<G>::primTree(
97 const G &graph,
98 int64_t root_vertex) {
99 clear();
100
101 predecessors.resize(graph.num_vertices());
102 distances.resize(graph.num_vertices());
103
104 auto v_root(graph.get_V(root_vertex));
105
106 using prim_visitor = visitors::Prim_dijkstra_visitor<V>;
107
108 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
109 CHECK_FOR_INTERRUPTS();
110
111 boost::prim_minimum_spanning_tree(
112 graph.graph,
113 &predecessors[0],
114 boost::distance_map(&distances[0]).
115 weight_map(get(&G::G_T_E::cost, graph.graph))
116 .root_vertex(v_root)
117 .visitor(prim_visitor(data)));
118
119 for (const auto v : data) {
120 /*
121 * its not a tree, its a forest
122 * - v is not on current tree
123 */
124 if (std::isinf(distances[v])) continue;
125 m_unassigned.erase(v);
126
127
128 auto u = predecessors[v];
129
130 /*
131 * Not a valid edge
132 */
133 if (u == v) continue;
134
135 auto cost = distances[u] - distances[v];
136 auto edge = graph.get_edge(u, v, cost);
137 this->m_spanning_tree.edges.insert(edge);
138 }
139 }
140
141
142 template <class G>
143 void
generate_mst(const G & graph)144 Pgr_prim<G>::generate_mst(const G &graph) {
145 this->clear();
146
147 size_t totalNodes = num_vertices(graph.graph);
148
149 m_unassigned.clear();
150 for (V v = 0; v < totalNodes; ++v) {
151 m_unassigned.insert(m_unassigned.end(), v);
152 }
153
154 while (!m_unassigned.empty()) {
155 auto root = *m_unassigned.begin();
156 m_unassigned.erase(m_unassigned.begin());
157 primTree(
158 graph,
159 graph.graph[root].id);
160 }
161 }
162
163 template <class G>
164 std::vector<pgr_mst_rt>
prim(G & graph)165 Pgr_prim<G>::prim(
166 G &graph) {
167 return this->mst(graph);
168 }
169
170 template <class G>
171 std::vector<pgr_mst_rt>
primBFS(G & graph,std::vector<int64_t> roots,int64_t max_depth)172 Pgr_prim<G>::primBFS(
173 G &graph,
174 std::vector<int64_t> roots,
175 int64_t max_depth) {
176 return this->mstBFS(graph, roots, max_depth);
177 }
178
179 template <class G>
180 std::vector<pgr_mst_rt>
primDFS(G & graph,std::vector<int64_t> roots,int64_t max_depth)181 Pgr_prim<G>::primDFS(
182 G &graph,
183 std::vector<int64_t> roots,
184 int64_t max_depth) {
185 return this->mstDFS(graph, roots, max_depth);
186 }
187
188 template <class G>
189 std::vector<pgr_mst_rt>
primDD(G & graph,std::vector<int64_t> roots,double distance)190 Pgr_prim<G>::primDD(
191 G &graph,
192 std::vector<int64_t> roots,
193 double distance) {
194 return this->mstDD(graph, roots, distance);
195 }
196
197
198
199 } // namespace functions
200 } // namespace pgrouting
201
202 #endif // INCLUDE_SPANNINGTREE_PGR_PRIM_HPP_
203