boost/graph/edge_connectivity.hpp

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