无论是实际网络还是对模型网络进行分析，都离不开对网络拓扑统计指标的计算。反映网络结构与动力学特性的统计指标有很多，Costa等的Characterization of Complex Networks: A Survey of measurements一文对此有全面的综述，本文仅介绍一些常用的统计指标在NetworkX中如何计算。

一、度、度分布

NetworkX可以用来统计图中每个节点的度，并生成度分布序列。下边是一段示例代码（这段代码可以在Shell里一行一行的输入，也可以将其保存为一个以py结尾的纯文本文件后直接运行），注意看注释部分：

import networkx as nx

对上述结果稍作处理，就可以在Origin等软件里绘制度分布曲线了，当然也可以用matplotlib直接作图，在上述代码后接着输入：

import matplotlib.pyplot as plt                 #导入科学绘图的matplotlib包

二、群聚系数

这个在NetworkX里实现起来很简单，只需要调用方法nx.average_clustering(G) 就可以完成平均群聚系数的计算，而调用nx.clustering(G) 则可以计算各个节点的群聚系数。

三、直径和平均距离

nx.diameter(G)返回图G的直径（最长最短路径的长度），而nx.average_shortest_path_length(G)则返回图G所有节点间平均最短路径长度。

四、匹配性

这个也比较简单，调用 nx.degree_assortativity(G) 方法可以计算一个图的度匹配性。

五、中心性

这个我大部分不知道怎么翻译，直接上NX的帮助文档吧，需要计算哪方面的centrality自己从里边找：）

Degree centrality measures.（点度中心性？）
degree_centrality(G)     Compute the degree centrality for nodes.
in_degree_centrality(G)     Compute the in-degree centrality for nodes.
out_degree_centrality(G)     Compute the out-degree centrality for nodes.

Closeness centrality measures.（紧密中心性？）
closeness_centrality(G[, v, weighted_edges])     Compute closeness centrality for nodes.

Betweenness centrality measures.（介数中心性？）
betweenness_centrality(G[, normalized, ...])     Compute betweenness centrality for nodes.
edge_betweenness_centrality(G[, normalized, ...])     Compute betweenness centrality for edges.

Current-flow closeness centrality measures.（流紧密中心性？）
current_flow_closeness_centrality(G[, ...])     Compute current-flow closeness centrality for nodes.
Current-Flow Betweenness

Current-flow betweenness centrality measures.（流介数中心性？）
current_flow_betweenness_centrality(G[, ...])     Compute current-flow betweenness centrality for nodes.
edge_current_flow_betweenness_centrality(G)     Compute current-flow betweenness centrality for edges.

Eigenvector centrality.（特征向量中心性？）
eigenvector_centrality(G[, max_iter, tol, ...])     Compute the eigenvector centrality for the graph G.
eigenvector_centrality_numpy(G)     Compute the eigenvector centrality for the graph G.

Load centrality.（彻底晕菜~~~）
load_centrality(G[, v, cutoff, normalized, ...])     Compute load centrality for nodes.
edge_load(G[, nodes, cutoff])     Compute edge load.


六、小结

上边介绍的统计指标只是NetworkX能计算的指标中的一小部分内容，除此之外NetworkX还提供了很多（我还没有用到过的）统计指标计算方法，感兴趣的朋友可以去查NetworkX的在线帮助文档：http://networkx.lanl.gov/reference/index.html。对于加权图的统计指标计算，NetworkX似乎没有直接提供方法（也可能是我没找到），估计需要自己动手编制一些程序来完成。

degree = nx.degree_histogram(G)          #返回图中所有节点的度分布序列
x = range(len(degree))                             #生成x轴序列，从1到最大度
y = [z / float(sum(degree)) for z in degree]
#将频次转换为频率，这用到Python的一个小技巧：列表内涵，Python的确很方便：）
plt.loglog(x,y,color="blue",linewidth=2)           #在双对数坐标轴上绘制度分布曲线
plt.show()                                                          #显示图表
G = nx.random_graphs.barabasi_albert_graph(1000,3)   #生成一个n=1000，m=3的BA无标度网络
print G.degree(0)                                   #返回某个节点的度
print G.degree()                                     #返回所有节点的度
print nx.degree_histogram(G)    #返回图中所有节点的度分布序列（从1至最大度的出现频次）

