應用圖論算法實現(xiàn)通風網(wǎng)絡可視化*

王孝東 胡乃聯(lián) 譚海林 趙曉杰

(北京科技大學土木與環(huán)境工程學院)

建立通風網(wǎng)絡的拓撲關系，對分支風路和節(jié)點編號，既是網(wǎng)絡解算最繁雜的一項工作，又是網(wǎng)絡解算在礦井通風應用中的一個瓶頸。一直以來，人們通過繪制單線的網(wǎng)絡圖后手工標注分支和節(jié)點編號［1］，但是，隨著礦山生產(chǎn)快速地向縱、橫方向開采，井下巷道越來越復雜，巷道數(shù)據(jù)已從簡單的數(shù)十條，增加到幾千條，甚至上萬條，面對大批量的井巷數(shù)據(jù)，傳統(tǒng)的手工編制方法顯得更加困難。近年來，許多學者采取了一些簡化網(wǎng)路的方法對分支和節(jié)點進行編號。如提出假、真拓撲通風網(wǎng)絡的概念，并實現(xiàn)了拓撲關系的自動生成;通過建立三維線框模型，在三維狀態(tài)下進行手動編號;采用在各實際中段平面圖上直接標注的方法，并且中段標注節(jié)點時用彩色筆標注，以避免重復和疏漏;用MVSS建立通風仿真系統(tǒng)，不對巷道和節(jié)點進行編號，巷道和節(jié)點僅僅作為一種符號，在網(wǎng)絡解算中不起任何拓撲關系的作用等［2-8］。每種編號方法在其通風網(wǎng)絡解算實現(xiàn)過程中均起到了不同的作用。

目前，在礦井通風安全領域，可視化的礦井通風仿真系統(tǒng)(MVSS)實現(xiàn)了礦井風流分配仿真、按需調(diào)節(jié)分配仿真、反風模擬;礦山通風模擬軟件(Ventsim)通過建立礦井直觀的三維通風系統(tǒng)模型，對通風網(wǎng)絡進行解算，優(yōu)選風機，對通風效果進行模擬檢測與控制［9-11］。但是，在礦山實際生產(chǎn)中，由于以上先進通風模擬軟件在國內(nèi)礦山并沒有得到完全的普及和應用，而礦井通風解算三維仿真技術又是當前礦山通風安全管理的必然趨勢，因此，本研究主要應用自身已有的資源和技術條件，即無仿真功能的風網(wǎng)解算軟件和三維礦業(yè)工程軟件，采用一種新的方法，應用相關知識編寫了兩步算法，從三維空間的角度對通風網(wǎng)絡圖中分支和節(jié)點的拓撲結構進行運算，解決了對礦井中大批量數(shù)據(jù)的快速處理，實現(xiàn)了圖—數(shù)—圖的轉換，完成了礦井通風網(wǎng)絡解算的三維可視化效果，并通過實例證明了該方法符合預定目標。

1 研究方法和算法描述

礦井通風系統(tǒng)，是用點的集合和線的集合表示其圖形，記為G=(V，E)。其中V為結點(即風流交匯點)的集合，所含結點數(shù)為|V|=m;E為分支(對應通風巷道)的集合，所含的分支數(shù)為|E|=n;記為V={v1，v2，…，vm}，E={e1，e2，…，en}。若vi，vj∈V，當邊ek=(vi，vj)∈E時，稱vi和vj是鄰接的，記作viadj vj，稱邊ek和結點vi，vj相關聯(lián)，否則記作vinadj vj。若邊ek的終點是邊em的起點，則稱em和ek是邊鄰接的，記作ekadj em，否則記作eknadj em。若以通風巷道中有關的通風參數(shù)阻力、風量、壓力等對相應的分支賦權，則為礦井通風網(wǎng)絡圖的賦權圖，記為N=(G，f)，f為各邊的權函數(shù)［12-13］。

1.1 研究方法

1.1.1 始末節(jié)點編號的研究方法

