Boost.Graph库:如何对命名顶点使用boost::is_isomorphism

Question

这个问题类似于BGL:顶点不变量同构的例子

我正在处理一个Boost.Graph教程，在两个没有属性的图上调用boost::is_isomorphism很容易。但是当顶点现在有名字的时候我就不能让它工作了。

此代码显示：

• 如何创建具有命名顶点的路径图(不重要)
• 我的测试代码
• 用命名顶点测试同构的函数

下面是我如何使用命名顶点创建路径图(这并不重要，但要完成)：

boost::adjacency_list<
  boost::vecS,
  boost::vecS,
  boost::undirectedS,
  boost::property<
    boost::vertex_name_t, std::string
  >
>
create_named_vertices_path_graph(
  const std::vector<std::string>& names
) noexcept
{
  auto g = create_empty_undirected_named_vertices_graph();
  if (names.size() == 0) { return g; }

  auto vertex_name_map
    = get( //not boost::get
      boost::vertex_name,
      g
    );

  auto vd_1 = boost::add_vertex(g);
  vertex_name_map[vd_1] = *names.begin();
  if (names.size() == 1) return g;

  const auto j = std::end(names);
  auto i = std::begin(names);
  for (++i; i!=j; ++i) //Skip first
  {
    auto vd_2 = boost::add_vertex(g);
    vertex_name_map[vd_2] = *i;
    const auto aer = boost::add_edge(vd_1, vd_2, g);
    assert(aer.second);
    vd_1 = vd_2;
  }
  return g;
}

这是我的测试：

void is_named_vertices_isomorphic_demo() noexcept
{
  const auto g = create_named_vertices_path_graph(
    { "Alpha", "Beta", "Gamma" }
  );
  const auto h = create_named_vertices_path_graph(
    { "Alpha", "Gamma", "Beta" }
  );
  assert( is_named_vertices_isomorphic(g,g));
  assert(!is_named_vertices_isomorphic(g,h));
}

我想或多或少地将函数is_named_vertices_isomorphic写成这样(注意:这将编译，但测试失败，这是BGL:顶点不变量同构的例子的启发)：

template <typename graph1, typename graph2>
bool is_named_vertices_isomorphic_correct(
  const graph1& g,
  const graph2& h
) noexcept
{
  auto ref_index_map = get(boost::vertex_index, g);
  using vd = typename boost::graph_traits<graph1>::vertex_descriptor;
  std::vector<vd> iso(boost::num_vertices(g));
  return boost::isomorphism(g,h,
    boost::isomorphism_map(
      make_iterator_property_map(iso.begin(), ref_index_map, iso[0])
    )
  );
}

看看BGL:顶点不变量同构的例子让我想出的问题：

template <typename Graph>
std::string discrete_vertex_invariant(
  const typename boost::graph_traits<Graph>::vertex_descriptor& vd,
  const Graph &g
)
{
  const auto name_map = get(boost::vertex_name,g);
  return name_map[vd];
}

template <typename Graph>
class discrete_vertex_invariant_functor
{
    using vertex_t = typename boost::graph_traits<Graph>::vertex_descriptor;
    const Graph& m_graph;
public:
    using result_type = std::string;
    using argument_type = vertex_t;
    discrete_vertex_invariant_functor(const Graph &g) : m_graph(g) {}
    result_type operator()(const vertex_t& vd) const
    {
        return discrete_vertex_invariant(vd,m_graph);
    }
    result_type max() const
    {
        return "";
    }
};

//helper function to help with argument deduction
template <typename Graph>
discrete_vertex_invariant_functor<Graph> make_discrete_vertex_invariant(
  const Graph &g
)
{
  return discrete_vertex_invariant_functor<Graph>(g);
}

template <typename graph1, typename graph2>
bool is_named_vertices_isomorphic_correct(
  const graph1& g,
  const graph2& h
) noexcept
{
  auto ref_index_map = get(boost::vertex_index, g);
  using vd = typename boost::graph_traits<graph1>::vertex_descriptor;
  std::vector<vd> iso(boost::num_vertices(g));
  return boost::isomorphism(
    g,
    h,
    isomorphism_map(
      make_iterator_property_map(iso.begin(), ref_index_map, iso[0])
    ).vertex_invariant1(make_discrete_vertex_invariant(g))
     .vertex_invariant2(make_discrete_vertex_invariant(h))
  );
}

这两种解决方案都失败了。谁能帮我？

Answer 1

函数，没有named_vertex_invariant类：

#include "named_vertex_invariant.h"

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

template <typename graph>
bool is_named_vertices_isomorphic(
  const graph &g,
  const graph &h
) noexcept {
  using vd = typename boost::graph_traits<graph>::vertex_descriptor;

  auto vertex_index_map = get(boost::vertex_index, g);
  std::vector<vd> iso(boost::num_vertices(g));

  typename named_vertex_invariant<graph>::str_to_int_map shared_names;
  named_vertex_invariant<graph> inv1{g, shared_names};
  named_vertex_invariant<graph> inv2{h, shared_names};
  inv1.collect_names();
  inv2.collect_names();

  return boost::isomorphism(g, h,
    boost::isomorphism_map(
      make_iterator_property_map(
        iso.begin(),
        vertex_index_map
      )
    )
    .vertex_invariant1(inv1)
    .vertex_invariant2(inv2)
  );
}

named_vertex_invariant类：

#include <map>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/isomorphism.hpp>

template <class graph>
struct named_vertex_invariant {
  using str_to_int_map = std::map<std::string, size_t>;
  using result_type = size_t;
  using argument_type
    = typename boost::graph_traits<graph>::vertex_descriptor;

  const graph& m_graph;
  str_to_int_map& m_mappings;

  size_t operator()(argument_type u) const {
      return m_mappings.at(boost::get(boost::vertex_name, m_graph, u));
  }
  size_t max() const noexcept { return m_mappings.size(); }

  void collect_names() noexcept {
    for (auto vd : boost::make_iterator_range(boost::vertices(m_graph))) {
      size_t next_id = m_mappings.size();
      auto ins = m_mappings.insert(
        { boost::get(boost::vertex_name, m_graph, vd), next_id}
      );
      if (ins.second) {
      //  std::cout << "Mapped '" << ins.first->first << "' to " << ins.first->second << "\n";
      }
    }
  }
};