graph-tool 练习

• 如何使用graph-tool模块，如何导入？如何使用graph，使用其算法？
• 如何使用Boost Graph库，安装，测试？

1 创建和操纵图

• 如何创建空图？
  
  g = Graph()

• 如何精准的创建有向图和无向图？
  
  ug = Graph(directed=False)

• 如何切换有向和无向？
  
  ug.set_directed(False)

• 如何查询图的有向和无向属性？
  
  assert(ug.is_directed() == False)

• 如何通过一个已有的图创建新图？
  
  g1 = Graph()

g2 = Graph(g1)

• 如何添加顶点？
  
  v1 = g.add_vertex()

v2 = g.add_vertex()

• 如何创建边？
  
  e = g.add_edge(v1， v2)

• 如何浏览显示已有的图？
  
  graph_draw(g， vertex_text=g.vertex_index， vertex_font_size=18，output_size=(200， 200)， output="two-nodes.png")

• 如何获得顶点的出度？
  
  print(v1.out_degree())

• 怎么返回一条边的source和target？
  
  print(e.source()， e.target())

• 如何创建顶点，创建指定数量的顶点？
  
  vlist = g.add_vertex(10)

print(len(list(vlist)))

• 如何获得顶点的索引？
  
  v = g.add_vertex()

print(g.vertex_index[v])

print(int(v))

• 怎么将顶点和边删除？fast == True选项如何使用？set_fast_edge_removal()如何使用？
  
  g.remove_edge(e)

g.remove_vertex(v2)

• 如何通过索引获得顶点？
  
  v = g.vertex(8)

• 如何通过索引获得边？
  
  g.add_edge(g.vertex(2)， g.vertex(3))

e = g.edge(2， 3)

• 如何显示边的索引？
  
  e = g.add_edge(g.vertex(0)， g.vertex(1))

print(g.edge_index[e])

1.1 遍历顶点和边

1.1.1 遍历所有顶点或边

• 如何遍历图所有的顶点或边？
  
  vertices()

edges()

for v in g.vertices()：

    print(v)

for e in g.edges()：

    print(e)

1.1.2 遍历一个顶点的neighbourhood

• 如何遍历顶点的出/入边以及出/入邻接点？
  
  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)

2 属性映射

• 什么是属性映射？有哪几种类型？由哪个类操作？属性映射的值得类型有哪几种？
  
  一种将额外信息与顶点、边或图本身相关联的方式。

顶点、边和图。

PropertyMap类

bool、int16_t、int32_t、int64_t、double、long double、string、vector bool

vector uint8_t、vector int16_t、vector int32_t、vector int64_t、vector double

vector long double、vector string、python::object

• 如何为图创建新的属性映射？
  
  new_vertex_property()

new_edge_property()

new_graph_property()

• 如何访问属性映射？
  
  通过顶点或边的描述符或图本身，来访问该值（属性映射描述符[顶点、边或图]）

vprop_double = g.new_vertex_property("double") 顶点的属性映射
  
  vprop_double[g.vertex(10)] = 3.1416
  
  .
  
  vprop_vint = g.new_vertex_property("vector<int>") 顶点的属性映射
  
  vprop_vint[g.vertex(40)] = [1, 3, 42, 54]
  
  .
  
  eprop_dict = g.new_edge_property("object") 边的属性映射
  
  eprop_dict[g.edges().next()] = {"foo": "bar", "gnu": 42}
  
  .
  
  gprop_bool = g.new_graph_property("bool") 图的属性映射
  
  gprop_bool[g] = True

• 属性映射访问的其他形式？
  
  vprop_double.get_array()[:] = random(g.num_vertices()) get_array()方法
  
  vprop_double.a = random(g.num_vertices()) a属性

2.1 内部属性映射

• 什么是内部属性映射？
  
  被复制并和图一起被保存到一个文件，属性被内在化

• 怎么使用内部属性映射？
  
  属性映射必须有一个唯一的名称，相当于一个类型，可以产生具体的实例，即具体的属性

vertex_properties vp
  
  edge_properties ep
  
  graph_properties gp

• 区分类型，名字和值！！！

