2

有人可以向我展示如何将 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() 的正确方法是什么？

4

1 回答 1

2

你可以在这里找到的定义degree_vertex_invariant。它只是一个带有 typedef 的函数对象，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))
         );
于 2012-08-22T14:35:56.790 回答