使用 add_edge_list() 方法创建图形的最佳方法是什么？

Question

我正在尝试通过graph-tool库（接近 10^6 - 10^7 个顶点）创建大图，并用顶点名称填充顶点属性或使用名称而不是顶点索引。我有：

1. 名单：

   ['50', '56', '568']
   

2. 一组边，但不是顶点索引，而是由它们的名称组成：

   edge_list = {frozenset({'568', '56'}), frozenset({'56', '50'}), frozenset({'50', '568'})}
   

因为add_edge_list()如果它们在图中没有这样的顶点，则允许创建顶点。我试图用它来填充一个空图。它工作正常，但是当我尝试按名称获取顶点时，出现错误，提示没有具有此类索引的顶点。

这是我的程序的代码：

['50', '56', '568']

的错误信息print(g.vertex('50'))：

ValueError: Invalid vertex index: 50

我想创建图表：

1. edge_list仅使用；
2. 通过名称快速访问顶点；
3. 按时间优化（如果可能，还有 RAM）。

有什么好的方法可以做到这一点吗？

编辑：当前代码：

edge_list = {frozenset({'568', '56'}), frozenset({'56', '50'}), frozenset({'50', '568'})}

Answer 1

如果你有一个 10^6 - 10^7 个顶点的密集图（它是一些医疗数据还是社交图？它可以改变一切），你不应该使用，networkx因为它是用纯 Python 编写的，所以它是 ~10-100时间比graph-tool或慢igraph。在您的情况下，我建议您使用graph-tool. 它是最快的（~as igraph）Python 图形处理库。

graph-tool行为不同于networkx。创建networkx节点时，其标识符是您在节点构造函数中编写的内容，因此您可以通过其 ID 获取节点。在图形工具中，每个顶点 ID 都是从 1 到 GRAPH_SIZE 的整数：

图中的每个顶点都有一个唯一的索引，它总是在 0 到 N?1 之间，其中 N 是顶点的数量。这个索引可以通过使用图的 vertex_index 属性（它是一个属性映射，见属性映射），或者通过将顶点描述符转换为一个 int 来获得。

每个关于图、顶点或边的附加信息都存储在属性映射中。当您使用.add_edge_list()with 时hashed=True，新的属性映射将作为 的结果返回.add_edge_list()。所以在你的情况下，你应该像这样处理你的顶点：

# Create graph
g = grt.Graph(directed=False)

# Create edge list
# Why frozensets? You don't really need them. You can use ordinary sets or tuples
edge_list = {
    frozenset({'568', '56'}),
    frozenset({'56', '50'}),
    frozenset({'50', '568'})
}

# Write returned PropertyMap to a variable!
vertex_ids = g.add_edge_list(edge_list, hashed=True, string_vals=True)

g.vertex(1)

Out [...]: <Vertex object with index '1' at 0x7f3b5edde4b0>

vertex_ids[1]

Out [...]: '56'

如果你想根据ID得到一个顶点，你应该手动构造mapping dict（好吧，我不是graph-tool大师，但我找不到简单的解决方案）：

very_important_mapping_dict = {vertex_ids[i]: i for i in range(g.num_vertices())}

所以你可以很容易地得到一个顶点索引：

very_important_mapping_dict['568']

Out [...]: 0

vertex_ids[0]

Out [...]: '568'