应用图论算法实现通风网络可视化*

2013-04-03王孝东胡乃联谭海林赵晓杰

金属矿山 2013年4期

王孝东胡乃联谭海林赵晓杰

(北京科技大学土木与环境工程学院)

建立通风网络的拓扑关系，对分支风路和节点编号，既是网络解算最繁杂的一项工作，又是网络解算在矿井通风应用中的一个瓶颈。一直以来，人们通过绘制单线的网络图后手工标注分支和节点编号［1］，但是，随着矿山生产快速地向纵、横方向开采，井下巷道越来越复杂，巷道数据已从简单的数十条，增加到几千条，甚至上万条，面对大批量的井巷数据，传统的手工编制方法显得更加困难。近年来，许多学者采取了一些简化网路的方法对分支和节点进行编号。如提出假、真拓扑通风网络的概念，并实现了拓扑关系的自动生成;通过建立三维线框模型，在三维状态下进行手动编号;采用在各实际中段平面图上直接标注的方法，并且中段标注节点时用彩色笔标注，以避免重复和疏漏;用MVSS建立通风仿真系统，不对巷道和节点进行编号，巷道和节点仅仅作为一种符号，在网络解算中不起任何拓扑关系的作用等［2-8］。每种编号方法在其通风网络解算实现过程中均起到了不同的作用。

目前，在矿井通风安全领域，可视化的矿井通风仿真系统(MVSS)实现了矿井风流分配仿真、按需调节分配仿真、反风模拟;矿山通风模拟软件(Ventsim)通过建立矿井直观的三维通风系统模型，对通风网络进行解算，优选风机，对通风效果进行模拟检测与控制［9-11］。但是，在矿山实际生产中，由于以上先进通风模拟软件在国内矿山并没有得到完全的普及和应用，而矿井通风解算三维仿真技术又是当前矿山通风安全管理的必然趋势，因此，本研究主要应用自身已有的资源和技术条件，即无仿真功能的风网解算软件和三维矿业工程软件，采用一种新的方法，应用相关知识编写了两步算法，从三维空间的角度对通风网络图中分支和节点的拓扑结构进行运算，解决了对矿井中大批量数据的快速处理，实现了图—数—图的转换，完成了矿井通风网络解算的三维可视化效果，并通过实例证明了该方法符合预定目标。

1 研究方法和算法描述

矿井通风系统，是用点的集合和线的集合表示其图形，记为G=(V，E)。其中V为结点(即风流交汇点)的集合，所含结点数为|V|=m;E为分支(对应通风巷道)的集合，所含的分支数为|E|=n;记为V={v1，v2，…，vm}，E={e1，e2，…，en}。若vi，vj∈V，当边ek=(vi，vj)∈E时，称vi和vj是邻接的，记作viadj vj，称边ek和结点vi，vj相关联，否则记作vinadj vj。若边ek的终点是边em的起点，则称em和ek是边邻接的，记作ekadj em，否则记作eknadj em。若以通风巷道中有关的通风参数阻力、风量、压力等对相应的分支赋权，则为矿井通风网络图的赋权图，记为N=(G，f)，f为各边的权函数［12-13］。

1.1 研究方法

1.1.1 始末节点编号的研究方法

根据图的邻接矩阵，可将分支的所有节点按一定的次序排列。设m阶矩阵A(G)=(aij)为图G的邻接矩阵［14］。所求矩阵为稀疏矩阵，在计算过程中存储非零元素的行和列的位置，同时统计出矩阵中非零元素的相同位置出现的次数(T)，如果T＞1，节点自动编号，编号从2开始顺序增加;如果T=1 and始节点or终节点，节点编号=1，矿井通风拟定所有进、出风口都视为伪节点，其节点编号均标为“1”［13］。

为了便于理解，以有向图G作为具体示例(如图1所示)。给出依据邻接矩阵运算过程中的节点与编号对应关系，如图2(a)。

图1 有向图

1.1.2 分支编号的研究方法