NetworkX提供了4种常见网络的建模方法，分别是：规则图，ER随机图，WS小世界网络和BA无标度网络。本文首先介绍在NetworkX生成这些网络模型的方法，然后以BA无标度网络的建模为例，分析利用NetworkX进行复杂网络演化模型设计的基本思路，以便将来开发出我们自己的模型。同时这篇文章里还涉及到一点复杂网络可视化的方法（后边有时间会另文介绍网络可视化的方法）。

一、规则图

规则图差不多是最没有复杂性的一类图了，在NetworkX中，用random_graphs.random_regular_graph(d, n)方法可以生成一个含有n个节点，每个节点有d个邻居节点的规则图。下面是一段示例代码，生成了包含20个节点、每个节点有3个邻居的规则图：

import networkx as nx
import matplotlib.pyplot as plt
RG = nx.random_graphs.random_regular_graph(3,20) #生成包含20个节点、每个节点有3个邻居的规则图RG
pos = nx.spectral_layout(RG)          #定义一个布局，此处采用了spectral布局方式，后变还会介绍其它布局方式，注意图形上的区别
nx.draw(RG,pos,with_labels=False,node_size = 30) #绘制规则图的图形，with_labels决定节点是非带标签（编号），node_size是节点的直径
plt.show() #显示图形

运行结果如下：

图1   NetworkX生成的规则图

 

二、ER随机图

ER随机图是早期研究得比较多的一类“复杂”网络，这个模型的基本思想是以概率p连接N个节点中的每一对节点。在NetworkX中，可以用random_graphs.erdos_renyi_graph(n,p)方法生成一个含有n个节点、以概率p连接的ER随机图：

import networkx as nx
import matplotlib.pyplot as plt
ER = nx.random_graphs.erdos_renyi_graph(20,0.2) #生成包含20个节点、以概率0.2连接的随机图
pos = nx.shell_layout(ER)          #定义一个布局，此处采用了shell布局方式
nx.draw(ER,pos,with_labels=False,node_size = 30)
plt.show()

运行结果如下：

图2   NetworkX生成的随机图

三、WS小世界网络

在NetworkX中，可以用random_graphs.watts_strogatz_graph(n, k, p)方法生成一个含有n个节点、每个节点有k个邻居、以概率p随机化重连边的WS小世界网络，下面是一个例子：

import networkx as nx
import matplotlib.pyplot as plt
WS = nx.random_graphs.watts_strogatz_graph(20,4,0.3) #生成包含20个节点、每个节点4个近邻、随机化重连概率为0.3的小世界网络
pos = nx.circular_layout(WS)          #定义一个布局，此处采用了circular布局方式
nx.draw(WS,pos,with_labels=False,node_size = 30) #绘制图形
plt.show()

运行结果如下：

图3   NetworkX生成的WS小世界网络

四、BA无标度网络

在NetworkX中，可以用random_graphs.barabasi_albert_graph(n, m)方法生成一个含有n个节点、每次加入m条边的BA无标度网络，下面是一个例子：

import networkx as nx
import matplotlib.pyplot as plt
BA= nx.random_graphs.barabasi_albert_graph(20,1) #生成n=20、m=1的BA无标度网络
pos = nx.spring_layout(BA)          #定义一个布局，此处采用了spring布局方式
nx.draw(BA,pos,with_labels=False,node_size = 30) #绘制图形
plt.show()

运行结果如下：

图4   NetworkX生成的BA无标度网络

 

五、对BA模型实现代码的分析

