vecS와 다른 VertexList가있는 adjacency_list

Question

struct MyNodeData 및 struct MyEdgeData의 두 필드가 포함 된 두 개의 구조체가 있습니다.

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; 
} 

그러나 나는 보통 내 그래프에서 가장자리와 정점을 추가/삭제해야합니다 : 나는 vecS인가로 그러나 VertexList와 그래프를 생성 할 때,이 예를 들어 등 정점의 설명에 액세스 할 수 아무런 문제가 없다. 그래서 vecS 대신에 setS 또는 listS를 VertexList로 사용하고 싶습니다. 왜냐하면 vecS를 사용하여 인덱스 중 하나를 삭제할 때 인덱스가 무효화되기 때문입니다! 문제는 VertexList를 setS 또는 listS로 정의하면 꼭지점/가장자리 목록을 탐색 할 수없고 이전처럼 디스크립터에 액세스 할 수 없다는 것입니다.

간단히 말해서, 제 질문은 listS를 사용하거나 setS를 정점 컨테이너로 사용하는 adjacency_list가 자동으로이 vertex_id 속성을 제공하지 않기 때문에 어떻게 위의 코드에 추가 할 수 있습니까?

Answer 1

현재 연결된 속성 맵을 제공하면됩니다.

<...> 
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++); 
} 

Answer 2

는하지만 일반적으로 내 그래프에서 가장자리와 정점을 추가/삭제해야합니다.

분리 정점과 에지가 vecS에서 가능하다 와리스트를 설정한다. vertex \ edge 디스크립터로 remove_vertex \ remove_edge를 호출하면된다. 위의 모든 컨테이너에서 \ vertex \ edge를 제거하면 반복기가 무효화됩니다. 즉, 그래프를 수정 한 후에 다시 정점 (g)을 호출해야합니다. 대부분의 컨테이너에서 컨테이너를 수정하면 반복기가 무효화됩니다. listS에서 꼭지점을 추가해도 반복기를 무효화 할 수는 없지만 이는 구현에 따라 다르며 신뢰할 수 없습니다.

그래프에 vertex_id 속성을 추가하여 언제든지 버텍스 설명자에 액세스 할 수 있습니다.