안녕하세요 scicomp 커뮤니티,
NetworkX (Python), JUNG 및 YFiles (Java) 와 같은 프레임 워크를 사용하여 그래프 알고리즘 분야에서 일했습니다 . 나는 지금 병렬 및 고성능 컴퓨팅 영역으로 들어가고 있습니다. 새 프로젝트의 경우 다음 기능을 갖춘 C ++ 그래프 라이브러리를 찾고 있습니다.
- 알고리즘 개발을 가능하게하는 직관적 인 인터페이스
- 동적 작업 지원 : 예 : 임의의 노드 / 에지 삽입 및 삭제
- 병렬화 지원 : 예 : 멀티 스레딩으로 발생하는 문제로부터 프로그래머를 보호
- 메모리 오버 헤드가 적고 고성능 컴퓨팅에 적합
일부 도서관을 제안하고 장단점뿐만 아니라 이러한 기준을 논의하십시오.
답변
부스트 그래프 라이브러리 및 LEMON
Daniel이 포괄적 인 답변 에서 언급했듯이 , 모든 기능을 갖춘 일반 C ++ 라이브러리는 Boost Graph Library 입니다. 너비 우선 및 깊이 우선 검색, 최소 스패닝 트리 및 연결된 구성 요소 검색과 같은 일부 기본 알고리즘을 수행 할 수있는 새로운 분산 메모리 확장이 있지만 새 프로젝트에는 익숙하지 않습니다. Boost Graph Library 자체는 평판이 좋으며 전 세계 많은 프로젝트에서 사용됩니다.
기본 HPC 그래프 작업을 수행하는 경우 Boost Graph Library로 시작하고 싶을 수도 있지만 많은 HPC C ++ 컴파일러는 Boost (C ++ 표준을 엄격하게 준수하더라도)에 어려움을 겪을 수 있습니다. HPC 시스템에서 작동하도록하려면 이전 버전의 Boost 또는 GCC와 같은 비 공급 업체 컴파일러
LEMON의 리포지토리를 빠르게 탐색하면 IBM BlueGene 슈퍼 컴퓨팅 팀의 참여가 있지만 MPI에 대한 종속성 또는 구성이 표시되지 않으므로 현재 직렬 그래프 라이브러리 일 가능성이 높습니다.
로드 밸런싱 및 동적 그래프 (재) 파티셔닝
로드 밸런싱 및 동적 그래프 파티셔닝에 관심이있는 경우 몇 가지 옵션이 더 있습니다. 아마도 가장 잘 알려진 라이브러리는 작년에 버전 4로 업데이트 된 ParMETIS 입니다. ParMETIS는 다중 물리 시뮬레이션에 중요한 정점 기반 가중치를 제공합니다.
ParMETIS의 유럽 경쟁 업체는 PT-Scotch 로 특정 유형의 문제에 대해 더 나은 성능을 보였지만 ParMETIS와 유사하게 자주 업데이트되지는 않습니다.
C ++의 과학 컴퓨팅을위한 Sandia National Laboratories Trilinos 메타 패키지의 일부인 Zoltan에 관심이있을 수도 있습니다 . Zoltan은 자체 계층 적 파티 셔 너를 갖추고 있으며 ParMETIS 및 PT-Scotch에 대한 인터페이스를 제공합니다.
그래프 500
동시 검색, 최적화 (단일 소스 최단 경로) 및 엣지 지향 (최대 독립 세트)의 최첨단 작업을하고 있다면 자유롭게 사용할 수있는 Graph500 벤치 마크에 관심이있을 것 입니다.
답변
아마도 Boost Graph Library 가 당신이 찾고 있는 것일 것 입니다. GraphViz의 DOT 형식으로 지정된 그래프를 읽는 파서가 있습니다. 메모리 오버 헤드에 대해서는 잘 모르지만 병렬화를 위한 변형을 제공합니다 .
또 다른 그래프 라이브러리는 LEMON 이지만 실제로는 알지 못하며 병렬화를 지원하는 경우 광고되지 않습니다. 그래도 웹 사이트는 좋은 인상을줍니다.)
답변
병렬 처리를 위해 설계된 동적 그래프 데이터 구조 인 STINGER 도 언급하고 싶습니다 . 웹 사이트에 따르면 다음과 같은 목표를 위해 설계되었습니다.
이식성 : STINGER 용으로 작성된 알고리즘은 여러 언어와 프레임 워크간에 쉽게 번역 / 이동할 수 있습니다.
생산성 : STINGER는 큰 그래프 커뮤니티가 서로의 연구 개발을 빠르게 활용할 수 있도록 공통의 추상 데이터 구조를 제공해야합니다. 이것은 철학적으로 희소 행렬과 밀도 행렬의 암묵적인 사용과 유사하다.
성능 : 모든 그래프 알고리즘에 대해 단일 데이터 구조가 최적 인 것은 아닙니다. STINGER의 목표는 대부분의 알고리즘을 잘 실행할 수있는 합리적인 데이터 구조를 구성하는 것입니다. 광범위한 일반적인 그래프 알고리즘에서 다른 일반 데이터 구조와 비교할 때 STINGER를 사용하면 성능이 크게 저하되지 않아야합니다. STINGER는 공유 메모리 주소 공간을 가정하고 순차적 또는 병렬 알고리즘을 모두 허용해야합니다. 데이터 구조는 병렬 알고리즘이 가능한 경우 동시성을 이용할 수 있도록해야합니다.
LEMON 또는 Boost Graph Library만큼 일반적이지 않으며 초기 개발 단계에 있습니다. 당신이 그것을 확인하면, 나는 당신의 의견에 관심이있을 것입니다.