前面我们介绍了NetworkX提供的4种网络演化模型的应用方法，但仅停留在使用已有的模型是不够的，实际工作中我们可能会自己开发一些网络演化模型。利用NetworkX提供的数据结构，我们可以比较方便的完成这一工作。下面以NetworkX中BA模型的实现代码为例，分析用NetworkX开发网络演化模型的一般思路。NetworkX中关于网络建模的代码在random_graphs.py这个文件中，可以用记事本打开它。为了叙述简便起见，我删掉了原始代码中的一些错误处理与初始条件定义的语句，红色部分是翻译后的注释。

#定义一个方法，它有两个参数：n - 网络节点数量；m - 每步演化加入的边数量
def barabasi_albert_graph(n, m):
    # 生成一个包含m个节点的空图 (即BA模型中t=0时的m0个节点)
    G=empty_graph(m)
    # 定义新加入边要连接的m个目标节点
    targets=range(m)
    # 将现有节点按正比于其度的次数加入到一个数组中，初始化时的m个节点度均为0，所以数组为空
    repeated_nodes=[]    
   # 添加其余的 n-m 个节点，第一个节点编号为m（Python的数组编号从0开始）
    source=m
    # 循环添加节点
    while source<n:
        # 从源节点连接m条边到选定的m个节点targets上（注意targets是上一步生成的）
        G.add_edges_from(zip([source]*m,targets))
        # 对于每个被选择的节点，将它们加入到repeated_nodes数组中（它们的度增加了1）
        repeated_nodes.extend(targets)
        # 将源点m次加入到repeated_nodes数组中（它的度增加了m）
        repeated_nodes.extend([source]*m)
        # 从现有节点中选取m个节点 ，按正比于度的概率（即度优先连接）
        targets=set()
        while len(targets)<m:
            #按正比于度的概率随机选择一个节点，见注释1
            x=random.choice(repeated_nodes)
            #将其添加到目标节点数组targets中
            targets.add(x)       
        #挑选下一个源点，转到循环开始，直到达到给定的节点数n
        source += 1
    #返回所得的图G
    return G

注释1：此步是关键，random.choice方法是从一个数组中随机地挑选一个元素。由于repeated_nodes数组中的节点出现次数是正比于节点度的，所以这样处理可以保证按度大小的概率选出节点，即实现了度优先连接。如果是按正比于节点适应性等非整数值优先连接，可以参考我的另一篇博文《根据值的大小随机取数组元素的方法》。

六、小结

NetworkX的优势之一就是开源，这也是所有Python库的优势（Python是脚本语言，它没有办法隐藏源代码）。NetworkX的源代码结构清晰，风格简练，注释详尽，是学习、研究复杂网络不错的参考资料。当然在这方面我也是初学者，更多的功能还需要在实际应用中不断去发掘和领会…………

科学可视化是利用计算机图形学来创建视觉图像，帮助人们理解那些采取错综复杂而又往往规模庞大的数字呈现形式的科学概念或结果。对于复杂网络研究来说，可视化技术同样重要，它有助于呈现或解释复杂网络数据和模型，进而从中发现（或许是从数据中不易发现的）各种模式、特点和关系。

在我的另一篇博文《 推荐一个复杂网络可视化的网站 》中，介绍了 www.visualcomplexity.com 这个网站，上边有大量复杂网络和复杂系统的图片，五彩缤纷，令人叹为观止。有的朋友可能会想，这些图形是否都是使用一些专业的平面设计软件制作的呢？其实，通过使用NetworkX，我们同样可以制作出精美的复杂网络图形，它提供了非常丰富的网络可视化功能。下边这幅动画就是用从NetworkX网站上下载的图片拼合而成的，感兴趣的朋友可以到 http://networkx.lanl.gov/gallery.html 这个地址去查看生成这些图形的源代码。
在这篇笔记中，我将简单地介绍使用NetworkX绘制复杂网络图形的基本方法。当然在这方面我也是初学，只略懂一些皮毛，希望能起到抛砖引玉的作用：）

一、基本绘图流程

在NetworkX中，绘制一个网络使用nx.draw()方法，它至少接受一个参数：即你希望绘制的网络G。实际上这个方法非常复杂，它可以指定20多个关键字参数，后边会介绍一些常用的参数，我们先从最简单的情况入手，看看下边的例子：

