ceph/src/boost/libs/graph/test/mcgregor_subgraphs_test.cpp

   1 //=======================================================================
   2 // Copyright 2009 Trustees of Indiana University.
   3 // Authors: Michael Hansen
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #include <cmath>
  11 #include <iostream>
  12 #include <fstream>
  13 #include <sstream>
  14 #include <vector>
  15
  16 #include <boost/lexical_cast.hpp>
  17 #include <boost/random.hpp>
  18 #include <boost/graph/adjacency_list.hpp>
  19 #include <boost/graph/filtered_graph.hpp>
  20 #include <boost/graph/graphviz.hpp>
  21 #include <boost/graph/isomorphism.hpp>
  22 #include <boost/graph/iteration_macros.hpp>
  23 #include <boost/graph/random.hpp>
  24 #include <boost/graph/mcgregor_common_subgraphs.hpp>
  25 #include <boost/property_map/shared_array_property_map.hpp>
  26 #include <boost/test/minimal.hpp>
  27
  28 bool was_common_subgraph_found = false, output_graphs = false;
  29 std::vector<std::string> simple_subgraph_list;
  30
  31 // Callback that compares incoming graphs to the supplied common
  32 // subgraph.
  33 template <typename Graph>
  34 struct test_callback {
  35
  36    test_callback(Graph& common_subgraph,
  37                  const Graph& graph1,
  38                  const Graph& graph2) :
  39     m_graph1(graph1),
  40     m_graph2(graph2),
  41     m_common_subgraph(common_subgraph) { }
  42
  43   template <typename CorrespondenceMapFirstToSecond,
  44             typename CorrespondenceMapSecondToFirst>
  45   bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
  46                   CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
  47                   typename boost::graph_traits<Graph>::vertices_size_type subgraph_size) {
  48
  49     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
  50     typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
  51     typedef std::pair<Edge, bool> EdgeInfo;
  52
  53     typedef typename boost::property_map<Graph, boost::vertex_index_t>::type VertexIndexMap;
  54     typedef typename boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
  55     typedef typename boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;
  56
  57     if (subgraph_size != num_vertices(m_common_subgraph)) {
  58       return (true);
  59     }
  60
  61     // Fill membership maps for both graphs
  62     typedef boost::shared_array_property_map<bool, VertexIndexMap> MembershipMap;
  63
  64     MembershipMap membership_map1(num_vertices(m_graph1),
  65                                   get(boost::vertex_index, m_graph1));
  66
  67     MembershipMap membership_map2(num_vertices(m_graph2),
  68                                   get(boost::vertex_index, m_graph2));
  69
  70     boost::fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2, membership_map1);
  71     boost::fill_membership_map<Graph>(m_graph2, correspondence_map_2_to_1, membership_map2);
  72
  73     // Generate filtered graphs using membership maps
  74     typedef typename boost::membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
  75       MembershipFilteredGraph;
  76
  77     MembershipFilteredGraph subgraph1 =
  78       boost::make_membership_filtered_graph(m_graph1, membership_map1);
  79
  80     MembershipFilteredGraph subgraph2 =
  81       boost::make_membership_filtered_graph(m_graph2, membership_map2);
  82
  83     VertexIndexMap vindex_map1 = get(boost::vertex_index, subgraph1);
  84     VertexIndexMap vindex_map2 = get(boost::vertex_index, subgraph2);
  85
  86     VertexNameMap vname_map_common = get(boost::vertex_name, m_common_subgraph);
  87     VertexNameMap vname_map1 = get(boost::vertex_name, subgraph1);
  88     VertexNameMap vname_map2 = get(boost::vertex_name, subgraph2);
  89
  90     EdgeNameMap ename_map_common = get(boost::edge_name, m_common_subgraph);
  91     EdgeNameMap ename_map1 = get(boost::edge_name, subgraph1);
  92     EdgeNameMap ename_map2 = get(boost::edge_name, subgraph2);
  93
  94     // Verify that subgraph1 matches the supplied common subgraph
  95     BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph) {
  96
  97       Vertex vertex_common = vertex(get(vindex_map1, vertex1), m_common_subgraph);
  98
  99       // Match vertex names
 100       if (get(vname_map_common, vertex_common) != get(vname_map1, vertex1)) {
 101
 102         // Keep looking
 103         return (true);
 104
 105       }
 106
 107       BGL_FORALL_VERTICES_T(vertex1_2, subgraph1, MembershipFilteredGraph) {
 108
 109         Vertex vertex_common2 = vertex(get(vindex_map1, vertex1_2), m_common_subgraph);
 110         EdgeInfo edge_common = edge(vertex_common, vertex_common2, m_common_subgraph);
 111         EdgeInfo edge1 = edge(vertex1, vertex1_2, subgraph1);
 112
 113         if ((edge_common.second != edge1.second) ||
 114             ((edge_common.second && edge1.second) &&
 115              (get(ename_map_common, edge_common.first) != get(ename_map1, edge1.first)))) {
 116
 117           // Keep looking
 118           return (true);
 119
 120         }
 121       }
 122
 123     } // BGL_FORALL_VERTICES_T (subgraph1)
 124
 125     // Verify that subgraph2 matches the supplied common subgraph
 126     BGL_FORALL_VERTICES_T(vertex2, subgraph2, MembershipFilteredGraph) {
 127
 128       Vertex vertex_common = vertex(get(vindex_map2, vertex2), m_common_subgraph);
 129
 130       // Match vertex names
 131       if (get(vname_map_common, vertex_common) != get(vname_map2, vertex2)) {
 132
 133         // Keep looking
 134         return (true);
 135
 136       }
 137
 138       BGL_FORALL_VERTICES_T(vertex2_2, subgraph2, MembershipFilteredGraph) {
 139
 140         Vertex vertex_common2 = vertex(get(vindex_map2, vertex2_2), m_common_subgraph);
 141         EdgeInfo edge_common = edge(vertex_common, vertex_common2, m_common_subgraph);
 142         EdgeInfo edge2 = edge(vertex2, vertex2_2, subgraph2);
 143
 144         if ((edge_common.second != edge2.second) ||
 145             ((edge_common.second && edge2.second) &&
 146              (get(ename_map_common, edge_common.first) != get(ename_map2, edge2.first)))) {
 147
 148           // Keep looking
 149           return (true);
 150
 151         }
 152       }
 153
 154     } // BGL_FORALL_VERTICES_T (subgraph2)
 155
 156     // Check isomorphism just to be thorough
 157     if (verify_isomorphism(subgraph1, subgraph2, correspondence_map_1_to_2)) {
 158
 159       was_common_subgraph_found = true;
 160
 161       if (output_graphs) {
 162
 163         std::fstream file_subgraph("found_common_subgraph.dot", std::fstream::out);
 164         write_graphviz(file_subgraph, subgraph1,
 165                        make_label_writer(get(boost::vertex_name, m_graph1)),
 166                        make_label_writer(get(boost::edge_name, m_graph1)));
 167
 168       }
 169
 170       // Stop iterating
 171       return (false);
 172
 173     }
 174
 175     // Keep looking
 176     return (true);
 177   }
 178
 179 private:
 180   const Graph& m_graph1, m_graph2;
 181   Graph& m_common_subgraph;
 182 };
 183
 184 template <typename Graph>
 185 struct simple_callback {
 186
 187   simple_callback(const Graph& graph1) :
 188     m_graph1(graph1) { }
 189
 190   template <typename CorrespondenceMapFirstToSecond,
 191             typename CorrespondenceMapSecondToFirst>
 192   bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
 193                   CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
 194                   typename boost::graph_traits<Graph>::vertices_size_type /*subgraph_size*/) {
 195
 196     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
 197
 198     std::stringstream subgraph_string;
 199
 200     BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph) {
 201
 202       Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);
 203
 204       if (vertex2 != boost::graph_traits<Graph>::null_vertex()) {
 205         subgraph_string << vertex1 << "," << vertex2 << " ";
 206       }
 207
 208     }
 209
 210     simple_subgraph_list.push_back(subgraph_string.str());
 211
 212     return (true);
 213   }
 214
 215 private:
 216   const Graph& m_graph1;
 217
 218 };
 219
 220 template <typename Graph,
 221           typename RandomNumberGenerator,
 222           typename VertexNameMap,
 223           typename EdgeNameMap>
 224 void add_random_vertices(Graph& graph, RandomNumberGenerator& generator,
 225                          int vertices_to_create, int max_edges_per_vertex,
 226                          VertexNameMap vname_map, EdgeNameMap ename_map) {
 227
 228   typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
 229   typedef std::vector<Vertex> VertexList;
 230
 231   VertexList new_vertices;
 232
 233   for (int v_index = 0; v_index < vertices_to_create; ++v_index) {
 234
 235     Vertex new_vertex = add_vertex(graph);
 236     put(vname_map, new_vertex, generator());
 237     new_vertices.push_back(new_vertex);
 238
 239   }
 240
 241   // Add edges for every new vertex. Care is taken to avoid parallel
 242   // edges.
 243   for (typename VertexList::const_iterator v_iter = new_vertices.begin();
 244        v_iter != new_vertices.end(); ++v_iter) {
 245
 246     Vertex source_vertex = *v_iter;
 247     int edges_for_vertex = (std::min)((int)(generator() % max_edges_per_vertex) + 1,
 248                                       (int)num_vertices(graph));
 249
 250     while (edges_for_vertex > 0) {
 251
 252       Vertex target_vertex = random_vertex(graph, generator);
 253
 254       if (source_vertex == target_vertex) {
 255         continue;
 256       }
 257
 258       BGL_FORALL_OUTEDGES_T(source_vertex, edge, graph, Graph) {
 259         if (target(edge, graph) == target_vertex) {
 260           continue;
 261         }
 262       }
 263
 264       put(ename_map, add_edge(source_vertex, target_vertex, graph).first,
 265           generator());
 266
 267       edges_for_vertex--;
 268     }
 269   }
 270 }
 271
 272 bool has_subgraph_string(std::string set_string) {
 273   return (std::find(simple_subgraph_list.begin(), simple_subgraph_list.end(),
 274                     set_string) != simple_subgraph_list.end());
 275 }
 276
 277 int test_main (int argc, char *argv[]) {
 278   int vertices_to_create = 10;
 279   int max_edges_per_vertex = 2;
 280   std::size_t random_seed = time(0);
 281
 282   if (argc > 1) {
 283     vertices_to_create = boost::lexical_cast<int>(argv[1]);
 284   }
 285
 286   if (argc > 2) {
 287     max_edges_per_vertex = boost::lexical_cast<int>(argv[2]);
 288   }
 289
 290   if (argc > 3) {
 291     output_graphs = boost::lexical_cast<bool>(argv[3]);
 292   }
 293
 294   if (argc > 4) {
 295     random_seed = boost::lexical_cast<std::size_t>(argv[4]);
 296   }
 297
 298   boost::minstd_rand generator(random_seed);
 299
 300   // Using a vecS graph here so that we don't have to mess around with
 301   // a vertex index map; it will be implicit.
 302   typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
 303     boost::property<boost::vertex_name_t, unsigned int,
 304     boost::property<boost::vertex_index_t, unsigned int> >,
 305     boost::property<boost::edge_name_t, unsigned int> > Graph;
 306
 307   typedef boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
 308   typedef boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;
 309
 310   // Generate a random common subgraph and then add random vertices
 311   // and edges to the two parent graphs.
 312   Graph common_subgraph, graph1, graph2;
 313
 314   VertexNameMap vname_map_common = get(boost::vertex_name, common_subgraph);
 315   VertexNameMap vname_map1 = get(boost::vertex_name, graph1);
 316   VertexNameMap vname_map2 = get(boost::vertex_name, graph2);
 317
 318   EdgeNameMap ename_map_common = get(boost::edge_name, common_subgraph);
 319   EdgeNameMap ename_map1 = get(boost::edge_name, graph1);
 320   EdgeNameMap ename_map2 = get(boost::edge_name, graph2);
 321
 322   for (int vindex = 0; vindex < vertices_to_create; ++vindex) {
 323     put(vname_map_common, add_vertex(common_subgraph), generator());
 324   }
 325
 326   BGL_FORALL_VERTICES(source_vertex, common_subgraph, Graph) {
 327
 328     BGL_FORALL_VERTICES(target_vertex, common_subgraph, Graph) {
 329
 330       if (source_vertex != target_vertex) {
 331         put(ename_map_common,
 332             add_edge(source_vertex, target_vertex, common_subgraph).first,
 333             generator());
 334       }
 335     }
 336   }
 337
 338   boost::randomize_property<boost::vertex_name_t>(common_subgraph, generator);
 339   boost::randomize_property<boost::edge_name_t>(common_subgraph, generator);
 340
 341   boost::copy_graph(common_subgraph, graph1);
 342   boost::copy_graph(common_subgraph, graph2);
 343
 344   // Randomly add vertices and edges to graph1 and graph2.
 345   add_random_vertices(graph1, generator, vertices_to_create,
 346                       max_edges_per_vertex, vname_map1, ename_map1);
 347
 348   add_random_vertices(graph2, generator, vertices_to_create,
 349                       max_edges_per_vertex, vname_map2, ename_map2);
 350
 351   if (output_graphs) {
 352
 353     std::fstream file_graph1("graph1.dot", std::fstream::out),
 354       file_graph2("graph2.dot", std::fstream::out),
 355       file_common_subgraph("expected_common_subgraph.dot", std::fstream::out);
 356
 357     write_graphviz(file_graph1, graph1,
 358                    make_label_writer(vname_map1),
 359                    make_label_writer(ename_map1));
 360
 361     write_graphviz(file_graph2, graph2,
 362                    make_label_writer(vname_map2),
 363                    make_label_writer(ename_map2));
 364
 365     write_graphviz(file_common_subgraph, common_subgraph,
 366                    make_label_writer(get(boost::vertex_name, common_subgraph)),
 367                    make_label_writer(get(boost::edge_name, common_subgraph)));
 368
 369   }
 370
 371   std::cout << "Searching for common subgraph of size " <<
 372     num_vertices(common_subgraph) << std::endl;
 373
 374   test_callback<Graph> user_callback(common_subgraph, graph1, graph2);
 375
 376   boost::mcgregor_common_subgraphs(graph1, graph2, true, user_callback,
 377     boost::edges_equivalent(boost::make_property_map_equivalent(ename_map1, ename_map2)).
 378     vertices_equivalent(boost::make_property_map_equivalent(vname_map1, vname_map2)));
 379
 380   BOOST_CHECK(was_common_subgraph_found);
 381
 382   // Test maximum and unique variants on known graphs
 383   Graph graph_simple1, graph_simple2;
 384   simple_callback<Graph> user_callback_simple(graph_simple1);
 385
 386   VertexNameMap vname_map_simple1 = get(boost::vertex_name, graph_simple1);
 387   VertexNameMap vname_map_simple2 = get(boost::vertex_name, graph_simple2);
 388
 389   put(vname_map_simple1, add_vertex(graph_simple1), 1);
 390   put(vname_map_simple1, add_vertex(graph_simple1), 2);
 391   put(vname_map_simple1, add_vertex(graph_simple1), 3);
 392
 393   add_edge(0, 1, graph_simple1);
 394   add_edge(0, 2, graph_simple1);
 395   add_edge(1, 2, graph_simple1);
 396
 397   put(vname_map_simple2, add_vertex(graph_simple2), 1);
 398   put(vname_map_simple2, add_vertex(graph_simple2), 2);
 399   put(vname_map_simple2, add_vertex(graph_simple2), 3);
 400   put(vname_map_simple2, add_vertex(graph_simple2), 4);
 401
 402   add_edge(0, 1, graph_simple2);
 403   add_edge(0, 2, graph_simple2);
 404   add_edge(1, 2, graph_simple2);
 405   add_edge(1, 3, graph_simple2);
 406
 407   // Unique subgraphs
 408   std::cout << "Searching for unique subgraphs" << std::endl;
 409   boost::mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2,
 410     true, user_callback_simple,
 411     boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
 412
 413   BOOST_CHECK(has_subgraph_string("0,0 1,1 "));
 414   BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
 415   BOOST_CHECK(has_subgraph_string("0,0 2,2 "));
 416   BOOST_CHECK(has_subgraph_string("1,1 2,2 "));
 417
 418   if (output_graphs) {
 419     std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
 420               std::ostream_iterator<std::string>(std::cout, "\n"));
 421
 422     std::cout << std::endl;
 423   }
 424
 425   simple_subgraph_list.clear();
 426
 427   // Maximum subgraphs
 428   std::cout << "Searching for maximum subgraphs" << std::endl;
 429   boost::mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2,
 430     true, user_callback_simple,
 431     boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
 432
 433   BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
 434
 435   if (output_graphs) {
 436     std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
 437               std::ostream_iterator<std::string>(std::cout, "\n"));
 438
 439     std::cout << std::endl;
 440   }
 441
 442   simple_subgraph_list.clear();
 443
 444   // Maximum, unique subgraphs
 445   std::cout << "Searching for maximum unique subgraphs" << std::endl;
 446   boost::mcgregor_common_subgraphs_maximum_unique(graph_simple1, graph_simple2,
 447     true, user_callback_simple,
 448     boost::vertices_equivalent(boost::make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
 449
 450   BOOST_CHECK(simple_subgraph_list.size() == 1);
 451   BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
 452
 453   if (output_graphs) {
 454     std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
 455               std::ostream_iterator<std::string>(std::cout, "\n"));
 456
 457     std::cout << std::endl;
 458   }
 459
 460   return 0;
 461 }