1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
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__
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>
30 template <typename Graph>
33 typename graph_traits<Graph>::vertex_iterator vi, vi_end, inner_vi;
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);
42 template <typename Graph>
45 typename graph_traits<Graph>::vertex_iterator
46 vi, vi_end, bipartition_start, inner_vi;
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);
56 template <typename AdjacencyList, typename Vertex>
57 void contract_edge(AdjacencyList& neighbors, Vertex u, Vertex v)
59 // Remove u from v's neighbor list
60 neighbors[v].erase(std::remove(neighbors[v].begin(),
66 // Replace any references to u with references to v
67 typedef typename AdjacencyList::value_type::iterator
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
75 Vertex u_neighbor(*u_neighbor_itr);
76 std::replace(neighbors[u_neighbor].begin(),
77 neighbors[u_neighbor].end(), u, v
81 // Remove v from u's neighbor list
82 neighbors[u].erase(std::remove(neighbors[u].begin(),
88 // Add everything in u's neighbor list to v's neighbor list
89 std::copy(neighbors[u].begin(),
91 std::back_inserter(neighbors[v])
94 // Clear u's neighbor list
99 enum target_graph_t { tg_k_3_3, tg_k_5};
101 } // namespace detail
106 template <typename Graph, typename ForwardIterator, typename VertexIndexMap>
107 bool is_kuratowski_subgraph(const Graph& g,
108 ForwardIterator begin,
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;
125 typedef adjacency_list<vecS, vecS, undirectedS> small_graph_t;
127 detail::target_graph_t target_graph = detail::tg_k_3_3; //unless we decide otherwise later
129 static small_graph_t K_5(detail::make_K_5<small_graph_t>());
131 static small_graph_t K_3_3(detail::make_K_3_3<small_graph_t>());
133 v_size_t n_vertices(num_vertices(g));
134 v_size_t max_num_edges(3*n_vertices - 5);
136 std::vector<v_list_t> neighbors_vector(n_vertices);
137 vertex_to_v_list_map_t neighbors(neighbors_vector.begin(), vm);
140 for(ForwardIterator itr = begin; itr != end; ++itr)
143 if (count++ > max_num_edges)
147 vertex_t u(source(e,g));
148 vertex_t v(target(e,g));
150 neighbors[u].push_back(v);
151 neighbors[v].push_back(u);
156 for(v_size_t max_size = 2; max_size < 5; ++max_size)
159 vertex_iterator_t vi, vi_end;
160 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
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)
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
176 while (neighbors[v].size() > 0 && neighbors[v].size() < max_size)
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
184 bool neighbor_sets_intersect = false;
186 vertex_t min_u = graph_traits<Graph>::null_vertex();
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;
194 neighbor_sets_intersect = false;
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;
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
210 if (*u_neighbor_itr == *inner_v_neighbor_itr)
212 neighbor_sets_intersect = true;
218 if (!neighbor_sets_intersect &&
219 (min_u == graph_traits<Graph>::null_vertex() ||
220 neighbors[u].size() < neighbors[min_u].size())
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.
235 detail::contract_edge(neighbors, u, v);
237 }//end iteration over v's neighbors
239 }//end iteration through vertices v
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)
247 target_graph = detail::tg_k_5;
251 if (target_graph == detail::tg_k_3_3)
255 }//end iteration through max degree 2,3, and 4
258 //Now, there should only be 5 or 6 vertices with any neighbors. Find them.
260 v_list_t main_vertices;
261 vertex_iterator_t vi, vi_end;
263 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
265 if (!neighbors[*vi].empty())
266 main_vertices.push_back(*vi);
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;
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;
280 for(itr = main_vertices.begin(); itr != itr_end; ++itr, ++si)
282 contracted_vertex_map[*itr] = *si;
285 typename v_list_t::iterator jtr, jtr_end;
286 for(itr = main_vertices.begin(); itr != itr_end; ++itr)
288 jtr_end = neighbors[*itr].end();
289 for(jtr = neighbors[*itr].begin(); jtr != jtr_end; ++jtr)
291 if (get(vm,*itr) < get(vm,*jtr))
293 add_edge(contracted_vertex_map[*itr],
294 contracted_vertex_map[*jtr],
301 if (target_graph == detail::tg_k_5)
303 return boost::isomorphism(K_5,contracted_graph);
305 else //target_graph == tg_k_3_3
307 return boost::isomorphism(K_3_3,contracted_graph);
317 template <typename Graph, typename ForwardIterator>
318 bool is_kuratowski_subgraph(const Graph& g,
319 ForwardIterator begin,
323 return is_kuratowski_subgraph(g, begin, end, get(vertex_index,g));
331 #endif //__IS_KURATOWSKI_SUBGRAPH_HPP__