source: NonGTP/Boost/boost/graph/edge_connectivity.hpp @ 857

Revision 857, 6.6 KB checked in by igarcia, 19 years ago (diff)
Line 
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
21namespace 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
Note: See TracBrowser for help on using the repository browser.