import networkx as nx                   #导入networkx包
import matplotlib.pyplot as plt     #导入绘图包matplotlib（需要安装，方法见第一篇笔记）
G =nx.random_graphs.barabasi_albert_graph(100,1)   #生成一个BA无标度网络G
nx.draw(G)                          #绘制网络G
plt.savefig("ba.png")           #输出方式1: 将图像存为一个png格式的图片文件
plt.show()                            #输出方式2: 在窗口中显示这幅图像

运行上述代码的结果如下：

这样，用短短的几行代码就完成了一个最基本的网络图形绘制，而且生成了一个功能丰富的窗体。窗口左下方的工具栏可以对图像进行放大、缩小、平移、保存等操作，可以自己动手试一下。同时，在源文件的目录下还生成了一个png格式的图片文件，可以把它插入报告或论文中，是不是很方便呢？

二、运用样式

上边的代码虽然简单，但生成的图形略显单调。NetworkX提供了一系列样式参数，可以用来修饰和美化图形，达到我们想要的效果。常用的参数包括：

      - `node_size`: 指定节点的尺寸大小(默认是300，单位未知，就是上图中那么大的点)
      - `node_color`: 指定节点的颜色 (默认是红色，可以用字符串简单标识颜色，例如'r'为红色，'b'为绿色等，具体可查看手册)
      - `node_shape`: 节点的形状（默认是圆形，用字符串'o'标识，具体可查看手册）
      - `alpha`: 透明度 (默认是1.0，不透明，0为完全透明)
      - `width`: 边的宽度 (默认为1.0)
      - `edge_color`: 边的颜色(默认为黑色)
      - `style`: 边的样式(默认为实现，可选： solid|dashed|dotted,dashdot)
      - `with_labels`: 节点是否带标签（默认为True）
      - `font_size`: 节点标签字体大小 (默认为12)
      - `font_color`: 节点标签字体颜色（默认为黑色）

灵活运用上述参数，可以绘制不同样式的网络图形，例如：nx.draw(G,node_size = 30,with_labels = False) 是绘制节点尺寸为30、不带标签的网络图。

三、运用布局

NetworkX在绘制网络图形方面提供了布局的功能，可以指定节点排列的形式。这些布局包括：

circular_layout：节点在一个圆环上均匀分布
random_layout：节点随机分布
shell_layout：节点在同心圆上分布
spring_layout：用Fruchterman-Reingold算法排列节点（这个算法我不了解，样子类似多中心放射状）
spectral_layout：根据图的拉普拉斯特征向量排列节点？我也不是太明白

布局用pos参数指定，例如：nx.draw(G,pos = nx.circular_layout(G))。在上一篇笔记中，四个不同的模型分别是用四种布局绘制的，可以到那里去看一下效果，此处就不再重复写代码了。

另外，也可以单独为图中的每个节点指定一个位置（x、y坐标），不过比较复杂，我还没有这样做过。感兴趣的朋友可以看一下NetworkX文档中的一个例子：http://networkx.lanl.gov/examples/drawing/knuth_miles.html。


四、添加文本

用plt.title()方法可以为图形添加一个标题，该方法接受一个字符串作为参数，fontsize参数用来指定标题的大小。例如：plt.title("BA Networks", fontsize = 20)。如果要在任意位置添加文本，则可以采用plt.text()方法。事实上这些功能（包括前边的图形保存等功能）并不是由NetworkX提供的，从包的名字上可以看出，这些绘图函数都是由matplotlib这个包提供的。NetworkX只是把与复杂网络绘图相关的功能重新包装了一下，让用户调用更方便而已。

需要补充的一点是，matplotlib并不直接支持中文文本，如果想输出中文，走正规方法还是挺麻烦的（见http://blog.csdn.net/KongDong/archive/2009/07/10/4338826.aspx）。不过有聪明的网友提出了一种偷梁换柱的解决方案：换字体。只要把一个中文字体文件（ttf文件）更名为Vera.ttf，拷贝到matplotlib的字体目录中覆盖原有文件，就可以输出中文了，具体细节见http://hi.baidu.com/ucherish/blog/item/63155e52b68c90070df3e3ff.html 。

