这可能是个愚蠢的问题,但假设我有一个很大(约十亿行)的 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]
- 是否有一种明显的方法来总体上改进此算法(独立于 Python)?
- 在 Python 中实现此类解决方案的最佳方式是什么?遍历原始 CSV 文件?将它加载到
pandas
并使用numpy
以某种方式对其进行矢量化(假设我有足够的内存...)?
编辑: 通过写“neighbors”,我希望表明我只想要一个无向图。抱歉,如果这不是很明显。
最佳答案
如果我没理解错的话,您希望将图形表示为 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),您可以先创建边缘,然后再创建边缘 - 一旦到达相应的线,您将创建顶点。
如果你不能保持这个假设,你仍然可以用这种方式创建你的图形表示,你只需要在最后进行一些清理,在那里你再次遍历边缘集,检查是否有任何边缘悬而未决(指向一个不存在的顶点),并通过删除这条边或创建顶点来处理这个问题——任何适合你需要的。
关于python - 从庞大的邻接列表中提取边缘列表的最有效方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40615146/