python - 확인 - 파이썬으로 배우는 자료구조




파이썬에서 가장 효율적인 그래프 데이터 구조는 무엇입니까? (5)

나는 NetworkX 를 보라고 강력히 NetworkX . 이 테스트는 전투 테스트를 거친 전쟁 말이며 네트워크 기반 데이터를 분석해야 할 때 가장 '연구'유형이 가장 먼저 사용하는 도구입니다. 노트북에서 문제없이 수십만 개의 가장자리가있는 그래프를 조작했습니다. 풍부하고 사용하기 쉬운 기능입니다. 기본 구현의 세부 사항이 아니라 현재 문제에 더 집중하고 있음을 알게 될 것입니다.

Erdős-Rényi 랜덤 그래프 생성 및 분석의 예


"""
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 ([email protected])"""
__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)

시각화도 간단합니다.

더 많은 시각화 : http://jonschull.blogspot.com/2008/08/graph-visualization.html

파이썬에서 큰 (10 ^ 7 노드) 그래프를 조작 할 수 있어야합니다. 각 노드 / 에지에 해당하는 데이터는 최소한의 문자열입니다. 메모리와 속도 면에서 가장 효율적인 방법은 무엇입니까?

dicts dict은 더 유연하고 구현하기 쉽지만 직관적으로 목록 목록이 더 빠를 것으로 예상합니다. 목록 옵션을 사용하면 데이터를 구조와 별도로 유지해야하지만 dicts는 일종의 무언가를 허용합니다.

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

무엇을 제안 하시겠습니까?

예, 나는 효율성의 의미에 대해 좀 더 명확해야했습니다. 이 특별한 경우에 나는 랜덤 액세스 검색의 관점에서 그것을 의미합니다.

데이터를 메모리에로드하는 것은 큰 문제가 아닙니다. 그것은 한 번에 끝났습니다. 시간이 많이 걸리는 부분은 노드를 방문하므로 정보를 추출하고 관심있는 메트릭을 측정 할 수 있습니다.

각 노드를 클래스로 만드는 것을 고려하지 않았지만 (모든 노드에 대해 속성이 동일합니다) 오버 헤드가 추가되는 것처럼 보입니까? 나는 누군가가 비슷한 사례에 대해 직접 경험할 수 있기를 바랐습니다. 결국 그래프는 CS에서 가장 일반적인 추상화 중 하나입니다.


내가 알기로, 랜덤 액세스는 파이썬의 dicts와 list 모두에 대해 일정한 시간에 있습니다. 차이점은리스트로 정수 인덱스의 랜덤 액세스 만 할 수 있다는 것입니다. 레이블로 노드를 조회해야한다고 가정하므로 dicts를 원합니다.

그러나 성능 측면에서 메모리에로드하는 것은 문제가되지 않지만 너무 많이 사용하면 디스크로 스와핑되어 Python의 매우 효율적인 dicts의 성능을 저하시킵니다. 메모리 사용량을 최대한 줄이십시오. 또한 RAM은 놀랍도록 저렴합니다. 이런 종류의 일을 많이한다면 적어도 4GB를 가질 필요가 없습니다.

메모리 사용을 줄이려는 조언이 필요하면 각 노드에 대해 추적하는 정보의 종류에 대한 추가 정보를 제공하십시오.


의심 할 여지없이 NetworkX는 지금까지 그래프를위한 최고의 데이터 구조입니다. 도우미 함수, 데이터 구조 및 알고리즘, 랜덤 시퀀스 생성기, 데코레이터, Cuthill-Mckee 주문, 컨텍스트 관리자와 같은 유틸리티가 제공됩니다.

NetworkX는 그래프, 디 그래프 및 멀티 그래프를 좋아하기 때문에 훌륭합니다. Adjacency List, Multiline Adjacency List, Edge List, GEXF, GML 등 여러 가지 방법으로 그래프를 작성할 수 있습니다. Pickle, GraphML, JSON, SparseGraph6 등과 함께 작동합니다.

근사, 이분법, 경계, 중심성, 도축, 클러스터링, 채색, 구성 요소, 연결성,주기, 방향성 비순환 그래프, 거리 측정, 우세한 세트, Eulerian, 동 형사상, 링크 분석, 링크 예측, 매칭 , 최소 스패닝 트리, 리치 클럽, 최단 경로, 순회, 트리.


이 질문은 이제 꽤 오래되었지만 graph-tool 이라는 그래프 조작을위한 내 자신의 파이썬 모듈을 언급하는 것이 좋습니다. 데이터 구조와 알고리즘은 부스트 ​​그래프 라이브러리를 사용하여 템플릿 메타 프로그래밍과 함께 C ++로 구현되므로 매우 효율적입니다. 따라서 성능 (메모리 사용 및 런타임 모두)은 순수한 C ++ 라이브러리와 비교할 수 있으며 사용 편의성을 희생하지 않으면 서 일반적인 파이썬 코드보다 훨씬 뛰어납니다. 나는 매우 큰 그래프로 작업하기 위해 끊임없이 그것을 사용합니다.


파이썬에서 클래스는 실제로 구현 될 때 dicts를 사용하기 때문에 클래스 기반 구조를 만드는 것은 아마도 dict 기반 구조보다 더 많은 오버 헤드를 가질 것입니다.





graph-theory