File indexing completed on 2025-07-05 08:35:00
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 #ifndef BOOST_EDGE_CONNECTIVITY
0011 #define BOOST_EDGE_CONNECTIVITY
0012
0013
0014
0015 #include <boost/config.hpp>
0016 #include <vector>
0017 #include <set>
0018 #include <algorithm>
0019 #include <boost/graph/adjacency_list.hpp>
0020 #include <boost/graph/edmonds_karp_max_flow.hpp>
0021
0022 namespace boost
0023 {
0024
0025 namespace detail
0026 {
0027
0028 template < class Graph >
0029 inline std::pair< typename graph_traits< Graph >::vertex_descriptor,
0030 typename graph_traits< Graph >::degree_size_type >
0031 min_degree_vertex(Graph& g)
0032 {
0033 typedef graph_traits< Graph > Traits;
0034 typename Traits::vertex_descriptor p;
0035 typedef typename Traits::degree_size_type size_type;
0036 size_type delta = (std::numeric_limits< size_type >::max)();
0037
0038 typename Traits::vertex_iterator i, iend;
0039 for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
0040 if (degree(*i, g) < delta)
0041 {
0042 delta = degree(*i, g);
0043 p = *i;
0044 }
0045 return std::make_pair(p, delta);
0046 }
0047
0048 template < class Graph, class OutputIterator >
0049 void neighbors(const Graph& g,
0050 typename graph_traits< Graph >::vertex_descriptor u,
0051 OutputIterator result)
0052 {
0053 typename graph_traits< Graph >::adjacency_iterator ai, aend;
0054 for (boost::tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
0055 *result++ = *ai;
0056 }
0057
0058 template < class Graph, class VertexIterator, class OutputIterator >
0059 void neighbors(const Graph& g, VertexIterator first, VertexIterator last,
0060 OutputIterator result)
0061 {
0062 for (; first != last; ++first)
0063 neighbors(g, *first, result);
0064 }
0065
0066 }
0067
0068
0069 template < class VertexListGraph, class OutputIterator >
0070 typename graph_traits< VertexListGraph >::degree_size_type edge_connectivity(
0071 VertexListGraph& g, OutputIterator disconnecting_set)
0072 {
0073
0074
0075 typedef graph_traits< VertexListGraph > Traits;
0076 typedef typename Traits::vertex_iterator vertex_iterator;
0077 typedef typename Traits::edge_iterator edge_iterator;
0078 typedef typename Traits::out_edge_iterator out_edge_iterator;
0079 typedef typename Traits::vertex_descriptor vertex_descriptor;
0080 typedef typename Traits::degree_size_type degree_size_type;
0081 typedef color_traits< default_color_type > Color;
0082
0083 typedef adjacency_list_traits< vecS, vecS, directedS > Tr;
0084 typedef typename Tr::edge_descriptor Tr_edge_desc;
0085 typedef adjacency_list< vecS, vecS, directedS, no_property,
0086 property< edge_capacity_t, degree_size_type,
0087 property< edge_residual_capacity_t, degree_size_type,
0088 property< edge_reverse_t, Tr_edge_desc > > > >
0089 FlowGraph;
0090 typedef typename graph_traits< FlowGraph >::edge_descriptor edge_descriptor;
0091
0092
0093
0094 vertex_descriptor u, v, p, k;
0095 edge_descriptor e1, e2;
0096 bool inserted;
0097 vertex_iterator vi, vi_end;
0098 edge_iterator ei, ei_end;
0099 degree_size_type delta, alpha_star, alpha_S_k;
0100 std::set< vertex_descriptor > S, neighbor_S;
0101 std::vector< vertex_descriptor > S_star, non_neighbor_S;
0102 std::vector< default_color_type > color(num_vertices(g));
0103 std::vector< edge_descriptor > pred(num_vertices(g));
0104
0105
0106
0107 FlowGraph flow_g(num_vertices(g));
0108
0109 typename property_map< FlowGraph, edge_capacity_t >::type cap
0110 = get(edge_capacity, flow_g);
0111 typename property_map< FlowGraph, edge_residual_capacity_t >::type res_cap
0112 = get(edge_residual_capacity, flow_g);
0113 typename property_map< FlowGraph, edge_reverse_t >::type rev_edge
0114 = get(edge_reverse, flow_g);
0115
0116 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
0117 {
0118 u = source(*ei, g), v = target(*ei, g);
0119 boost::tie(e1, inserted) = add_edge(u, v, flow_g);
0120 cap[e1] = 1;
0121 boost::tie(e2, inserted) = add_edge(v, u, flow_g);
0122 cap[e2] = 1;
0123 rev_edge[e1] = e2;
0124 rev_edge[e2] = e1;
0125 }
0126
0127
0128
0129
0130 boost::tie(p, delta) = detail::min_degree_vertex(g);
0131 S_star.push_back(p);
0132 alpha_star = delta;
0133 S.insert(p);
0134 neighbor_S.insert(p);
0135 detail::neighbors(
0136 g, S.begin(), S.end(), std::inserter(neighbor_S, neighbor_S.begin()));
0137
0138 boost::tie(vi, vi_end) = vertices(g);
0139 std::set_difference(vi, vi_end, neighbor_S.begin(), neighbor_S.end(),
0140 std::back_inserter(non_neighbor_S));
0141
0142 while (!non_neighbor_S.empty())
0143 {
0144 k = non_neighbor_S.front();
0145
0146 alpha_S_k = edmonds_karp_max_flow(
0147 flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
0148
0149 if (alpha_S_k < alpha_star)
0150 {
0151 alpha_star = alpha_S_k;
0152 S_star.clear();
0153 for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
0154 if (color[*vi] != Color::white())
0155 S_star.push_back(*vi);
0156 }
0157 S.insert(k);
0158 neighbor_S.insert(k);
0159 detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
0160 non_neighbor_S.clear();
0161 boost::tie(vi, vi_end) = vertices(g);
0162 std::set_difference(vi, vi_end, neighbor_S.begin(), neighbor_S.end(),
0163 std::back_inserter(non_neighbor_S));
0164 }
0165
0166
0167 std::vector< bool > in_S_star(num_vertices(g), false);
0168 typename std::vector< vertex_descriptor >::iterator si;
0169 for (si = S_star.begin(); si != S_star.end(); ++si)
0170 in_S_star[*si] = true;
0171
0172 degree_size_type c = 0;
0173 for (si = S_star.begin(); si != S_star.end(); ++si)
0174 {
0175 out_edge_iterator ei, ei_end;
0176 for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
0177 if (!in_S_star[target(*ei, g)])
0178 {
0179 *disconnecting_set++ = *ei;
0180 ++c;
0181 }
0182 }
0183 return c;
0184 }
0185
0186 }
0187
0188 #endif