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
24namespace 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

source code of boost/boost/graph/is_kuratowski_subgraph.hpp