与 boost 图形库中的 std::vector 相关的外部属性映射

Question

我目前正在尝试定义增强图的外部属性。我使用一些捆绑属性作为内部属性：

struct VertexProperties
{
  int demand;
};

struct EdgeProperties
{ 
  uint capacity;
  int cost;
};

typedef adjacency_list <vecS, vecS, bidirectionalS, VertexProperties, EdgeProperties> Graph;

但是，在算法过程中，我需要一些外部属性，也就是说，我希望能够将图形的边/顶点映射到存储在 std::vector 中的元素，这样我就可以可以通过操作符[]（Edge e）访问它们。我站在 boost 文档前面，毫无头绪。看来我需要一个 property_map，但我不知道如何将它们与向量一起使用。到目前为止，我发现的唯一示例涉及从顶点到向量的映射，但由于顶点是无符号整数，因此这是微不足道的。

到目前为止，我对 boost 感到非常沮丧，我认为它会节省我很多时间来自己实现和测试图形类，我真的不明白这种疯狂的模板元编程的东西......

Answer 1

无论图表中有哪些内部和/或捆绑属性，您都可以创建外部属性映射。在边缘上创建属性映射有些困难，因为您需要一个 edge_index 映射，而 adjacency_list 默认情况下没有这些映射； compressed_sparse_row_graph 确实如此，但其结构在构造后大多是只读的。您可以在边缘上使用associative_property_map，或者创建边缘索引图作为内部属性（如果您不经常更改图形），填充它，然后使用它来构建外部属性映射（例如，使用shared_array_property_map）。

Answer 2

我最近遇到了同样的问题，以下是我最终附加顶点属性的方法（在此代码片段中称为度）：

// Graph has to have _index_ property (vector-based graphs get it implicitly)
typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
// Storage type for the _degree_ property
typedef std::vector<uint> DegreeVector;
// Type of the _degree_ property map
typedef iterator_property_map<typename DegreeVector::iterator, IndexMap> DegreeMap;

// Graph in question
Graph g(5);
// Actual storage
DegreeVector degree_storage(num_vertices(g));
// This is needed to construct _degree_ property map
IndexMap index_map = get(vertex_index, g);
// Create _degree_ property map
DegreeMap degree_map = make_iterator_property_map(degree_storage.begin(), index_map);

// Now degree_map is ready to be used
degree_map[some_vertex_id] = 10;