부스트 그래프 라이브러리 메모리 소비 큰 그래프

Question

나는 커다란 그래프 (30k 버텍스, 250m 에지)를 가지고 있고 부스트 그래프 라이브러리 인접리스트 (나는 vecs와리스트를 모두 시도했다)를 사용하면 25gb를 소비한다. 16GB 이상의 RAM을 가진 PC를 구하기가 쉽지 않으므로 메모리 사용을 줄이기 위해 무엇을 권합니까?

Answer 1

저는 작업중인 그래프를 사용하는 검증 기술에 동일한 문제가있었습니다. 엄청난 양의 데이터 (정점 및 가장자리)로 작업하는 경우 직접 만든 미세 조정 된 데이터 구조를 사용해야합니다.

가장자리가 많은 경우에는 인접성 매트릭스 사용을 고려해야합니다. 이 같은 것을 사용할 수 있도록 가장자리, 무게를 가지고 : 가장자리가 속성을 가지고 있지 않은 경우는, 각 에지를 표현하는 하나의 비트를 사용하여 최적화 된 vector<vector<bool> >를 사용할 수

vector<int> vertices; 
vector<vector<int> > edges; 

합니다.

가장자리를 확인하거나 추가 할 때 인접 매트릭스가 빠르지 만 가장자리를 반복하는 것은 좋지 않습니다.

BGL과 내 자신의 그래프에서 동일한 속성을 사용하면 그래프가 훨씬 작다고 말할 수 있습니다.