c++ - BGL : Example of isomorphism with vertex invariants

Question

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

以下是更多细节:

我在顶点上定义了一组离散属性，以便我可以用整数标记每个顶点。所以我有一个从任何顶点(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

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

使用您的 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))
         );