根據(jù)圖的鄰接矩陣，可將分支的所有節(jié)點按一定的次序排列。設m階矩陣A(G)=(aij)為圖G的鄰接矩陣［14］。所求矩陣為稀疏矩陣，在計算過程中存儲非零元素的行和列的位置，同時統(tǒng)計出矩陣中非零元素的相同位置出現(xiàn)的次數(shù)(T)，如果T＞1，節(jié)點自動編號，編號從2開始順序增加;如果T=1 and始節(jié)點or終節(jié)點，節(jié)點編號=1，礦井通風擬定所有進、出風口都視為偽節(jié)點，其節(jié)點編號均標為“1”［13］。

為了便于理解，以有向圖G作為具體示例(如圖1所示)。給出依據(jù)鄰接矩陣運算過程中的節(jié)點與編號對應關系，如圖2(a)。

圖1 有向圖

1.1.2 分支編號的研究方法

構造關聯(lián)矩陣，將各分支按分支的始節(jié)點和終節(jié)點的排列次序排列，設m×n階矩陣B(G)= (bij)m×n為圖G的關聯(lián)矩陣。由此可構造行向量函數(shù):分支行向量E=(e1，e2，…，en)，分支始節(jié)點行向量V1=(v11，v12，…，v1n)，分支末節(jié)點行向量V2= (v21，v22，…，v2n)。依次排列可得ei=(v1i，v2i)，通過行向量運算生成關聯(lián)矩陣，按節(jié)點的有序偶對關系為分支編號，編號從1開始，直到所有的有序偶對關系均編號為止，如圖2(b)所示。

圖2 編號算法流程

1.1.3 賦權值的研究方法

風網(wǎng)解算的結果主要指井下所有分支巷道的參數(shù)(權值)，反映通風網(wǎng)絡圖中節(jié)點和分支的屬性值，依據(jù)賦權圖的概念［12］，對于通風網(wǎng)絡N所具有的權函數(shù)，同理可按照分支E中元素的排列次序進行排列，相應的行向量可轉換為

將上述各行向量按順序排列可得到fi=ei= (v1i，v2i)，經(jīng)向量運算后生成關聯(lián)矩陣，對應于分支E中的所有節(jié)點坐標賦值，形成多對一形式。最終以向量和矩陣的形式反映礦井通風網(wǎng)絡圖的結構及相應的權函數(shù)，如圖3。

圖3 賦權算法流程

1.2 算法描述

1.2.1 算法1——編號

在研究分支和節(jié)點之間的拓撲關系基礎上，并結合深度優(yōu)先搜索的算法［15-18］，通過對圖使用遍歷算法可以獲得圖的結構信息。使用Visual C++6.0標準模板庫中的類模板vector容器類，定義了分支類和節(jié)點類2個容器類，分別用于存儲所有分支信息和每一條分支中包含的所有結點信息。

程序算法如下:

Step 1循環(huán)遍歷網(wǎng)絡圖中所有的分支(E)和結點(V)，給定網(wǎng)絡圖中所有分支的結點出現(xiàn)次數(shù)(T)，結點坐標(C)，分支編號(Enum)，結點編號(Vnum)，始節(jié)點(V［begin］)，末節(jié)點(V［end］);

Step 2

for所有分支結點

Step 3

for所有分支結點

Step 4

for分支所有結點

對所有分支中出現(xiàn)兩次以上的節(jié)點進行編號，編號從2開始依次增加;

1.2.2 算法2——賦權值

通過相關計算求解，可得到2張數(shù)據(jù)表(即分支節(jié)點編號數(shù)據(jù)表和解算結果數(shù)據(jù)表)。對網(wǎng)絡圖中各分支的所有節(jié)點賦權值時，以分支編號作為公共字段，按對應關系進行相應鏈接，以空行作為一條分支賦值的結束點，形成多對一的對應關系。

算法如下:

Step 1新建一個表文件(File3)用于存儲賦值后的信息，給定通風網(wǎng)絡解算結果數(shù)據(jù)表(File1)和分支節(jié)點編號的數(shù)據(jù)表(File2)，