构造关联矩阵，将各分支按分支的始节点和终节点的排列次序排列，设m×n阶矩阵B(G)= (bij)m×n为图G的关联矩阵。由此可构造行向量函数:分支行向量E=(e1，e2，…，en)，分支始节点行向量V1=(v11，v12，…，v1n)，分支末节点行向量V2= (v21，v22，…，v2n)。依次排列可得ei=(v1i，v2i)，通过行向量运算生成关联矩阵，按节点的有序偶对关系为分支编号，编号从1开始，直到所有的有序偶对关系均编号为止，如图2(b)所示。

图2 编号算法流程

1.1.3 赋权值的研究方法

风网解算的结果主要指井下所有分支巷道的参数(权值)，反映通风网络图中节点和分支的属性值，依据赋权图的概念［12］，对于通风网络N所具有的权函数，同理可按照分支E中元素的排列次序进行排列，相应的行向量可转换为

将上述各行向量按顺序排列可得到fi=ei= (v1i，v2i)，经向量运算后生成关联矩阵，对应于分支E中的所有节点坐标赋值，形成多对一形式。最终以向量和矩阵的形式反映矿井通风网络图的结构及相应的权函数，如图3。

图3 赋权算法流程

1.2 算法描述

1.2.1 算法1——编号

在研究分支和节点之间的拓扑关系基础上，并结合深度优先搜索的算法［15-18］，通过对图使用遍历算法可以获得图的结构信息。使用Visual C++6.0标准模板库中的类模板vector容器类，定义了分支类和节点类2个容器类，分别用于存储所有分支信息和每一条分支中包含的所有结点信息。

程序算法如下:

Step 1循环遍历网络图中所有的分支(E)和结点(V)，给定网络图中所有分支的结点出现次数(T)，结点坐标(C)，分支编号(Enum)，结点编号(Vnum)，始节点(V［begin］)，末节点(V［end］);

Step 2

for所有分支结点

Step 3

for所有分支结点

Step 4

for分支所有结点

对所有分支中出现两次以上的节点进行编号，编号从2开始依次增加;

1.2.2 算法2——赋权值

通过相关计算求解，可得到2张数据表(即分支节点编号数据表和解算结果数据表)。对网络图中各分支的所有节点赋权值时，以分支编号作为公共字段，按对应关系进行相应链接，以空行作为一条分支赋值的结束点，形成多对一的对应关系。

算法如下:

Step 1新建一个表文件(File3)用于存储赋值后的信息，给定通风网络解算结果数据表(File1)和分支节点编号的数据表(File2)，

Step 2定义变量:

CString CalcResult;∥ File1计算结果值(分支编号，风阻，风量，风压)

CString NCoord;∥节点坐标值(x，y，z，始末节点编号，分支编号)

CString DataLink;∥每个节点链接后的结果值(x，y，z，始末节点编号，分支编号，风阻，风量，风压，…)

Step 3循环遍历File1的数据，

读取一行File1.CalcResult;

读取一行File2.NCoord;

Step 4 DataLink=NCoord+“，”+CalcResult，保存DataLink→File3;

Step 5循环遍历File2的数据，继续读取下一行File2.NCoord;

Step 6如果File2.NCoord不为null，执行Step3;否则，执行Step2;

Step 7结束。

2 实例应用与分析

为了验证该方法在矿井通风网络解算的三维可视化的可行性，现以国内某矿山的实际数据为实例。该矿山矿体比较分散，各采区的布置相对较远，现主要开采范围达36 km2，开采高差范围近900 m，从2 350 m到深部1 360 m共形成了13个主要开采中段，面对如此复杂的矿井，所建立的通风网络图涉及到成百上千的分支和节点数据，为了降低工作量和减少人为失误，同时保证解算结果的准确和实现三维可视化的真实性，须解决网络数据信息批量处理的问题，对巷道和节点数据进行编号提取、整理、转换、合并及显示。如图4所示为3D Mine软件平台下建立的需要参与编号和赋权运算的三维网络图。

图4 3D M ine矿井通风三维网络

2.1 矿井通风网络解算数据表的算法验证

调用算法1，完成对图4中所有分支和节点的自动编号，并作为风网解算的基础数据;调用算法2，把风网解算结果数据赋值给图4中对应的分支和节点，同时生成一张完整的矿井通风网络解算数据表，如表1所示。

