[12] | 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/edmunds_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 > |
---|
| 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 (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 > |
---|
| 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 (tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai) |
---|
| 43 | *result++ = *ai; |
---|
| 44 | } |
---|
| 45 | template < typename Graph, typename VertexIterator, |
---|
| 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 |
---|
| 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 (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { |
---|
| 91 | u = source(*ei, g), v = target(*ei, g); |
---|
| 92 | tie(e1, inserted) = add_edge(u, v, flow_g); |
---|
| 93 | cap[e1] = 1; |
---|
| 94 | 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 | 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 = edmunds_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 (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 (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 |
---|
| 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 | } |
---|