boost::graph同构的用法

Question

如何在使用 adjacency_list<vecS, vecS, undirectedS> 时指定 boost::isomorphism_map？

我要完成的内容已标记为 ?????????:

typedef adjacency_list<vecS, vecS, undirectedS> graph_t;
      graph_t g1(n), g2(n);

      add_edge(0, 1, g1); add_edge(1, 2, g1); 

      add_edge(9, 10, g2);  add_edge(10, 11, g2);  

      std::vector<graph_traits<graph_t>::vertex_descriptor> f(n);

      bool ret = isomorphism
        (g1, g2, isomorphism_map
         (make_iterator_property_map(f.begin(), ?????????, f[0])));

Answer 1

要创建迭代器属性-map，您需要两个参数：

make_iterator_property_map( RAIter iter, ID id )

放弃你的第三个论点。

第一个：f.begin() 是第一个元素的随机访问迭代器。

ID需要是顶点索引图。在您的情况下，您可以从图中查询它（因为 vecS 导致隐式顶点索引）：

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/isomorphism.hpp>
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> graph_t;

int main() {
    int n = 12;
    graph_t g1(n), g2(n);

    add_edge(0, 1, g1);
    add_edge(1, 2, g1);

    add_edge(9, 10, g2);
    add_edge(10, 11, g2);

    std::vector<graph_t::vertex_descriptor> f(n);

    bool ret = isomorphism(
            g1, g2,
            isomorphism_map(boost::make_iterator_property_map(f.begin(), boost::get(boost::vertex_index, g1)))
        );
}

备注

考虑制作一个安全的迭代器映射：

boost::make_safe_iterator_property_map(f.begin(), n, boost::get(boost::vertex_index, g1))

如果您对安全性不感兴趣 (?!??)，您可以缩短很多时间：

bool ret = isomorphism(g1, g2, boost::isomorphism_map(f.data()));

这会自动使用 vertex_index。

boost::graph同构的用法

Usage of boost::graph isomorphism

c++

c++11

boost

graph

isomorphism

备注