]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(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(K_5,contracted_graph); | |
304 | } | |
305 | else //target_graph == tg_k_3_3 | |
306 | { | |
307 | return boost::isomorphism(K_3_3,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__ |