Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-07-05 08:35:00

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/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 } // namespace detail
0067 
0068 // O(m n)
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     // Type Definitions
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     // Variable Declarations
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     // Create a network flow graph out of the undirected graph
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; // not sure about this
0123         rev_edge[e1] = e2;
0124         rev_edge[e2] = e1;
0125     }
0126 
0127     //-------------------------------------------------------------------------
0128     // The Algorithm
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     { // at most n - 1 times
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     // Compute edges of the cut [S*, ~S*]
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 } // namespace boost
0187 
0188 #endif // BOOST_EDGE_CONNECTIVITY