Matgraph使用心得
最近在学习图论方面的内容，一向是比较懒不喜欢干重复的事情，因此在编写代码的时候就留意了一下Matlab关于图论方面的工具箱，没想到还真找到了，既然别人已经做好了这个工作，那就直接拿来用吧，也算是站在巨人的肩膀上，毕竟就我们这渣渣水平要想创造是不大可能的，NB了自然就会有想法。用了几天天觉得效果确实不错。总共算是有两个，一个叫Matgraph，一个叫MatlabBGL，前者提供了一些操作集，关于具体算法实现的比较少，而后者太凶残了基本实现了图论里面的所有算法，由于最近算法是某渣渣设计的，要自行编程只能使用Matgraph了，学了几天算是小有感触吧，国内的资料确实比较少，顶多一篇文档还是英文的，我就说说自己使用过程中的体会，算是抛砖引玉。
一、Basic principles
1）Matgraph里面所处理的图均为简单图，对于那种两个顶点之间有多个边相连的情况就无能为力了。
2）所有图的顶点均被编号为自然数，1-n，这个是没法改变的，如果删除某个顶点那么编号比它大的顶点编号会自动改变，这点需要特别注意，如果你要频繁改变图顶点的个数，你必须对他做个标记，Label函数后面介绍。
3）有一个核心的概念叫graph object，你可以理解为图形对象，matgraph里面所有的图均是用这个实现的，虽然它的核心由结构体实现的，但是很像是用面向对象的思想设计的，设计者对它进行了良好的封装，提供了一系列的API，所有处理过程必须在创建graph开始，挺简单就是一句
g=graph
这样g就是一个graph对象。
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进行操作（再次指针。。。我也
没办法解释）要实现这个功能，简单的调用copy(h,g)。这样h和g就是不同的东西，你可以随心所欲地操作而不用担心把原来的图搞丢了。
三、Basic Graph operations
好了，有了graph object什么都好办了。在你创建graph的时候它是啥都没有的，就是一个空的东西，每个图均是由一条条的边与定点构成的，要使用具体的某个图你还是得一个个的添加。
add(g,u,v)：给图g添加由顶点u和顶点v构成的一条边，这里u和v均为顶点的序号，自然数，如果他们是负数或者两个相等，那么啥也不干，如果u和v的值比图g现有顶点还大，那么创建新的顶点。显然一条条边的添加是有点麻烦了，如果你想一次性地添加n条边，那么add(g,elist)会是你想要的，这个elist是一个n*2的矩阵，每一行代表由两顶点构成的边。
delete有了add之后，你就可以构造任何图形了（simple graph），虽然还是有点麻烦。既然有add那么少不了delete。delete(g,v)删除图g中标号为v的顶点，所有与v相关的边均被删除，另外，删完之后，所有比这个v大的顶点的编号会重新改变！！特别注意。就是说有1,2,3,4,5五个顶点，你删除了3，实际最后序号还是1,2,3,4.，且不说一条条边的删很麻烦，删了之后序号变了让你很纠结，比如你想删3,4，先删除了3,那么4会调整为3，接下来是删序号为3的顶点，对于复杂的情况好纠结。delete(g,elist)vlist为一个列向量，一次性地删除n个顶点，恩，不错，就是它了。如果你仅仅想删一条边那就是delete(g,u,v)了，说到这就不再罗嗦了，一样的。如果删一系列的边就是delete(g,vlist)，还是想提醒一下，删多个边的vlist矩阵是n*2的，而删多个顶点的elist是n*1的向量，delet(g,[2,3])与delete(g,[2,3]')是不同的。
resize(g,n)把g的定点数改成n如果n比现有顶点少，那么比n大的顶点会被删除，反之会创建几个孤立的顶点。注意resize(g,0)很好用哦。
set_matrix一条条边的添加是不是很慢呢，即使你能一次添一系列的边，这个还是要自己去找，多麻烦。图的存储可以有邻接矩阵，邻接表，十字链表等，这些数据结构可以在不同的语言或者平台实现，set_marix(g,A)可以使用图的邻接矩阵来创建graph，是不是很nice？还是想说这个A不是带权的，相邻就是1否则为0，对角线是0，必须是无向图所以也是对称的，使用这个之前最好检验一下，函数check_matrix(A)可以判断A是否是符合要求的邻接矩阵。
四、Graph inspectors
有了add和delet的无敌组合，还有set_matrix创建图形就不啥问题了，如果你add，delete爽了一把的时候自个儿都不知道这个图是啥样的话那不就纠结了，正好有一系列的函数来 inspect这个graph。
nv(g) 返回g的顶点数，个人理解 number of vertices（顶点）
ne(g) 返回g的边的个数 number of edges
size(g) 重载的函数，返回顶点数和边数的向量
has(g,u,v) 检查顶点u与v之间是否连通，也可写作g(u,v)为了可读性建议用前者，这个是将常用到的操作。
neighbors(g,v)返回顶点v的所有邻接点，是个一维行向量，也可写作g(v)同上。 deg(g,v)返回顶点v的degree
find_path(g,u,v)返回顶点u与v之间的最短路径，是一个行向量，如果不连通则返回空，可以用isempty检查
isconnected(g)判断图的连通性，if true就是1，图连通是指任意两点均连通
dist(g,u,v)返回顶点u与v之间的最短路的长度，个人感觉没啥意义，貌似这里面所有的图均没法赋权，都是一让人情以何堪。
matrix(g)返回图g的邻接矩阵，注意这里是个logical类型的，可以用double()强转换。
好了基本操作就这么些，已经能完成很多很多操作了，其实现在看来功能远远没满足要求。没有赋权图的表示，没有有向图的表示，纠结，计算个最短费用还要用find_path()外加一个赋权阵点乘实现，作者想法貌似有点少啊
五、Input and Output
很多东西来说data persistence是非常重要的，所以IO操作非常重要，由于matgraph有自己的数据类型(graph object)，暂这么说吧，不准确，要保存这种特殊的对象必然有特定的操作。
其实作者的想法很简单，既然图可以又边表示，边又两顶点确定，所以实际上来说存储的就是一个n*2的矩阵的文本文件，你可以用这种格式保存你的图形对象然后直接load这个矩阵然后add list。
save(g,filename)保存g，实际上保存的不仅仅是上面的那个矩阵，还有很多其他的信息，毕竟是自己的格式
load(g,filename)读取filename里面的内容并创建graph g，注意这个filename里面的内容也不仅仅是一个n*2的矩阵，必须是又上面的save函数创建的文件。
六、Visualization
这个其实是很重要的一部分内容，数据可视化，刚开始的学这个的时候我就一直抱怨没法看到我自己创建的图具体长啥样子，看到这立马眼前一亮啊有木有，非常直观，简单而又强大。
draw(g)画出graph g这些顶点是按顺序排成一个圆的
ldraw(g)画graph以及他们的label
ndraw(g)画graph以及他们的序号
cdraw(g)可以调颜色
光这几个函数画出来的图形虽然是可以但还是好混乱完全看不清楚，排成一个圆。。。想着就没多大用
distxy(g)调用matlab的优化工具箱根据顶点之间的欧氏距离大小来画出这个图，这个碉堡了有木有！！实测非常符合实际情况，很好用，表示作者还是很天才 mdsxy(g)上面那个方法虽然厉害，但是定点多的时候会有点慢，如果你既不想看到一个圆圈又需要一点速度的话可以考虑这个，它提供了一种便利逮捕时最优解 OK数据可视化就这样子了，个人觉得还是可以满足要求的
七、其他
1）Label上面说了，删除顶点序号会变化，如果你怕你以后认不出来的话可以给他们贴上标签，label(g,v,string)用string给v贴标签，这样即使v'标号变了，标签不会变，还可以get_label来查看标签，在不知道删除多个顶点之前，我就是根据label判断谁是谁的。
2）Handling large graph
Matgraph默认使用方阵来存储graph的，如果图非常大的时候预计速度比较慢，这时可以考虑稀疏矩阵存储，
sparse(g)将graph用稀疏矩阵存储
full(g)转换为原来的模式
好了，大概就这么多了，毕竟我也才学两天左右，还要花一天的时间来消化写这
东西，还是有很多不甚清楚的也必然有些地方理解有误，欢迎大家批评指正，也希望能有所帮助，最后呢，给出我最近用matgraph写的一些脚本吧，仅供参考。 然后呢，至于matlabBGL这个工具箱由于我的电脑抽风装不上，发邮件给那个作者他竟然不理我。。。我也没办法啦，具体还在处理中，等有时间了再介绍那个，虽然还没有用过，但是看起来好NB的样子哦
还有OpenGL也正在学习中，感觉超级强大的说，但是总感觉我有点脑残，纹理光线什么的都不懂啊，我勒个去，数学也差好多都没法理解。。。有经验或者有专长的童鞋来帮下啊。。。在下感激不尽。。。
附录：
%% graph_demo.m calculate a proper route for the Network Communications % @authored by tws at 2012/8/30 20:43
% last modefied at 2012/8/31 10:46 14:13
%% -------------------initialize----------------------------------
clear,clc
load graphdata
[M,N] = size(raw_graph);
g = graph; % 建立图形对象,g表示必须存在的边
h = graph; % h表示添加边之后的图
l = graph; % l表示删除三个节点之后的图
set_matrix(g,necessary_matrix_v);%用邻接矩阵初始化必须存在的边
t = 3; % 删除三个节点
mincost = inf; % 最小费用初始化为inf
cost = 0;
is_draw = 0;
%% ------------find the needed vertex and labeled---------------
needed_edge = (raw_matrix - necessary_matrix_v); % 找出需要连接的边的邻接矩阵
%% --------------对于邻接矩阵有更好的方法----------------------------
for i = 1:M % 将此矩阵变为上三角矩阵，避免重复
for j = 1:i
needed_edge(i,j) = 0;
end
end
%% ------------------------------------------------------------------
needed_edge = max(needed_edge,needed_edge');
[needed_x,needed_y] = find(needed_edge == 1); % 找出需要添加的边的序号 elist = [needed_x,needed_y]; % elist 为需要添加的边*2的矩阵
needed_len = length(needed_x);
for k = 1:M % 为避免最后删除节点认不出，添加标号
label(g,k,num2str(k));
end
%% ------lists the combination of three point to be
deleted---------------------------------------
all_delete_three = combntns(1:M-2,t); %删除三个点的所有可能组合，返回的是一个x*3的矩阵，标号为1-9
[num_of_del,t] = size(all_delete_three); % num_of_del 要删除节点的组合数
%% ------------------------main loop-------------------------------------------------------------- tic
for i = 1:needed_len
all_possibilities = combntns(1:needed_len,i); % 挑选出来的所有可能组合数，i表示从1-needed_len添加边
[num_of_p,y] = size(all_possibilities); % num_of_p表示所有删除可能的组合数
%% ------------loop for adding edges-------------------------
for one_possibilities = 1:num_of_p
copy(h,g);
logic_del = zeros(num_of_del,1); % 存储87个组合是否全部满足条件的logic变量
temp1 = all_possibilities(one_possibilities,:);% 保存所有可能的一种情况的索引，为一个i的向量
add(h,elist(temp1,:)); % 添加需要的边 if ~isconnected(h) % 如果添加节点之后不是连通图，直接pass
continue
end
%% ----------------loop for deleting three vertices---------
for one_of_del = 1:num_of_del % 删除三个顶点
copy(l,h) % 先将h备份起来 temp2 = all_delete_three(one_of_del,:); % 挑出组合中的一个组合，
%len_x = nv(l); %
%edge_before = edges(l); % l中边的对数 %l_matrix = double(matrix(l));
delete(l,temp2'); % 删除三条边，temp'为一个列向量时删除的是顶点
%edge_after = edges(l);
if has_path(l,7,8) %
logic_del(one_of_del) = 1;
end
end
%% -------------end of deleting for---------------------------
if all(logic_del)
% disp(['添加',num2str(i),'条边满足条件
']); % 计算费用 %% -----最开始的做法，循环相加，渣渣--------------------- %cost = 0;
%for m = 1:len_x
% cost = cost +
raw_graph(str2double(get_label(h,edge_before(m,1))),str2double(get_label(h,edge_before(m,2))));
%end
%% -----使用邻接矩阵直接点乘,nice-----------------------
cost = sum(sum(double(matrix(h)).*raw_graph))/2;
if cost < mincost
mincost = cost;
temp_list = elist(temp1,:);
is_draw = 1;
end
%% ---------------------------------------------------
%logic_del = 0; % 一定注意清零啊啊
end % end of the judge of
end
%% ----------end of adding for-------------------------------
if is_draw
disp(['添加',num2str(i),'条边的最小费用为',num2str(mincost)]); mincost = inf;
figure(i);
temp = graph;
copy(temp,g);
add(temp,temp_list);
distxy(temp);
ldraw(temp);
title(['添加',num2str(i),'条边的费用最少铺设方案']);
free(temp)
clear temp
is_draw = 0;
end
end
toc
%% ---------------end of main loop--------------------------------
free_all;% 注意释放
%%