1 //=======================================================================
2 // Copyright 2000 University of Notre Dame.
3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 #ifndef BOOST_EDGE_CONNECTIVITY
11 #define BOOST_EDGE_CONNECTIVITY
12
13 // WARNING: not-yet fully tested!
14
15 #include <boost/config.hpp>
16 #include <vector>
17 #include <set>
18 #include <algorithm>
19 #include <boost/graph/edmonds_karp_max_flow.hpp>
20
21 namespace boost
22 {
23
24 namespace detail
25 {
26
27 template < class Graph >
28 inline std::pair< typename graph_traits< Graph >::vertex_descriptor,
29 typename graph_traits< Graph >::degree_size_type >
min_degree_vertex(Graph & g)30 min_degree_vertex(Graph& g)
31 {
32 typedef graph_traits< Graph > Traits;
33 typename Traits::vertex_descriptor p;
34 typedef typename Traits::degree_size_type size_type;
35 size_type delta = (std::numeric_limits< size_type >::max)();
36
37 typename Traits::vertex_iterator i, iend;
38 for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
39 if (degree(*i, g) < delta)
40 {
41 delta = degree(*i, g);
42 p = *i;
43 }
44 return std::make_pair(p, delta);
45 }
46
47 template < class Graph, class OutputIterator >
neighbors(const Graph & g,typename graph_traits<Graph>::vertex_descriptor u,OutputIterator result)48 void neighbors(const Graph& g,
49 typename graph_traits< Graph >::vertex_descriptor u,
50 OutputIterator result)
51 {
52 typename graph_traits< Graph >::adjacency_iterator ai, aend;
53 for (boost::tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
54 *result++ = *ai;
55 }
56
57 template < class Graph, class VertexIterator, class OutputIterator >
neighbors(const Graph & g,VertexIterator first,VertexIterator last,OutputIterator result)58 void neighbors(const Graph& g, VertexIterator first, VertexIterator last,
59 OutputIterator result)
60 {
61 for (; first != last; ++first)
62 neighbors(g, *first, result);
63 }
64
65 } // namespace detail
66
67 // O(m n)
68 template < class VertexListGraph, class OutputIterator >
edge_connectivity(VertexListGraph & g,OutputIterator disconnecting_set)69 typename graph_traits< VertexListGraph >::degree_size_type edge_connectivity(
70 VertexListGraph& g, OutputIterator disconnecting_set)
71 {
72 //-------------------------------------------------------------------------
73 // Type Definitions
74 typedef graph_traits< VertexListGraph > Traits;
75 typedef typename Traits::vertex_iterator vertex_iterator;
76 typedef typename Traits::edge_iterator edge_iterator;
77 typedef typename Traits::out_edge_iterator out_edge_iterator;
78 typedef typename Traits::vertex_descriptor vertex_descriptor;
79 typedef typename Traits::degree_size_type degree_size_type;
80 typedef color_traits< default_color_type > Color;
81
82 typedef adjacency_list_traits< vecS, vecS, directedS > Tr;
83 typedef typename Tr::edge_descriptor Tr_edge_desc;
84 typedef adjacency_list< vecS, vecS, directedS, no_property,
85 property< edge_capacity_t, degree_size_type,
86 property< edge_residual_capacity_t, degree_size_type,
87 property< edge_reverse_t, Tr_edge_desc > > > >
88 FlowGraph;
89 typedef typename graph_traits< FlowGraph >::edge_descriptor edge_descriptor;
90
91 //-------------------------------------------------------------------------
92 // Variable Declarations
93 vertex_descriptor u, v, p, k;
94 edge_descriptor e1, e2;
95 bool inserted;
96 vertex_iterator vi, vi_end;
97 edge_iterator ei, ei_end;
98 degree_size_type delta, alpha_star, alpha_S_k;
99 std::set< vertex_descriptor > S, neighbor_S;
100 std::vector< vertex_descriptor > S_star, non_neighbor_S;
101 std::vector< default_color_type > color(num_vertices(g));
102 std::vector< edge_descriptor > pred(num_vertices(g));
103
104 //-------------------------------------------------------------------------
105 // Create a network flow graph out of the undirected graph
106 FlowGraph flow_g(num_vertices(g));
107
108 typename property_map< FlowGraph, edge_capacity_t >::type cap
109 = get(edge_capacity, flow_g);
110 typename property_map< FlowGraph, edge_residual_capacity_t >::type res_cap
111 = get(edge_residual_capacity, flow_g);
112 typename property_map< FlowGraph, edge_reverse_t >::type rev_edge
113 = get(edge_reverse, flow_g);
114
115 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
116 {
117 u = source(*ei, g), v = target(*ei, g);
118 boost::tie(e1, inserted) = add_edge(u, v, flow_g);
119 cap[e1] = 1;
120 boost::tie(e2, inserted) = add_edge(v, u, flow_g);
121 cap[e2] = 1; // not sure about this
122 rev_edge[e1] = e2;
123 rev_edge[e2] = e1;
124 }
125
126 //-------------------------------------------------------------------------
127 // The Algorithm
128
129 boost::tie(p, delta) = detail::min_degree_vertex(g);
130 S_star.push_back(p);
131 alpha_star = delta;
132 S.insert(p);
133 neighbor_S.insert(p);
134 detail::neighbors(
135 g, S.begin(), S.end(), std::inserter(neighbor_S, neighbor_S.begin()));
136
137 boost::tie(vi, vi_end) = vertices(g);
138 std::set_difference(vi, vi_end, neighbor_S.begin(), neighbor_S.end(),
139 std::back_inserter(non_neighbor_S));
140
141 while (!non_neighbor_S.empty())
142 { // at most n - 1 times
143 k = non_neighbor_S.front();
144
145 alpha_S_k = edmonds_karp_max_flow(
146 flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
147
148 if (alpha_S_k < alpha_star)
149 {
150 alpha_star = alpha_S_k;
151 S_star.clear();
152 for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
153 if (color[*vi] != Color::white())
154 S_star.push_back(*vi);
155 }
156 S.insert(k);
157 neighbor_S.insert(k);
158 detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
159 non_neighbor_S.clear();
160 boost::tie(vi, vi_end) = vertices(g);
161 std::set_difference(vi, vi_end, neighbor_S.begin(), neighbor_S.end(),
162 std::back_inserter(non_neighbor_S));
163 }
164 //-------------------------------------------------------------------------
165 // Compute edges of the cut [S*, ~S*]
166 std::vector< bool > in_S_star(num_vertices(g), false);
167 typename std::vector< vertex_descriptor >::iterator si;
168 for (si = S_star.begin(); si != S_star.end(); ++si)
169 in_S_star[*si] = true;
170
171 degree_size_type c = 0;
172 for (si = S_star.begin(); si != S_star.end(); ++si)
173 {
174 out_edge_iterator ei, ei_end;
175 for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
176 if (!in_S_star[target(*ei, g)])
177 {
178 *disconnecting_set++ = *ei;
179 ++c;
180 }
181 }
182 return c;
183 }
184
185 } // namespace boost
186
187 #endif // BOOST_EDGE_CONNECTIVITY
188