1 /*PGR-GNU*****************************************************************
2 File: pgr_randomSpanningTree.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_RANDOMSPANNINGTREE_HPP_
29 #define INCLUDE_SPANNINGTREE_PGR_RANDOMSPANNINGTREE_HPP_
30 #pragma once
31
32 #include <boost/config.hpp>
33 #include <boost/graph/adjacency_list.hpp>
34 #include <boost/graph/random_spanning_tree.hpp>
35 #include <boost/random/random_number_generator.hpp>
36 #include <boost/graph/graph_traits.hpp>
37
38 #include <vector>
39 #include <random>
40 #include <iostream>
41 #include <exception>
42
43 #include "cpp_common/basePath_SSEC.hpp"
44 #include "cpp_common/pgr_base_graph.hpp"
45 #include "cpp_common/interruption.h"
46
47 template < class G > class Pgr_randomSpanningTree;
48 // user's functions
49 // for development
50
51 //******************************************
52
53 template < class G >
54 class Pgr_randomSpanningTree {
55 public:
56 typedef typename G::V V;
57 typedef typename G::E E;
58
59 std::vector<pgr_randomSpanningTree_t> randomSpanningTree(
60 G &graph,
61 int64_t root_vertex);
62
63 private:
64 // Member
65 std::vector< V > predecessors;
66
67 // Function
68 std::vector< pgr_randomSpanningTree_t >
undirectedGraph(const G & graph,int64_t root_vertex)69 undirectedGraph(
70 const G &graph,
71 int64_t root_vertex) {
72 std::ostringstream log;
73 auto v_root(graph.get_V(root_vertex));
74
75 std::minstd_rand rng;
76
77 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
78 CHECK_FOR_INTERRUPTS();
79
80 // TODO(aps)
81 // This function is running in infinite loop
82 try {
83 boost::random_spanning_tree(
84 graph.graph,
85 rng,
86 boost::root_vertex(v_root)
87 .predecessor_map(&predecessors[0])
88 .weight_map(get(&G::G_T_E::cost, graph.graph)));
89 } catch (std::exception const &ex) {
90 log << ex.what();
91 } catch (...) {
92 log << "Unknown exception caught";
93 }
94
95 std::vector< pgr_randomSpanningTree_t > resul;
96 return resul;
97 std::vector< pgr_randomSpanningTree_t > results;
98 double totalcost = 0;
99 pgr_randomSpanningTree_t tmp;
100
101 tmp.root_vertex = root_vertex;
102 tmp.edge = -1;
103 tmp.cost = 0;
104 tmp.tree_cost = totalcost;
105
106 results.push_back(tmp);
107
108 for (size_t j = 0; j < predecessors.size(); j++) {
109 if (j != v_root) {
110 pgr_randomSpanningTree_t tmp;
111
112 auto start_node = graph.graph[predecessors[j]].id;
113 auto end_node = graph.graph[j].id; // node
114
115 auto v_sn(graph.get_V(start_node));
116 auto v_en(graph.get_V(end_node));
117
118 auto cost = graph[boost::edge(
119 predecessors[j], j, graph.graph).first].cost;
120 auto edge_id =
121 graph.get_edge_id(v_sn, v_en, cost);
122 totalcost += cost;
123
124 tmp.root_vertex = root_vertex;
125 tmp.edge = edge_id; // edge_id
126 tmp.cost = cost; // cost
127 tmp.tree_cost = totalcost; // tree_cost
128 results.push_back(tmp);
129 }
130 }
131 return results;
132 }
133 };
134
135 template < class G >
136 std::vector<pgr_randomSpanningTree_t>
randomSpanningTree(G & graph,int64_t root_vertex)137 Pgr_randomSpanningTree< G >::randomSpanningTree(
138 G &graph,
139 int64_t root_vertex ) {
140 predecessors.clear();
141 // TODO(aps)
142 // Currently only running for undirected graph
143 return undirectedGraph(
144 graph,
145 root_vertex);
146 }
147
148
149 #endif // INCLUDE_SPANNINGTREE_PGR_RANDOMSPANNINGTREE_HPP_
150