(1)表1中前3项字段是分支巷道的所有结点坐标值(x、y、z)，定位了矿井巷道的空间关系;算法1，增加“始末节点编号”字段，对每一条分支的始、末节点编号，增加“巷道编号”字段对所有分支巷道进行自动编号并按升序排列;算法2，为所有分支巷道中包含的所有结点都被赋于了一组权值。本算法达到了预定目标。

(2)从表1中可看出每一条分支可以由2个或以上结点自动生成，无论每条分支巷道中有多少个结点，都只确定唯一的始、末节点;如表中巷道编号为50的分支有6个结点坐标值，此处从图7中可看出是一个环形的井底车场，为了保证本算法所生成的数据表格具有更好的可移植性、不失真，对此绕道中的增加结点坐标均参与赋权运算。

(3)各个分支巷道之间用空行分隔，使得各分支相互独立，赋权后可允许关联分支的相同节点赋于不同的权值，如表1中的巷道编号51和52分支，51的始节点编号99是52的始节点编号99，但其后的参数并不相同，出现了同一个节点有2种权值，因为该节点是交叉点，分别属于3条相对独立的分支，根据通风网络节点风量平衡的原理，与该节点相邻的上下各边的风量满足节点风量平衡定律，即节点相邻的上边风量之和等于下边的风量之和，节点参数的重复并不影响关联分支风路的解算值，因此本算法符合通风解算的要求。

2.2 矿井通风三维网络图的算法验证

利用3D Mine软件平台，导入表1所有数据，同时设置其“显示描述值”菜单功能，操作者能够依据“浏览属性值”方式显示表1中的任一参数值。

(1)图5(a)显示矿井进风口、出风口和漏风口的编号均为“1”，依据矿井通风网络的解算原理，从矿井出风口到进风口，经过地表大气的分支为伪分支，该分支的风阻为零，并不是网路中的真实巷道，其相应的节点为伪节点。

(2)图5(b)为始、末节点的编号，每个节点可以和1个分支或多个分支相关联，除了进、出风口外，其余每个节点既是后1条分支的始节点，又是前1条分支的末节点;可看出环形井底车场的节点编号97和99对应的2条分支是并联分支;针对并联、角联等情况，在分支中增加1个节点的方式使得其中1条分支变换为2段分支或者是在分支中加入部分结点参与赋权运算，因为如果按2点控制1条直线的方式，此处并联分支会出现重合显示的错误判断。

表1 矿井通风网络数据

(3)图5(c)为分支的编号顺序具有随机性，程序运算时，按照深度优先搜索的算法有序地沿着图中的分支访问图中所有的节点，通过对图进行遍历来获得图的结构信息，但是，由于网络图中存在复杂的串、并联和角联的原因，因而分支编号顺序会存在一定的随机性。

(4)图6显示了每段巷道的风量值，通过执行算法2为各条分支赋权值，其他如风扇机功率、风机型号、轴功率、巷道净断面积、巷道长度等，均可以此向量形式表示;如果把已建立的三维巷道实体模型、相关通风构筑物和风流方向导入图6中，即生成图7所示的矿井通风网络解的三维可视化效果图，显示时可按照不同颜色对各个巷道中段分别着色，图中清晰、直观地显示了2个中段的风量值和坚井、斜井的风量值。

(5)对照图6和图7，在巷道编号为70位置处安设辅助风机，该辅助风机的风量是解算前按照理论需风量初拟的，风机安设在绕道中，而在与绕道相并联的运输巷道中设置2道自动风门，为了减小漏风，提高通风网络解算的精确性，此处作了简化处理，因此算法中并没有对此编号和赋值，符合风网解算的实际情况。

(6)从图7风路中的风量值可以看出多条巷道交汇点处，既有风流流入，又有风流流出，符合流入流出交汇点的风量之和为零的风量平衡定律，并没有出现风量混乱的情形，证明本算法的结果是正确的。

通过以上图表对照，并结合矿山实际情况分析，算法1和算法2的运算结果符合矿井通风网络解算的映射关系，显示效果达到预定的目标，实现了矿井通风网络解算的三维可视化。