Qual é a estrutura de dados do gráfico mais eficiente em Python?

votos
63

I precisa de ser capaz de manipular uma grande (10 ^ 7 nós) no gráfico pitão. Os dados correspondentes para cada nó / limite é mínimo, por exemplo, um pequeno número de cadeias de caracteres. O que é o mais eficiente em termos de memória e velocidade , maneira de fazer isso?

A dict de dicts é mais flexível e mais simples de implementar, mas eu intuitivamente esperar uma lista de listas para ser mais rápido. A opção lista também exigiria que eu manter os dados separados da estrutura, enquanto dicts permitiria algo do tipo:

graph[I][J][Property]=value

O que você sugeriria?


Sim, eu deveria ter sido um pouco mais clara sobre o que eu quero dizer com eficiência. Neste caso específico, eu quero dizer isso em termos de recuperação de acesso aleatório.

Carregar os dados para a memória não é um problema enorme. Isso é feito uma vez por todas. A parte demorada é visitar os nós para que eu possa extrair as informações e medir as métricas Estou interessado na.

Eu não tinha considerado tornando cada nó de uma classe (propriedades são as mesmas para todos os nós) mas parece que gostaria de acrescentar uma camada extra de sobrecarga? Eu estava esperando que alguém teria alguma experiência direta com um caso semelhante que pudessem compartilhar. Afinal de contas, os gráficos são uma das abstrações mais comuns no CS.

Publicado 04/08/2008 em 13:00
fonte usuário
Em outras línguas...                            


7 respostas

votos
51

Eu fortemente defender você olhar para NetworkX . É um cavalo de guerra batalha-testado e a primeira ferramenta a maioria dos tipos 'pesquisa' chegar para quando eles precisam fazer análise de dados baseados em rede. Tenho manipulado gráficos com 100s de milhares de bordas sem problema em um notebook. Sua característica rico e muito fácil de usar. Você vai encontrar-se concentrando-se mais sobre o problema na mão, em vez dos detalhes na implementação subjacente.

Exemplo de Erdős-Rényi geração gráfico aleatório e análise


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

Visualizações também são simples:

digite descrição da imagem aqui

Mais de visualização: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Respondeu 26/08/2008 em 18:43
fonte usuário

votos
12

Mesmo que esta questão é agora bastante antigo, acho que vale a pena mencionar o meu próprio módulo python para a manipulação gráfico chamado gráfico-ferramenta . É muito eficiente, uma vez que as estruturas de dados e algoritmos são implementados em C ++, com metaprograming modelo, usando o impulso Graph Library. Portanto o seu desempenho (tanto no uso de memória e tempo de execução) é comparável a uma biblioteca pura C ++, e podem ser ordens de magnitude melhor do que o código python típico, sem sacrificar a facilidade de uso. Eu uso-me constantemente a trabalhar com gráficos muito grandes.

Respondeu 27/11/2010 em 15:10
fonte usuário

votos
6

Como já mencionado, NetworkX é muito bom, com uma outra opção a ser IGRAPH . Ambos os módulos terão a maioria (se não todas) as ferramentas de análise é provável que você precisa, e ambas as bibliotecas são usados rotineiramente com grandes redes.

Respondeu 27/08/2008 em 11:01
fonte usuário

votos
4

Um dicionário pode também conter sobrecarga, de acordo com a aplicação real. A hashtable geralmente contêm algum número primo de nós disponíveis para começar, mesmo que você só pode usar um par de nós.

A julgar pelo seu exemplo, "Propriedade", você estaria melhor com uma abordagem de classe para o nível final e as propriedades reais? Ou é os nomes das propriedades mudando um monte de nó em nó?

Eu diria que o que significa "eficiente" depende de um monte de coisas, como:

  • velocidade de atualizações (insert, update, delete)
  • velocidade de recuperação de acesso aleatório
  • velocidade de recuperação sequencial
  • memória usada

Eu acho que você vai descobrir que uma estrutura de dados que é a vontade rápida, geralmente, consomem mais memória do que aquele que é lento. Isso nem sempre é o caso, mas estruturas maioria dos dados parece seguir este.

Um dicionário pode ser fácil de usar, e dar-lhe acesso relativamente uniforme rápido, ele provavelmente irá usar mais memória do que, como você sugere, listas. Listas, no entanto, geralmente tendem a conter mais sobrecarga quando você inserir dados em que, a menos que preallocate nós X, em que voltará a usar mais memória.

Minha sugestão, em geral, seria apenas para usar o método que parece ser o mais natural para você, e depois fazer um "teste de stress" do sistema, adicionando uma quantidade substancial de dados a ele e ver se ele se torna um problema.

Você também pode considerar a adição de uma camada de abstração para o seu sistema, de modo que você não tem que alterar a interface de programação, se você mais tarde necessidade de mudar a estrutura de dados interno.

Respondeu 04/08/2008 em 13:09
fonte usuário

votos
3

Pelo que entendi, de acesso aleatório é em tempo constante para ambos os dicts e listas do Python, a diferença é que você só pode fazer de acesso aleatório de índices inteiros com listas. Estou assumindo que você precisa procurar um nó por seu rótulo, assim que você quer um dicionário de dicts.

No entanto, em frente ao desempenho, carregá-lo na memória pode não ser um problema, mas se você usar muito, você vai acabar trocando para o disco, que vai matar o desempenho do mesmo dicts altamente eficientes do Python. Tente manter o uso da memória para baixo tanto quanto possível. Além disso, a RAM é incrivelmente barato agora; se você fizer esse tipo de coisa muito, não há nenhuma razão para não ter pelo menos 4GB.

Se você gostaria de conselhos sobre como manter o uso da memória para baixo, dar mais algumas informações sobre o tipo de informação que você está acompanhando para cada nó.

Respondeu 06/08/2008 em 06:37
fonte usuário

votos
2

Fazendo uma estrutura baseada em classes provavelmente teria mais sobrecarga do que a estrutura baseada em dict, já que em classes Python realmente usar dicts quando são implementadas.

Respondeu 04/08/2008 em 13:41
fonte usuário

votos
1

Sem dúvida NetworkX é a melhor estrutura de dados até agora para o gráfico. Ele vem com utilitários como funções auxiliares, estruturas de dados e algoritmos, geradores de sequência aleatória, decoradores, Cuthill-Mckee encomendar, gerentes de contexto

NetworkX é grande porque wowrs para gráficos, dígrafos, e Multigrafo. Pode escrever gráfico com várias maneiras: Lista de Adjacência, Multiline Lista de Adjacência, Lista Edge, GEXF, GML. Ele funciona com salmoura, GraphML, JSON, SparseGraph6 etc.

Tem implimentation de vários algoritmos radimade incluindo: aproximação, Bipartite, Divisa, centralidade, Clique, Clustering, Colorir, Componentes, Conectividade, Ciclos, Directed acíclico Gráficos, medidas de distância, conjunto dominante, Eulerian, isomorfismo, Análise de Ligação, Link Prediction, Matching , Minimum Spanning Tree, rich Club, caminhos mais curtos, Transversal, Árvore.

Respondeu 18/01/2016 em 09:08
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more