BGL：使用捆绑的属性来存储另一个顶点的顶点描述符 [英] BGL: Using bundled properties to store vertex descriptor of another vertex

问题描述

我试图使用 boost :: adjacency list 创建一个树图，并绑定属性存储每个顶点的父，我想存储顶点描述符的方式如果我删除一个顶点，它们不会无效，所以我使用 boost :: listS ，代码应该看起来像这样

  //树图的自定义顶点
 struct tree_vertex_info {
 //父顶点的描述符
 boost :: graph_traits< Tree> :: vertex_descriptor parent_in_tree; 
}; 
 //树图类型
 typedef boost :: adjacency_list& boost :: listS，boost :: listS，boost :: directedS 
 tree_vertex_info，boost :: no_property，graph_info>树; 
  

但这不会工作，因为Tree必须在结构定义之后定义。有没有其他方法来做捆绑属性？我想我可以使用int变量而不是vertex_descriptor类型来存储vertex_descriptors，但是因为我使用 boost :: listS 来存储它们我不知道是否可以。

理论上，你可以这样：

 <$> 
 c $ c> struct tree_vertex_info; // forward-declaration 
 
 typedef boost :: adjacency_list< 
 boost :: listS，boost :: listS，boost :: directedS，
 tree_vertex_info，boost :: no_property，graph_info>树; 
 
 struct tree_vertex_info {
 boost :: graph_traits< Tree> :: vertex_descriptor parent_in_tree; 
};但是，这将需要 boost :: adjacency_list  c>类模板来支持不完整类型（这是 tree_vertex_info 是只有一个向前声明，直到编译器达到完整的声明的）。据我所知， boost :: adjacency_list 类不支持不完整的类型（我知道实现相当多，我不认为它会工作） 
 
 
 
我实际上正在开发一个新版本的 boost :: adjacency_list 其中我调用 boost :: adjacency_list_BC ，因为它基于Boost.Container容器，并且它将支持不完全类型。但是，它仍处于测试阶段（请按此处或此处），Boost.Container的最新版本似乎有破碎的东西，我仍然需要弄清楚。顺便说一句，我还有一些BGL树数据结构以及新的BGL概念和树的性状（因为你似乎正在实现一种树）。
 
 
 
另外，如果你的动机真的是你在那里（父在树），那么你应该使用 boost :: bidirectionalS 你的 adjacency_list 能够从一个子顶点到它的父代（这就是 boost :: bidirectionalS 获取双向图）。
 
 
 
最后，要真正解决这种情况，你必须使用类型擦除技术。一个简单的现成方法是使用 boost :: any 删除vertex_descriptor的类型，如下所示：
  struct tree_vertex_info {
 //父顶点描述符
 boost :: any parent_in_tree; 
}; 
 
 //树图类型
 typedef boost :: adjacency_list& boost :: listS，boost :: listS，boost :: directedS 
 tree_vertex_info，boost :: no_property，graph_info> ;树; 
  
只需查找 Boost.Any 了解如何使用它。
 
 
我想我可以使用int变量而不是vertex_descriptor类型来存储vertex_descriptors，但由于我使用listS来存储它们，我不知道是否可以。
 
 
不，你不能。你不能依赖于vertex_descriptor类型是什么特别的（例如，你不能假设它是一个整数类型，更不用说int）。我偶然知道vertex_descriptor通常是一个迭代器类型（例如 std :: list< T> :: iterator ）或者一个大小类型（如 std :: size_t 或 std :: vector< T> :: size_type ），但这是一个实现细节，你不应该，依靠。
 
I am trying to create a tree graph using boost::adjacency list and bundled properties to store the parent for every vertex, I want to store vertex descriptors in a way that they wont invalidate in case I remove a vertex, so I use boost::listS, the code should look something like this
// 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;
But this would not work since Tree must be defined after the struct definition. Is there any other way to do it with bundled properties? I thought I could use an int variable instead of vertex_descriptor type to store vertex_descriptors but since I use boost::listS to store them I am not sure if can.
解决方案
Theoretically, you could have something like this:
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;
};
However, this would require the boost::adjacency_list class template to support incomplete types (which is what tree_vertex_info is while there is only a forward-declaration, until the compiler reaches the complete declaration of it). As far as I know, the boost::adjacency_list class does not support incomplete types (and I know that implementation quite a bit, and I don't think it would work) and it is certainly not guaranteed to support them.

I am actually working on a new version of boost::adjacency_list which I call boost::adjacency_list_BC because it's based on Boost.Container containers, and it will support incomplete types. However, it is still kind at a beta stage (follow here or here), and the latest versions of Boost.Container seem to have broken something that I still need to figure out. By the way, I also have a number of BGL tree data-structures as well as new BGL concepts and traits for trees (since you seem to be implementing a kind of tree).

Also, if your motivation for this is really what you have there (the "parent-in-tree"), then you should be using boost::bidirectionalS in your adjacency_list to be able to get from a child vertex to its parent (that's what boost::bidirectionalS means, you get a BidirectionalGraph).

Finally, to actually solve this situation you are in, you'll have to use a type-erasure technique. A simple off-the-shelf way to do it is to use boost::any to erase the type of the vertex_descriptor, like so:
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;
Just look up Boost.Any for instructions on using it.

  
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.
No, you cannot. You cannot depend on the vertex_descriptor type being anything in particular (e.g., you cannot assume it is an integer type, let alone "int"). I happen to know that vertex_descriptor is usually either an iterator type (such as std::list<T>::iterator) or a size-type (like std::size_t or std::vector<T>::size_type), but that's an implementation detail that you should not and cannot rely on.

                        
这篇关于BGL：使用捆绑的属性来存储另一个顶点的顶点描述符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！