graph-tool文档(一)- 快速开始使用Graph-tool - 1.创建和操纵图

时间:2022-03-17 19:51:08

目录:

快速开始使用graph-tool

  • 创建和操纵图

    -- 遍历顶点和边

    ----- 遍历所有顶点或边

    ----- 遍历一个顶点的neighbourhood

名词解释:

instante:实例

directed:有向;undirected:无向

on-the-fly:动态

property maps:属性映射

vertices and edges:顶点和边

descriptor:描述符

degree:度

index:索引

attribute:属性;property

invalidated:无效

iteration:迭代;iterators:迭代器

neighbours:邻接点

obtain:获取


graph_tool模块提供了一个图形类和一些操作它的算法。(graph_tool是一个模块,提供了类及其算法)

为了提高性能,这个类的内部以及大多数算法都是用c++编写的,使用了Boost Graph库。(Boost Graph Library,C++)

必须先导入模块,才能使用。包被细分成几个子模块。使用一个命令就可以将它们全部导入:(导入,子模块)

>>> from graph_tool.all import *

在下面,总是默认这一行是被运行的。


创建和操纵图

通过实例化一个Graph类来创建一个空图:(类的实例化)

>>> g = Graph()

默认情况下,新创建的图总是有向图。要想创建一个无向图,必须加入一个参数:(默认有向图)

>>> ug = Graph(directed=False)

可以使用set_directed()方法动态地将一个图在无向图和有向图之间切换(反之亦然)。

图的这种属性可以通过is_directed()查询:

>>> ug = Graph()
>>> ug.set_directed(False)
>>> assert(ug.is_directed() == False) #assert是什么意思?

也可以通过另一个图来创建一个新图,这时,整个图(它的内部属性映射,参见属性映射章节)将被复制:

>>> g1 = Graph()
>>> # ... construct g1 ...
>>> g2 = Graph(g1) # g1 and g2 are copies

以上,g2是g1的“深度”拷贝,即g2的任何修改不会影响到g1。

一旦创建了一个图,就可以向它填充顶点和边。

可以使用add_vertex()方法添加顶点,这将返回一个顶点类的实例,也被称为顶点描述符。(vertex类的实例,descriptor)

例如,下面的代码创建了两个顶点,并返回了存储在变量v1和v2中的顶点描述符。

>>> v1 = g.add_vertex()
>>> v2 = g.add_vertex()

可以通过类似的方式添加图的边,使用add_edge()方法,这将返回一个边的描述符(edge类的实例)。

>>> e = g.add_edge(v1, v2)

上面的代码创建了一个从v1到v2的有向边。

我们可以使用graph_draw()函数显示到目前为止我们创建的图。

>>> graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=18,
... output_size=(200, 200), output="two-nodes.png")
<...>

graph-tool文档(一)- 快速开始使用Graph-tool - 1.创建和操纵图

图1:通过上面的命令创建的一个简单的有两个顶点和一条边的有向图

使用顶点和边的描述符,可以以任意的方式检查和操作图。

例如,为了获得一个顶点的出度,我们可以简单地调用out_degree()方法:

>>> print(v1.out_degree())
1

类似地,我们可以使用in_degree()方法查询入度。

注意:

对于无向图,“出度”是度的同义词,在这种情况下,一个顶点的入度总是零。

边的描述符有两个有用的方法:source()target(),它分别返回一条边的来源顶点和目标顶点。(source 和 target)

>>> print(e.source(), e.target())
0 1

add_vertex()方法还接受一个可选参数来指定要创建顶点的数量。(参数:数量)

如果该值大于1,则返回一个在添加顶点描述符上的迭代器:(返回,迭代器)

>>> vlist = g.add_vertex(10)
>>> print(len(list(vlist)))
10

图中的每个顶点有一个唯一的索引,它总是在0和N-1之间,N则是顶点的数量。(索引)

可以通过使用图的vertex_index属性来获取这个索引(这是一个属性映射,见属性映射一章),或将顶点描述符转换为int类型。(图的属性映射获得索引)

>>> v = g.add_vertex()
>>> print(g.vertex_index[v]) #注意是方括号
12
>>> print(int(v))
12

也可以随时使用remove_vertex()remove_edge()方法将边和顶点删除:

