BGL：与顶点不变量同构的示例 [英] BGL: Example of isomorphism with vertex invariants

问题描述

有人可以告诉我一个例子，如何使用Boost图表库同构函数与顶点不变量？我正在查看 http：// www .boost.org / doc / libs / 1_50_0 / libs / graph / example / isomorphism.cpp ，它使用degree_vertex_invariant（）。但是，我想定义我自己的不变函数，一个例子真的可以帮助我理解如何做到这一点。

can someone show me an example of how to use the Boost Graph Library isomorphism function with vertex invariants? I'm looking at the example at http://www.boost.org/doc/libs/1_50_0/libs/graph/example/isomorphism.cpp, which uses degree_vertex_invariant(). However, I want to define my own invariant function and an example would really help me to understand how to do this.

这里有一些更多的细节：

Here are some more details:

我在顶点定义一组离散属性，使我可以用一个整数标记每个顶点。所以我有一个从任何顶点（g，v）到其不变标签的映射，这是一个unsigned int。这些标签不一定是唯一的，即同一图中的几个顶点可以共享相同的标签。所以假设我定义了一个函数：

I am defining a set of discrete attributes on vertices such that I can label each vertex with an integer. So I have a mapping from any vertex(g,v) to its invariant label, which is an unsigned int. These labels are not necessarily unique, i.e. several vertices in the same graph can share the same label. So suppose I define a function:

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

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

... but I get an error:

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

定义discrete_vertex_invariant（）的正确方法是什么？

What is the correct way to define discrete_vertex_invariant()?

推荐答案

您可以找到这里定义 degree_vertex_invariant 。它只是一个具有 result_type 和 argument_type 的typedef的函数对象，期望使用并且还有一个成员 max ，它返回一个等于不变量的最大值的整数加一。

You can find here the definition of degree_vertex_invariant. It's simply a function object with typedefs for result_type and argument_type that is expected to be called with each of the vertices of the graph and that also has a member called max that return an integer equal to the max value of your invariants plus one.

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

A similar functor using your discrete_vertex_invariant function would look like this:

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

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

You could then invoke isomorphism using its named-parameter version:

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

这篇关于BGL：与顶点不变量同构的示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！