Python中高效表示子图（数据结构）

Question

在Python中，保存和比较给定输入图G中生成的子图的有效方法是什么？在

一些细节：

1. 输入图G是一个有向的简单图，其顶点数在n=100-10000之间变化。边数-可以假设最大值为完整图的10%（通常较少），因此在这种情况下，它给出了n*（n-1）/10的最大数目

2. 有一种算法可以从输入图G生成成百上千的子图。并对每个子图进行了一些（耗时）计算。 必须存储对“子图，计算结果”以备以后使用（动态规划方法-如果给定的子图已经被处理，我们希望重用其结果）。

3. 由于第（2）点，最好将子图/结果对存储在以子图为键的字典中。如何有效地完成？关于子图散列值高效计算的一些想法？

4. 假设内存不是问题，我可以找到内存足够的机器来保存数据，所以我们只关注速度。

当然，如果已经有很好的数据结构可以帮助解决这个问题（比如scipy的稀疏矩阵），那么它们是非常受欢迎的。在

我只想知道你对这个问题的看法，也许还有一些关于解决这个问题的建议。 我知道有很好的Python图形/网络库，比如NetworkX，igraph，graph tool，它们有非常有效的算法来处理所提供的图形。但似乎（或者我找不到）有效的方法来实现第（2）点。3.）

Answer 1

这里的关键点是算法已经生成的图形的数据格式。它是否通过添加顶点和边来构造一个新的图？它可以重写吗？它是否使用给定的格式（矩阵、邻接列表、顶点和节点集等）

但是，如果您可以选择，因为子图的基数“低”，而且空间不是问题，我会将子图存储为位掩码的数组（位掩码部分是可选的，但它是散列的，并且是紧凑集）。子图表示就是

• L全局图中节点引用的列表G。它也可以是用作哈希的位掩码
• A位掩码（矩阵）的数组，其中A[i][j]是边L[i] -> L[j]的真值

这利用了Python整数的无限大低空间需求。空间复杂度是O（n*n），但是可以获得高效的遍历，并且可以很容易地散列结构。在