1 /*PGR-GNU***************************************************************** 2 File: pgr_mst.hpp 3 4 Copyright (c) 2018 Vicky Vergara 5 mail: vicky at georepublic dot de 6 7 ------ 8 9 This program is free software; you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation; either version 2 of the License, or 12 (at your option) any later version. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 22 23 ********************************************************************PGR-GNU*/ 24 25 #ifndef INCLUDE_SPANNINGTREE_PGR_MST_HPP_ 26 #define INCLUDE_SPANNINGTREE_PGR_MST_HPP_ 27 #pragma once 28 29 #include <visitors/dfs_visitor_with_root.hpp> 30 #include <visitors/edges_order_bfs_visitor.hpp> 31 #include <visitors/edges_order_dfs_visitor.hpp> 32 #include <boost/graph/connected_components.hpp> 33 #include <boost/graph/filtered_graph.hpp> 34 35 #include <set> 36 #include <utility> 37 #include <string> 38 #include <vector> 39 40 #include "cpp_common/pgr_base_graph.hpp" 41 #include "cpp_common/interruption.h" 42 #include "spanningTree/details.hpp" 43 44 namespace pgrouting { 45 namespace functions { 46 47 template <class G> 48 class Pgr_mst { 49 protected: 50 typedef typename G::B_G B_G; 51 typedef typename G::V V; 52 typedef typename G::E E; 53 typedef typename G::E_i E_i; 54 55 56 protected: 57 virtual void generate_mst(const G &graph) = 0; 58 clear()59 void clear() { 60 this->m_spanning_tree.clear(); 61 this->m_components.clear(); 62 this->m_tree_id.clear(); 63 } 64 65 std::vector<pgr_mst_rt> no_order(const G & graph)66 no_order(const G &graph) { 67 return no_ordering(graph); 68 } 69 70 std::vector<pgr_mst_rt> dfs_order(const G & graph)71 dfs_order(const G &graph) { 72 return dfs_ordering(graph); 73 } 74 75 std::vector<pgr_mst_rt> bfs_order(const G & graph)76 bfs_order(const G &graph) { 77 return bfs_ordering(graph); 78 } 79 mst(const G & graph)80 std::vector<pgr_mst_rt> mst(const G &graph) { 81 m_suffix = ""; 82 m_get_component = false; 83 m_distance = -1; 84 m_max_depth = -1; 85 m_roots.clear(); 86 87 no_neg_costs(graph); 88 this->generate_mst(graph); 89 return no_order(graph); 90 } 91 92 mstBFS(const G & graph,std::vector<int64_t> roots,int64_t max_depth)93 std::vector<pgr_mst_rt> mstBFS( 94 const G &graph, 95 std::vector<int64_t> roots, 96 int64_t max_depth) { 97 m_suffix = "BFS"; 98 m_get_component = true; 99 m_distance = -1; 100 m_max_depth = max_depth; 101 m_roots = details::clean_vids(roots); 102 103 this->generate_mst(graph); 104 return bfs_order(graph); 105 } 106 mstDFS(const G & graph,std::vector<int64_t> roots,int64_t max_depth)107 std::vector<pgr_mst_rt> mstDFS( 108 const G &graph, 109 std::vector<int64_t> roots, 110 int64_t max_depth) { 111 m_suffix = "DFS"; 112 m_get_component = false; 113 m_distance = -1; 114 m_max_depth = max_depth; 115 m_roots = details::clean_vids(roots); 116 117 this->generate_mst(graph); 118 return dfs_order(graph); 119 } 120 mstDD(const G & graph,std::vector<int64_t> roots,double distance)121 std::vector<pgr_mst_rt> mstDD( 122 const G &graph, 123 std::vector<int64_t> roots, 124 double distance) { 125 m_suffix = "DD"; 126 m_get_component = false; 127 m_distance = distance; 128 m_max_depth = -1; 129 m_roots = details::clean_vids(roots); 130 131 this->generate_mst(graph); 132 return dfs_order(graph); 133 } 134 135 protected: 136 std::vector<int64_t> m_roots; 137 bool m_get_component; 138 int64_t m_max_depth; 139 double m_distance; 140 141 struct InSpanning { 142 std::set<E> edges; operator ()pgrouting::functions::Pgr_mst::InSpanning143 bool operator()(E e) const { return edges.count(e); } clearpgrouting::functions::Pgr_mst::InSpanning144 void clear() { edges.clear(); } 145 } m_spanning_tree; 146 147 148 /** m_components[v]: 149 * - is empty (when m_get_component = 0) 150 * - has the component number of vertex v (when m_get_component != 0) 151 */ 152 std::vector<size_t> m_components; 153 154 /** 155 * Stores which function is being executed. 156 * 157 * TODO change to enum 158 */ 159 std::string m_suffix; 160 161 /** m_tree_id[v]: 162 * - is empty (when m_get_component = 0) 163 * - has the component number of vertex v (when m_get_component = 1) 164 * - has the min vertex id that belongs to the component (when m_get_component = 2) 165 */ 166 std::vector<int64_t> m_tree_id; 167 168 private: 169 template <typename T> get_results(T order,int64_t p_root,const G & graph)170 std::vector<pgr_mst_rt> get_results( 171 T order, 172 int64_t p_root, 173 const G &graph) { 174 std::vector<pgr_mst_rt> results; 175 176 std::vector<double> agg_cost(graph.num_vertices(), 0); 177 std::vector<int64_t> depth(graph.num_vertices(), 0); 178 int64_t root(p_root); 179 180 for (const auto edge : order) { 181 auto u = graph.source(edge); 182 auto v = graph.target(edge); 183 if (depth[u] == 0 && depth[v] != 0) { 184 std::swap(u, v); 185 } 186 187 auto component = m_get_component? m_tree_id[m_components[u]] : 0; 188 if (m_suffix != "" && depth[u] == 0 && depth[v] == 0) { 189 if (!m_roots.empty() && graph[u].id != root) std::swap(u, v); 190 if (m_roots.empty() && graph[u].id != component) std::swap(u, v); 191 if (!p_root && graph[u].id > graph[v].id) std::swap(u, v); 192 193 root = p_root? p_root: graph[u].id; 194 depth[u] = -1; 195 results.push_back({ 196 root, 197 0, 198 graph[u].id, 199 -1, 200 0.0, 201 0.0 }); 202 } 203 204 agg_cost[v] = agg_cost[u] + graph[edge].cost; 205 depth[v] = depth[u] == -1? 1 : depth[u] + 1; 206 207 if ((m_suffix == "") 208 || ((m_suffix == "BFS") && (m_max_depth >= depth[v])) 209 || ((m_suffix == "DFS") && m_max_depth >= depth[v]) 210 || ((m_suffix == "DD") && m_distance >= agg_cost[v])) { 211 results.push_back({ 212 root, 213 m_suffix != ""? depth[v] : 0, 214 graph[v].id, 215 graph[edge].id, 216 graph[edge].cost, 217 m_suffix != ""? agg_cost[v] : 0.0 218 }); 219 } 220 } 221 return results; 222 } 223 224 calculate_component(const G & graph)225 void calculate_component(const G &graph) { 226 if (!m_get_component) return; 227 228 m_components.resize(num_vertices(graph.graph)); 229 230 /* 231 * Calculate connected components 232 * 233 * Number of components of graph: num_comps components 234 */ 235 auto num_comps = boost::connected_components( 236 graph.graph, 237 &m_components[0]); 238 239 m_tree_id.resize(num_comps, 0); 240 241 for (const auto v : boost::make_iterator_range(vertices(graph.graph))) { 242 m_tree_id[m_components[v]] = 243 (m_tree_id[m_components[v]] == 0 244 || m_tree_id[m_components[v]] >= graph[v].id) ? 245 graph[v].id : m_tree_id[m_components[v]]; 246 } 247 } 248 249 std::vector<pgr_mst_rt> no_ordering(const G & graph)250 no_ordering(const G &graph) { 251 return get_results(m_spanning_tree.edges, 0, graph); 252 } 253 254 std::vector<pgr_mst_rt> dfs_forest(const G & graph)255 dfs_forest(const G &graph) { 256 boost::filtered_graph<B_G, InSpanning, boost::keep_all> 257 mstGraph(graph.graph, m_spanning_tree, {}); 258 std::vector<E> visited_order; 259 260 using dfs_visitor = visitors::Edges_order_dfs_visitor<E>; 261 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */ 262 CHECK_FOR_INTERRUPTS(); 263 try { 264 boost::depth_first_search(mstGraph, visitor(dfs_visitor(visited_order))); 265 } catch (boost::exception const& ex) { 266 (void)ex; 267 throw; 268 } catch (std::exception &e) { 269 (void)e; 270 throw; 271 } catch (...) { 272 throw; 273 } 274 275 return get_results(visited_order, 0, graph); 276 } 277 278 279 std::vector<pgr_mst_rt> dfs_ordering(const G & graph)280 dfs_ordering(const G &graph) { 281 boost::filtered_graph<B_G, InSpanning, boost::keep_all> 282 mstGraph(graph.graph, m_spanning_tree, {}); 283 284 if (m_roots.empty()) { 285 return dfs_forest(graph); 286 } else { 287 std::vector<pgr_mst_rt> results; 288 for (const auto root : m_roots) { 289 std::vector<E> visited_order; 290 291 using dfs_visitor = visitors::Dfs_visitor_with_root<V, E>; 292 if (graph.has_vertex(root)) { 293 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */ 294 CHECK_FOR_INTERRUPTS(); 295 try { 296 boost::depth_first_search( 297 mstGraph, 298 visitor(dfs_visitor(graph.get_V(root), visited_order)) 299 .root_vertex(graph.get_V(root))); 300 } catch(found_goals &) { 301 {} 302 } catch (boost::exception const& ex) { 303 (void)ex; 304 throw; 305 } catch (std::exception &e) { 306 (void)e; 307 throw; 308 } catch (...) { 309 throw; 310 } 311 auto result = get_results(visited_order, root, graph); 312 results.insert(results.end(), result.begin(), result.end()); 313 } else { 314 results.push_back({root, 0, root, -1, 0.0, 0.0}); 315 } 316 } 317 return results; 318 } 319 } 320 321 std::vector<pgr_mst_rt> bfs_ordering(const G & graph)322 bfs_ordering(const G &graph) { 323 std::vector<pgr_mst_rt> results; 324 /* 325 * order by bfs 326 */ 327 boost::filtered_graph<B_G, InSpanning, boost::keep_all> 328 mst(graph.graph, m_spanning_tree, {}); 329 330 calculate_component(graph); 331 332 std::vector<int64_t> roots; 333 if (!m_roots.empty()) { 334 roots = m_roots; 335 } else { 336 roots = m_tree_id; 337 } 338 339 using bfs_visitor = visitors::Edges_order_bfs_visitor<E>; 340 for (auto root : roots) { 341 std::vector<E> visited_order; 342 if (graph.has_vertex(root)) { 343 boost::breadth_first_search(mst, 344 graph.get_V(root), 345 visitor(bfs_visitor(visited_order))); 346 347 auto tree_results = get_results(visited_order, root, graph); 348 results.insert(results.end(), tree_results.begin(), tree_results.end()); 349 } else { 350 results.push_back({root, 0, root, -1, 0.0, 0.0}); 351 } 352 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */ 353 CHECK_FOR_INTERRUPTS(); 354 } 355 356 return results; 357 } 358 no_neg_costs(const G & graph)359 bool no_neg_costs(const G &graph) { 360 E_i ei, ei_end; 361 for (boost::tie(ei, ei_end) = edges(graph.graph); ei != ei_end; ++ei) 362 pgassert(graph[*ei].cost > 0); 363 return true; 364 } 365 }; 366 367 } // namespace functions 368 } // namespace pgrouting 369 370 #endif // INCLUDE_SPANNINGTREE_PGR_MST_HPP_ 371