graph-tool程序库的使用文档_graph-tool安装

复杂网络

需积分: 50 101 浏览量更新于2023-05-18 评论 1 收藏 22.48MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

2019/4/9 Quick start using graph-tool — graph-tool 2.27 documentation

https://graph-tool.skewed.de/static/doc/quickstart.html 1/17

Quick start using graph-tool

The

graph_tool

module provides a

Graph

class and several algorithms that operate on it. The

internals of this class, and of most algorithms, are written in C++ for performance, using the

Boost Graph Library.

The module must be of course imported before it can be used. The package is subdivided into

several sub-modules. To import everything from all of them, one can do:

>>> from graph_tool.all import *

In the following, it will always be assumed that the previous line was run.

Creating and manipulating graphs

An empty graph can be created by instantiating a

Graph

class:

>>> g = Graph()

By default, newly created graphs are always directed. To construct undirected graphs, one

must pass a value to the directed parameter:

>>> ug = Graph(directed=False)

A graph can always be switched on-the-fly from directed to undirected (and vice versa), with

the

set_directed()

method. The “directedness” of the graph can be queried with the

is_directed()

method,

>>> ug = Graph()

>>> ug.set_directed(False)

>>> assert ug.is_directed() == False

A graph can also be created by providing another graph, in which case the entire graph (and

its internal property maps, see Property maps) is copied:

>>> g1 = Graph()

>>> # ... construct g1 ...

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

Above, g2 is a “deep” copy of g1, i.e. any modification of g2 will not affect g1.

Once a graph is created, it can be populated with vertices and edges. A vertex can be added

with the

add_vertex()

method, which returns an instance of a

Vertex

class, also called a vertex

descriptor. For instance, the following code creates two vertices, and returns vertex

descriptors stored in the variables v1 and v2.

>>> v1 = g.add_vertex()

>>> v2 = g.add_vertex()

Edges can be added in an analogous manner, by calling the

add_edge()

method, which returns

an edge descriptor (an instance of the

Edge

class):

2019/4/9 Quick start using graph-tool — graph-tool 2.27 documentation

https://graph-tool.skewed.de/static/doc/quickstart.html 3/17

of the graph (which is a property map, see Property maps), or by converting the vertex

descriptor to an int.

>>> v = g.add_vertex()

>>> print(g.vertex_index[v])

>>> print(int(v))

Edges and vertices can also be removed at any time with the

remove_vertex()

and

remove_edge()

methods,

>>> g.remove_edge(e) # e no longer exists

>>> g.remove_vertex(v2) # the second vertex is also gone

 Note

Removing a vertex is typically an \(O(N)\) operation. The vertices are internally stored in a

STL vector, so removing an element somewhere in the middle of the list requires the

shifting of the rest of the list. Thus, fast \(O(1)\) removals are only possible either if one can

guarantee that only vertices in the end of the list are removed (the ones last added to the

graph), or if the relative vertex ordering is invalidated. The latter behavior can be achieved

by passing the option fast == True, to

remove_vertex()

, which causes the vertex being

deleted to be ‘swapped’ with the last vertex (i.e. with the largest index), which will in turn

inherit the index of the vertex being deleted.

 Warning

Because of the above, removing a vertex with an index smaller than \(N-1\) will invalidate

either the last (fast = True) or all (fast = False) descriptors pointing to vertices with

higher index.

As a consequence, if more than one vertex is to be removed at a given time, they should

always be removed in decreasing index order:

# 'del_list' is a list of vertex descriptors

for v in reversed(sorted(del_list)):

g.remove_vertex(v)

Alternatively (and preferably), a list (or any iterable) may be passed directly as the vertex

parameter of the

remove_vertex()

function, and the above is performed internally (in C++).

Note that property map values (see Property maps) are unaffected by the index changes

due to vertex removal, as they are modified accordingly by the library.

 Note

Removing an edge is an \(O(k_{s} + k_{t})\) operation, where \(k_{s}\) is the out-degree of the

source vertex, and \(k_{t}\) is the in-degree of the target vertex. This can be made faster by

setting

set_fast_edge_removal()

to True, in which case it becomes \(O(1)\), at the expense of

additional data of size \(O(E)\).

2019/4/9 Quick start using graph-tool — graph-tool 2.27 documentation

https://graph-tool.skewed.de/static/doc/quickstart.html 4/17

No edge descriptors are ever invalidated after edge removal, with the exception of the edge

being removed.

Since vertices are uniquely identifiable by their indexes, there is no need to keep the vertex

descriptor lying around to access them at a later point. If we know its index, we can obtain the

descriptor of a vertex with a given index using the

vertex()

method,

>>> v = g.vertex(8)

