williamr@2: //=======================================================================
williamr@2: // Copyright 2000 University of Notre Dame.
williamr@2: // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: 
williamr@2: #ifndef BOOST_EDGE_CONNECTIVITY
williamr@2: #define BOOST_EDGE_CONNECTIVITY
williamr@2: 
williamr@2: // WARNING: not-yet fully tested!
williamr@2: 
williamr@2: #include <boost/config.hpp>
williamr@2: #include <vector>
williamr@2: #include <set>
williamr@2: #include <algorithm>
williamr@2: #include <boost/graph/edmunds_karp_max_flow.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   namespace detail {
williamr@2: 
williamr@2:     template <class Graph>
williamr@2:     inline
williamr@2:     std::pair<typename graph_traits<Graph>::vertex_descriptor,
williamr@2:               typename graph_traits<Graph>::degree_size_type>
williamr@2:     min_degree_vertex(Graph& g)
williamr@2:     {
williamr@2:       typedef graph_traits<Graph> Traits;
williamr@2:       typename Traits::vertex_descriptor p;
williamr@2:       typedef typename Traits::degree_size_type size_type;
williamr@2:       size_type delta = (std::numeric_limits<size_type>::max)();
williamr@2: 
williamr@2:       typename Traits::vertex_iterator i, iend;
williamr@2:       for (tie(i, iend) = vertices(g); i != iend; ++i)
williamr@2:         if (degree(*i, g) < delta) {
williamr@2:           delta = degree(*i, g);
williamr@2:           p = *i;
williamr@2:         }
williamr@2:       return std::make_pair(p, delta);
williamr@2:     }
williamr@2: 
williamr@2:     template <class Graph, class OutputIterator>
williamr@2:     void neighbors(const Graph& g, 
williamr@2:                    typename graph_traits<Graph>::vertex_descriptor u,
williamr@2:                    OutputIterator result)
williamr@2:     {
williamr@2:       typename graph_traits<Graph>::adjacency_iterator ai, aend;
williamr@2:       for (tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
williamr@2:         *result++ = *ai;
williamr@2:     }
williamr@2: 
williamr@2:     template <class Graph, class VertexIterator, class OutputIterator>
williamr@2:     void neighbors(const Graph& g, 
williamr@2:                    VertexIterator first, VertexIterator last,
williamr@2:                    OutputIterator result)
williamr@2:     {
williamr@2:       for (; first != last; ++first)
williamr@2:         neighbors(g, *first, result);
williamr@2:     }
williamr@2: 
williamr@2:   } // namespace detail
williamr@2: 
williamr@2:   // O(m n)
williamr@2:   template <class VertexListGraph, class OutputIterator>
williamr@2:   typename graph_traits<VertexListGraph>::degree_size_type
williamr@2:   edge_connectivity(VertexListGraph& g, OutputIterator disconnecting_set)
williamr@2:   {
williamr@2:     //-------------------------------------------------------------------------
williamr@2:     // Type Definitions
williamr@2:     typedef graph_traits<VertexListGraph> Traits;
williamr@2:     typedef typename Traits::vertex_iterator vertex_iterator;
williamr@2:     typedef typename Traits::edge_iterator edge_iterator;
williamr@2:     typedef typename Traits::out_edge_iterator out_edge_iterator;
williamr@2:     typedef typename Traits::vertex_descriptor vertex_descriptor;
williamr@2:     typedef typename Traits::degree_size_type degree_size_type;
williamr@2:     typedef color_traits<default_color_type> Color;
williamr@2: 
williamr@2:     typedef adjacency_list_traits<vecS, vecS, directedS> Tr;
williamr@2:     typedef typename Tr::edge_descriptor Tr_edge_desc;
williamr@2:     typedef adjacency_list<vecS, vecS, directedS, no_property, 
williamr@2:       property<edge_capacity_t, degree_size_type,
williamr@2:         property<edge_residual_capacity_t, degree_size_type,
williamr@2:           property<edge_reverse_t, Tr_edge_desc> > > > 
williamr@2:       FlowGraph;
williamr@2:     typedef typename graph_traits<FlowGraph>::edge_descriptor edge_descriptor;
williamr@2: 
williamr@2:     //-------------------------------------------------------------------------
williamr@2:     // Variable Declarations
williamr@2:     vertex_descriptor u, v, p, k;
williamr@2:     edge_descriptor e1, e2;
williamr@2:     bool inserted;
williamr@2:     vertex_iterator vi, vi_end;
williamr@2:     edge_iterator ei, ei_end;
williamr@2:     degree_size_type delta, alpha_star, alpha_S_k;
williamr@2:     std::set<vertex_descriptor> S, neighbor_S;
williamr@2:     std::vector<vertex_descriptor> S_star, non_neighbor_S;
williamr@2:     std::vector<default_color_type> color(num_vertices(g));
williamr@2:     std::vector<edge_descriptor> pred(num_vertices(g));
williamr@2: 
williamr@2:     //-------------------------------------------------------------------------
williamr@2:     // Create a network flow graph out of the undirected graph
williamr@2:     FlowGraph flow_g(num_vertices(g));
williamr@2: 
williamr@2:     typename property_map<FlowGraph, edge_capacity_t>::type
williamr@2:       cap = get(edge_capacity, flow_g);
williamr@2:     typename property_map<FlowGraph, edge_residual_capacity_t>::type
williamr@2:       res_cap = get(edge_residual_capacity, flow_g);
williamr@2:     typename property_map<FlowGraph, edge_reverse_t>::type
williamr@2:       rev_edge = get(edge_reverse, flow_g);
williamr@2: 
williamr@2:     for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
williamr@2:       u = source(*ei, g), v = target(*ei, g);
williamr@2:       tie(e1, inserted) = add_edge(u, v, flow_g);
williamr@2:       cap[e1] = 1;
williamr@2:       tie(e2, inserted) = add_edge(v, u, flow_g);
williamr@2:       cap[e2] = 1; // not sure about this
williamr@2:       rev_edge[e1] = e2;
williamr@2:       rev_edge[e2] = e1;
williamr@2:     }
williamr@2: 
williamr@2:     //-------------------------------------------------------------------------
williamr@2:     // The Algorithm
williamr@2: 
williamr@2:     tie(p, delta) = detail::min_degree_vertex(g);
williamr@2:     S_star.push_back(p);
williamr@2:     alpha_star = delta;
williamr@2:     S.insert(p);
williamr@2:     neighbor_S.insert(p);
williamr@2:     detail::neighbors(g, S.begin(), S.end(), 
williamr@2:                       std::inserter(neighbor_S, neighbor_S.begin()));
williamr@2: 
williamr@2:     std::set_difference(vertices(g).first, vertices(g).second,
williamr@2:                         neighbor_S.begin(), neighbor_S.end(),
williamr@2:                         std::back_inserter(non_neighbor_S));
williamr@2: 
williamr@2:     while (!non_neighbor_S.empty()) { // at most n - 1 times
williamr@2:       k = non_neighbor_S.front();
williamr@2: 
williamr@2:       alpha_S_k = edmunds_karp_max_flow
williamr@2:         (flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
williamr@2: 
williamr@2:       if (alpha_S_k < alpha_star) {
williamr@2:         alpha_star = alpha_S_k;
williamr@2:         S_star.clear();
williamr@2:         for (tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
williamr@2:           if (color[*vi] != Color::white())
williamr@2:             S_star.push_back(*vi);
williamr@2:       }
williamr@2:       S.insert(k);
williamr@2:       neighbor_S.insert(k);
williamr@2:       detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
williamr@2:       non_neighbor_S.clear();
williamr@2:       std::set_difference(vertices(g).first, vertices(g).second,
williamr@2:                           neighbor_S.begin(), neighbor_S.end(),
williamr@2:                           std::back_inserter(non_neighbor_S));
williamr@2:     }
williamr@2:     //-------------------------------------------------------------------------
williamr@2:     // Compute edges of the cut [S*, ~S*]
williamr@2:     std::vector<bool> in_S_star(num_vertices(g), false);
williamr@2:     typename std::vector<vertex_descriptor>::iterator si;
williamr@2:     for (si = S_star.begin(); si != S_star.end(); ++si)
williamr@2:       in_S_star[*si] = true;
williamr@2: 
williamr@2:     degree_size_type c = 0;
williamr@2:     for (si = S_star.begin(); si != S_star.end(); ++si) {
williamr@2:       out_edge_iterator ei, ei_end;
williamr@2:       for (tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
williamr@2:         if (!in_S_star[target(*ei, g)]) {
williamr@2:           *disconnecting_set++ = *ei;
williamr@2:           ++c;
williamr@2:         }
williamr@2:     }
williamr@2:     return c;
williamr@2:   }
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif // BOOST_EDGE_CONNECTIVITY