五、小结

这篇笔记简单介绍了用NetworkX绘制复杂网络图形的方法，实际上NetworkX的制图能力是很强的（主要是matplotlib的功劳），本文所介绍的功能只是其中最基础的一部分，更多功能还有待我们一起去发掘。再次推荐 http://networkx.lanl.gov/gallery.html上的绘图示例代码，能看懂弄清这些代码，用NetworkX绘图应该就难不住你了：）

二分图又称二部图，是图论中的一种特殊模型，它的顶点可分割为两个互不相交的子集，并且图中的每条边所关联的两个顶点分别属于这两个不同的顶点集。二分图在复杂网络分析中有很多应用，例如科学家合作网络（作者和论文）、商品网络（商品和购买者）、城市公交网络（线路和站点）等都可以用二分图来进行描述。NetworkX提供了一些基本的二分图建模与分析功能，下面对这些功能作一个简单的介绍。

一、建立二分图

建立二分图与建立普通的图方法比较类似，需要注意的是，边只能在不同类节点之间添加，同类节点之间不要添加边就可以。下面是一个简单的例子（本例中用1开头的编号表示项目节点，用2开头的编号表示参与者节点）：

import networkx as nx
B = nx.Graph()
#添加一个项目101，它有3个参与者：201,202,203
B.add_edge(101,201)
B.add_edge(101,202)
B.add_edge(101,203)
#添加一个项目102，它有2个参与者：203,202,2034
B.add_edge(102,203)
B.add_edge(102,204)
…………………………

此外，
NetworkX还提供了多种二分图演化模型的建立方法，在这里把它们列出来供大家参考：
-- networkx.generators.classic.complete_bipartite_graph(n1, n2, create_using=None)--networkx.generators.bipartite.bipartite_configuration_model (aseq, bseq, create_using=None, seed=None)
根据两个度序列建立一个二分图
-- networkx.generators.bipartite.bipartite_random_regular_graph(d, n, create_using=None, seed=None)
建立一个随机的规则二分图
-- networkx.generators.bipartite.bipartite_preferential_attachment_graph(aseq, p, create_using=None, seed=None)
建立一个优先连接的二分图
-- networkx.generators.bipartite.bipartite_havel_hakimi_graph(aseq, bseq, create_using=None)
根据两个度序列建立一个Havel-Hakimi模式的二分图（下面两个模型类似，我没有接触过这个模型，不太理解具体含义）
-- networkx.generators.bipartite.bipartite_reverse_havel_hakimi_graph(aseq, bseq, create_using=None)
-- networkx.generators.bipartite.bipartite_alternating_havel_hakimi_graph(aseq, bseq, create_using=None)

二、检测图的二分性

用networkx.is_bipartite()方法可以检测一个图是否是二分图。例如对上边代码建立的二分图，nx.is_bipartite(B)返回的结果是True，而对一个随机图R = nx.random_graphs.gnp_random_graph(100,0.2)，由于它不是二分图，nx.is_bipartite(R)返回的结果是False。

NetworkX并没有提供图的二分度计算方法，如果使用到这一功能需要自己编制代码。何大韧老师等编写的《复杂系统与复杂网络》一书的132页有二分度的计算公式，感兴趣的朋友可以自己实现这一程序。

此外，NetworkX还提供了对二分图节点进行着色的算法：networkx.bipartite_color()，它可以返回一个字典结构，分别为二分图中的两类节点赋予一个颜色值以示区别。例如对前面建立的二分图进行着色：print nx.bipartite_color(B)，将返回结果 ：{101: 1, 102: 1, 201: 0, 202: 0, 203: 0, 204: 0}，项目节点被赋予颜色值1，参与者节点的颜色值是0。可以用这个值来检测节点类型，也可以用它来进行绘图（参看第4篇笔记《网络可视化》）。

三、二分图的投影

