BGL adjacency_list：如何使用顶点属性而非描述符对 out_edges 进行排序

Question

使用 BGL adjacency_list，我希望顶点的出边按目标顶点的属性排序。

在 BGL 中，出边列表已经按目标顶点描述符排序，但我恰好使用 listS 作为我的顶点容器，所以我的顶点描述符是 void* 指针。不幸的是，我发现按这些地址排序会使我的图遍历顺序不确定。我的顶点确实有一个自定义的属性 class，它有一个 ID 可用于对出边进行排序，但我无法使其工作。（见下面的代码。）

我参考了这个问题，这对诊断问题很有帮助，但我没有看到很好的解决方案：

未分类的 MWE

这是一个 MWE，没有任何排序尝试。请注意，我以 0、5、2、8 的顺序创建带有 id 的顶点，以模拟顶点地址的顺序与 id 不同。在我的实际应用中，我不能保证这些顶点的地址会遵循 id 排序。

Live On Coliru

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/directed_graph.hpp>

class VertexInfo
{
public:
    VertexInfo(int i) : id(i) {}
    int id;
};

int main()
{
    typedef boost::adjacency_list< boost::setS,
                                   boost::listS,    
                                   boost::bidirectionalS,
                                   VertexInfo,
                                   boost::no_property,
                                   boost::no_property,
                                   boost::listS
                                 > Graph;

    //typedef boost::graph_traits<Graph>::edge_descriptor Edge;
    typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

    Graph g;

    Vertex src  = boost::add_vertex(VertexInfo(0), g);
    Vertex tar1 = boost::add_vertex(VertexInfo(5), g);
    Vertex tar2 = boost::add_vertex(VertexInfo(2), g);
    Vertex tar3 = boost::add_vertex(VertexInfo(8), g);

    boost::add_edge(src, tar1, g);
    boost::add_edge(src, tar2, g);
    boost::add_edge(src, tar3, g);

    // If sorted by address, the order would probably be:
    // 0 --> 5
    // 0 --> 2
    // 0 --> 8
    // If sorted by ID, the order should be:
    // 0 --> 2
    // 0 --> 5
    // 0 --> 8

    typename boost::graph_traits<Graph>::out_edge_iterator ei, ei_end;
    for(boost::tie(ei, ei_end) = boost::out_edges(src, g); ei != ei_end; ++ei)
    {
        std::cout << g[boost::source(*ei, g)].id 
                  << " --> " 
                  << g[boost::target(*ei, g)].id 
                  << std::endl;
    }

    return 0; 
}

目前给我的是：

0 --> 5
0 --> 2
0 --> 8

但我需要它来给我这个：

0 --> 2
0 --> 5
0 --> 8

尝试排序，无效

我查看了 Boost 文档，发现这两部分很有帮助。

BGL 提供了一个示例，说明如何通过创建自定义容器选择器并为该容器使用自定义比较器来对出边 (ordered_out_edges.cpp) 进行排序。不幸的是，示例中的比较器使用目标顶点描述符和边的默认属性来进行比较。我需要一个基于目标顶点的自定义属性进行比较的比较器；无法访问图形对象。
BGL 还展示了如何将 custom vertex property tag 添加到顶点；我曾希望我可以在没有图形对象的情况下从顶点描述符访问一个标记的顶点属性；但这似乎也不起作用

Live On Coliru

#include <iostream>
#include <functional>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/directed_graph.hpp>

// http://www.boost.org/doc/libs/1_55_0/libs/graph/example/ordered_out_edges.cpp
// http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/using_adjacency_list.html#sec:custom-vertex-properties
// 
// http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/adjacency_list.html

// ??
// 

#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
#error BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION not supported
#endif

// See custom-vetex-properties
struct vertex_info_t
{
    typedef boost::vertex_property_tag kind;
};

class VertexInfo
{
public:
    VertexInfo(int i) : id(i) {}
    int id;
};

