應用圖論算法實現通風網絡可視化*

2013-04-03 09:33:02王孝東胡乃聯譚海林趙曉杰

金屬礦山 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的運算結果符合礦井通風網絡解算的映射關系，顯示效果達到預定的目標，實現了礦井通風網絡解算的三維可視化。