2

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

struct VertexProperties
{
  int demand;
};

struct EdgeProperties
{ 
  uint capacity;
  int cost;
};

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

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

到目前为止，我对 boost 感到非常沮丧，我认为它可以为我节省大量时间来实现和测试一个图形类，我真的没有得到这个疯狂的模板元编程的东西......

4

2 回答 2

5

You can create external property maps regardless of what internal and/or bundled properties are in your graph. Creating property maps on edges is somewhat more difficult because you need an edge_index map, and adjacency_list doesn't have those by default; compressed_sparse_row_graph does but its structure is mostly read-only after construction. You can either use associative_property_map on the edges, or create an edge index map as an internal property (if you don't change your graph too often), fill it, then use it to build the external property map (using shared_array_property_map, for example).

于 2011-11-24T23:29:18.803 回答
1

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

// 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;
于 2013-10-19T17:21:24.187 回答