二分图可以通过向参与者节点投影或向项目节点投影转换为一个单分图（见下图），NetworkX提供的networkx.project(B, nodes)方法可以完成这一工作。它接受两个参数：一个是二分图B，另一个是投向的节点集合nodes。
对于节点集合的提取可以用networkx.bipartite_sets方法，它可以将一个二分图的两类节点提取为两个集合(X,Y)，其中X是项目节点，Y是参与者节点。下面是一段示例代码，演示上述两个函数的用法：

（接第一节的代码之后）
NSet = nx.bipartite_sets(B)   #将二分图中的两类节点分别提取出来
Act = nx.project(B,NSet[0])     #向项目节点投影
Actor = nx.project(B,NSet[1]) #向参与者节点投影
print Act.edges() #输出 [(101, 102)]
print Actor.edges()   #输出 [(201, 202), (201, 203), (202, 203), (203, 204)]

四、通过派系提取构造二分图

对于一个存在派系（Clique）的图，可以通过提取派系结构生成一个二分图。NetworkX提供的networkx.make_clique_bipartite方法可以从图中查找派系，然后将一个派系作为一个项目节点并和该派系中的节点建立连接，从而构造一个二分图。它是二分图向参与者节点投影的逆过程，下边是一段示例代码：

（接第三节的代码之后）
G = nx.make_clique_bipartite(Actor)
print G.edges() #输出：[(201, -1), (202, -1), (203, -2), (203, -1), (204, -2)]

补充一点，NetworkX的派系提取算法据说效率很高，不过我没有做过这方面的东西，感兴趣的朋友可以去看它的源代码（见http://networkx.lanl.gov/reference/algorithms.clique.html）。

五、小结

本篇笔记介绍了用NetworkX进行二分图建模与分析的方法，到今天为止，我的《NetworkX学习笔记》就暂告一段落了。我目前的工作中只用到了这几篇笔记中所写的功能，以后如果有其他的心得体会我还会继续进行补充。希望这些文章对学习和研究复杂网络的朋友们能起到一点帮助作用，也欢迎各位留言批评、讨论。

最后，向NetworkX的三位开发者Aric Hagberg、Dan Schult 、Pieter Swart 以及许许多多的贡献者致敬^*，感谢他们为我们提供了这样一个优秀的复杂网络分析工具！

根据三位开发者的建议，如果要在论文中引用NetworkX，请引用以下文献:
Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008


* 意外发现NetworkX的贡献者里还有复杂网络圈里的周涛、刘建国和汪秉宏老师，佩服啊！见https://networkx.lanl.gov/trac/changeset/681/networkx/trunk/networkx ：“Graph A and B are from Tao Zhou, Jian-Guo Liu, Bing-Hong Wang: Comment on ``Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality". http://arxiv.org/pdf/physics/0511084 ”

