BGL：如何有效地存储edge_descriptors和vertex_descriptors？ [英] BGL: How do I store edge_descriptors and vertex_descriptors efficiently?

问题描述

所以我解决了我的循环依赖问题与BGL解决了我来到另一个障碍。

我目前使用邻接列表来建模我的图。应用节点和边的绑定属性来存储图中的一些信息。所以我有这样的：

  class Node {
 int x，int y // position 
 }; 
 class Edge {
 float length; 
}; 
 
 boost :: adjacency_list& boost :: listS，boost :: listS，boost :: directedS，Node，Edge> 
  

当我想将快捷方式存储到我的代码中某处的特定节点和边对于有几个车道的街道）。我的第一种方法是保存edge_descriptors和vertex_descriptors在我需要它们。但我想知道这样的描述符有多大（以字节为单位）。也许有一个更好的解决方案，如存储只是一小部分的信息，以获得相同的结果。

有人知道用于此类型向量的内存量：

  std :: vector< edge_descriptor> ？ 
  

我已经考虑过只存储指向edge_descriptors的指针，但我不知道是否以及如何工作。

//////////////////////////////////// ////////////////////////////////////////////////// ////////////////////////////////////////////////// ///////////////////////////////

编辑：现在我的第一个问题已经thorougly回答我仍然想知道一件事。我想为我的图类构建一些界面。这个接口应该将图类的细节与其他类分开，这些类不能意识到图的细节。因此，其他类应该优选地将节点和边缘识别为数字。
所以我想出了两个想法：

1. 我使用一个hash_map std :: tr1 :: unordered_map< int，edge_descriptor> 以便能够将数字转换为描述符，这些描述符再次被用作我的图形对象的索引。这可能是一个很大的步骤 - 也许如果有足够的节点和边缘要计算，哈希值的计算将花费太多的时间
   。这就是为什么我有第二个想法。


2. 图本身应该在内部将这些数字转换为边和节点。我知道内部属性和属性映射可以用来实现我的想法。然后你可以通过输入类似的东西来访问一个节点：
   
   boost :: property_map< My_Graph，my_prop> :: type index = get（my_prop（），G）;

但是有没有办法将这些属性映射与我的捆绑属性组合？

$ b

解决方案

顶点和边缘描述符的大小非常小。

顶点描述符是数字。
边描述符是一个小结构，包含源和目标顶点描述符，以及指向附加到边描述符的内部数据的指针。

因此，您的问题的答案是你可以在向量中使用它们。它不会构成内存问题。

So after my circular dependency problem with the BGL was solved I've come to another obstacle.

I'm currently using an adjacency-list to model my graph. Bundled properties for both nodes and edges are applied to store some information in the graph. So I have something like this:

class Node {
    int x, int y // position
};
class Edge {
    float length;
};

boost::adjacency_list<boost::listS, boost::listS, boost::directedS, Node, Edge>

The problem arises when I want to store shortcuts to specific nodes and edges somewhere else in my code (e.g. for a street that has several lanes). My first approach was to save edge_descriptors and vertex_descriptors where I needed them. But I'm wondering how big (in terms of bytes) such descriptors would be. Maybe there is a better solution such as to store just a fraction of information to get the same results.

Does anybody know the amount of memory that is used for a vector of this type:

std::vector<edge_descriptor> ?

I already thought about just storing pointers to edge_descriptors but I don't know if and how that would work.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

EDIT: Now that my first question has been thorougly answered I am still wondering one thing. I want to build some kind of interface for my graph class. This interface shall seperate the graph class details from other classes which must not be aware of the details of the graph. Thus other classes should preferably recognize nodes and edges as numbers. So I came up with two ideas:

1. I use a hash_map std::tr1::unordered_map<int, edge_descriptor> to be able to translate the numbers to descriptors which again are then used as indices to my graph-object. This might be one step to much - maybe the calculation of the hash values will take too much time if there are enough nodes and edges to be calculated. That's why I had a second idea.
2. The graph itself shall internally convert these numbers to edges and nodes. I know that internal properties together with property maps can be used to realize my idea. You can then access a node by just typing something like:
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

But is there a way to combine such property maps with my bundled properties?

Or do you have another idea which I didn't hit on, yet?

解决方案

Vertex and edge descriptors take a very small size.

Vertex descriptors are numbers. Edge descriptors are a small structure containing source and target vertex descriptors, and a pointer to internal data attached to edge descriptors.

Therefore the answer to your question is that you can use them in vectors. It won't constitue a memory issue.

这篇关于BGL：如何有效地存储edge_descriptors和vertex_descriptors？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！