Chris@16: //=======================================================================
Chris@16: // Copyright 2007 Aaron Windsor
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: #ifndef __IS_KURATOWSKI_SUBGRAPH_HPP__
Chris@16: #define __IS_KURATOWSKI_SUBGRAPH_HPP__
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/tuple/tuple.hpp>   //for tie
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/graph/isomorphism.hpp>
Chris@16: #include <boost/graph/adjacency_list.hpp>
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <vector>
Chris@16: #include <set>
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:   
Chris@16:   namespace detail
Chris@16:   {
Chris@16: 
Chris@16:     template <typename Graph>
Chris@16:     Graph make_K_5()
Chris@16:     {
Chris@16:       typename graph_traits<Graph>::vertex_iterator vi, vi_end, inner_vi;
Chris@16:       Graph K_5(5);
Chris@16:       for(boost::tie(vi,vi_end) = vertices(K_5); vi != vi_end; ++vi)
Chris@16:         for(inner_vi = next(vi); inner_vi != vi_end; ++inner_vi)
Chris@16:           add_edge(*vi, *inner_vi, K_5);
Chris@16:       return K_5;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <typename Graph>
Chris@16:     Graph make_K_3_3()
Chris@16:     {
Chris@16:       typename graph_traits<Graph>::vertex_iterator 
Chris@16:         vi, vi_end, bipartition_start, inner_vi;
Chris@16:       Graph K_3_3(6);
Chris@16:       bipartition_start = next(next(next(vertices(K_3_3).first)));
Chris@16:       for(boost::tie(vi, vi_end) = vertices(K_3_3); vi != bipartition_start; ++vi)
Chris@16:         for(inner_vi= bipartition_start; inner_vi != vi_end; ++inner_vi)
Chris@16:           add_edge(*vi, *inner_vi, K_3_3);
Chris@16:       return K_3_3;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <typename AdjacencyList, typename Vertex>
Chris@16:     void contract_edge(AdjacencyList& neighbors, Vertex u, Vertex v)
Chris@16:     {
Chris@16:       // Remove u from v's neighbor list
Chris@16:       neighbors[v].erase(std::remove(neighbors[v].begin(), 
Chris@16:                                      neighbors[v].end(), u
Chris@16:                                      ), 
Chris@16:                          neighbors[v].end()
Chris@16:                          );
Chris@16:       
Chris@16:       // Replace any references to u with references to v
Chris@16:       typedef typename AdjacencyList::value_type::iterator 
Chris@16:         adjacency_iterator_t;
Chris@16:       
Chris@16:       adjacency_iterator_t u_neighbor_end = neighbors[u].end();
Chris@16:       for(adjacency_iterator_t u_neighbor_itr = neighbors[u].begin();
Chris@16:           u_neighbor_itr != u_neighbor_end; ++u_neighbor_itr
Chris@16:           )
Chris@16:         {
Chris@16:           Vertex u_neighbor(*u_neighbor_itr);
Chris@16:           std::replace(neighbors[u_neighbor].begin(), 
Chris@16:                        neighbors[u_neighbor].end(), u, v
Chris@16:                        );
Chris@16:         }
Chris@16:       
Chris@16:       // Remove v from u's neighbor list
Chris@16:       neighbors[u].erase(std::remove(neighbors[u].begin(), 
Chris@16:                                      neighbors[u].end(), v
Chris@16:                                      ), 
Chris@16:                          neighbors[u].end()
Chris@16:                          );
Chris@16:       
Chris@16:       // Add everything in u's neighbor list to v's neighbor list
Chris@16:       std::copy(neighbors[u].begin(), 
Chris@16:                 neighbors[u].end(), 
Chris@16:                 std::back_inserter(neighbors[v])
Chris@16:                 );
Chris@16:       
Chris@16:       // Clear u's neighbor list
Chris@16:       neighbors[u].clear();
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16:     enum target_graph_t { tg_k_3_3, tg_k_5};
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Graph, typename ForwardIterator, typename VertexIndexMap>
Chris@16:   bool is_kuratowski_subgraph(const Graph& g,
Chris@16:                               ForwardIterator begin, 
Chris@16:                               ForwardIterator end, 
Chris@16:                               VertexIndexMap vm
Chris@16:                               )
Chris@16:   {
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
Chris@16:     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type e_size_t;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
Chris@16:     typedef typename std::vector<vertex_t> v_list_t;
Chris@16:     typedef typename v_list_t::iterator v_list_iterator_t;
Chris@16:     typedef iterator_property_map
Chris@16:       <typename std::vector<v_list_t>::iterator, VertexIndexMap> 
Chris@16:       vertex_to_v_list_map_t;
Chris@16: 
Chris@16:     typedef adjacency_list<vecS, vecS, undirectedS> small_graph_t;
Chris@16: 
Chris@16:     detail::target_graph_t target_graph = detail::tg_k_3_3; //unless we decide otherwise later
Chris@16: 
Chris@16:     static small_graph_t K_5(detail::make_K_5<small_graph_t>());
Chris@16: 
Chris@16:     static small_graph_t K_3_3(detail::make_K_3_3<small_graph_t>());
Chris@16: 
Chris@16:     v_size_t n_vertices(num_vertices(g));
Chris@16:     v_size_t max_num_edges(3*n_vertices - 5);
Chris@16: 
Chris@16:     std::vector<v_list_t> neighbors_vector(n_vertices);
Chris@16:     vertex_to_v_list_map_t neighbors(neighbors_vector.begin(), vm);
Chris@16: 
Chris@16:     e_size_t count = 0;
Chris@16:     for(ForwardIterator itr = begin; itr != end; ++itr)
Chris@16:       {
Chris@16: 
Chris@16:         if (count++ > max_num_edges)
Chris@16:           return false;
Chris@16: 
Chris@16:         edge_t e(*itr);
Chris@16:         vertex_t u(source(e,g));
Chris@16:         vertex_t v(target(e,g));
Chris@16: 
Chris@16:         neighbors[u].push_back(v);
Chris@16:         neighbors[v].push_back(u);
Chris@16: 
Chris@16:       }
Chris@16: 
Chris@16: 
Chris@16:     for(v_size_t max_size = 2; max_size < 5; ++max_size)
Chris@16:       {
Chris@16: 
Chris@16:         vertex_iterator_t vi, vi_end;
Chris@16:         for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
Chris@16:           {
Chris@16:             vertex_t v(*vi);
Chris@16: 
Chris@16:             //a hack to make sure we don't contract the middle edge of a path
Chris@16:             //of four degree-3 vertices
Chris@16:             if (max_size == 4 && neighbors[v].size() == 3)
Chris@16:               {
Chris@16:                 if (neighbors[neighbors[v][0]].size() +
Chris@16:                     neighbors[neighbors[v][1]].size() +
Chris@16:                     neighbors[neighbors[v][2]].size()
Chris@16:                     < 11 // so, it has two degree-3 neighbors
Chris@16:                     )
Chris@16:                   continue;
Chris@16:               }
Chris@16: 
Chris@16:             while (neighbors[v].size() > 0 && neighbors[v].size() < max_size)
Chris@16:               {
Chris@16:                 // Find one of v's neighbors u such that v and u
Chris@16:                 // have no neighbors in common. We'll look for such a 
Chris@16:                 // neighbor with a naive cubic-time algorithm since the 
Chris@16:                 // max size of any of the neighbor sets we'll consider 
Chris@16:                 // merging is 3
Chris@16:                 
Chris@16:                 bool neighbor_sets_intersect = false;
Chris@16:                 
Chris@16:                 vertex_t min_u = graph_traits<Graph>::null_vertex();
Chris@16:                 vertex_t u;
Chris@16:                 v_list_iterator_t v_neighbor_end = neighbors[v].end();
Chris@16:                 for(v_list_iterator_t v_neighbor_itr = neighbors[v].begin();
Chris@16:                     v_neighbor_itr != v_neighbor_end; 
Chris@16:                     ++v_neighbor_itr
Chris@16:                     )
Chris@16:                   {
Chris@16:                     neighbor_sets_intersect = false;
Chris@16:                     u = *v_neighbor_itr;
Chris@16:                     v_list_iterator_t u_neighbor_end = neighbors[u].end();
Chris@16:                     for(v_list_iterator_t u_neighbor_itr = 
Chris@16:                           neighbors[u].begin();
Chris@16:                         u_neighbor_itr != u_neighbor_end && 
Chris@16:                           !neighbor_sets_intersect; 
Chris@16:                         ++u_neighbor_itr
Chris@16:                         )
Chris@16:                       {
Chris@16:                         for(v_list_iterator_t inner_v_neighbor_itr = 
Chris@16:                               neighbors[v].begin();
Chris@16:                             inner_v_neighbor_itr != v_neighbor_end; 
Chris@16:                             ++inner_v_neighbor_itr
Chris@16:                             )
Chris@16:                           {
Chris@16:                             if (*u_neighbor_itr == *inner_v_neighbor_itr)
Chris@16:                               {
Chris@16:                                 neighbor_sets_intersect = true;
Chris@16:                                 break;
Chris@16:                               }
Chris@16:                           }
Chris@16:                         
Chris@16:                       }
Chris@16:                     if (!neighbor_sets_intersect &&
Chris@16:                         (min_u == graph_traits<Graph>::null_vertex() || 
Chris@16:                          neighbors[u].size() < neighbors[min_u].size())
Chris@16:                         )
Chris@16:                       {
Chris@16:                         min_u = u;
Chris@16:                       }
Chris@16:                         
Chris@16:                   }
Chris@16: 
Chris@16:                 if (min_u == graph_traits<Graph>::null_vertex())
Chris@16:                   // Exited the loop without finding an appropriate neighbor of
Chris@16:                   // v, so v must be a lost cause. Move on to other vertices.
Chris@16:                   break;
Chris@16:                 else
Chris@16:                   u = min_u;
Chris@16: 
Chris@16:                 detail::contract_edge(neighbors, u, v);
Chris@16: 
Chris@16:               }//end iteration over v's neighbors
Chris@16: 
Chris@16:           }//end iteration through vertices v
Chris@16: 
Chris@16:         if (max_size == 3)
Chris@16:           {
Chris@16:             // check to see whether we should go on to find a K_5
Chris@16:             for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
Chris@16:               if (neighbors[*vi].size() == 4)
Chris@16:                 {
Chris@16:                   target_graph = detail::tg_k_5;
Chris@16:                   break;
Chris@16:                 }
Chris@16: 
Chris@16:             if (target_graph == detail::tg_k_3_3)
Chris@16:               break;
Chris@16:           }
Chris@16:         
Chris@16:       }//end iteration through max degree 2,3, and 4
Chris@16: 
Chris@16:     
Chris@16:     //Now, there should only be 5 or 6 vertices with any neighbors. Find them.
Chris@16:     
Chris@16:     v_list_t main_vertices;
Chris@16:     vertex_iterator_t vi, vi_end;
Chris@16:     
Chris@16:     for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
Chris@16:       {
Chris@16:         if (!neighbors[*vi].empty())
Chris@16:           main_vertices.push_back(*vi);
Chris@16:       }
Chris@16:     
Chris@16:     // create a graph isomorphic to the contracted graph to test 
Chris@16:     // against K_5 and K_3_3
Chris@16:     small_graph_t contracted_graph(main_vertices.size());
Chris@16:     std::map<vertex_t,typename graph_traits<small_graph_t>::vertex_descriptor> 
Chris@16:       contracted_vertex_map;
Chris@16:     
Chris@16:     typename v_list_t::iterator itr, itr_end;
Chris@16:     itr_end = main_vertices.end();
Chris@16:     typename graph_traits<small_graph_t>::vertex_iterator 
Chris@16:       si = vertices(contracted_graph).first;
Chris@16:     
Chris@16:     for(itr = main_vertices.begin(); itr != itr_end; ++itr, ++si)
Chris@16:       {
Chris@16:         contracted_vertex_map[*itr] = *si;
Chris@16:       }
Chris@16: 
Chris@16:     typename v_list_t::iterator jtr, jtr_end;
Chris@16:     for(itr = main_vertices.begin(); itr != itr_end; ++itr)
Chris@16:       {
Chris@16:         jtr_end = neighbors[*itr].end();
Chris@16:         for(jtr = neighbors[*itr].begin(); jtr != jtr_end; ++jtr)
Chris@16:           {
Chris@16:             if (get(vm,*itr) < get(vm,*jtr))
Chris@16:               {
Chris@16:                 add_edge(contracted_vertex_map[*itr],
Chris@16:                          contracted_vertex_map[*jtr],
Chris@16:                          contracted_graph
Chris@16:                          );
Chris@16:               }
Chris@16:           }
Chris@16:       }
Chris@16:     
Chris@16:     if (target_graph == detail::tg_k_5)
Chris@16:       {
Chris@16:         return boost::isomorphism(K_5,contracted_graph);
Chris@16:       }
Chris@16:     else //target_graph == tg_k_3_3
Chris@16:       {
Chris@16:         return boost::isomorphism(K_3_3,contracted_graph);
Chris@16:       }
Chris@16:     
Chris@16:     
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   template <typename Graph, typename ForwardIterator>
Chris@16:   bool is_kuratowski_subgraph(const Graph& g, 
Chris@16:                               ForwardIterator begin, 
Chris@16:                               ForwardIterator end
Chris@16:                               )
Chris@16:   {
Chris@16:     return is_kuratowski_subgraph(g, begin, end, get(vertex_index,g));
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:   
Chris@16: }
Chris@16: 
Chris@16: #endif //__IS_KURATOWSKI_SUBGRAPH_HPP__