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