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

我需要能够在 python 中操作一个大型(10 ^ 7个节点)图。对应于每个节点/边的数据是最小的，例如，少量字符串。就 记忆和速度而言，最有效的方法是什么？

字典的结构更加灵活，实现起来也更加简单，但是我直觉地认为列表的列表会更快。List 选项还要求将数据与结构分开，而 dicts 则允许这样的操作:

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

你有什么建议？

是的，我应该更清楚我所说的效率是什么意思。在这个特殊的情况下，我指的是随机访问检索。

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

我没有考虑过将每个节点作为一个类(所有节点的属性都是相同的) ，但是这似乎会增加额外的开销层？我希望有人能有一些直接的经验与类似的情况下，他们可以分享。毕竟，图是 CS 中最常见的抽象之一。

30691 次浏览
小开

字典还可能包含开销，这取决于实际的实现。散列表通常包含一些可用节点的质数，即使您可能只使用其中的几个节点。

根据你的例子，“财产”，你会更好的与类方法的最后一级和不动产？或者属性的名称在不同的节点之间变化很大？

我认为“高效”的含义取决于很多因素，比如:

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

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

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

一般来说，我的建议是，只使用对您来说最自然的方法，然后对系统进行“压力测试”，向其中添加大量数据，看看是否会出现问题。

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

小开

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

小开

据我所知，对于 Python 的 dicts 和 list，随机访问的时间是固定的，区别在于只能对列表进行整数索引的随机访问。我假设您需要根据节点的标签来查找节点，所以您需要一个 dicts。

然而，在性能方面，将它加载到内存中可能不是问题，但是如果使用过多，最终将切换到磁盘，这将扼杀 Python 的高效指令的性能。尽可能地降低内存使用。此外，RAM 现在非常便宜; 如果你经常做这种事情，没有理由不至少有4GB。

如果您希望获得有关降低内存使用的建议，请提供有关为每个节点跟踪的信息类型的更多信息。

小开
最佳答案

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

想象也很直观:

enter image description here

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

小开

如前所述，NetworkX 非常好，另一个选项是 图表。这两个模块都将拥有您可能需要的大部分(如果不是全部的话)分析工具，并且这两个库通常与大型网络一起使用。

小开

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

小开

毫无疑问，NetworkX 是迄今为止最好的图形数据结构。它提供了辅助函数、数据结构和算法、随机序列生成器、修饰器、 Cuthill-Mckee 排序、上下文管理器等实用工具

NetworkX 很棒，因为它适用于图、有向图和多图。它可以用多种方式写图: 邻接表，多行邻接表, 边缘列表，GEXF，GML。它与 Pickle，GraphML，JSON，SparseGraph6等工作。

它实施了各种无线电算法，包括: 近似，二分，边界，中心性，团，聚类，着色，分量，连通性，圈，有向无环图, 距离度量，支配集，Eulerian，同构，链接分析，链接预测，匹配，最小生成树，富俱乐部，最短路径，遍历，树。


提交答案