3

想了很久，终于决定把这个问题贴在这里。几天前，我开始graph-tool用来做各种事情。在那之前我一直在使用Networkx。我已经看到了令人印象深刻的性能比较，并认为一切都很简单。但是，我立即遇到了速度问题，并提出了一个与它的特定方面相关的问题。我得到了一个令我满意的快速答复。但是，现在这个速度问题时不时地困扰着我，我找不到任何关于graph-tool这与有效使用它有关。例如，从我上一个问题的答案中，我意识到最好将所有边添加在一起而不是一个接一个，这是一个非常重要的注意点，但在任何地方都没有提到！我现在有两个类似的问题：

(1) 如何选择给定节点的随机邻居？我只能看到以下解决方案：

nbr = np.random.choice(list(v.all_neighbours()))

由于v.all_neighbours()是生成器，我必须将其转换为列表以选择随机元素。这会减慢代码速度，但我没有看到更好的方法。

(2) 我想为list图中的每个顶点分配一个 1d 向量（可以吗？），然后我以特定方式交换和修改它们。这只是一个属性映射，我想查看一些有关如何有效使用它的文档。但是，我找不到任何东西。

(3) 我正在尝试模拟三元闭包，该网络本身随着时间而变化。因此，在每个时间步，我都需要关于图中每个顶点的邻居的信息。同样，我必须创建一个列表（或 numpy 数组）：

nbrs = [w for w in v.neighbours()]

这大大降低了我的代码速度。这意味着我没有正确执行此操作，但我找不到任何文档可以告诉我如何在图形工具中有效地使用邻居。

不知何故Networkx，我为相同任务编写的程序完全优于我根本买不到的图形工具代码。

这个列表可能会增加，因此，如果有人可以向我指出一些关于有效使用图形工具的文档，除了回答上述具体问题之外，我会非常高兴。

提前致谢。

4

2 回答 2

1

我会尝试做出更多“graph-tool特定”的答案：

1）实际上这个与python有关，所以你可能想使用这个线程中random.shuffle的解决方案 但是，如果你要重复这样做，（如果你有足够的可用内存），我认为它可能会更好将邻接矩阵作为scipy稀疏矩阵，然后使用该矩阵：

import graph_tool
from graph_tool.spectral import adjacency
import numpy as np

g = graph_tool.Graph()
g.add_vertex(100)
edges = np.random.randint(0, 100, (500,2))
g.add_edge_list(edges)

mat = adjacency(g).tolil()
rows = mat.rows.copy() # mat.rows = in-neighbours for each vertex
map(np.random.shuffle, rows)
rnd_neighbours = { i:row[0] for i, row in enumerate(rows) if row }

其中rnd_neighbours包含每个非零度数顶点的一个随机邻居的索引。

2) 阅读graph-tool有关PropertyMaps和详细版本的文档，lists 被接受为python::object或简单地object。然后，您可以将它们作为PropertyMap.

3) 对于三元闭包，请查看集群模块和邮件列表上的此线程。

编辑：顺便说一句，我忘了提及它，但您可以使用 、 和 in 访问和更改 OpenMPopenmp_enabled线程openmp_get_num_threads的openmp_set_num_threads数量graph-tool。但是在文档中找不到它......但这里是源代码。

于 2016-04-11T20:48:10.613 回答
1

您可以将邻居和顶点作为数组访问，这将加速您的代码，如文档中所述：https ://graph-tool.skewed.de/static/doc/quickstart.html#fast-iteration-over-vertices-and -边缘

例如，不要这样做：

nbr = np.random.choice(list(v.out_neighbours()))

你应该做：

nbr = np.random.choice(g.get_out_neighbours(v))

这应该更快，因为使用数组而不是列表。

于 2017-11-03T01:12:59.217 回答