为什么不能将listS用作VertexList模板参数来进行增强图的同构性测试? [英] Why can't I use listS for the VertexList template parameter for boost graph's isomorphism test?

问题描述

以下程序基于boost网站提供的示例

The following program is based on an example provided by the boost website https://www.boost.org/doc/libs/master/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp

#include <boost/graph/vf2_sub_graph_iso.hpp>
using namespace boost;

int main() {
  typedef property<edge_name_t, char> edge_property;
  typedef property<vertex_name_t, char, property<vertex_index_t, int> >
      vertex_property;

  typedef adjacency_list<vecS, listS, bidirectionalS, vertex_property,
                         edge_property>
      graph_type;

  // Build graph1
  graph_type graph1;

  auto v0 = add_vertex(vertex_property('a'), graph1);
  auto v1 = add_vertex(vertex_property('a'), graph1);
  auto v2 = add_vertex(vertex_property('a'), graph1);

  add_edge(v0, v1, edge_property('b'), graph1);
  add_edge(v1, v2, edge_property('b'), graph1);
  add_edge(v0, v2, edge_property('d'), graph1);

  // Build graph2
  graph_type graph2;
  auto w0 = add_vertex(vertex_property('a'), graph2);
  auto w1 = add_vertex(vertex_property('a'), graph2);
  auto w2 = add_vertex(vertex_property('a'), graph2);

  add_edge(w0, w1, edge_property('b'), graph2);
  add_edge(w1, w2, edge_property('b'), graph2);
  add_edge(w0, w2, edge_property('d'), graph2);

  // create predicates
  typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
  typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t>
      vertex_comp_t;
  vertex_comp_t vertex_comp = make_property_map_equivalent(
      get(vertex_name, graph1), get(vertex_name, graph2));

  typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
  typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
  edge_comp_t edge_comp = make_property_map_equivalent(get(edge_name, graph1),
                                                       get(edge_name, graph2));

  // Create callback
  vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);

  vf2_graph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
                edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));

  return 0;
}

回调函数不打印任何内容.但是，如果我将第9行的 listS 更改为 vecS ，则代码可以正常工作.我不明白为什么使用 listS 不能通过同构检查.即使我使用listS，也可以使其正常工作吗?

The callback function doesn't print anything. But if I change listS at line 9 to vecS, the code works fine. I don't understand why using listS fails the isomorphism check. Is it possible to make it work even if I use listS?

推荐答案

vecS 具有隐式顶点索引.

listS 没有.因此，它使用内部属性 vertex_index_t ，但是您没有初始化它.

listS doesn't. Therefore it uses the internal property vertex_index_t but you didn't initialize it.

这里是现代化版本，可以测试针对graph1/graph2的vecS/listS的所有组合:

Here's modernized version that tests all combinations of vecS/listS possible for graph1/graph2:

在编译器资源管理器中实时运行

Live On Compiler Explorer

#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/property_map/property_map.hpp>

template <typename Graph>
void fill_vertex_index(Graph& g) {
    auto idmap = get(boost::vertex_index, g);
    using Prop = boost::property_traits<decltype(idmap)>;

    // only if the property is writable
    if constexpr (std::is_convertible_v<
            typename Prop::category,
            boost::read_write_property_map_tag>)
    {
        std::cout << " - Filling vertex_index\n";
        typename Prop::value_type id = 0; // or just int id = 0; for us
        for (auto v : boost::make_iterator_range(vertices(g)))
            put(idmap, v, id++);
    }
}

template <typename Graph>
Graph create_graph() {
    Graph g;

    auto v0 = add_vertex({'a'}, g);
    auto v1 = add_vertex({'a'}, g);
    auto v2 = add_vertex({'a'}, g);

    fill_vertex_index(g);

    add_edge(v0, v1, {'b'}, g);
    add_edge(v1, v2, {'b'}, g);
    add_edge(v0, v2, {'d'}, g);

    return g;
}

using edge_property   = boost::property<boost::edge_name_t, char>;
using vertex_property = boost::property<boost::vertex_name_t, char, boost::property<boost::vertex_index_t, int> >;

template <typename Selector>
using graph_type = boost::adjacency_list<
    boost::vecS,
    Selector,
    boost::bidirectionalS,
    vertex_property,
    edge_property>;

template <typename Selector1, typename Selector2> void do_test() {
  std::cout << "\n ---" << __PRETTY_FUNCTION__ << " --- \n";
  // Build graphs
  using G1 = graph_type<Selector1>;
  using G2 = graph_type<Selector2>;
  auto graph1 = create_graph<G1>();
  auto graph2 = create_graph<G2>();

  // create predicates
  auto vertex_comp = make_property_map_equivalent(
      get(boost::vertex_name, graph1), get(boost::vertex_name, graph2));

  auto edge_comp = make_property_map_equivalent(
      get(boost::edge_name, graph1), get(boost::edge_name, graph2));

  boost::vf2_print_callback<G1, G2> callback(graph1, graph2);

  vf2_graph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
      edges_equivalent(edge_comp)
      .vertices_equivalent(vertex_comp));
}

int main() {
    do_test<boost::vecS,  boost::vecS>();
    do_test<boost::vecS,  boost::listS>();
    do_test<boost::listS, boost::vecS>();
    do_test<boost::listS, boost::listS>();
}

打印

 ---void do_test() [with Selector1 = boost::vecS; Selector2 = boost::vecS] --- 
(0, 0) (1, 1) (2, 2) 

 ---void do_test() [with Selector1 = boost::vecS; Selector2 = boost::listS] --- 
 - Filling vertex_index
(0, 0) (1, 1) (2, 2) 

 ---void do_test() [with Selector1 = boost::listS; Selector2 = boost::vecS] --- 
 - Filling vertex_index
(0, 0) (1, 1) (2, 2) 

 ---void do_test() [with Selector1 = boost::listS; Selector2 = boost::listS] --- 
 - Filling vertex_index
 - Filling vertex_index
(0, 0) (1, 1) (2, 2) 

这篇关于为什么不能将listS用作VertexList模板参数来进行增强图的同构性测试?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！