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

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

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

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

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

1 研究方法和算法描述

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

1.1 研究方法

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

根據(jù)圖的鄰接矩陣，可將分支的所有節(jié)點按一定的次序排列。設(shè)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é)點與編號對應(yīng)關(guān)系，如圖2(a)。

圖1 有向圖

1.1.2 分支編號的研究方法

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

圖2 編號算法流程

1.1.3 賦權(quán)值的研究方法

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

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

圖3 賦權(quán)算法流程

1.2 算法描述

1.2.1 算法1——編號

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

程序算法如下:

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

Step 2

for所有分支結(jié)點

Step 3

for所有分支結(jié)點

Step 4

for分支所有結(jié)點

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

1.2.2 算法2——賦權(quán)值

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

算法如下:

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

Step 2定義變量:

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

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

CString DataLink;∥每個節(jié)點鏈接后的結(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結(jié)束。

2 實例應(yīng)用與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

圖5 礦井通風網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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