////////////////////////////////////////
// See libs/graph/example/ordered_out_edges.cpp
template <class StoredEdge>
struct Comparator : public std::binary_function<StoredEdge, StoredEdge, bool>
{
    bool operator()(const StoredEdge& e1, const StoredEdge& e2)
    {
        return boost::get(vertex_info_t(), e1.get_target()).id < boost::get(vertex_info_t(), e2.get_target()).id;
        //return e2.get_target() < e1.get_target(); // reverse order of insertion, an example to prove custom OrderedSetS but does not use vertex properties
    }
};
struct OrderedSetS {};
namespace boost
{
    template <class ValueType>
    struct container_gen<OrderedSetS, ValueType>
    {
        typedef std::set<ValueType, Comparator<ValueType> > type;
    };
    template <>
    struct parallel_edge_traits<OrderedSetS>
    { 
        typedef allow_parallel_edge_tag type;
    };
}
////////////////////////////////////////

int main()
{
    typedef boost::adjacency_list< OrderedSetS, //boost::setS,
                                   boost::listS,    
                                   boost::bidirectionalS,
                                   boost::property<vertex_info_t, VertexInfo>, //VertexInfo,
                                   boost::no_property,
                                   boost::no_property,
                                   boost::listS
                                 > Graph;

    //typedef boost::graph_traits<Graph>::edge_descriptor Edge;
    typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

    Graph g;

    Vertex src  = boost::add_vertex(VertexInfo(0), g);
    Vertex tar1 = boost::add_vertex(VertexInfo(5), g);
    Vertex tar2 = boost::add_vertex(VertexInfo(2), g);
    Vertex tar3 = boost::add_vertex(VertexInfo(8), g);

    boost::add_edge(src, tar1, g);
    boost::add_edge(src, tar2, g);
    boost::add_edge(src, tar3, g);

    // If sorted by address, the order would probably be:
    // 0 --> 5
    // 0 --> 2
    // 0 --> 8
    // If sorted by ID, the order should be:
    // 0 --> 2
    // 0 --> 5
    // 0 --> 8

    typename boost::graph_traits<Graph>::out_edge_iterator ei, ei_end;
    for(boost::tie(ei, ei_end) = boost::out_edges(src, g); ei != ei_end; ++ei)
    {
        std::cout << boost::get( boost::get(vertex_info_t(), g), boost::source(*ei, g) ).id 
                  << " --> " 
                  << boost::get( boost::get(vertex_info_t(), g), boost::target(*ei, g) ).id 
                  << std::endl;
    }

    return 0; 
}

这会导致编译错误

main.cpp:38:26: error: no matching function for call to 'get(vertex_info_t, void*&)'
         return boost::get(vertex_info_t(), e1.get_target()).id < boost::get(vertex_info_t(), e2.get_target()).id;

它不允许我通过 vertex_info_t 标签获得 VertexInfo 属性 class 只有一个顶点描述符 (void*) 而没有图。

问题

谁能想出一种方法来根据目标顶点的外部或内部标记属性对出边进行排序？

Answer 1

In BGL, the out-edge list is already sorted by target vertex descriptor

还没有检查过，但马上我会说这是一个未记录的实现细节，而不是可以依赖的东西（除非你可以指出文档中说明的位置）。

UPDATE 感谢@EvanW 我现在记得我 did 早些时候检查过这个：。因此，给定一个有序的 OutEdgeListS 你可以依赖顶点描述符排序的出边（直到更新版本的 BGL可能会更改实施细节）。

然而，问题当然是 vertex_descriptor 值本身在这里不是确定性的。

BGL also shows how to add a custom vertex property tag to the vertex; I had hoped that I could access a tagged vertex property from the vertex descriptor without having the graph object; but that doesn't seem to work either

确实，您已经指出了问题所在：虽然存储边对象有属性束（这就是使它们束的原因），但顶点是仅由它们的描述符引用（如您所述，它们是不透明的）。

所以唯一的解决方法是以某种方式使图形对象可用。由于 adjacency_list<> 没有提供自定义边缘容器构造方式的方法¹，因此大致有两种方法：

使用全局引用，这当然有不支持多个图形类型实例的缺点。我强烈建议不要这样做，因为它太容易破坏（例如，当您按值传递图形时可能已经存在）并以其他方式限制图形的使用（例如，您将无法使用子图）。
在边缘属性中存储冗余图形参考。这相当浪费，但它确实起到了作用，至少对于这个简单的测试用例而言（请参阅下面的警告）

概念验证

方法 2. 提出了另一个技术障碍，这就是您可以转发声明 Graph 的要求，因此您实际上可以在 EdgeInfo²:

