使用 BGL adjacency_list，我希望顶点的出边按目标顶点的属性排序。
在 BGL 中，出边列表已经按目标顶点描述符排序，但我碰巧使用 listS 作为我的顶点容器，所以我的顶点描述符是 void* 指针。不幸的是，我发现按这些地址排序会使我的图遍历顺序不确定。我的顶点确实有一个自定义属性类，它有一个可用于对出边进行排序的 ID，但我无法使其工作。 (见下面的代码。)
我已经提到了这个问题，这有助于诊断问题，但我没有看到一个很好的解决方案:boost graph library: deterministic order of iteration of in_edges?
未分类的 MWE
这是一个没有任何排序尝试的 MWE。请注意，我以 0、5、2、8 的顺序创建具有 id 的顶点，以模拟与 id 顺序不同的顶点地址。在我的实际应用中，我不能保证这些顶点的地址将遵循 id 顺序。
#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到顶点；我曾希望我可以在没有图形对象的情况下从顶点描述符访问标记的顶点属性；但这似乎也不起作用
#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
// https://stackoverflow.com/questions/30968690/boost-graph-library-deterministic-order-of-iteration-of-in-edges
// http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/adjacency_list.html
// ??
// https://stackoverflow.com/questions/9169276/bgl-edgeu-v-g-with-custom-associative-container-for-edge-lists
#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;
它不允许我通过只有顶点描述符 (void*) 而没有的 vertex_info_t 标签获取 VertexInfo 属性类图表。
问题
谁能想出一种方法来根据目标顶点的外部或内部标记属性对出边进行排序？
最佳答案
In BGL, the out-edge list is already sorted by target vertex descriptor
还没有检查，但马上我会说无论如何这是一个未记录的实现细节，而不是可以依赖的东西(除非你可以指出文档中说明的位置)。
更新 感谢@EvanW，我现在记得我之前确实检查过这个:boost graph library: deterministic order of iteration of in_edges? .所以，给定一个有序的 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
确实，您已经指出了问题所在:尽管存储边对象的属性 bundle 就在那里(这就是使它们捆绑的原因)，但顶点仅由它们的描述符(不透明的)引用，如您所述)。
所以唯一的解决方法是以某种方式使图形对象可用。自 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 .请注意，我在 Debug模式下格外小心，因此我们断言 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 standardadd_edgeimplementation 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 的小 helper 新边的属性(为简洁起见使用 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);
}
}
我们准备好开始了:
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 )来破解它，因为一切都假定 StoredEdge s 可以是默认构造的，也可以是从 EdgeProperty 构造的目的。无法注入(inject)对图形的引用。
² 再次强调，你不能作弊，因为即使你存储了 void const*将无法实际转换为 Graph在边缘集的比较器中输入类型，因为......在声明 Graph 之前无法知道类型:)
³ 很容易忘记它，但我们添加了一个自定义构造函数，所以我们不能有默认构造的 EdgeInfo就在身边。
关于c++ - BGL adjacency_list : How to sort out_edges using vertex property, 不是描述符，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40963804/