BGL:具有顶点不变量的同构示例

Question

有没有人可以给我展示一个如何使用Boost Graph Library同构函数和顶点不变量的例子？我正在查看使用degree_vertex_invariant()的http://www.boost.org/doc/libs/1_50_0/libs/graph/example/isomorphism.cpp示例。然而，我想定义我自己的不变函数，一个例子将真正帮助我理解如何做到这一点。

以下是更多细节：

我在顶点上定义了一组离散属性，这样我就可以用整数标记每个顶点。所以我有一个从任何顶点(g，v)到它的不变标签的映射，这是一个无符号整数。这些标签不一定是唯一的，即同一图中的几个顶点可以共享相同的标签。假设我定义了一个函数：

template <typename Graph>
unsigned discrete_vertex_invariant(const typename boost::graph_traits<Graph>::vertex_descriptor &v, const Graph &g)

我想这样调用同构：

typename property_map<Graph, vertex_index_t>::type
      v1_index_map = get(vertex_index, g1),
      v2_index_map = get(vertex_index, g2);
vector<typename graph_traits<Graph>::vertex_descriptor> f(num_vertices(g1));

bool is_isomorphic = isomorphism(g1, g2,
   isomorphism_map(make_iterator_property_map(f.begin(), v1_index_map, f[0])),
   discrete_vertex_invariant, discrete_vertex_invariant
)) 

..。但我得到一个错误：

no matching function for call to ‘isomorphism(
...
 <unresolved overloaded function type>, <unresolved overloaded function type>)’

定义discrete_vertex_invariant()的正确方式是什么？

Answer 1

您可以在degree_vertex_invariant的定义中找到here。它只是一个带有result_type和argument_type类型定义的函数对象，预计会被图的每个顶点调用，并且还有一个名为max的成员，该成员返回的整数等于不变量的最大值加1。

使用您的discrete_vertex_invariant函数的类似函数器将如下所示：

template <typename Graph>
class discrete_vertex_invariant_functor
{
    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
    const Graph &graph;
public:
    typedef unsigned int result_type;
    typedef vertex_t argument_type;
    discrete_vertex_invariant_functor(const Graph &g):graph(g){}
    result_type operator()(argument_type v)const
    {
        return discrete_vertex_invariant(v,graph);
    }
    result_type max()
    {
        return MAX_LABEL+1;
    }
};

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

然后，您可以使用其命名参数版本调用isomorphism：

bool ret=isomorphism(g1, g2, 
            isomorphism_map(make_iterator_property_map(f.begin(), v1_index_map, f[0]))
            .vertex_invariant1(make_discrete_vertex_invariant(g1))
            .vertex_invariant2(make_discrete_vertex_invariant(g2))
         );