Estou procurando uma biblioteca de gráficos dinâmicos paralela em C ++

Olá comunidade scicomp,

Trabalhei na área de algoritmos de grafos usando frameworks como NetworkX (Python), JUNG e YFiles (Java). Agora estou entrando na área da computação paralela e de alto desempenho. Para um novo projeto, estou procurando uma biblioteca de gráficos C ++ com os seguintes recursos:

• possui uma interface intuitiva que permite o desenvolvimento de algoritmos
• suporta operações dinâmicas: por exemplo, inserções e exclusões arbitrárias de nós / arestas
• suporta paralelização: por exemplo, protege o programador de problemas decorrentes de multithreading
• possui pouca sobrecarga de memória e é adequado para computação de alto desempenho

Por favor, sugira algumas bibliotecas e discuta esses critérios, bem como prós e contras.

Biblioteca de Gráficos Boost e LEMON

Como Daniel menciona em sua resposta abrangente , a biblioteca C ++ geral mais completa é a Boost Graph Library . Há uma nova extensão de memória distribuída capaz de executar alguns algoritmos básicos, como pesquisa de largura e profundidade, árvores de abrangência mínima e pesquisa de componentes conectados, mas não estou muito familiarizado com o novo projeto. A Biblioteca de Gráficos Boost em si tem boa reputação e é usada em muitos projetos em todo o mundo.

Se você estiver executando um trabalho básico de gráfico do HPC, poderá começar com a Boost Graph Library, mas lembre-se de que muitos compiladores HPC C ++ têm dificuldade com o Boost (apesar de sua aderência estrita aos padrões do C ++) e pode ser necessário usar um versão mais antiga do Boost ou um compilador não fornecedor, como o GCC, para que ele funcione nos sistemas HPC.

Uma rápida navegação nos repositórios do LEMON mostra que há envolvimento da equipe de supercomputação IBM BlueGene, mas não vejo nenhuma dependência ou configuração para MPI, portanto, provavelmente é apenas uma biblioteca de gráficos seriais no momento.

Balanceamento de carga e (re) particionamento de gráfico dinâmico

Se você estiver interessado no balanceamento de carga e no particionamento dinâmico de gráficos, terá várias outras opções. Talvez a biblioteca mais conhecida seja o ParMETIS , que foi atualizado para a versão 4 no ano passado. O ParMETIS possui uma ponderação baseada em vértices, o que é importante para simulações multi-físicas.

O concorrente europeu do ParMETIS é o PT-Scotch , que teve melhor desempenho para certos tipos de problemas, mas, semelhante ao ParMETIS, não é atualizado com frequência.

Você também pode estar interessado em Zoltan , que faz parte do meta-pacote Sandia National Laboratories Trilinos para computação científica em C ++. O Zoltan possui seus próprios particionadores hierárquicos e interfaces para o ParMETIS e o PT-Scotch.

Graph500

Se você estiver trabalhando no limite da pesquisa simultânea, otimização (caminho mais curto de fonte única) e orientado a margens (conjunto independente máximo), também estará interessado no benchmark Graph500 disponível gratuitamente .

Talvez a Biblioteca de Gráficos Boost seja o que você está procurando. Possui um analisador para ler gráficos especificados no formato DOT do GraphViz. Embora eu realmente não saiba sobre sobrecarga de memória, ela fornece uma variante para paralelização .

Outra biblioteca de gráficos é o LEMON, mas eu realmente não a conheço e se tiver suporte para paralelização, não será anunciado. Seu site causa uma boa impressão;)

Também gostaria de mencionar o STINGER , uma estrutura de dados de gráficos dinâmicos projetada para paralelismo. Segundo o site, ele foi desenvolvido para os seguintes objetivos:

Portabilidade: Algoritmos escritos para STINGER podem ser facilmente traduzidos / portados entre vários idiomas e estruturas

Produtividade: O STINGER deve fornecer uma estrutura de dados abstrata comum, de modo que a grande comunidade de gráficos possa alavancar rapidamente os desenvolvimentos de pesquisa uns dos outros. Isso é semelhante em filosofia ao uso implícito da comunidade de algoritmos numéricos de matrizes esparsas e densas.

Desempenho: Reconhece-se que nenhuma estrutura de dados é ideal para todos os algoritmos de gráficos. O objetivo do STINGER é configurar uma estrutura de dados sensível que possa executar bem a maioria dos algoritmos. Não deve haver redução significativa no desempenho do uso do STINGER quando comparado a outra estrutura geral de dados em um amplo conjunto de algoritmos gráficos típicos. STINGER deve assumir um espaço de endereço de memória compartilhado e permitir algoritmos sequenciais ou paralelos. A estrutura de dados deve permitir que algoritmos paralelos explorem a simultaneidade sempre que possível.

Não é tão genérico quanto o LEMON ou a Boost Graph Library e está em um estágio anterior de desenvolvimento. Se você der uma olhada, eu estaria interessado em seus comentários.