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

Question

我正在尝试使用 graph-tool 库创建大型图形（大约 10^6 - 10^7 个顶点），并将顶点属性填充为顶点名称或使用名称而不是顶点索引。 我有以下内容：

1. list of names:

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

2. set of edges, but instead of vertex indexes it consists of their names:

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

由于add_edge_list()允许在图中创建顶点，如果该顶点不存在。我正在尝试使用它来填充一个空图。这个想法很好，但是当我尝试按名称获取顶点时，我收到了一个错误，提示没有这样索引的顶点。

下面是我的程序代码：

g = grt.Graph(directed=False)
edge_list = {frozenset({'568', '56'}), frozenset({'56', '50'}), frozenset({'50', '568'})}
ids = ['50', '56', '568']
g.add_edge_list(edge_list, hashed=True, string_vals=True)
print(g.vertex('50'))

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

ValueError: Invalid vertex index: 50

我想创建图表：

1. 仅使用edge_list；
2. 通过名称快速访问顶点；
3. 时间最优（如果可能还要考虑内存占用）。

有没有好的方法可以实现这个需求？

编辑： 当前代码：

g = grt.Graph(directed=False)
g.add_vertex(len(ids))
vprop = g.new_vertex_property("string", vals=ids)
g.vp.user_id = vprop  
for vert1, vert2 in edges_list:
    g.add_edge(g.vertex(ids_dict[vert1]), g.vertex(ids_dict[vert2]))

- Korevykh Maria

Answer 1

如果你有一个包含10^6 - 10^7个顶点的稠密图（这是一些医疗数据还是社交图？这可能会改变一切），你不应该使用networkx，因为它是用纯Python编写的，所以比graph-tool或igraph慢大约10-100倍。在你的情况下，我建议你使用graph-tool。它是最快的（与igraph相当）Python图处理库。 graph-tool的行为与networkx不同。当你创建networkx节点时，其标识符就是你在节点构造函数中编写的，所以你可以通过其ID获取节点。在graph-tool中，每个顶点ID都是从1到GRAPH_SIZE的整数：

图中每个顶点都有一个唯一的索引，它始终在0到N-1之间，其中N是顶点数。可以通过使用图的vertex_index属性（它是一个属性映射，请参见属性映射）或将顶点描述符转换为int来获取此索引。

有关图形、顶点或边的任何其他信息都存储在属性映射中。当您使用.add_edge_list()和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获取顶点，您需要手动构建映射字典（好吧，我不是一个graph-tool大师，但我找不到简单的解决方案）：

非常重要的映射字典 = {vertex_ids[i]：i for i in range(g.num_vertices())}

这样，您就可以轻松地获取顶点索引：

very_important_mapping_dict['568']

Out [...]: 0

vertex_ids[0]

Out [...]: '568'

- vurmux

---

是的，它实际上是一个社交图。这会有所帮助吗？ 我正在使用igraph进行聚类（或搜索社区，如果您更喜欢这个术语），并使用graph-tool来测量中心性和绘制图形。 我正在使用frozenset从源收集数据。运行时是主要问题。问题是：使用add_edge_lis()还是在循环中使用add_edge()更快？我已将当前代码添加到上面的问题字段中。 - Korevykh Maria