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