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 | |
---|
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 (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 |
---|