为什么我不能使用 listS 作为 VertexList 模板参数来进行 boost 图的同构测试？

Question

以下程序是根据boost网站提供的例子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 也可以让它工作吗？

Answer 1

vecS 具有隐式顶点索引。

listS 没有。因此它使用内部属性 vertex_index_t 但你没有初始化它。

这是测试 vecS/listS 的所有可能组合的现代化版本 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 模板参数来进行 boost 图的同构测试？

Why can't I use listS for the VertexList template parameter for boost graph's isomorphism test?

c++

boost

isomorphism

boost-graph