中存储类型化指针

struct ForwardGraph;

struct VertexInfo
{
    VertexInfo(int i) : id(i) {}
    int id;
};

struct EdgeInfo {
    ForwardGraph const* graph;
    EdgeInfo(ForwardGraph const& g) : graph(&g) {}
    //EdgeInfo(EdgeInfo const&) = delete;
    EdgeInfo& operator=(EdgeInfo const&) = delete;
};

现在，稍微间接地定义 ForwardGraph：

typedef boost::adjacency_list<by_idS, boost::listS, boost::bidirectionalS, VertexInfo, EdgeInfo> GraphImpl;

struct ForwardGraph : GraphImpl {
    using GraphImpl::GraphImpl; // inherit constructors
};

关键当然是如何连接by_idS。请注意，我在调试模式下格外小心，因此我们断言 graph 实际上为我们的边缘设置一致 ³。

struct by_idS { };

namespace boost {
    template <class T>
    struct container_gen<by_idS, T> {
        struct cmp {
            bool operator()(const T& e1, const T& e2) const {
                auto const* g1 = get(&EdgeInfo::graph, e1);
                auto const* g2 = get(&EdgeInfo::graph, e2);
                assert(g1 && g2 && g1 == g2);

                auto& g = *g1;
                return g[e1.get_target()].id < g[e2.get_target()].id;
            }
        };

        typedef std::multiset<T, cmp> type;
    };

    template <> struct parallel_edge_traits<by_idS> { typedef allow_parallel_edge_tag type; };
}

CAVEAT: I wouldn't be absolutely convinced that no algorithm of Boost's is going to copy edge properties when graphs are copied. Sadly, prohibiting EdgeInfo's copy constructor breaks the standard add_edge implementation because if doesn't allow move semantics. Again, this lives in a detail namespace, so the only real way to hack it is to contribute changes to BGL

防止忘记为新边添加 EdgeInfo 属性的小帮手（为简洁起见使用 c++14）：

namespace boost {
    auto add_edge(GraphImpl::vertex_descriptor src, GraphImpl::vertex_descriptor tgt, ForwardGraph& g) {
        return add_edge(src, tgt, EdgeInfo { g }, g);
    }
}

我们准备好了：

Live On Coliru

typedef ForwardGraph Graph;

int main() {
    Graph g;

    auto src  = boost::add_vertex({0}, g);
    auto tar1 = boost::add_vertex({5}, g);
    auto tar2 = boost::add_vertex({2}, g);
    auto tar3 = boost::add_vertex({8}, g);

    boost::add_edge(src, tar1, g);
    boost::add_edge(src, tar2, g);
    boost::add_edge(src, tar3, g);

    typename boost::graph_traits<Graph>::out_edge_iterator ei, ei_end;
    for(auto e : boost::make_iterator_range(boost::out_edges(src, g)))
        std::cout << g[boost::source(e, g)].id << " --> " << g[boost::target(e, g)].id << std::endl;
}

版画

0 --> 2
0 --> 5
0 --> 8

¹ 你甚至不能通过在细节命名空间中专门化类型（即 adj_list_gen<>::struct config）来破解它，因为一切都假定 StoredEdges 可以是默认构造的或从 EdgeProperty 对象。无法注入对图形的引用。

² 再次，你不能作弊，因为即使你存储了一个 void const* 也没有办法实际转换为你的边集比较器内部的 Graph 类型，因为......在声明 Graph :)

之前无法知道类型

³ 很容易忘记它，但我们添加了一个自定义构造函数，因此我们不能有默认构造的 EdgeInfos。

BGL adjacency_list：如何使用顶点属性而非描述符对 out_edges 进行排序

BGL adjacency_list: How to sort out_edges using vertex property, not descriptor

c++

boost

boost-graph

未分类的 MWE

尝试排序，无效

问题

概念验证

BGL adjacency_list：如何使用顶点 属性 而非描述符对 out_edges 进行排序

BGL adjacency_list: How to sort out_edges using vertex property, not descriptor

c++

boost

boost-graph

未分类的 MWE

尝试排序，无效

问题

概念验证

BGL adjacency_list：如何使用顶点属性而非描述符对 out_edges 进行排序