VertexList与vecS不同的adjacency_list [英] adjacency_list with VertexList different from vecS

问题描述

我有两个包含一些字段的结构：struct MyNodeData和struct MyEdgeData。当我创建一个VertexList为vecS的图时，访问顶点描述符是没有问题的。例如：

  typedef adjacency_list< setS，vecS，undirectedS，MyNodeData，MyEdgeData>图形; 
 
 typedef Graph :: vertex_descriptor MyNodeDataID; 
 typedef Graph :: edge_descriptor MyEdgeDataID; 
 typedef graph_traits<图表> :: vertex_iterator VertexIterator; 
 typedef graph_traits<图表> :: edge_iterator EdgeIterator; 
 typedef graph_traits<图表> :: adjacency_iterator AdjacencyIterator; 
 typedef property_map< Graph，vertex_index_t> :: type IndexMap; 
 
图形g; 
 const IndexMap index = get（vertex_index，g）; 
 
 / * Puisaprèsavoirajoutédes vertex et edges，je peuxaccéderpar exempleàla liste des vertex comme suite：* / 
 pair< VertexIterator，VertexIterator>六; （vi =顶点（g）; vi.first！= vi.second; ++ vi.first）
 {
 cout< 顶点：<< index [* vi.first]<< ENDL; 
 //或：cout<< 顶点：<< * vi.first<< ENDL; 
} 
  

但我通常需要从图形中添加/删除边和顶点。所以我想使用setS或listS作为VertexList而不是vecS，因为使用vecS时，当我们删除其中的一个时，索引无效！
问题是，如果我将VertexList定义为setS或listS，那么我不能浏览顶点/边的列表，并像我以前那样访问描述符！

为了简短起见，我的问题是：由于使用listS或setS作为顶点容器的adjacency_list不会自动提供此vertex_id属性，所以我如何将它添加到上面的代码中？

 < ...> 
 typedef Graph :: vertex_descriptor NodeID; 
 
 typedef map< NodeID，size_t> IndexMap; 
 IndexMap mapIndex; 
 associative_property_map< IndexMap> propmapIndex（mapIndex）; 
< ...> 
 
 //索引所有顶点
 int i = 0; 
 BGL_FORALL_VERTICES（v，g，Graph）
 {
 put（propmapIndex，v，i ++）; 
} 
  

I have two structs containing some fields: struct MyNodeData, and struct MyEdgeData. When I create a graph with VertexList as vecS, there is no problem to access the descriptor of vertices etc. For example:

typedef adjacency_list<setS, vecS, undirectedS, MyNodeData, MyEdgeData> Graph;

typedef Graph::vertex_descriptor MyNodeDataID;
typedef Graph::edge_descriptor MyEdgeDataID;
typedef graph_traits < Graph >::vertex_iterator VertexIterator;
typedef graph_traits < Graph >::edge_iterator EdgeIterator;
typedef graph_traits < Graph >::adjacency_iterator AdjacencyIterator;
typedef property_map < Graph, vertex_index_t >::type IndexMap;

Graph g;
const IndexMap index = get(vertex_index, g);

/* Puis après avoir ajouté des vertex et edges, je peux accéder par exemple à la liste des vertex comme suite: */
pair<VertexIterator, VertexIterator> vi;
for(vi = vertices(g); vi.first != vi.second; ++vi.first)
{
   cout << "vertex: " << index[*vi.first] << endl;
   // or: cout << "vertex: " << *vi.first << endl;
}

But I usually need to add/delete edges and vertices from my graph. So I want to use setS or listS as a VertexList, instead of vecS, since with vecS the indexes are invalidated when we delete one of them ! The problem is that if I define VertexList as setS or listS, I can not browse the list of vertices/edges and access there descriptors like I did before !

To make it short, my question is: Since an adjacency_list that uses listS or setS as the vertex container does not automatically provide this vertex_id property, how can I add it to the code above ?

解决方案

Currently, you just need to provide an associative property map.

<...>
typedef Graph::vertex_descriptor NodeID;

typedef map<NodeID, size_t> IndexMap;
IndexMap mapIndex;
associative_property_map<IndexMap> propmapIndex(mapIndex);
<...>

// indexing all vertices
int i=0;
BGL_FORALL_VERTICES(v, g, Graph)
{
   put(propmapIndex, v, i++);
}

这篇关于VertexList与vecS不同的adjacency_list的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！