python - 从庞大的邻接列表中提取边缘列表的最有效方法是什么？

Question

这可能是个愚蠢的问题，但假设我有一个很大(约十亿行)的 CSV 文件，其中包含邻接列表，其中顶点由如下字符串表示:

+------------+---------------------------+
|     id     |         neighbors         |
+------------+---------------------------+
| 'james'    | 'michael, jane, pete'     |
| 'doug'     | 'cliff'                   |
| 'amy'      | 'bobby, russell, richard' |
| 'richard'  | 'kam, earl, cliff'        |
| 'marshawn' |                           |
| 'bobby'    | 'emily, james, doug'      |
+------------+---------------------------+

从这些类型的邻接表中，我想要做的就是输出一个顶点集和一个由无向对顶点组成的边集。就是这样。

实现这一目标的最有效策略是什么？我们如何在 Python 中实现它？

为了简要概述下面的算法，让:

• add('bobby'):将顶点'bobby'添加到顶点集的操作
• edge('bobby','emily'):将('bobby', 'emily')添加到边集中的操作
• ingraph('bobby'):检查顶点'bobby'是否在顶点集中

假设我们采用从空图开始并按顺序添加顶点的方法。然后我的第一次尝试(在非常原始的伪代码中)将是这样的:

ids = [...all id's in the CSV...]
unexplored = list(ids)

for i in ids:
    add(i)
    for j in unexplored:
        if i in neighbors(j):
            if not ingraph(j): add(j)
            edge(i, j)              
    del unexplored[0]

1. 是否有一种明显的方法来总体上改进此算法(独立于 Python)？
2. 在 Python 中实现此类解决方案的最佳方式是什么？遍历原始 CSV 文件？将它加载到 pandas 并使用 numpy 以某种方式对其进行矢量化(假设我有足够的内存...)？

编辑: 通过写“neighbors”，我希望表明我只想要一个无向图。抱歉，如果这不是很明显。

Answer 1

如果我没理解错的话，您希望将图形表示为 G(V, E)，其中 V 和 E 是两个集合，具有 Vertices 和 Edges

由于边缘边缘是无向的，您需要考虑某种方式来表示它们。要么你不关心他们的方向，并且总是检查两个方向之一是否有边缘，要么你规范化他们，例如通过对元组使用字母数字排序。

因此，我们假设您选择后者，那么 E 是一组元组，其中的条目遵循严格的顺序

e = (v1, v2), v1 < v2.

有了这个定义，您就可以逐行处理您的文件，将 ID 添加到 Set V，创建包含邻居的元组 (ID, neighbor) 或 (neighbor, ID) 取决于他们的字母数字顺序，并将其添加到您的 Set E。

如果您坚持边的规范表示，Python 会注意，Set 中不会有重复的边，因为它被定义为一组无序的唯一元素。 https://docs.python.org/2/library/sets.html

只要您可以假设您的文件是正确的，并且没有边缘，没有尽头(因为缺少 ID)，您可以先创建边缘，然后再创建边缘 - 一旦到达相应的线，您将创建顶点。
如果你不能保持这个假设，你仍然可以用这种方式创建你的图形表示，你只需要在最后进行一些清理，在那里你再次遍历边缘集，检查是否有任何边缘悬而未决(指向一个不存在的顶点)，并通过删除这条边或创建顶点来处理这个问题——任何适合你需要的。