1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 
9 /*
10    IMPORTANT!!!
11    ~~~~~~~~~~~~
12    This example uses interfaces that have been deprecated and removed from Boost.Grpah.
13    Someone needs to update it, as it does NOT compile.
14 */
15 
16 #include <boost/config.hpp>
17 #include <algorithm>
18 #include <utility>
19 #include <boost/graph/edmonds_karp_max_flow.hpp>
20 #include <boost/graph/push_relabel_max_flow.hpp>
21 #include <boost/graph/adjacency_list.hpp>
22 #include <boost/graph/graphviz.hpp>
23 
24 namespace boost
25 {
26   template < typename Graph >
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     typename graph_traits < Graph >::vertex_descriptor p;
32     typedef typename graph_traits < Graph >::degree_size_type size_type;
33     size_type delta = (std::numeric_limits < size_type >::max)();
34     typename graph_traits < Graph >::vertex_iterator i, iend;
35     for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
36       if (degree(*i, g) < delta)
37       {
38         delta = degree(*i, g);
39         p = *i;
40       }
41     return std::make_pair(p, delta);
42   }
43 
44   template < typename Graph, typename OutputIterator >
neighbors(const Graph & g,typename graph_traits<Graph>::vertex_descriptor u,OutputIterator result)45     void neighbors(const Graph & g,
46                    typename graph_traits < Graph >::vertex_descriptor u,
47                    OutputIterator result)
48   {
49     typename graph_traits < Graph >::adjacency_iterator ai, aend;
50     for (boost::tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
51       *result++ = *ai;
52   }
53   template < typename Graph, typename VertexIterator,
neighbors(const Graph & g,VertexIterator first,VertexIterator last,OutputIterator result)54     typename OutputIterator > void neighbors(const Graph & g,
55                                              VertexIterator first,
56                                              VertexIterator last,
57                                              OutputIterator result)
58   {
59     for (; first != last; ++first)
60       neighbors(g, *first, result);
61   }
62 
63   template < typename VertexListGraph, typename OutputIterator >
64   typename graph_traits < VertexListGraph >::degree_size_type
edge_connectivity(VertexListGraph & g,OutputIterator disconnecting_set)65   edge_connectivity(VertexListGraph & g, OutputIterator disconnecting_set)
66   {
67     typedef typename graph_traits <
68       VertexListGraph >::vertex_descriptor vertex_descriptor;
69     typedef typename graph_traits <
70       VertexListGraph >::degree_size_type degree_size_type;
71     typedef color_traits < default_color_type > Color;
72     typedef typename adjacency_list_traits < vecS, vecS,
73       directedS >::edge_descriptor edge_descriptor;
74     typedef adjacency_list < vecS, vecS, directedS, no_property,
75       property < edge_capacity_t, degree_size_type,
76       property < edge_residual_capacity_t, degree_size_type,
77       property < edge_reverse_t, edge_descriptor > > > > FlowGraph;
78 
79     vertex_descriptor u, v, p, k;
80     edge_descriptor e1, e2;
81     bool inserted;
82     typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
83     degree_size_type delta, alpha_star, alpha_S_k;
84     std::set < vertex_descriptor > S, neighbor_S;
85     std::vector < vertex_descriptor > S_star, nonneighbor_S;
86     std::vector < default_color_type > color(num_vertices(g));
87     std::vector < edge_descriptor > pred(num_vertices(g));
88 
89     FlowGraph flow_g(num_vertices(g));
90     typename property_map < FlowGraph, edge_capacity_t >::type
91       cap = get(edge_capacity, flow_g);
92     typename property_map < FlowGraph, edge_residual_capacity_t >::type
93       res_cap = get(edge_residual_capacity, flow_g);
94     typename property_map < FlowGraph, edge_reverse_t >::type
95       rev_edge = get(edge_reverse, flow_g);
96 
97     typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
98     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
99       u = source(*ei, g), v = target(*ei, g);
100       boost::tie(e1, inserted) = add_edge(u, v, flow_g);
101       cap[e1] = 1;
102       boost::tie(e2, inserted) = add_edge(v, u, flow_g);
103       cap[e2] = 1;
104       rev_edge[e1] = e2;
105       rev_edge[e2] = e1;
106     }
107 
108     boost::tie(p, delta) = min_degree_vertex(g);
109     S_star.push_back(p);
110     alpha_star = delta;
111     S.insert(p);
112     neighbor_S.insert(p);
113     neighbors(g, S.begin(), S.end(),
114               std::inserter(neighbor_S, neighbor_S.begin()));
115     std::set_difference(vertices(g).first, vertices(g).second,
116                         neighbor_S.begin(), neighbor_S.end(),
117                         std::back_inserter(nonneighbor_S));
118 
119     while (!nonneighbor_S.empty()) {
120       k = nonneighbor_S.front();
121       alpha_S_k = edmonds_karp_max_flow
122         (flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
123       if (alpha_S_k < alpha_star) {
124         alpha_star = alpha_S_k;
125         S_star.clear();
126         for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
127           if (color[*vi] != Color::white())
128             S_star.push_back(*vi);
129       }
130       S.insert(k);
131       neighbor_S.insert(k);
132       neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
133       nonneighbor_S.clear();
134       std::set_difference(vertices(g).first, vertices(g).second,
135                           neighbor_S.begin(), neighbor_S.end(),
136                           std::back_inserter(nonneighbor_S));
137     }
138 
139     std::vector < bool > in_S_star(num_vertices(g), false);
140     typename std::vector < vertex_descriptor >::iterator si;
141     for (si = S_star.begin(); si != S_star.end(); ++si)
142       in_S_star[*si] = true;
143     degree_size_type c = 0;
144     for (si = S_star.begin(); si != S_star.end(); ++si) {
145       typename graph_traits < VertexListGraph >::out_edge_iterator ei, ei_end;
146       for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
147         if (!in_S_star[target(*ei, g)]) {
148           *disconnecting_set++ = *ei;
149           ++c;
150         }
151     }
152 
153     return c;
154   }
155 
156 }
157 
158 int
main()159 main()
160 {
161   using namespace boost;
162   GraphvizGraph g;
163   read_graphviz("figs/edge-connectivity.dot", g);
164 
165   typedef graph_traits < GraphvizGraph >::edge_descriptor edge_descriptor;
166   typedef graph_traits < GraphvizGraph >::degree_size_type degree_size_type;
167   std::vector < edge_descriptor > disconnecting_set;
168   degree_size_type c =
169     edge_connectivity(g, std::back_inserter(disconnecting_set));
170 
171   std::cout << "The edge connectivity is " << c << "." << std::endl;
172 
173   property_map < GraphvizGraph, vertex_attribute_t >::type
174     attr_map = get(vertex_attribute, g);
175 
176   std::cout << "The disconnecting set is {";
177   for (std::vector < edge_descriptor >::iterator i =
178        disconnecting_set.begin(); i != disconnecting_set.end(); ++i)
179     std::
180       cout << "(" << attr_map[source(*i, g)]["label"] << "," <<
181       attr_map[target(*i, g)]["label"] << ") ";
182   std::cout << "}." << std::endl;
183   return EXIT_SUCCESS;
184 }
185