Python中最有效的图形数据结构是什么?[关闭]

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

尽管这个问题现在已经很老了,但我认为值得一提的是我自己的用于图形操作的python模块 graph-tool . 它是非常有效的,因为数据结构和算法是用C++实现的,使用模板元编程,使用Boost图形库。因此,它的性能(无论是在内存使用和运行时)都与纯C++库相媲美,并且可以比典型的Python代码好几个数量级,而不牺牲使用的方便性。我经常用它来处理非常大的图形。

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

字典还可能包含开销,具体取决于实际的实现。哈希表通常包含一些主要的可用节点数,即使您可能只使用其中的几个节点。

从你的例子来看,“属性”,你会更好地使用类方法来处理最终级别和真实属性吗?或者属性的名称在节点之间变化很大?

我想说,“高效”的含义取决于很多事情,比如:

• 更新速度(插入、更新、删除)
• 随机存取检索速度
• 顺序检索速度
• 内存使用

我认为您会发现,一个快速的数据结构通常比一个缓慢的数据结构消耗更多的内存。情况并非总是如此,但大多数数据结构似乎都遵循这一点。

字典可能很容易使用,并且给您相对一致的快速访问,它最有可能使用比您建议的列表更多的内存。然而,当您向列表中插入数据时,列表通常会包含更多的开销,除非它们预先分配X节点,在X节点中它们将再次使用更多的内存。

一般来说,我的建议是使用你认为最自然的方法,然后对系统进行“压力测试”,向系统添加大量数据,看看是否会成为问题。

您还可以考虑向系统添加一个抽象层,这样,如果以后需要更改内部数据结构,就不必更改编程接口。

据我所知,对于python的dict和list,随机访问都是在一个恒定的时间内进行的,不同的是,只能使用list对整数索引进行随机访问。我假设您需要根据节点的标签来查找它,所以您需要一个dict的dict。

但是,在性能方面,将其加载到内存中可能不是问题,但是如果使用太多,最终会交换到磁盘,这甚至会破坏Python高效dict的性能。尽量减少内存使用。而且,RAM现在也非常便宜;如果你经常做这种事情,那么就没有理由不至少拥有4GB。

如果您希望获得关于减少内存使用量的建议,请提供关于每个节点跟踪的信息种类的更多信息。

创建基于类的结构可能比基于dict的结构有更多的开销,因为在Python中,类在实现时实际上使用dict。

网络无疑是目前图形的最佳数据结构。它附带了诸如助手函数、数据结构和算法、随机序列生成器、装饰器、Cuthill McKee排序、上下文管理器等实用程序。

NetworkX非常棒,因为它适用于图形、有向图和多图形。它可以用多种方式编写图形:邻接表,多行邻接表, 边缘列表,GEXF,GML。它适用于泡菜、石墨、JSON、Spasegraph6等。

它实现了各种半径算法,包括: 近似、二部、边界、中心性、集团、聚类、着色、成分、连通性、循环、有向非循环图, 距离度量,控制集,欧拉,同构,链接分析,链接预测,匹配,最小生成树,丰富的俱乐部,最短路径,遍历,树。