具有边缘列表的自定义关联容器的BGL edge(u，v，g)

问题描述

我刚刚开始学习bgl，并在使用带有自定义顺序的std :: set作为adjacency_list中的边缘列表的容器时遇到了一个问题.我定义了运算符<根据边缘的属性对边缘进行排序，就像在ordered_out_edges.cpp示例中一样.这里boost :: edge_unique_ordering是一个自定义属性标签.

I've just begun learning bgl and have hit on a problem while using a std::set with a custom ordering as the container for edge lists in an adjacency_list. I define the operator< to order the edges based on their properties, much like in the ordered_out_edges.cpp example. Here boost::edge_unique_ordering is a custom property tag.

template < typename Edge >
struct order_by_unique_order: public std::binary_function< Edge, Edge, bool >
{
    inline bool operator() (const Edge& e1, const Edge& e2) const
    {
        return boost::get(boost::edge_unique_ordering, e1) < boost::get(boost::edge_unique_ordering, e2);
    }
};

struct default_edge_containerS {};

namespace boost
{
    template < class ValueType >
    struct container_gen< default_edge_containerS, ValueType >
    {
        typedef std::set< ValueType, order_by_unique_order< ValueType > > type;
    };
}

通常它可以正常工作，但是当我使用edge(u，v，g)函数时，我遇到了迭代器异常.如果我将这些调用替换为一种变通方法，以避免通过(源，目标)请求边缘，那么一切正常.

In general it is working fine, but I am getting iterator exceptions when I use the edge(u, v, g) function. If I replace these calls with a workaround to avoid requesting edges by (source, target) then everything works fine.

我仔细检查了Boost代码，很确定原因是什么，我只是不确定这是否意味着我做错了什么，这是Boost代码的问题，还是只是没有证明的不兼容性.该函数在u的边缘列表容器上调用set :: find(StoredEdge(v)).现在，默认的stored_edge :: operator<只是比较目标顶点，但就我而言，我的自定义运算符<会被调用，并且正在寻找的StoredEdge(v)显然是默认初始化的，没有任何属性，这大概是问题的原因.在我看来，edge(u，v，g)应该严格基于目标顶点搜索任何匹配项，而不管容器内的边缘受到什么排序.

I looked through the boost code and I'm pretty sure I know what the cause is, I'm just unsure if it means I'm doing something wrong, it's a problem with the boost code, or just an undocumented incompatibility. The function invokes set::find(StoredEdge(v)) on the out edge list container of u. Now the default stored_edge::operator< just compares target vertices, but in my case my custom operator< is being called, and the StoredEdge(v) which is being looked for is obviously default initialized with no properties, which presumably is the cause of the problem. It seems to me that edge(u, v, g) should be searching for any match based strictly on the target vertex, regardless of what ordering is imposed on the edges within the container.

任何人都可以阐明我可能做错了什么或不理解吗?

Can anyone shed some light on what I may be doing wrong or not understanding?

推荐答案

您似乎需要编写一个包装比较运算符，该运算符采用一个类型(将使用StoredEdge类型填充)并比较结果使用自定义比较功能在两个输入上输入get_target)的值，例如:

It looks like you will need to write a wrapper comparison operator that takes a type (which will be filled in using the StoredEdge type) and compares the results of get_target) on the two inputs using your custom compare function, using something like:

template <typename Cmp>
struct target_compare {
  Cmp cmp;
  target_compare(const Cmp& cmp): cmp(cmp) {}
  template <typename SE>
  bool operator()(const SE& a, const SE& b) const {
    return cmp(a.get_target(), b.get_target());
  }
};

然后在set中使用target_compare<order_by_unique_order<Edge> >作为比较类型.

then use target_compare<order_by_unique_order<Edge> > as the comparison type in your set.

这篇关于具有边缘列表的自定义关联容器的BGL edge(u，v，g)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！