Python中最有效的图形数据结构是什么？

Question

我需要能够在python中操作一个大的(10 ^ 7个节点)图形.对应于每个节点/边缘的数据是最小的,例如,少量的字符串.在内存和速度方面,最有效的方法是什么？

dicts的词典更灵活,更易于实现,但我直观地期望列表列表更快.list选项还要求我将数据与结构分开,而dicts允许这样的东西:

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

你会建议什么？

---

是的,我应该对效率的意思更清楚一点.在这个特殊情况下,我的意思是随机访问检索.

将数据加载到内存中不是一个大问题.这是一劳永逸的.耗时的部分是访问节点,因此我可以提取信息并测量我感兴趣的指标.

我没有考虑过让每个节点成为一个类(所有节点的属性都相同),但似乎会增加一层额外的开销？我希望有人可以直接体验他们可以分享的类似案例.毕竟,图形是CS中最常见的抽象之一.

Answer 1

我强烈建议你看看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 (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)

可视化也很简单:

更多可视化:http://jonschull.blogspot.com/2008/08/graph-visualization.html

Answer 2

即使这个问题现在很老了,我认为值得一提的是我自己的python模块用于图形操作,称为图形工具.它非常有效,因为数据结构和算法是用C++实现的,使用Boost Graph Library进行模板元编程.因此,它的性能(内存使用和运行时)与纯C++库相当,并且可以比典型的python代码好几个数量级,而不会牺牲易用性.我经常使用它来处理非常大的图形.

Answer 3

如前所述,NetworkX非常好,另一个选项是igraph.这两个模块将拥有您可能需要的大多数(如果不是全部)分析工具,并且这两个库通常用于大型网络.