부스트 그래프 정점 식별

Question

부스트 그래프의 정점을 부호없는 정수로 매핑해야합니다. 이 사이트의 관련 게시물 (1, 2)에서이를 수행하는 올바른 방법은 맞춤형 정점 클래스를 만드는 것임을 알았습니다.

struct Vertex { uint32_t index; }; 
typedef boost::adjacency_list<boost::vecS, boost::vecS, 
    boost::directedS, Vertex> BoostGraphType;  

typedef BoostGraphType::vertex_descriptor vertex_desc; 

// now i can use 
BoostGraphType g; 

vertex_desc vd = boost::add_vertex(g); 
g[vd].index = magic; 

그러나, 문서 (Iterator and Descriptor Stability/Invalidation)에 따라, 정점 기술자 내가 정점을지도하기 위해 보관해서는 안 즉, 무효가 될 수 있습니다.

내 맞춤형 정점 클래스 + .index가 있으므로 문제가되지 않습니다.

하지만 나중에 특정 인덱스에 대한 vertex_descriptor를 검색하는 방법은 무엇입니까? 선형 검색없이 어떻게 할 수 있습니까?

또는 이러한 정점 버텍스 클래스보다 각 버텍스에 대한 영구 ID를 유지하는 더 좋은 방법이 있습니까?

Answer 1

그래프가 adjacency_list<boost::vecS, boost::vecS, ... 일 때 정점 기술자는 정수입니다. 버텍스를 제거하면 일부 버텍스 설명자가 유효하지 않을 수 있습니다. 마찬가지로 가장자리를 제거하면 일부 가장자리 설명자가 유효하지 않게됩니다. 그래프 요소를 절대로 제거하지 않으면 이러한 정수 설명자가 유효합니다.

BGL 설명서에 "정점 및 가장자리 설명자가 안정적 (무효화되지 않음)을 원하면 adjacency_list의 VertexList 및 OutEdgeList 템플릿 매개 변수에 listS 또는 setS를 사용하십시오."

adjacency_list<boost::listS,...을 사용하는 경우 vertex_index 속성을 생성하고 업데이트해야 할 수 있습니다. 많은 알고리즘이 없으면 작동하지 않습니다. 자세한 내용은 여기를 참조하십시오 https://stackoverflow.com/a/19758844/2876861