1 /*PGR-GNU*****************************************************************
2 File: pgr_kruskal.hpp
3
4 Copyright (c) 2015 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_KRUSKAL_HPP_
29 #define INCLUDE_SPANNINGTREE_PGR_KRUSKAL_HPP_
30 #pragma once
31
32 #include <boost/graph/kruskal_min_spanning_tree.hpp>
33 #include <vector>
34 #include "spanningTree/pgr_mst.hpp"
35 #include "cpp_common/interruption.h"
36
37 namespace pgrouting {
38 namespace functions {
39
40 template <class G>
41 class Pgr_kruskal : public Pgr_mst<G> {
42 public:
43 std::vector<pgr_mst_rt> kruskal(G &graph);
44
45 std::vector<pgr_mst_rt> kruskalBFS(
46 G &graph,
47 std::vector<int64_t> roots,
48 int64_t max_depth);
49
50 std::vector<pgr_mst_rt> kruskalDFS(
51 G &graph,
52 std::vector<int64_t> roots,
53 int64_t max_depth);
54
55 std::vector<pgr_mst_rt> kruskalDD(
56 G &graph,
57 std::vector<int64_t> roots,
58 double distance);
59
60 private:
61 typedef typename G::B_G B_G;
62 typedef typename G::V V;
63 typedef typename G::E E;
64
65 /* Does all the work */
66 void generate_mst(const G &graph);
67 };
68
69
70 template <class G>
71 void
generate_mst(const G & graph)72 Pgr_kruskal<G>::generate_mst(const G &graph) {
73 this->clear();
74 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
75 CHECK_FOR_INTERRUPTS();
76 boost::kruskal_minimum_spanning_tree(
77 graph.graph,
78 std::inserter(this->m_spanning_tree.edges, this->m_spanning_tree.edges.begin()),
79 boost::weight_map(get(&G::G_T_E::cost, graph.graph)));
80 }
81
82
83 template <class G>
84 std::vector<pgr_mst_rt>
kruskal(G & graph)85 Pgr_kruskal<G>::kruskal(
86 G &graph) {
87 return this->mst(graph);
88 }
89
90
91 template <class G>
92 std::vector<pgr_mst_rt>
kruskalBFS(G & graph,std::vector<int64_t> roots,int64_t max_depth)93 Pgr_kruskal<G>::kruskalBFS(
94 G &graph,
95 std::vector<int64_t> roots,
96 int64_t max_depth) {
97 return this->mstBFS(graph, roots, max_depth);
98 }
99
100 template <class G>
101 std::vector<pgr_mst_rt>
kruskalDFS(G & graph,std::vector<int64_t> roots,int64_t max_depth)102 Pgr_kruskal<G>::kruskalDFS(
103 G &graph,
104 std::vector<int64_t> roots,
105 int64_t max_depth) {
106 return this->mstDFS(graph, roots, max_depth);
107 }
108
109 template <class G>
110 std::vector<pgr_mst_rt>
kruskalDD(G & graph,std::vector<int64_t> roots,double distance)111 Pgr_kruskal<G>::kruskalDD(
112 G &graph,
113 std::vector<int64_t> roots,
114 double distance) {
115 return this->mstDD(graph, roots, distance);
116 }
117
118
119 } // namespace functions
120 } // namespace pgrouting
121
122 #endif // INCLUDE_SPANNINGTREE_PGR_KRUSKAL_HPP_
123