Step 2定義變量:

CString CalcResult;∥ File1計算結果值(分支編號，風阻，風量，風壓)

CString NCoord;∥節(jié)點坐標值(x，y，z，始末節(jié)點編號，分支編號)

CString DataLink;∥每個節(jié)點鏈接后的結果值(x，y，z，始末節(jié)點編號，分支編號，風阻，風量，風壓，…)

Step 3循環(huán)遍歷File1的數(shù)據(jù)，

讀取一行File1.CalcResult;

讀取一行File2.NCoord;

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

Step 5循環(huán)遍歷File2的數(shù)據(jù)，繼續(xù)讀取下一行File2.NCoord;

Step 6如果File2.NCoord不為null，執(zhí)行Step3;否則，執(zhí)行Step2;

Step 7結束。

2 實例應用與分析

為了驗證該方法在礦井通風網(wǎng)絡解算的三維可視化的可行性，現(xiàn)以國內(nèi)某礦山的實際數(shù)據(jù)為實例。該礦山礦體比較分散，各采區(qū)的布置相對較遠，現(xiàn)主要開采范圍達36 km2，開采高差范圍近900 m，從2 350 m到深部1 360 m共形成了13個主要開采中段，面對如此復雜的礦井，所建立的通風網(wǎng)絡圖涉及到成百上千的分支和節(jié)點數(shù)據(jù)，為了降低工作量和減少人為失誤，同時保證解算結果的準確和實現(xiàn)三維可視化的真實性，須解決網(wǎng)絡數(shù)據(jù)信息批量處理的問題，對巷道和節(jié)點數(shù)據(jù)進行編號提取、整理、轉換、合并及顯示。如圖4所示為3D Mine軟件平臺下建立的需要參與編號和賦權運算的三維網(wǎng)絡圖。

圖4 3D M ine礦井通風三維網(wǎng)絡

2.1 礦井通風網(wǎng)絡解算數(shù)據(jù)表的算法驗證

調(diào)用算法1，完成對圖4中所有分支和節(jié)點的自動編號，并作為風網(wǎng)解算的基礎數(shù)據(jù);調(diào)用算法2，把風網(wǎng)解算結果數(shù)據(jù)賦值給圖4中對應的分支和節(jié)點，同時生成一張完整的礦井通風網(wǎng)絡解算數(shù)據(jù)表，如表1所示。

(1)表1中前3項字段是分支巷道的所有結點坐標值(x、y、z)，定位了礦井巷道的空間關系;算法1，增加“始末節(jié)點編號”字段，對每一條分支的始、末節(jié)點編號，增加“巷道編號”字段對所有分支巷道進行自動編號并按升序排列;算法2，為所有分支巷道中包含的所有結點都被賦于了一組權值。本算法達到了預定目標。

(2)從表1中可看出每一條分支可以由2個或以上結點自動生成，無論每條分支巷道中有多少個結點，都只確定唯一的始、末節(jié)點;如表中巷道編號為50的分支有6個結點坐標值，此處從圖7中可看出是一個環(huán)形的井底車場，為了保證本算法所生成的數(shù)據(jù)表格具有更好的可移植性、不失真，對此繞道中的增加結點坐標均參與賦權運算。

(3)各個分支巷道之間用空行分隔，使得各分支相互獨立，賦權后可允許關聯(lián)分支的相同節(jié)點賦于不同的權值，如表1中的巷道編號51和52分支，51的始節(jié)點編號99是52的始節(jié)點編號99，但其后的參數(shù)并不相同，出現(xiàn)了同一個節(jié)點有2種權值，因為該節(jié)點是交叉點，分別屬于3條相對獨立的分支，根據(jù)通風網(wǎng)絡節(jié)點風量平衡的原理，與該節(jié)點相鄰的上下各邊的風量滿足節(jié)點風量平衡定律，即節(jié)點相鄰的上邊風量之和等于下邊的風量之和，節(jié)點參數(shù)的重復并不影響關聯(lián)分支風路的解算值，因此本算法符合通風解算的要求。