>>> gprop = g.new_graph_property("int")  #定义了一个类型

>>> g.graph_properties["foo"] = gprop   # 定义了一个变量

>>> g.graph_properties["foo"] = 42      # 为变量赋了一个值

>>> print(g.graph_properties["foo"])   #输出变量的值

42

>>> del g.graph_properties["foo"]       # 删除了定义过的变量

• 如何通过属性访问属性映射？

>>> vprop = g.new_vertex_property("double")

>>> g.vp.foo = vprop    # 等价于g.vertex_properties["foo"] = vprop

>>> v = g.vertex(0)

>>> g.vp.foo[v] = 3.14  #等价于v.vertex_properties["foo"] = 3.14

>>> print(g.vp.foo[v])

3.14

图的I/O

• 图保存和加载的四种格式？
  
  graphml、dot、gml和gt

• 图从文件保存和加载的方法，从磁盘加载的方法？
  
  save()

load()

load_graph()
  
  .

g = Graph()

g.save("my_graph.xml.gz")

g2 = load_graph("my_graph.xml.gz")

.

pickle模块

一个例子:构建一个 Price网络

• 如何看懂Price网络的代码？

#! /usr/bin/env python

# We will need some things from several places

from __future__ import division, absolute_import, print_function

import sys

if sys.version_info < (3,):

    range = xrange

import os

from pylab import *  # for plotting

from numpy.random import *  # for random sampling

seed(42)

# We need to import the graph_tool module itself

from graph_tool.all import *

# let's construct a Price network (the one that existed before Barabasi). It is

# a directed network, with preferential attachment. The algorithm below is

# very naive, and a bit slow, but quite simple.

# We start with an empty, directed graph

g = Graph()

# We want also to keep the age information for each vertex and edge. For that

# let's create some property maps

v_age = g.new_vertex_property("int")

e_age = g.new_edge_property("int")

# The final size of the network

N = 100000

# We have to start with one vertex

v = g.add_vertex()

v_age[v] = 0

# we will keep a list of the vertices. The number of times a vertex is in this

# list will give the probability of it being selected.

vlist = [v]

# let's now add the new edges and vertices

for i in range(1, N):

    # create our new vertex

    v = g.add_vertex()

    v_age[v] = i

    # we need to sample a new vertex to be the target, based on its in-degree +

    # 1. For that, we simply randomly sample it from vlist.

    i = randint(0, len(vlist))

    target = vlist[i]

    # add edge

    e = g.add_edge(v, target)

    e_age[e] = i

    # put v and target in the list

    vlist.append(target)

    vlist.append(v)

# now we have a graph!

# let's do a random walk on the graph and print the age of the vertices we find,

# just for fun.

v = g.vertex(randint(0, g.num_vertices()))

while True:

    print("vertex:", int(v), "in-degree:", v.in_degree(), "out-degree:",

          v.out_degree(), "age:", v_age[v])

    if v.out_degree() == 0:

        print("Nowhere else to go... We found the main hub!")

        break

    n_list = []

    for w in v.out_neighbours():

        n_list.append(w)

    v = n_list[randint(0, len(n_list))]

# let's save our graph for posterity. We want to save the age properties as

# well... To do this, they must become "internal" properties:

g.vertex_properties["age"] = v_age

g.edge_properties["age"] = e_age

# now we can save it

g.save("price.xml.gz")

# Let's plot its in-degree distribution

in_hist = vertex_hist(g, "in")

y = in_hist[0]

err = sqrt(in_hist[0])

err[err >= y] = y[err >= y] - 1e-2

figure(figsize=(6,4))

errorbar(in_hist[1][:-1], in_hist[0], fmt="o", yerr=err,

        label="in")

gca().set_yscale("log")

gca().set_xscale("log")

gca().set_ylim(1e-1, 1e5)

gca().set_xlim(0.8, 1e3)

subplots_adjust(left=0.2, bottom=0.2)

xlabel("$k_{in}$")

ylabel("$NP(k_{in})$")

tight_layout()

savefig("price-deg-dist.pdf")

savefig("price-deg-dist.png")