Qual é a estrutura de dados gráficos mais eficiente em Python?[fechado]

Question

Preciso ser capaz de manipular um gráfico grande (10 ^ 7 nós) em python.Os dados correspondentes a cada nó/aresta são mínimos, digamos, um pequeno número de strings.Qual é o mais eficiente, em termos de memória e velocidade, maneira de fazer isso?

Um dict of dicts é mais flexível e simples de implementar, mas intuitivamente espero que uma lista de listas seja mais rápida.A opção list também exigiria que eu mantivesse os dados separados da estrutura, enquanto os dicts permitiriam algo do tipo:

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

O que você sugeriria?

---

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

Carregar os dados na memória não é um grande problema.Isso foi feito de uma vez por todas.A parte demorada é visitar os nós para extrair as informações e medir as métricas que me interessam.

Eu não pensei em transformar cada nó em uma classe (as propriedades são as mesmas para todos os nós), mas parece que isso adicionaria uma camada extra de sobrecarga.Eu esperava que alguém tivesse alguma experiência direta com um caso semelhante que pudesse compartilhar.Afinal, os gráficos são uma das abstrações mais comuns em CS.

Answer 1

Eu recomendaria fortemente que você olhasse RedeX.É um cavalo de guerra testado em batalha e a primeira ferramenta que a maioria dos tipos de “pesquisa” utiliza quando precisam fazer análises de dados baseados em rede.Eu manipulei gráficos com centenas de milhares de arestas sem problemas em um notebook.Seus recursos são ricos e muito fáceis de usar.Você se concentrará mais no problema em questão do que nos detalhes da implementação subjacente.

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

"""
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)

As visualizações também são diretas:

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

Answer 2

Embora esta questão seja bastante antiga, acho que vale a pena mencionar meu próprio módulo python para manipulação de gráficos chamado ferramenta gráfica.É muito eficiente, pois as estruturas de dados e algoritmos são implementados em C++, com metaprogramação de templates, utilizando a Biblioteca Boost Graph.Portanto, seu desempenho (tanto em uso de memória quanto em tempo de execução) é comparável a uma biblioteca C++ pura e pode ser muito melhor do que o código python típico, sem sacrificar a facilidade de uso.Eu mesmo o uso constantemente para trabalhar com gráficos muito grandes.

Answer 3

Como já mencionado, o NetworkX é muito bom, sendo outra opção gráfico.Ambos os módulos terão a maioria (se não todas) das ferramentas de análise que você provavelmente precisará, e ambas as bibliotecas são usadas rotineiramente em grandes redes.

Answer 4

Um dicionário também pode conter sobrecarga, dependendo da implementação real.Uma tabela hash geralmente contém um número primo de nós disponíveis para começar, mesmo que você possa usar apenas alguns nós.

A julgar pelo seu exemplo, "Propriedades", você se sairia melhor com uma abordagem de classe para o nível final e propriedades imobiliárias?Ou os nomes das propriedades mudam muito de nó para nó?

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

• velocidade das atualizações (inserir, atualizar, excluir)
• velocidade de recuperação de acesso aleatório
• velocidade de recuperação sequencial
• memória usada

Acho que você descobrirá que uma estrutura de dados rápida geralmente consumirá mais memória do que uma lenta.Nem sempre é esse o caso, mas a maioria das estruturas de dados parece seguir isso.

Um dicionário pode ser fácil de usar e fornecer acesso rápido e relativamente uniforme; provavelmente usará mais memória do que, como você sugere, listas.As listas, no entanto, geralmente tendem a conter mais sobrecarga quando você insere dados nelas, a menos que pré-aloquem nós X, nos quais usarão novamente mais memória.

Minha sugestão, em geral, seria apenas usar o método que lhe parecer mais natural, e depois fazer um "teste de estresse" do sistema, adicionando uma quantidade substancial de dados a ele e ver se isso se torna um problema.

Você também pode considerar adicionar uma camada de abstração ao seu sistema, para que não precise alterar a interface de programação se precisar alterar posteriormente a estrutura de dados interna.

Answer 5

Pelo que entendi, o acesso aleatório é em tempo constante tanto para os dictos quanto para as listas do Python, a diferença é que você só pode fazer acesso aleatório de índices inteiros com listas.Estou assumindo que você precisa procurar um nó pelo seu rótulo, então você quer um ditado de dictos.

No entanto, no que diz respeito ao desempenho, carregá-lo na memória pode não ser um problema, mas se você usar muito, acabará trocando para o disco, o que prejudicará o desempenho até mesmo dos dictos altamente eficientes do Python.Tente manter o uso de memória o máximo possível.Além disso, a RAM é incrivelmente barata no momento;se você faz muito esse tipo de coisa, não há razão para não ter pelo menos 4 GB.

Se desejar conselhos sobre como manter o uso de memória baixo, forneça mais algumas informações sobre o tipo de informação que você está rastreando para cada nó.

Answer 6

Criar uma estrutura baseada em classes provavelmente teria mais sobrecarga do que a estrutura baseada em dict, já que em python as classes realmente usam dictos quando são implementados.

Answer 7

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

NetworkX é ótimo porque funciona para gráficos, dígrafos e multigráficos.Ele pode escrever gráficos de várias maneiras:Lista de adjacência, lista de adjacência multilina, lista de borda, gexf, GML.Funciona com Pickle, GraphML, JSON, SparseGraph6 etc.

Possui implementação de vários algoritmos radimade, incluindo:Aproximação, bipartido, limite, centralidade, clique, agrupamento, coloração, componentes, conectividade, ciclos, gráficos aciclicos direcionados, medidas de distância, conjuntos dominantes, euleriano, isomorfismo, análise de links, previsão de link, correspondência, extensão mínima, clube rico, curto Caminhos, Traversal, Árvore.