]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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/edmonds_karp_max_flow.hpp> | |
20 | ||
21 | namespace 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 (boost::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 (boost::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 (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { | |
115 | u = source(*ei, g), v = target(*ei, g); | |
116 | boost::tie(e1, inserted) = add_edge(u, v, flow_g); | |
117 | cap[e1] = 1; | |
118 | boost::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 | boost::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 | boost::tie(vi, vi_end) = vertices(g); | |
136 | std::set_difference(vi, vi_end, | |
137 | neighbor_S.begin(), neighbor_S.end(), | |
138 | std::back_inserter(non_neighbor_S)); | |
139 | ||
140 | while (!non_neighbor_S.empty()) { // at most n - 1 times | |
141 | k = non_neighbor_S.front(); | |
142 | ||
143 | alpha_S_k = edmonds_karp_max_flow | |
144 | (flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]); | |
145 | ||
146 | if (alpha_S_k < alpha_star) { | |
147 | alpha_star = alpha_S_k; | |
148 | S_star.clear(); | |
149 | for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi) | |
150 | if (color[*vi] != Color::white()) | |
151 | S_star.push_back(*vi); | |
152 | } | |
153 | S.insert(k); | |
154 | neighbor_S.insert(k); | |
155 | detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin())); | |
156 | non_neighbor_S.clear(); | |
157 | boost::tie(vi, vi_end) = vertices(g); | |
158 | std::set_difference(vi, vi_end, | |
159 | neighbor_S.begin(), neighbor_S.end(), | |
160 | std::back_inserter(non_neighbor_S)); | |
161 | } | |
162 | //------------------------------------------------------------------------- | |
163 | // Compute edges of the cut [S*, ~S*] | |
164 | std::vector<bool> in_S_star(num_vertices(g), false); | |
165 | typename std::vector<vertex_descriptor>::iterator si; | |
166 | for (si = S_star.begin(); si != S_star.end(); ++si) | |
167 | in_S_star[*si] = true; | |
168 | ||
169 | degree_size_type c = 0; | |
170 | for (si = S_star.begin(); si != S_star.end(); ++si) { | |
171 | out_edge_iterator ei, ei_end; | |
172 | for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei) | |
173 | if (!in_S_star[target(*ei, g)]) { | |
174 | *disconnecting_set++ = *ei; | |
175 | ++c; | |
176 | } | |
177 | } | |
178 | return c; | |
179 | } | |
180 | ||
181 | } // namespace boost | |
182 | ||
183 | #endif // BOOST_EDGE_CONNECTIVITY |