[29] | 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/edmunds_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> |
---|
| 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 (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> |
---|
| 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 (tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai) |
---|
| 52 | *result++ = *ai; |
---|
| 53 | } |
---|
| 54 | |
---|
| 55 | template <class Graph, class VertexIterator, class OutputIterator> |
---|
| 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 |
---|
| 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 (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { |
---|
| 115 | u = source(*ei, g), v = target(*ei, g); |
---|
| 116 | tie(e1, inserted) = add_edge(u, v, flow_g); |
---|
| 117 | cap[e1] = 1; |
---|
| 118 | 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 | 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 | std::set_difference(vertices(g).first, vertices(g).second, |
---|
| 136 | neighbor_S.begin(), neighbor_S.end(), |
---|
| 137 | std::back_inserter(non_neighbor_S)); |
---|
| 138 | |
---|
| 139 | while (!non_neighbor_S.empty()) { // at most n - 1 times |
---|
| 140 | k = non_neighbor_S.front(); |
---|
| 141 | |
---|
| 142 | alpha_S_k = edmunds_karp_max_flow |
---|
| 143 | (flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]); |
---|
| 144 | |
---|
| 145 | if (alpha_S_k < alpha_star) { |
---|
| 146 | alpha_star = alpha_S_k; |
---|
| 147 | S_star.clear(); |
---|
| 148 | for (tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi) |
---|
| 149 | if (color[*vi] != Color::white()) |
---|
| 150 | S_star.push_back(*vi); |
---|
| 151 | } |
---|
| 152 | S.insert(k); |
---|
| 153 | neighbor_S.insert(k); |
---|
| 154 | detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin())); |
---|
| 155 | non_neighbor_S.clear(); |
---|
| 156 | std::set_difference(vertices(g).first, vertices(g).second, |
---|
| 157 | neighbor_S.begin(), neighbor_S.end(), |
---|
| 158 | std::back_inserter(non_neighbor_S)); |
---|
| 159 | } |
---|
| 160 | //------------------------------------------------------------------------- |
---|
| 161 | // Compute edges of the cut [S*, ~S*] |
---|
| 162 | std::vector<bool> in_S_star(num_vertices(g), false); |
---|
| 163 | typename std::vector<vertex_descriptor>::iterator si; |
---|
| 164 | for (si = S_star.begin(); si != S_star.end(); ++si) |
---|
| 165 | in_S_star[*si] = true; |
---|
| 166 | |
---|
| 167 | degree_size_type c = 0; |
---|
| 168 | for (si = S_star.begin(); si != S_star.end(); ++si) { |
---|
| 169 | out_edge_iterator ei, ei_end; |
---|
| 170 | for (tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei) |
---|
| 171 | if (!in_S_star[target(*ei, g)]) { |
---|
| 172 | *disconnecting_set++ = *ei; |
---|
| 173 | ++c; |
---|
| 174 | } |
---|
| 175 | } |
---|
| 176 | return c; |
---|
| 177 | } |
---|
| 178 | |
---|
| 179 | } // namespace boost |
---|
| 180 | |
---|
| 181 | #endif // BOOST_EDGE_CONNECTIVITY |
---|