2.2 礦井通風三維網(wǎng)絡圖的算法驗證

利用3D Mine軟件平臺，導入表1所有數(shù)據(jù)，同時設置其“顯示描述值”菜單功能，操作者能夠依據(jù)“瀏覽屬性值”方式顯示表1中的任一參數(shù)值。

(1)圖5(a)顯示礦井進風口、出風口和漏風口的編號均為“1”，依據(jù)礦井通風網(wǎng)絡的解算原理，從礦井出風口到進風口，經(jīng)過地表大氣的分支為偽分支，該分支的風阻為零，并不是網(wǎng)路中的真實巷道，其相應的節(jié)點為偽節(jié)點。

(2)圖5(b)為始、末節(jié)點的編號，每個節(jié)點可以和1個分支或多個分支相關聯(lián)，除了進、出風口外，其余每個節(jié)點既是后1條分支的始節(jié)點，又是前1條分支的末節(jié)點;可看出環(huán)形井底車場的節(jié)點編號97和99對應的2條分支是并聯(lián)分支;針對并聯(lián)、角聯(lián)等情況，在分支中增加1個節(jié)點的方式使得其中1條分支變換為2段分支或者是在分支中加入部分結點參與賦權運算，因為如果按2點控制1條直線的方式，此處并聯(lián)分支會出現(xiàn)重合顯示的錯誤判斷。

表1 礦井通風網(wǎng)絡數(shù)據(jù)

(3)圖5(c)為分支的編號順序具有隨機性，程序運算時，按照深度優(yōu)先搜索的算法有序地沿著圖中的分支訪問圖中所有的節(jié)點，通過對圖進行遍歷來獲得圖的結構信息，但是，由于網(wǎng)絡圖中存在復雜的串、并聯(lián)和角聯(lián)的原因，因而分支編號順序會存在一定的隨機性。

(4)圖6顯示了每段巷道的風量值，通過執(zhí)行算法2為各條分支賦權值，其他如風扇機功率、風機型號、軸功率、巷道凈斷面積、巷道長度等，均可以此向量形式表示;如果把已建立的三維巷道實體模型、相關通風構筑物和風流方向導入圖6中，即生成圖7所示的礦井通風網(wǎng)絡解的三維可視化效果圖，顯示時可按照不同顏色對各個巷道中段分別著色，圖中清晰、直觀地顯示了2個中段的風量值和堅井、斜井的風量值。

(5)對照圖6和圖7，在巷道編號為70位置處安設輔助風機，該輔助風機的風量是解算前按照理論需風量初擬的，風機安設在繞道中，而在與繞道相并聯(lián)的運輸巷道中設置2道自動風門，為了減小漏風，提高通風網(wǎng)絡解算的精確性，此處作了簡化處理，因此算法中并沒有對此編號和賦值，符合風網(wǎng)解算的實際情況。

(6)從圖7風路中的風量值可以看出多條巷道交匯點處，既有風流流入，又有風流流出，符合流入流出交匯點的風量之和為零的風量平衡定律，并沒有出現(xiàn)風量混亂的情形，證明本算法的結果是正確的。

通過以上圖表對照，并結合礦山實際情況分析，算法1和算法2的運算結果符合礦井通風網(wǎng)絡解算的映射關系，顯示效果達到預定的目標，實現(xiàn)了礦井通風網(wǎng)絡解算的三維可視化。

3 結論

(1)算法是依據(jù)圖論和礦井通風理論編寫的，所得結果中的礦井進出風口的編號、始末節(jié)點編號和分支編號符合通風網(wǎng)絡解算時基礎數(shù)據(jù)的要求;賦權運算的結果與預定目標一致。

圖5 礦井通風網(wǎng)絡的拓撲結構

圖6 基于風量顯示的局部放大礦井通風系統(tǒng)圖

圖7 加載巷道實體模型后局部放大的礦井通風系統(tǒng)圖

