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
13 Boost.Grpah. 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, OutputIterator result)
47 {
48 typename graph_traits< Graph >::adjacency_iterator ai, aend;
49 for (boost::tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
50 *result++ = *ai;
51 }
52 template < typename Graph, typename VertexIterator, typename OutputIterator >
neighbors(const Graph & g,VertexIterator first,VertexIterator last,OutputIterator result)53 void neighbors(const Graph& g, VertexIterator first, VertexIterator last,
54 OutputIterator result)
55 {
56 for (; first != last; ++first)
57 neighbors(g, *first, result);
58 }
59
60 template < typename VertexListGraph, typename OutputIterator >
edge_connectivity(VertexListGraph & g,OutputIterator disconnecting_set)61 typename graph_traits< VertexListGraph >::degree_size_type edge_connectivity(
62 VertexListGraph& g, OutputIterator disconnecting_set)
63 {
64 typedef typename graph_traits< VertexListGraph >::vertex_descriptor
65 vertex_descriptor;
66 typedef typename graph_traits< VertexListGraph >::degree_size_type
67 degree_size_type;
68 typedef color_traits< default_color_type > Color;
69 typedef
70 typename adjacency_list_traits< vecS, vecS, directedS >::edge_descriptor
71 edge_descriptor;
72 typedef adjacency_list< vecS, vecS, directedS, no_property,
73 property< edge_capacity_t, degree_size_type,
74 property< edge_residual_capacity_t, degree_size_type,
75 property< edge_reverse_t, edge_descriptor > > > >
76 FlowGraph;
77
78 vertex_descriptor u, v, p, k;
79 edge_descriptor e1, e2;
80 bool inserted;
81 typename graph_traits< VertexListGraph >::vertex_iterator vi, vi_end;
82 degree_size_type delta, alpha_star, alpha_S_k;
83 std::set< vertex_descriptor > S, neighbor_S;
84 std::vector< vertex_descriptor > S_star, nonneighbor_S;
85 std::vector< default_color_type > color(num_vertices(g));
86 std::vector< edge_descriptor > pred(num_vertices(g));
87
88 FlowGraph flow_g(num_vertices(g));
89 typename property_map< FlowGraph, edge_capacity_t >::type cap
90 = get(edge_capacity, flow_g);
91 typename property_map< FlowGraph, edge_residual_capacity_t >::type res_cap
92 = get(edge_residual_capacity, flow_g);
93 typename property_map< FlowGraph, edge_reverse_t >::type rev_edge
94 = get(edge_reverse, flow_g);
95
96 typename graph_traits< VertexListGraph >::edge_iterator ei, ei_end;
97 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
98 {
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(
114 g, S.begin(), S.end(), 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 {
121 k = nonneighbor_S.front();
122 alpha_S_k = edmonds_karp_max_flow(
123 flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
124 if (alpha_S_k < alpha_star)
125 {
126 alpha_star = alpha_S_k;
127 S_star.clear();
128 for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
129 if (color[*vi] != Color::white())
130 S_star.push_back(*vi);
131 }
132 S.insert(k);
133 neighbor_S.insert(k);
134 neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
135 nonneighbor_S.clear();
136 std::set_difference(vertices(g).first, vertices(g).second,
137 neighbor_S.begin(), neighbor_S.end(),
138 std::back_inserter(nonneighbor_S));
139 }
140
141 std::vector< bool > in_S_star(num_vertices(g), false);
142 typename std::vector< vertex_descriptor >::iterator si;
143 for (si = S_star.begin(); si != S_star.end(); ++si)
144 in_S_star[*si] = true;
145 degree_size_type c = 0;
146 for (si = S_star.begin(); si != S_star.end(); ++si)
147 {
148 typename graph_traits< VertexListGraph >::out_edge_iterator ei, ei_end;
149 for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
150 if (!in_S_star[target(*ei, g)])
151 {
152 *disconnecting_set++ = *ei;
153 ++c;
154 }
155 }
156
157 return c;
158 }
159
160 }
161
main()162 int main()
163 {
164 using namespace boost;
165 GraphvizGraph g;
166 read_graphviz("figs/edge-connectivity.dot", g);
167
168 typedef graph_traits< GraphvizGraph >::edge_descriptor edge_descriptor;
169 typedef graph_traits< GraphvizGraph >::degree_size_type degree_size_type;
170 std::vector< edge_descriptor > disconnecting_set;
171 degree_size_type c
172 = edge_connectivity(g, std::back_inserter(disconnecting_set));
173
174 std::cout << "The edge connectivity is " << c << "." << std::endl;
175
176 property_map< GraphvizGraph, vertex_attribute_t >::type attr_map
177 = get(vertex_attribute, g);
178
179 std::cout << "The disconnecting set is {";
180 for (std::vector< edge_descriptor >::iterator i = disconnecting_set.begin();
181 i != disconnecting_set.end(); ++i)
182 std::cout << "(" << attr_map[source(*i, g)]["label"] << ","
183 << attr_map[target(*i, g)]["label"] << ") ";
184 std::cout << "}." << std::endl;
185 return EXIT_SUCCESS;
186 }
187