c++ - BGL : Using bundled properties to store vertex descriptor of another vertex

Question

我正在尝试使用 boost::adjacency list 和捆绑属性创建一个 TreeMap 来存储每个顶点的父级，我想以一种它们不会失效的方式存储顶点描述符以防万一我删除了一个顶点，所以我使用了 boost::listS，代码应该是这样的

// custom vertex for tree graphs
struct tree_vertex_info{
    // descriptor of parent vertex
    boost::graph_traits<Tree>::vertex_descriptor parent_in_tree;
};
// the tree graph type
typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS
        tree_vertex_info, boost::no_property, graph_info> Tree;

但这行不通，因为 Tree 必须在结构定义之后定义。有没有其他方法可以使用捆绑属性来做到这一点？我以为我可以使用 int 变量而不是 vertex_descriptor 类型来存储 vertex_descriptors 但由于我使用 boost::listS 来存储它们我不确定是否可以。

Answer 1

理论上，你可以有这样的东西:

struct tree_vertex_info;  // forward-declaration

typedef boost::adjacency_list<
  boost::listS, boost::listS, boost::directedS, 
  tree_vertex_info, boost::no_property, graph_info> Tree;

struct tree_vertex_info {
  boost::graph_traits<Tree>::vertex_descriptor parent_in_tree;
};

但是，这需要 boost::adjacency_list类模板以支持不完整的类型(这就是 tree_vertex_info 是什么，只有前向声明，直到编译器达到它的完整声明)。据我所知，boost::adjacency_list类不支持不完整的类型(我很了解该实现，但我认为它行不通)并且当然不能保证支持它们。

我实际上正在开发新版本的 boost::adjacency_list我称之为boost::adjacency_list_BC因为它基于 Boost.Container 容器，并且它将支持不完整的类型。然而，它仍然处于测试阶段(遵循 here 或 here )，最新版本的 Boost.Container 似乎破坏了一些我仍然需要弄清楚的东西。顺便说一句，我还有一些 BGL 树数据结构以及新的 BGL 概念和树的特征(因为您似乎正在实现一种树)。

另外，如果你这样做的动机真的是你所拥有的(“树中的 parent ”)，那么你应该使用 boost::bidirectionalS在你的adjacency_list能够从一个子顶点到达它的父顶点(这就是 boost::bidirectionalS 的意思，你得到一个 BidirectionalGraph )。

最后，要真正解决您所处的这种情况，您必须使用类型删除技术。一个简单的现成方法是使用 boost::any删除 vertex_descriptor 的类型，像这样:

struct tree_vertex_info{
  // descriptor of parent vertex
  boost::any parent_in_tree;
};

// the tree graph type
typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS
        tree_vertex_info, boost::no_property, graph_info> Tree;

只需查找Boost.Any获取使用说明。

I thought I could use an int variable instead of vertex_descriptor type to store vertex_descriptors but since I use listS to store them I am not sure if can.

不，你不能。你不能依赖于 vertex_descriptor 类型是任何特定的(例如，你不能假设它是一个整数类型，更不用说“int”了)。我碰巧知道 vertex_descriptor 通常是迭代器类型(例如 std::list<T>::iterator )或大小类型(例如 std::size_t 或 std::vector<T>::size_type )，但这是您不应该也不能依赖的实现细节。