(2)算法的結果不僅反映于圖中，而且能夠自動生成數(shù)據(jù)表的形式;圖表結合有利于更好服務于礦山企業(yè)的管理。

(3)通過對分支節(jié)點的三維點線坐標進行運算，能夠與實際巷道情況相對應，更有利于通風網(wǎng)絡解算的準確性和三維可視化模擬的真實性。

(4)主要針對復雜通風網(wǎng)絡圖中的大量數(shù)據(jù)難以手工處理的問題，采用兩步算法來解決，避免了煩瑣、重復的數(shù)據(jù)處理和轉換，減少勞動時間，提高勞動效率。

(5)引入圖論算法，實現(xiàn)了數(shù)據(jù)的圖形化，并通過實際例子驗證了本方法的可操作性及可靠性。

［1］ 林建廣，蔣仲安.具有網(wǎng)絡圖繪制與風機優(yōu)選功能的礦井通風網(wǎng)絡解算系統(tǒng)［J］.礦冶工程，2007，6(3):20-23.

［2］ 汪 亮，張 峰，朱華新，等.三河尖礦通風系統(tǒng)網(wǎng)絡圖的自動繪制研究［J］.礦業(yè)工程，2009，8(4):60-62.

［3］ 吳 兵，盧本陶，水林娜.由通風網(wǎng)絡結構數(shù)據(jù)自動生成通風網(wǎng)絡圖研究［J］.中國安全生產(chǎn)科學技術，2005，12(6):25-28.

［4］ 吳 超，李孜軍，黃沛生，等.極復雜礦井通風網(wǎng)絡分析實踐與經(jīng)驗［J］.金屬礦山，2003(10):50-53.

［5］ 楊志強，趙千里，等.礦井通風三維仿真模擬理論與礦用空氣幕理論［M］.北京:冶金工業(yè)出版社，2008:104-105.

［6］ 劉云崗，魏連江，李曉峰.通風網(wǎng)絡拓撲關系的自動生成［J］.礦業(yè)工程，2009，2(1):47-49.

［7］ 段 東.礦井通風系統(tǒng)拓撲關系自動生成的研究及風網(wǎng)解算［D］.遼寧工程技術大學，2006.

［8］ 郝憲杰，魏連江，張宏捷.通風網(wǎng)絡拓撲關系的自動建立研究［J］.煤礦安全，2008，4(11):18-20.

［9］ 賈進章，劉 劍，耿曉偉.礦井通風仿真系統(tǒng)數(shù)學模型［J］.遼寧工程技術大學學報，2003，8(22):88-90.

［10］ 李雨成，劉 劍，賈廷貴.MVSS3.0在礦井通風系統(tǒng)改造中的應用［J］.煤礦安全，2007(4):21-22.

［11］ 柳明明.Ventsim三維通風仿真系統(tǒng)在金屬礦山的應用［J］.金屬礦山，2010(10):120-123.

［12］ 方富貴.圖論的算法和應用研究［J］.計算機與數(shù)字工程，2012(2):115-118.

［13］ 陳梅芳，丁德馨，張傳飛.基于MATLAB的礦井通風網(wǎng)絡圖的矩陣表示及電算方法［J］.礦業(yè)研究與開發(fā)，2007，12(6):65-67.

［14］ 甘 煥，趙嵩正，高 娜.一種雙代號網(wǎng)絡圖節(jié)點編號方法［J］.陜西理工學院學報:自然科學版，2007，3(1):60-63.

［15］ 季現(xiàn)偉.基于三維條件的礦井通風網(wǎng)絡解算系統(tǒng)研究［D］.昆明:昆明理工大學，2012.

［16］ 劉 萍，馮桂蓮.圖的深度優(yōu)先搜索遍歷算法分析及其應用［J］.青海師范大學學報:自然科學版，2007(3):41-44.

［17］ 周 泰.圖的深度優(yōu)先遍歷算法及運用［J］.電腦編程技巧與維護，2011(16):93-94.