>>> g.remove_edge(e)                               # e no longer exists
>>> g.remove_vertex(v2) # the second vertex is also gone

注意:

删除一个顶点通常是一个数学处理错误操作。

顶点都存储在一个STL向量内部,所以删除列表中间的一个元素需要改变列表的其余部分。

因此,快速删除(数学处理错误)仅是可能是:保证只删除列表的最后顶点(最后添加的顶点),或者相对顶点顺序是无效的。

最后一个行为可以通过remove_vertex() 的 fast == True 选项实现,导致被删除的顶点与最后一个顶点“交换”(即最大索引),这将反过来继承被删除了的顶点的索引。

警告:

由于以上原因,删除索引小于(n-1)的顶点将会使最后的(fast = True)或所有的(fast = True)指向较高索引顶点的描述符失效。

因此,如果在指定时间要删除超过一个顶点,他们应该被以索引降序的方式删除:

# 'del_list' is a list of vertex descriptors
for v in reversed(sorted(del_list)):
g.remove_vertex(v)

或者(最好),列表(或任何迭代器)直接作为顶点参数传递给remove_vertex()函数,上述过程在C++内部执行。

注意,属性映射值(参见属性映射)不受顶点删除后索引变化的影响。

注意:

删除一条边是一个(O(k{s} + k{t}))的操作,(k{s})是源顶点的出度,和(k{t})是目标顶点的入度。

可以通过设置set_fast_edge_removal()为真,更快地实现这个,在这种情况下,它变成(O(1)),以牺牲(O(E))空间大小。

边的描述符不会在边被删除之后失效。

既然顶点是索引的唯一标识,那就没有必要保持顶点标识符 lying around to access them at a later point.

如果我们知道了它的索引,我们就可以获取顶点的标识符,通过一个给定的索引,使用vertex()方法。

>>> v = g.vertex(8)

这需要一个索引,并返回一个顶点描述符。

边不能直接得到其索引,但如果一条边的源和目标顶点指定了,那就可以通过使用edge()方法获得它。

>>> g.add_edge(g.vertex(2), g.vertex(3))
<...>
>>> e = g.edge(2, 3)

获得边或顶点描述符的另一种方法是通过迭代,见迭代部分。

这实际上是获取顶点和边的描述符最有效的方式。

和顶点一样,边也有唯一的索引,这是由edge_index属性指定的:

>>> e = g.add_edge(g.vertex(0), g.vertex(1))
>>> print(g.edge_index[e])
1

不同于顶点,边的索引不一定要符合任何特定的范围。

如果没有边被删除,边的索引范围将在([0,E-1]),(E)是边的数量,早添加的边将有更低的索引值。

然而,如果一个边被删除,其索引将“空缺”,其余的索引停留在未修改的状态,因此不会处于([0,E-1])的范围内。

如果一个新的边被添加,它将重用旧的索引,以升序的方式。

遍历顶点和边

算法必须经常遍历顶点、边、顶点的出度等。

图和顶点类提供了不同类型的迭代器来实现这些。

迭代器总是指向边或顶点描述符。

遍历所有顶点和边

我们应该使用vertices()edges()方法来遍历图所有的顶点或边:

for v in g.vertices():
print(v)
for e in g.edges():
print(e)

上面的代码将依序打印图的顶点和边。

遍历领接点

顶点的出、入边,出、如邻接点可以分别通过out_edges()in_edges()out_neighbours()和** in_neighbours()**方法来迭代。

from itertools import izip
for v in g.vertices():
for e in v.out_edges():
print(e)
for w in v.out_neighbours():
print(w) # the edge and neighbours order always match
for e,w in izip(v.out_edges(), v.out_neighbours()):
assert(e.target() == w)

上面的代码将打印图中所有顶点的出边和出邻接点。

注意:

迭代器访问顶点和边的顺序总是与其被添加到图中的顺序一致(除了edges()返回的迭代器)。

通常,算法不关心这个次序,但是如果需要,可以使用这个固有的顺序。

警告:

任何情况下,在迭代时,你都不应该删除顶点或边的描述符,因为这会使迭代器失效(同C++)。

如果你打算在迭代期间删除顶点或边,您必须首先将它们存储某个地方(如列表),然后在不使用迭代器的时候删除它们。

在迭代期间删除会导致异常。

原文链接:Quick start using graph-tool