BGL : edge_descriptors 및 vertex_descriptors를 효율적으로 저장하려면 어떻게해야합니까?

Question

BGL에 대한 순환 종속성 문제가 해결 된 후에 다른 장애물이 있습니다.

현재 그래프를 만들려면 인접 목록을 사용하고 있습니다. 그래프에 일부 정보를 저장하기 위해 노드와 가장자리 모두에 대한 번들 된 특성이 적용됩니다. 내가 (예를 들어, 여러 차선이있는 도로에 대한) 내 코드에서 특정 노드와 다른 곳 가장자리에 바로 가기를 저장할 때

class Node { 
    int x, int y // position 
}; 
class Edge { 
    float length; 
}; 

boost::adjacency_list<boost::listS, boost::listS, boost::directedS, Node, Edge> 

문제가 발생 : 그래서 이런 식으로 뭔가가있다. 내 첫 번째 접근 방식은 내가 필요한 곳에서 edge_descriptors와 vertex_descriptors를 저장하는 것이었다. 그러나 나는 (바이트의 관점에서) 얼마나 많은 디스크립터가 될지 궁금해하고있다. 어쩌면 정보의 일부만 저장하여 동일한 결과를 얻는 것과 같은 더 나은 솔루션이있을 수 있습니다.

는 사람이이 유형의 벡터에 사용되는 메모리의 양을 알고 있습니까 :

std::vector<edge_descriptor> ? 

은 이미 단지 edge_descriptors에 대한 포인터를 저장하는 생각을하지만 그 일을한다면 어떻게 모르겠어요.

///////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////// /////////////////////

편집 : 이제 내 첫 번째 질문에 답을 얻었으니 한 가지 궁금한 점이 있습니다. 내 그래프 클래스에 대한 인터페이스를 구축하고 싶습니다. 이 인터페이스는, 그래프의 상세를 인식 할 수없는 다른 클래스로부터 그래프 클래스의 상세를 분리 할 필요가 있습니다. 따라서 다른 클래스는 노드와 모서리를 숫자로 인식하는 것이 바람직합니다. 내가 다시 다음 내 그래프 객체에 대한 지표로 사용되는 설명에 숫자를 번역 할 수하는 hash_map std::tr1::unordered_map<int, edge_descriptor>를 사용

1. : 그래서 나는이 개 아이디어를 내놓았다. 한 단계가 될 수 있습니다. 계산할 노드와 모서리가 충분하면 해시 값 계산에 많은 시간이 걸릴 수 있습니다. 그래서 두 번째 아이디어가 있습니다.
2. 그래프 자체는이 수를 내부적으로 가장자리와 노드로 변환합니다. 속성 맵과 함께 내부 속성을 사용하여 내 아이디어를 실현할 수 있음을 알고 있습니다. 당신은 단지 같은 것을 입력하여 노드에 액세스 할 수 있습니다
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

하지만 내 번들 속성과 같은 속성지도를 결합하는 방법이 있나요?

또는 내가 아직 공격하지 않은 다른 아이디어가 있습니까?

Answer 1

꼭지점 및 가장자리 설명자는 매우 작은 크기입니다.

꼭지점 설명자는 숫자입니다. 에지 디스크립터는 소스 및 타겟 정점 디스크립터를 포함하는 작은 구조이며 에지 디스크립터에 첨부 된 내부 데이터에 대한 포인터입니다.

따라서 질문에 대한 대답은 벡터로 사용할 수 있다는 것입니다. 그것은 기억 문제를 구성하지 않습니다.