【R语言在最优化中的应用】igraph 包在图与网络分析中的应用

图与网络规划是近几十年来运筹学领域中发展迅速、而且十分灵活的一个分支。由于它对实际问题的描述，具有直观性，故广泛应用于物理学、化学、信息论、控制论、计算机科学、社会科学、以及现代经济管理科学等许多科学领域。图与网络分析的内容十分丰富，这里只介绍路径规划、网络流、最小生成树、旅行商等几个经典问题。

igraph 包在图与网络分析中的应用

igraph 包是一个非常强大的包，它可以快速轻松地创建、绘制和分析无向图及有向图(图的顶点和边允许百万以上），并解决了经典图论问题，如最小生成树、最大网络流量、最短路等问题。该包内容很丰富，下面仅讨论几个常见问题。

igraph包中，graph.maxflow() 函数可以解决最大流问题，用法为：

graph.maxflow(graph, source, target, capacity=NULL)

其中，graph 为要处理的图，为igraph 格式，其创立方式非常简单，参见帮助文档。source 和target 分别代表网络中要求最大流的起始点和终点，capacity 为边的权重。

minimum.spanning.tree() 函数可以解决最小生成树问题，用法为：

minimum.spanning.tree(graph, weights=NULL, algorithm=NULL, ...)

其中，graph 意义同上，weights 为边的权，algorithm 为所选择的算法，如果置空(默认)，函数将自动选取算法。

shortest.paths() 函数可以解决任意两顶点间(要求边的权非负) 的最短路问题，用法为：

shortest.paths(graph,v=V(graph),mode=c("all","out","in"),weights=NULL)

其中，graph、weight 意义同上，v为该图的顶点(V(graph) 即为求图的顶点)，mode 为字符变量，当其为"all" 时，忽略图形边的方向，即将图作为无向图(默认) 来计算最短路程；当其为"out" 时，考虑各个边的方向；当其为"in" 时，考虑各个边的方向，但此时将各边的方向倒置。因此，mode 取"all" 时，所得的最短路矩阵为对称的，取"out" 和"in" 时，所得的两个矩阵互为转置矩阵。

例 图3 是个有向图10，方向如图中箭头所示，边上的数字为其权重，试求下列问题：

1. 从顶点0 到顶点7 的最大流量(此时图中各条边上的数字代表容量限制)；

2. 该连通图的最小生成树；

3. 该图中任意两顶点之间的最短路程(考虑方向)。

解：这三个问题是图论中的典型问题。首先，应该在R中构造该图，然后分别调用相关命令即可。

R代码及运行结果如下:

1 > library(igraph) #载入包 2 > e = matrix(nc = 3, byrow = TRUE, c(0,1,5, 0,2,4, 0,3,3, 1,5,3, 1,4,5, 3 + 2,5,3, 2,6,2, 3,6,2, 4,1,5, 4,7,4, 5,7,3, 6,7,5)) #边的权矩阵 4 > g = add.edges(graph.empty(8), t(e[,1:2]), weight = e[,3]) #构造图 5 > tkplot(g) #绘制网络图 6 [1] 35 7 > graph.maxflow(g, 0,7, capacity = E(g)$weight) #最大流 8 [1] 11 9 > mst = minimum.spanning.tree(g) #最小生成树 10 > tkplot(mst) #绘制最小生成树 11 [1] 36 12 > (tree_min = sum(E(mst)$weight)) #计算并输出最小生成树的权 13 [1] 20 14 > shortest.paths(g, mode = "out") #最短路矩阵 15 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] 16 [1,] 0 5 4 3 10 7 5 10 1 > library(igraph) #载入包 2 > e = matrix(nc = 3, byrow = TRUE, c(0,1,5, 0,2,4, 0,3,3, 1,5,3, 1,4,5, 3 + 2,5,3, 2,6,2, 3,6,2, 4,1,5, 4,7,4, 5,7,3, 6,7,5)) #边的权矩阵 4 > g = add.edges(graph.empty(8), t(e[,1:2]), weight = e[,3]) #构造图 5 > tkplot(g) #绘制网络图 6 [1] 35 7 > graph.maxflow(g, 0,7, capacity = E(g)$weight) #最大流 8 [1] 11 9 > mst = minimum.spanning.tree(g) #最小生成树 10 > tkplot(mst) #绘制最小生成树 11 [1] 36 12 > (tree_min = sum(E(mst)$weight)) #计算并输出最小生成树的权 13 [1] 20 14 > shortest.paths(g, mode = "out") #最短路矩阵 15 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] 16 [1,] 0 5 4 3 10 7 5 10

图3 为所画的网络图(边上的数字由其它软件所绘)。图4 为最小生成树图。

由第8 行可知，最大流为11。由第13 行可知，最小生成树的权为20。由15 – 23 行(最短路矩阵) 可以知道该网络上每两个定点的最短路。如顶点0 到顶点7 的最短路为10(矩阵中第1 行第8 列对应的元素)。需要说明的是，第6，11 行结果表示这是R软件打开的第35，36 个tk 图形设备，与本题的具体内容无关。

观察以上代码和输出结果，发现R仅仅用短短十行代码，就解决了最大流问题、最短路问题、最小生成树问题，并绘制出两个相关的图形，其效率之高，令人叹为观止。而LINGO 则需要针对每个问题输入不同模型、约束条件等，远远不如R效率高，至于绘图功能，LINGO 还需要很大的改进。

求红包