1 /*PGR-GNU*****************************************************************
2 File: pgr_stoerWagner.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_MINCUT_PGR_STOERWAGNER_HPP_
29 #define INCLUDE_MINCUT_PGR_STOERWAGNER_HPP_
30 #pragma once
31
32 #include <boost/config.hpp>
33 #include <boost/graph/adjacency_list.hpp>
34 #include <boost/graph/graph_traits.hpp>
35 #include <boost/graph/one_bit_color_map.hpp>
36 #include <boost/graph/stoer_wagner_min_cut.hpp>
37 #include <boost/property_map/property_map.hpp>
38 #include <boost/typeof/typeof.hpp>
39
40 #include <iostream>
41 #include <vector>
42 #include <algorithm>
43 #include <sstream>
44 #include <functional>
45 #include <limits>
46
47 #include "cpp_common/basePath_SSEC.hpp"
48 #include "cpp_common/pgr_base_graph.hpp"
49
50 template < class G > class Pgr_stoerWagner;
51 // user's functions
52 // for development
53
54 //******************************************
55
56 template < class G >
57 class Pgr_stoerWagner {
58 public:
59 typedef typename G::V V;
60 typedef typename G::E E;
61 typedef typename G::E_i E_i;
62
63 std::vector<pgr_stoerWagner_t> stoerWagner(
64 G &graph);
65
66 private:
67 std::vector< pgr_stoerWagner_t >
generatestoerWagner(const G & graph)68 generatestoerWagner(
69 const G &graph ) {
70 std::vector< pgr_stoerWagner_t > results;
71 auto parities = boost::make_one_bit_color_map(
72 num_vertices(graph.graph),
73 get(boost::vertex_index, graph.graph));
74
75 double w = stoer_wagner_min_cut(
76 graph.graph,
77 get(&G::G_T_E::cost, graph.graph),
78 boost::parity_map(parities));
79
80 double totalcost = 0;
81 E_i ei, ei_end;
82 for (boost::tie(ei, ei_end) = edges(graph.graph); ei != ei_end; ei++) {
83 auto s = source(*ei, graph.graph);
84 auto t = target(*ei, graph.graph);
85
86 if (get(parities, s) != get(parities, t)) {
87 pgr_stoerWagner_t tmp;
88
89 tmp.cost = graph[*ei].cost;
90
91 auto edge_id =
92 graph.get_edge_id(
93 source(*ei, graph.graph),
94 target(*ei, graph.graph),
95 tmp.cost);
96
97 tmp.edge = edge_id;
98 totalcost += tmp.cost;
99 tmp.mincut = totalcost;
100 results.push_back(tmp);
101 }
102 }
103
104 pgassert(w == totalcost);
105 return results;
106 }
107 };
108
109 template < class G >
110 std::vector<pgr_stoerWagner_t>
stoerWagner(G & graph)111 Pgr_stoerWagner< G >::stoerWagner(
112 G &graph) {
113 pgassert(num_vertices(graph.graph) > 1);
114 return generatestoerWagner(
115 graph);
116 }
117
118
119 #endif // INCLUDE_MINCUT_PGR_STOERWAGNER_HPP_
120