1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | #ifndef __IS_KURATOWSKI_SUBGRAPH_HPP__ |
9 | #define __IS_KURATOWSKI_SUBGRAPH_HPP__ |
10 | |
11 | #include <boost/config.hpp> |
12 | #include <boost/tuple/tuple.hpp> //for tie |
13 | #include <boost/property_map/property_map.hpp> |
14 | #include <boost/graph/properties.hpp> |
15 | #include <boost/graph/isomorphism.hpp> |
16 | #include <boost/graph/adjacency_list.hpp> |
17 | |
18 | #include <algorithm> |
19 | #include <vector> |
20 | #include <set> |
21 | |
22 | |
23 | |
24 | namespace boost |
25 | { |
26 | |
27 | namespace detail |
28 | { |
29 | |
30 | template <typename Graph> |
31 | Graph make_K_5() |
32 | { |
33 | typename graph_traits<Graph>::vertex_iterator vi, vi_end, inner_vi; |
34 | Graph K_5(5); |
35 | for(boost::tie(vi,vi_end) = vertices(K_5); vi != vi_end; ++vi) |
36 | for(inner_vi = next(vi); inner_vi != vi_end; ++inner_vi) |
37 | add_edge(*vi, *inner_vi, K_5); |
38 | return K_5; |
39 | } |
40 | |
41 | |
42 | template <typename Graph> |
43 | Graph make_K_3_3() |
44 | { |
45 | typename graph_traits<Graph>::vertex_iterator |
46 | vi, vi_end, bipartition_start, inner_vi; |
47 | Graph K_3_3(6); |
48 | bipartition_start = next(next(next(vertices(K_3_3).first))); |
49 | for(boost::tie(vi, vi_end) = vertices(K_3_3); vi != bipartition_start; ++vi) |
50 | for(inner_vi= bipartition_start; inner_vi != vi_end; ++inner_vi) |
51 | add_edge(*vi, *inner_vi, K_3_3); |
52 | return K_3_3; |
53 | } |
54 | |
55 | |
56 | template <typename AdjacencyList, typename Vertex> |
57 | void contract_edge(AdjacencyList& neighbors, Vertex u, Vertex v) |
58 | { |
59 | // Remove u from v's neighbor list |
60 | neighbors[v].erase(std::remove(neighbors[v].begin(), |
61 | neighbors[v].end(), u |
62 | ), |
63 | neighbors[v].end() |
64 | ); |
65 | |
66 | // Replace any references to u with references to v |
67 | typedef typename AdjacencyList::value_type::iterator |
68 | adjacency_iterator_t; |
69 | |
70 | adjacency_iterator_t u_neighbor_end = neighbors[u].end(); |
71 | for(adjacency_iterator_t u_neighbor_itr = neighbors[u].begin(); |
72 | u_neighbor_itr != u_neighbor_end; ++u_neighbor_itr |
73 | ) |
74 | { |
75 | Vertex u_neighbor(*u_neighbor_itr); |
76 | std::replace(neighbors[u_neighbor].begin(), |
77 | neighbors[u_neighbor].end(), u, v |
78 | ); |
79 | } |
80 | |
81 | // Remove v from u's neighbor list |
82 | neighbors[u].erase(std::remove(neighbors[u].begin(), |
83 | neighbors[u].end(), v |
84 | ), |
85 | neighbors[u].end() |
86 | ); |
87 | |
88 | // Add everything in u's neighbor list to v's neighbor list |
89 | std::copy(neighbors[u].begin(), |
90 | neighbors[u].end(), |
91 | std::back_inserter(neighbors[v]) |
92 | ); |
93 | |
94 | // Clear u's neighbor list |
95 | neighbors[u].clear(); |
96 | |
97 | } |
98 | |
99 | enum target_graph_t { tg_k_3_3, tg_k_5}; |
100 | |
101 | } // namespace detail |
102 | |
103 | |
104 | |
105 | |
106 | template <typename Graph, typename ForwardIterator, typename VertexIndexMap> |
107 | bool is_kuratowski_subgraph(const Graph& g, |
108 | ForwardIterator begin, |
109 | ForwardIterator end, |
110 | VertexIndexMap vm |
111 | ) |
112 | { |
113 | |
114 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
115 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; |
116 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
117 | typedef typename graph_traits<Graph>::edges_size_type e_size_t; |
118 | typedef typename graph_traits<Graph>::vertices_size_type v_size_t; |
119 | typedef typename std::vector<vertex_t> v_list_t; |
120 | typedef typename v_list_t::iterator v_list_iterator_t; |
121 | typedef iterator_property_map |
122 | <typename std::vector<v_list_t>::iterator, VertexIndexMap> |
123 | vertex_to_v_list_map_t; |
124 | |
125 | typedef adjacency_list<vecS, vecS, undirectedS> small_graph_t; |
126 | |
127 | detail::target_graph_t target_graph = detail::tg_k_3_3; //unless we decide otherwise later |
128 | |
129 | static small_graph_t K_5(detail::make_K_5<small_graph_t>()); |
130 | |
131 | static small_graph_t K_3_3(detail::make_K_3_3<small_graph_t>()); |
132 | |
133 | v_size_t n_vertices(num_vertices(g)); |
134 | v_size_t max_num_edges(3*n_vertices - 5); |
135 | |
136 | std::vector<v_list_t> neighbors_vector(n_vertices); |
137 | vertex_to_v_list_map_t neighbors(neighbors_vector.begin(), vm); |
138 | |
139 | e_size_t count = 0; |
140 | for(ForwardIterator itr = begin; itr != end; ++itr) |
141 | { |
142 | |
143 | if (count++ > max_num_edges) |
144 | return false; |
145 | |
146 | edge_t e(*itr); |
147 | vertex_t u(source(e,g)); |
148 | vertex_t v(target(e,g)); |
149 | |
150 | neighbors[u].push_back(v); |
151 | neighbors[v].push_back(u); |
152 | |
153 | } |
154 | |
155 | |
156 | for(v_size_t max_size = 2; max_size < 5; ++max_size) |
157 | { |
158 | |
159 | vertex_iterator_t vi, vi_end; |
160 | for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) |
161 | { |
162 | vertex_t v(*vi); |
163 | |
164 | //a hack to make sure we don't contract the middle edge of a path |
165 | //of four degree-3 vertices |
166 | if (max_size == 4 && neighbors[v].size() == 3) |
167 | { |
168 | if (neighbors[neighbors[v][0]].size() + |
169 | neighbors[neighbors[v][1]].size() + |
170 | neighbors[neighbors[v][2]].size() |
171 | < 11 // so, it has two degree-3 neighbors |
172 | ) |
173 | continue; |
174 | } |
175 | |
176 | while (neighbors[v].size() > 0 && neighbors[v].size() < max_size) |
177 | { |
178 | // Find one of v's neighbors u such that v and u |
179 | // have no neighbors in common. We'll look for such a |
180 | // neighbor with a naive cubic-time algorithm since the |
181 | // max size of any of the neighbor sets we'll consider |
182 | // merging is 3 |
183 | |
184 | bool neighbor_sets_intersect = false; |
185 | |
186 | vertex_t min_u = graph_traits<Graph>::null_vertex(); |
187 | vertex_t u; |
188 | v_list_iterator_t v_neighbor_end = neighbors[v].end(); |
189 | for(v_list_iterator_t v_neighbor_itr = neighbors[v].begin(); |
190 | v_neighbor_itr != v_neighbor_end; |
191 | ++v_neighbor_itr |
192 | ) |
193 | { |
194 | neighbor_sets_intersect = false; |
195 | u = *v_neighbor_itr; |
196 | v_list_iterator_t u_neighbor_end = neighbors[u].end(); |
197 | for(v_list_iterator_t u_neighbor_itr = |
198 | neighbors[u].begin(); |
199 | u_neighbor_itr != u_neighbor_end && |
200 | !neighbor_sets_intersect; |
201 | ++u_neighbor_itr |
202 | ) |
203 | { |
204 | for(v_list_iterator_t inner_v_neighbor_itr = |
205 | neighbors[v].begin(); |
206 | inner_v_neighbor_itr != v_neighbor_end; |
207 | ++inner_v_neighbor_itr |
208 | ) |
209 | { |
210 | if (*u_neighbor_itr == *inner_v_neighbor_itr) |
211 | { |
212 | neighbor_sets_intersect = true; |
213 | break; |
214 | } |
215 | } |
216 | |
217 | } |
218 | if (!neighbor_sets_intersect && |
219 | (min_u == graph_traits<Graph>::null_vertex() || |
220 | neighbors[u].size() < neighbors[min_u].size()) |
221 | ) |
222 | { |
223 | min_u = u; |
224 | } |
225 | |
226 | } |
227 | |
228 | if (min_u == graph_traits<Graph>::null_vertex()) |
229 | // Exited the loop without finding an appropriate neighbor of |
230 | // v, so v must be a lost cause. Move on to other vertices. |
231 | break; |
232 | else |
233 | u = min_u; |
234 | |
235 | detail::contract_edge(neighbors, u, v); |
236 | |
237 | }//end iteration over v's neighbors |
238 | |
239 | }//end iteration through vertices v |
240 | |
241 | if (max_size == 3) |
242 | { |
243 | // check to see whether we should go on to find a K_5 |
244 | for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) |
245 | if (neighbors[*vi].size() == 4) |
246 | { |
247 | target_graph = detail::tg_k_5; |
248 | break; |
249 | } |
250 | |
251 | if (target_graph == detail::tg_k_3_3) |
252 | break; |
253 | } |
254 | |
255 | }//end iteration through max degree 2,3, and 4 |
256 | |
257 | |
258 | //Now, there should only be 5 or 6 vertices with any neighbors. Find them. |
259 | |
260 | v_list_t main_vertices; |
261 | vertex_iterator_t vi, vi_end; |
262 | |
263 | for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) |
264 | { |
265 | if (!neighbors[*vi].empty()) |
266 | main_vertices.push_back(*vi); |
267 | } |
268 | |
269 | // create a graph isomorphic to the contracted graph to test |
270 | // against K_5 and K_3_3 |
271 | small_graph_t contracted_graph(main_vertices.size()); |
272 | std::map<vertex_t,typename graph_traits<small_graph_t>::vertex_descriptor> |
273 | contracted_vertex_map; |
274 | |
275 | typename v_list_t::iterator itr, itr_end; |
276 | itr_end = main_vertices.end(); |
277 | typename graph_traits<small_graph_t>::vertex_iterator |
278 | si = vertices(g_: contracted_graph).first; |
279 | |
280 | for(itr = main_vertices.begin(); itr != itr_end; ++itr, ++si) |
281 | { |
282 | contracted_vertex_map[*itr] = *si; |
283 | } |
284 | |
285 | typename v_list_t::iterator jtr, jtr_end; |
286 | for(itr = main_vertices.begin(); itr != itr_end; ++itr) |
287 | { |
288 | jtr_end = neighbors[*itr].end(); |
289 | for(jtr = neighbors[*itr].begin(); jtr != jtr_end; ++jtr) |
290 | { |
291 | if (get(vm,*itr) < get(vm,*jtr)) |
292 | { |
293 | add_edge(contracted_vertex_map[*itr], |
294 | contracted_vertex_map[*jtr], |
295 | contracted_graph |
296 | ); |
297 | } |
298 | } |
299 | } |
300 | |
301 | if (target_graph == detail::tg_k_5) |
302 | { |
303 | return boost::isomorphism(param0: K_5,param1: contracted_graph); |
304 | } |
305 | else //target_graph == tg_k_3_3 |
306 | { |
307 | return boost::isomorphism(param0: K_3_3,param1: contracted_graph); |
308 | } |
309 | |
310 | |
311 | } |
312 | |
313 | |
314 | |
315 | |
316 | |
317 | template <typename Graph, typename ForwardIterator> |
318 | bool is_kuratowski_subgraph(const Graph& g, |
319 | ForwardIterator begin, |
320 | ForwardIterator end |
321 | ) |
322 | { |
323 | return is_kuratowski_subgraph(g, begin, end, get(vertex_index,g)); |
324 | } |
325 | |
326 | |
327 | |
328 | |
329 | } |
330 | |
331 | #endif //__IS_KURATOWSKI_SUBGRAPH_HPP__ |
332 | |