-
Matgraph
使用心得
最近在学习图论方面的内容，一向是比较懒不喜欢干重复的事
情，因此在编
写代码的时候就留意了一下
Matlab
关于图论方面的工具箱，
没想到还真找到了，
既
然别人已经做好了这个工作，那就直接拿来用吧，也算是站在巨人的肩膀上，
毕竟就我们
这渣渣水平要想创造是不大可能的，
NB
了自然就会有想法。用
了几
天天觉得效果确实不错。
总共算是有两个，
一个叫
Matgraph
，
一
个叫
MatlabBGL
，
前者提供了
一些操作集，
关于具体算法实现的比较少，
而后者太凶残了基本
实现
了图论里面的所有算法，由于最近算法是某渣渣设计的，要自行编程只能使用
Matgraph
了，学了几天算是小有感触吧，国内的资料确实比较
少，顶多一篇文
档还是英文的，我就说说自己使用过程中的体会，算是抛砖引玉。
一、
Basic principles
1
）
Matgraph
里面所处理的图均为简单图，对于那种两个顶点之间有多个边相连
的情况就无能
为力了。
2
）所有图的顶点均被编号
为自然数，
1-n
，这个是没法改变的，如果删除某个顶
点那么编号比它大的顶点编号会自动改变，
这点需要特别注意，
如果你要频繁改
变图顶点的个数，你必须对他做个标记，
Label
函数后面介绍。
3
）有一个核心的概念叫
graph
object
，你可以理解为图形对象，
matgraph
里面所
有的图均是用这个实现的，
虽然它的
核心由结构体实现的，
但是很像是用面向对
象的思想设计的，设
计者对它进行了良好的封装，提供了一系列的
API
，所有处<
/p>
理过程必须在创建
graph
开始，挺简
单就是一句
g=graph
这样<
/p>
g
就是一个
graph
< br>对象。
4
）这里的
graph object
与一般的
matlab
元素的
behavior
不一样，它的传递是基
于指针
的！所以说，在传值的过程中，如果你对传进来的
graph
对
象做了任何的
修改，那么他就真的变了。
For
Example
，如果有个
graph g
，你想删除两条边看
这个图的连通性是否能够保持，然后写个函数，输入
g
，输出
bool
变量，
在这个
过程中你删了两条边，
判断得到了你要的结果，
接下来对
g
在干别的事儿，
你会
发现它的两条边真的被你删了，
而你仅仅想是判断一下
结果！
所以在进行这样的
操作的时候要特别注意备份。看到这里
，学过
C
语言稍微懂点指针的童鞋估计
会笑我罗嗦了，是的，这完全是
C
的风格，传指针而非传值，所
以，对于
graph
内存的管理也是必须，注意释放！
！
For sake of speed
，想一
下，如果
graph
非常
大，那么这个
graph
必然占很大空间，直接传值就会很多费内存，如果传
地址，
那么它就是一个一定位数的整型数了。
如果看到这不懂传
值与传指针的话，
那么
你的
C
语言简直太渣了，老老实实去复习吧。就是这样，
matlab
一般操作均是
传值，这个是传指针，天壤之别，记住了。
二、
Declaring graph
objects and memory management
到这里大概知道
graph
对象了，
如果你要使用
Matgraph
，
那么就离不开
graph
，
声明它很简单，
g = graph;
就
ok
，上面
说了它是基于
C
语言传递的是指针，所以
必须进行内存管理，
在你不使用它的时候就要释放空间，这样
free(g)
。如果你不
注意这个东西的话，会经常出错提示
out of menmory
！
！即
使你使用
clear
命令也
是无效的，
再次声明，不使用
graph object
的时候先
free
再
clear
。
然后呢，你如果想对
g
进行备份处理，让
h=g
这样是不行的，这样
h
与
g
是
同一个东西，
你对
h
进
行任何操作实际上也是对
g
进行操作
（
再次指针。
。
。
我也
< br>没办法解释）要实现这个功能，简单的调用
copy(h,g)
< br>。这样
h
和
g
< br>就是不同的
东西，你可以随心所欲地操作而不用担心把原来的图搞丢了。
三、
Basic Graph
operations
好了，
有了
graph object
什么都好办了。
在你创建
graph<
/p>
的时候它是啥都没有
的，
就是一个空的东
西，
每个图均是由一条条的边与定点构成的，
要使用具体的
某个图你还是得一个个的添加。
add(
g,u,v)
：
给图
g
添加由顶点
u
和顶点
v
构成的一条边，
这里
u
和
v
均为顶
点的序号，自然数，如果
他们是负数或者两个相等，那么啥也不干，如果
u
和
v
的值比图
g
现有顶点还
大，
那么创建新的顶点。
显然一条条边的添加是有点麻烦
了，如果你想一次性地添加
n
条边，那么
add(g,elist)
会是你想要的，这个
elist
是一个
n*2
的矩阵，
每一行代表由两顶点构成的边。
delete
有了
add
之后，
你就可以构
造任何图形了
（
simple graph
）
，
虽然还是有
点麻烦。既然有<
/p>
add
那么少不了
delete
。
delete(g,v)
删除图
g
中标号为
v
的顶点，
所有与
v
相关的边均被删除，
另外，
删完之后，
所有比这个
v
大的顶点的编号会
重新改变！
！特
别注意。就是说有
1,2,3,4,5
五个顶点，你删除了
3
，实际最后序
号还是
1,2,3,4.
，且不说一条条边的删很麻烦，删了之后序号变了让你很纠结，<
/p>
比如你想删
3,4
，先删除了
3,
那么
4
会调整为
3
，接下来是删序号为
3
< br>的顶点，
对于复杂的情况好纠结。
delete(g,e
list)vlist
为一个列向量，一次性地删除
n
个顶
点，恩，不错，就是它了。如果你仅仅想删一条边那就是
delete(g,u,v)
了，说到
这就不再罗
嗦了，一样的。如果删一系列的边就是
delete(g,vlist)
，还是想提醒一
下，删多个边的
vlist
矩阵是
n*2
的，而删多个顶点的
elist
是
n*1
的向量，
delet(g,[2,3])
与
de
lete(g,[2,3]')
是不同的。
< br>resize(g,n)
把
g
的
定点数改成
n
如果
n
< br>比现有顶点少，
那么比
n
大的顶
点会被
删除，反之会创建几个孤立的顶点。注意
resize(
g,0)
很好用哦。
set_mat
rix
一条条边的添加是不是很慢呢，即使你能一次添一系列的边，这
< br>个还是要自己去找，多麻烦。图的存储可以有邻接矩阵，邻接表，十字链表等，
这
些数据结构可以在不同的语言或者平台实现，
set_marix(g,A)
可以使用图的邻接
矩阵来创建
graph
，是不是很
nice
？还是想说这个
A
不是带权的，相邻就是
1
否
则为
0
，对角线是
0
，必须是无向图所以也是对称的，使用这个之前最好检验一
< br>下，函数
check_matrix(A)
可以判断
A
是否是符合要求的邻接矩阵。
四、
Graph inspectors
有了
add
和
delet
的无敌组合，
还有
set_matrix
创建图形就不啥问题了，
如果
你
add
，
delete
爽了
一把的时候自个儿都不知道这个图是啥样的话那不就纠结了，
正好有一系列的函数来
inspect
这个
graph
。
nv(g)
返回
g
的顶点数，个人理解
number of
vertices
（顶点）
ne(g)
返回
g
< br>的边的个数
number of edges
size(g)
重载的函数，返回顶点数和边数的向量
has(g,u,v)
检查顶点
u<
/p>
与
v
之间是否连通，也可写作
g(u,v)
为了可读性建议用前
者，这个是将常
用到的操作。
neighbors(g,v)
返回顶点
v
的所有邻接点，是个一维行向量，也可写作
g(v)
同上。
deg(g,v)
返回顶点
v
的<
/p>
degree
find_path(g,u,v)
返回顶点
u
与
v
之间的最短路径，是一个行向量，如果不连通则
返回空，可以用
isempty
检查
i
sconnected(g)
判断图的连通性，
if true
就是
1
，图连通是指任意两点均连通<
/p>
dist(g,u,v)
返回顶点
u
与
v
之间的最短
路的长度，个人感觉没啥意义，貌似这里
面所有的图均没法赋权，都是一让人情以何堪。
matrix(g)
返回图
g
的邻接矩阵，注意这里是个
logical<
/p>
类型的，可以用
double()
强
转换。
好了基本操作就这么些，
已经能完成很多很多操作了，
其实现在看来功能远远没
< br>满足要求。没有赋权图的表示，没有有向图的表示，纠结，计算个最短费用还要
用
find_path()
外加一个赋权阵点乘实现，作者想法貌
似有点少啊
五、
Input and
Output
很多东西来说
data persistenc
e
是非常重要的，所以
IO
操作非常重
要，由于
matgraph
有自己的数据类型
< br>(graph object)
，暂这么说吧，不准确，要保存这种特
殊的对象必然有特定的操作。
其实作者的想法很
简单，
既然图可以又边表示，
边又两顶点确定，
所以实际上来
说存储的就是一个
n*2
的矩阵的文本文件，
你可以用这种格式保存你的图形对象
然后直接
load
这个矩阵然后
ad
d list
。
save(g,fi
lename)
保存
g
，实际上保存的
不仅仅是上面的那个矩阵，还有很多其他
的信息，毕竟是自己的格式
load(g,filename)
读取
filename
里面的内容并创建
graph g<
/p>
，
注意这个
filename
里面
的内容也不仅仅是一个
n*2
的矩阵，必须是又上面的
save
函数创建的文件。<
/p>
六、
Visualization <
/p>
这个其实是很重要的一部分内容，数据可视化，刚开始的学这个的时候我就
一直抱怨没法看到我自己创建的图具体长啥样子，看到这立马眼前一亮啊有木
有
，非常直观，简单而又强大。
draw(g)
画出
graph
g
这些顶点是按顺序排成一个圆的
l
draw(g)
画
graph
以及他们
的
label
ndraw(g)
画<
/p>
graph
以及他们的序号
cdraw(g)
可以调颜色
光这几个函数画出来的图形虽然是可以但还是好混乱完全看不清楚，排成一个
< br>圆。
。
。想着就没多大用
distxy(g)
调用
matlab
的优化工具箱根据顶点之间的欧氏距离大小来画出这个图，
这个碉堡
了有木有！
！实测非常符合实际情况，很好用，表示作者还是很天才
mdsxy(g)
上面那个方法虽然厉害，但是定点多的
时候会有点慢，如果你既不想看
到一个圆圈又需要一点速度的话可以考虑这个，
它提供了一种便利逮捕时最优解
OK
数据可视化就这样子了，个人觉得还是可以满足要求的
七、其他
1
）
Label
上面说了，
删除顶点序号
会变化，
如果你怕你以后认不出来的话可以给
他们贴上标签，<
/p>
label(g,v,string)
用
string
给
v
贴标签，
这样即使
v'
标号变了，
标签
不会变，还可以
get_label
来查看标签，在不知道删除多个顶点之前，我就是根
据
lab
el
判断谁是谁的。
2
）
Handling large
graph
Matgraph
默认使用方阵来存储
graph
的，如果图非常大的时候预计速度比较慢，
这时可以考虑稀疏矩阵存储，
sparse(g)
将
graph
用稀疏矩阵存储
full(g)
转换为原来的模式
<
/p>
好了，
大概就这么多了，
毕竟我也才学两
天左右，
还要花一天的时间来消化写这