which takes an index, and returns a vertex descriptor. Edges cannot be directly obtained by

its index, but if the source and target vertices of a given edge are known, it can be retrieved

with the

edge()

method

>>> g.add_edge(g.vertex(2), g.vertex(3))

<...>

>>> e = g.edge(2, 3)

Another way to obtain edge or vertex descriptors is to iterate through them, as described in

section Iterating over vertices and edges. This is in fact the most useful way of obtaining

vertex and edge descriptors.

Like vertices, edges also have unique indexes, which are given by the

edge_index

property:

>>> e = g.add_edge(g.vertex(0), g.vertex(1))

>>> print(g.edge_index[e])

Differently from vertices, edge indexes do not necessarily conform to any specific range. If no

edges are ever removed, the indexes will be in the range \([0, E-1]\), where \(E\) is the number

of edges, and edges added earlier have lower indexes. However if an edge is removed, its

index will be “vacant”, and the remaining indexes will be left unmodified, and thus will not all

lie in the range \([0, E-1]\). If a new edge is added, it will reuse old indexes, in an increasing

order.

Iterating over vertices and edges

Algorithms must often iterate through vertices, edges, out-edges of a vertex, etc. The

Graph

and

Vertex

classes provide different types of iterators for doing so. The iterators always point to

edge or vertex descriptors.

Iterating over all vertices or edges

In order to iterate through all the vertices or edges of a graph, the

vertices()

and

edges()

methods should be used:

for v in g.vertices():

print(v)

for e in g.edges():

print(e)

The code above will print the vertices and edges of the graph in the order they are found.

2019/4/9 Quick start using graph-tool — graph-tool 2.27 documentation

https://graph-tool.skewed.de/static/doc/quickstart.html 5/17

Iterating over the neighborhood of a vertex

The out- and in-edges of a vertex, as well as the out- and in-neighbors can be iterated through

with the

out_edges()

in_edges()

out_neighbors()

and

in_neighbors()

methods, respectively.

from itertools import izip

for v in g.vertices():

for e in v.out_edges():

print(e)

for w in v.out_neighbors():

print(w)

# the edge and neighbors order always match

for e, w in izip(v.out_edges(), v.out_neighbors()):

assert e.target() == w

The code above will print the out-edges and out-neighbors of all vertices in the graph.

 Warning

You should never remove vertex or edge descriptors when iterating over them, since this

invalidates the iterators. If you plan to remove vertices or edges during iteration, you must

first store them somewhere (such as in a list) and remove them only after no iterator is

being used. Removal during iteration will cause bad things to happen.

Fast iteration over vertices and edges

While convenient, looping over the graph as described in the previous section is not the most

efficient approach. This is because the loops are performed in pure Python, and hence it

undermines the main feature of the library, which is the offloading of loops from Python to

C++. Following the

numpy

philosophy,

graph_tool

also provides an array-based interface that

avoids loops in Python. This is done with the

get_vertices()

get_edges()

get_out_edges()

get_in_edges()

get_out_neighbors()

get_in_neighbors()

get_out_degrees()

and

get_in_degrees()

methods, which return

numpy.ndarray

instances instead of iterators.

For example, using this interface we can get the out-degree of each node via:

print(g.get_out_degrees(g.get_vertices()))

[1 0 1 0 0 0 0 0 0 0 0 0]

or the sum of the product of the in and out-degrees of the endpoints of each edge with:

edges = g.get_edges()

print((edges[:,0] * edges[:,1]).sum())

Property maps

Property maps are a way of associating additional information to the vertices, edges or to the

graph itself. There are thus three types of property maps: vertex, edge and graph. All of them

剩余389页未读，继续阅读

SongNingSDUT

粉丝: 0
资源: 2

会员权益专享

graph-tool程序库的使用文档

评论0

会员权益专享

最新资源

graph-tool程序库的使用文档

评论0

classgraph-4.8.83-API文档-中英对照版.zip

classgraph-4.8.90-API文档-中文版.zip

graph-tool-2.43.tar.bz2

conda安装graph-tool

离线安装graph-tool

graph-tool 安装

PackagesNotFoundError: The following packages are not available from current channels: - graph-tool

conda的安装graph-tool出现源路径错误

arm64 系统安装graph-tool

networkx igraph graph-tool等之间的效率

安装graph-tool出现源路径错误

PackagesNotFoundError: The following packages are not available from current channels: - graph-tool==2.29

python-graph-core

vue-d3-graph-main

怎么用Linux安装图日create模块

neo4j-graph-data-science-2.4.0.jar

hdl-graph-slam

STA中的Graph-Based Analysis

git log --all --graph --decorate

会员权益专享

最新资源