c++ - Boost.Graph 库:如何使用 boost::is_isomorphism 命名顶点

Question

此问题类似于 BGL: Example of isomorphism with vertex invariants

我正在研究 Boost.Graph tutorial在两个没有属性的图上调用 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: Example of isomorphism with vertex invariants):

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: Example of isomorphism with vertex invariants让我想到了这个:

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

看来您并不追求同构，至少严格按照定义是这样。

如果您实际上希望比较图而不考虑顶点索引顺序，但严格比较顶点名称，则必须将名称映射到整数类型(因为 max_vertex_invariant 值应为无符号整数)。

这里有一个简单的实现方法:

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));

    VertexInvariant::Map shared_names;
    VertexInvariant inv1 { g, shared_names };
    VertexInvariant inv2 { h, shared_names };

    inv1.collect_names();
    inv2.collect_names();

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

我还没有让事情变得通用，因为它会分散注意力。

For good form, you'd need to use boost::property_maps::property_traits<boost::property_map<graph1, boost::vertex_name_t>::const_type>::value_type or similar, and check that the resultant type is actually compatible for comparison between graph1 and graph1 etc.

To be "actually" generic you'd want to pass in a deduced property map instead of boost::get(boost::vertex_name, g) and so on.

To be honest, I feel that this doesn't make much sense for such semantic-laden things as the iso-morphism invariants. You can obviously make things as generic as you need them to be for your application.

struct VertexInvariant {
    using Map = std::map<std::string, size_t>;
    Graph const& _graph;
    Map&         _mappings;

    using result_type = size_t;
    using argument_type = Graph::vertex_descriptor;

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

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

helper 在哪里VertexInvariant定义为:

struct VertexInvariant {
    using Map = std::map<std::string, size_t>;
    Graph const& _graph;
    Map&         _mappings;

    using result_type = size_t;
    using argument_type = Graph::vertex_descriptor;

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

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

完整演示

Live On Coliru

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

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                    boost::property<boost::vertex_name_t, std::string> >;

Graph create_empty_undirected_named_vertices_graph() { return {}; }

Graph 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(boost::vertex_name, g); // not boost::get

    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 name_it = std::begin(names);
    for (++name_it; name_it != j; ++name_it) // Skip first
    {
        auto vd_2 = boost::add_vertex(g);
        vertex_name_map[vd_2] = *name_it;
        const auto aer = boost::add_edge(vd_1, vd_2, g);
        assert(aer.second);
        vd_1 = vd_2;
    }
    return g;
}

//////////////////////////////////////// {{{
namespace {

    struct VertexInvariant {
        using Map = std::map<std::string, size_t>;
        Graph const& _graph;
        Map&         _mappings;

        using result_type = size_t;
        using argument_type = Graph::vertex_descriptor;

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

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


}
//////////////////////////////////////// }}}

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));

    VertexInvariant::Map shared_names;
    VertexInvariant inv1 { g, shared_names };
    VertexInvariant inv2 { h, shared_names };

    inv1.collect_names();
    inv2.collect_names();

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

void is_named_vertices_isomorphic_demo() noexcept {
    const auto g = create_named_vertices_path_graph({ "Alpha", "Beta", "Gamma" });
    std::cout << "\n==== g:\n"; boost::print_graph(g, boost::get(boost::vertex_name, g));
    const auto h = create_named_vertices_path_graph({ "Alpha", "Gamma", "Beta" });
    std::cout << "\n==== h:\n"; boost::print_graph(h, boost::get(boost::vertex_name, h));

    assert(is_named_vertices_isomorphic(g, g));
    assert(!is_named_vertices_isomorphic(g, h));
}

int main() { is_named_vertices_isomorphic_demo(); }

打印:

==== g:
Alpha --> Beta 
Beta --> Gamma 
Gamma --> 

==== h:
Alpha --> Gamma 
Gamma --> Beta 
Beta -->