boost/graph/is_kuratowski_subgraph.hpp

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