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