建立一个完全二分图

 首先，基本上所有的graph library都有其局限性，不同的数据结构有优点的同时必然有缺点，图算法对数据结构的依赖性构成另一个原因。所以如果是想用一个工具包解决所有的问题显然是一种奢望，很多时候甚至必须要从头写自己的代码。但是阅读igraph和networkx这样成型了的函数库对熟悉算法和相关语言的技巧是很有用的。

      igraph(http://igraph.sourceforge.net/)是在处理复杂网络问题中用的比较多的C语言函数库，不过它也提供了R，Python的接口。

      networkx(http://networkx.lanl.gov/)是用基于python的dictionary的一个复杂网络库。众所周知的是，python语言在对程序效率要求不是很苛刻的时候是构建程序的最佳选择一(对python不熟悉的图论研究者可以看看我在人人上的一篇日志（http://blog.renren.com/blog/bp/QmicNX45As)，而用python语言写成的networkx充分利用了python中的dictionary的特性，将python的动态性发挥到了极致，研究networkx源代码对于研究算法和做相关的实验是我们的不二选择。但是对于规模很大的问题，性能上的要求需要我们去使用诸如igraph,BGL(boost graph library,不过基本已经停止开发）之类用C/C++写成的库。

igraph中图的数据结构
      igraph中基本的graph structure采用的是EdgeList，所以在igraph中自然而然的允许multiedge的存在，当然它也提供了Adjancency list（对某些算法，大部分算法接受的参数是edgelist）。数据结构igraph_t定义如下:

 
typedef struct igraph_s {
  igraph_integer_t n;
  igraph_bool_t directed;
  igraph_vector_t from;
  igraph_vector_t to;
  igraph_vector_t oi;
  igraph_vector_t ii;
  igraph_vector_t os;
  igraph_vector_t is;
  void *attr;
} igraph_t;

（注意igraph中顶点和边都是从0开始编号一直到总数减一）。其中n是图的顶点个数，directed标志是否是有向图。所有边的顶点存储在from和to两个向量(igraph_vector_t)中，oi[e]对应的是编号为e的边所对应的尾结点在from中的index，同样ii[e]对应于e的头节点在to中的index（也就是是说e 可以表示为 from[oi[e]] -> to[ii[e]]）。所以from,to,oi,ii都是长度与边数相同的向量。os和is则和oi，ii相反，表示的是从顶点到边的映射，从顶点v出发的第一条边为 from[oi[os[v]]] -> to[ii[os[v]]]，所以当os[v] == os[v + 1]时候就表示从该顶点没有出边。向量is同理。os,is都是长度为顶点数加一的向量。操作igraph_t的一些基本API如igraph_empty, igraph_adjacent等见于文档手册（btw，igraph的文档写的很全很好，有空应该研究一下它制作文档的技术）。

 

      因为采用的是edgelist的结构，所以增/减边（顶点）的操作在igraph中是相当耗费时间的。add和delete操作的时间复杂度基本上都是O(|V| + |E|)或者O(|V|)。（oops!）

 

      igraph实现了自己的一套数据结构诸如vector, heap,hashtable（一般的C程序库都是这么干的，C程序员总是重复制造轮子么。。。），因为C没有C++/Java中的泛型，一般都是采取void*指针或者宏的方式来实现泛型。igraph采用的是后者。大致看了一下，感觉收获还是很多的。igraph将类型无关的代码都抽象出来放在*pmt.h *pmt这样的文件模板里面。types.h和相关的C文件中则利用这些代码模板生成相应的声明和定义。一个典型的代码片段如下：

#define BASE_BOOL  
#include "igraph_pmt.h"  
#include "vector.pmt"  
#include "igraph_pmt_off.h"  
#undef BASE_BOOL 
#define BASE_BOOL
#include "igraph_pmt.h"
#include "vector.pmt"
#include "igraph_pmt_off.h"
#undef BASE_BOOL

 

其中vector.pmt定义的是类型无关的代码，igraph_pmt_off.h则小心翼翼的将宏清除出去（再一次感慨C++有模板真是太好了。。。）。这种手法还是有借鉴意义的（比起void*我更喜欢这样）。

      另外还学到了#error可以用来检测编译期间的错误（又一次证明我对C的了解还是太少太少。。。汗）。

      igraph的基本数据结构就写这么多，感兴趣的研究者可以去看API文档和相应的源码。算法留待下回分解，igraph中最出彩的部分就是它实现了相当一部分较新的复杂网络算法（包括网络流、图同构、匹配算法以及社团结构等）。

Networkx的数据结构
      得益于python语言的简洁明快，所以看Networkx的源码基本上是一览无余，这应该就是Knuth所说的Literate Programming吧。Networkx中图的数据结构主要有Graph（简单无向图）, DiGraph（简单有向图）, MultiGraph（允许有重边的无向图）和MultiDiGraph（允许有重边的有向图）。他们的实现都扎根于Python字典类的强大（Oreilly出版的《代码之美》一书中称Python的Dictionary类为全能战士，此话一点不错！）。关于Networkx的数据结构我这里就不赘述了，Python代码最好的解释了它自己。（再次向大家推荐Python编程语言！ -_- )。

 

本文来自程序员宝宝，转载请标明出处：http://blog.csdn.net/rogerrecharad/archive/2010/11/07/5993723.aspx