用最長路徑法自動生成通風網絡圖
吳 兵,盧本陶,水林娜
(中國礦業大學,北京100083)
摘 要:通風網絡圖是礦井通風管理的重要圖件之一,也是進行礦井通風係統模擬、網絡解算、通風係統優化的基礎資料。根據通風網絡圖的特點,介紹了一種由通風網絡結構數據自動生成通風網絡圖的方法,並進行了開發實現和實踐應用。
關鍵詞:礦井通風;最長路徑算法;網絡圖;通風網絡結構數據;自動生成
中圖分類號:TD724 文獻標識碼:A 文章編號:1003-496X(2006)
Automatic Generation of Ventilation Network Graph by Longest Path AlgorithmWU Bing,LU Bentao,SHUI Lin-na(
0 引 言
礦井通風是保證礦井正常運轉的決定性因素,是礦井各生產環節中最基本的一環。礦井通風係統是由縱橫交錯的井巷構成的一個複雜係統。用圖論的方法對通風係統進行抽象描述,把通風係統變成一個由線、點及其屬性組成的係統,稱為通風網絡。
礦井通風網絡圖是用直觀的幾何圖形來表示通風係統的圖形,能清楚地反映風網的結構和風流的流動特性,是進行各種通風計算的基礎。礦井通風係統縱橫交錯,構成1個複雜的網絡,在對礦井通風係統進行03manbetx
計算之前,需要首先畫出通風網絡圖。由於通風網絡圖隻反映風流方向及節點與分支間的相互關係,節點位置與分支線的形狀可以任意改變,因此對於同樣的通風網絡結構數據可以畫出無數個通風網絡圖。
但由於礦井通風網絡一般都比較複雜,巷道數目繁多,礦井通風網絡圖的繪製是一項十分繁瑣的工作。靠手工繪製不僅效率低、速度慢、工作量大,易於出錯,而且還需要不斷調整,美觀協調方麵往往不盡人意,修改也非常不方便。現有的通風網絡解算軟件大多是文本方式的數據處理,沒有跟通風網絡圖進行很好的對應。這些缺點極大地製約了礦井通風網絡解算軟件的推廣使用。
1 自動生成通風網絡圖方法
通風網絡圖包含了2類數據:一類是圖的結構數據即分支與節點的連接關係拓撲關係及分支的擴展屬性數據;一類是物理數據即網絡圖的節點坐標和分支形狀等也就是網絡圖的視覺效果。由於通風網絡結構數據中隻包含了分支與分支、分支與節點的拓撲關係,沒有包含位置坐標關係。自動生成通風網絡圖實質就是根據通風網絡結構數據中的這種拓撲關係來確定每個節點的位置及每條分支的形狀,生成美觀實用的通風網絡圖。對於1個給定的通風網絡結構數據是唯一的,但圖形數據可以千變萬化。
通風網絡圖的繪製原則一般如下:
(1)用風地點並排布置在網絡圖中部,進風節點位於其下邊;回風節點在網絡圖的上部,風機出口節點在最上部。
(2)分支方向基本都應由下至上、分支間的交叉盡可能少、網絡圖總的形狀基本為“橢圓”形。
(3)合並節點,某些距離較近、阻力很小的幾個節點,可簡化為1個節點。
2 由最長路徑法生成通風網絡圖
2.1 最長路徑法算法
一個網絡中,網絡中任意節點j的最長路徑為:流入節點j的所有分支的始節點i中最長路徑長度者加一,其計算公式為:對於一個有n個節點的網絡:
JnLen〔j〕=0,j=1JnLen〔j〕=max{JnLen〔i1〕, JnLen〔i2〕,…JnLen〔in〕} + 1,j=2,……,n。
式中 JnLen〔j〕———節點j的最長路徑長度; JnLen〔i〕———為流入節點j的所有分支始節點i的最長路徑長度。
示例如下:如圖1所示的通風網絡圖中節點4到節點1的最長路徑長度為:
JnLen〔4〕=max{JnLen〔3〕}+1;JnLen〔3〕=max{JnLen〔2〕, JnLen〔1〕}+1;JnLen〔2〕= max{JnLen〔1〕}+1, JnLen〔1〕=0。所以JnLen〔4〕=JnLen〔3〕+1=JnLen〔2〕+1+1= JnLen〔1〕+1+1+1 = 3,同時把節點3保存為節點4的最長路徑的前節點,節點2保存為節點3的最長路徑的前節點,節點1保存為節點2的最長路徑的前節點,所以節點4到節點1的最長路徑長度為3,所經過的節點為4,3,2,1。
具體算法流程圖如圖2所示。
2.2 通風網絡圖的設置
同一個通風網絡結構數據,可以生成無數個拓撲結構相同的通風網絡圖,因此,為了自動生成網絡圖,用戶需要根據自己的要求設置網絡圖的圖幅的方向、圖幅的大小及圖形形狀。網絡圖的整體方向指的是大部分分支的方向。圖幅範圍指的是整幅圖所占的大致範圍。由於通風網絡圖中分支形狀可分為2種,一是直線,二是圓弧。若為直線時,可由始末節點確定分支的位置。若為圓弧時,還因根據曲率角度(即圓弧的弦的中點與始節點所組成的線段與弦之間的夾角)來確定圓弧上的另一點的坐標。同時還可根據用戶的需要使生成圖的交叉點少。
圖2 節點最長路徑算法流程圖
2.3 最長路徑法確定節點位置和分支形狀
(1)進風節點和回風節點的布置。通風網絡圖是一個閉合的有向圖,根據通風網絡結構數據中的虛擬分支(指虛擬的用於連接大氣節點的巷道)信息可以找出通風網絡圖中的進風節點和回風節點。因為前麵通風網絡圖設置中已經確定了通風網絡圖的方向和圖幅大小,根據方向可以確定進回風節點位於圖幅的哪側,根據圖幅大小和進回風的節點總數求出節點之間的寬度可以確定進回風節點的具體位置。
(2)其它節點的布置。通風網絡圖是1個閉合的有向圖,在進回風節點的位置確定後,從進風口和回風口中各任選1節點。根據前麵通風網絡圖設置中的曲率角度可以確定由這兩個節點所組成的圓弧。用最長路徑法找出這兩個節點間的最長路徑中所包含的節點,使這些節點按次序等弧長的位於這兩個節點所組成的圓弧中,其分支形狀與兩節點間的分支形狀一致。這樣可以確定這兩個節點之間最長路徑中所包含的節點位置及分支形狀。當某一分支確定了位置和形狀後,把這分支設置成已繪製完成的標誌,後麵的節點求最長路徑時將不考慮此分支。當某一節點的所有流進該節點的分支都已繪製完成時,把該節點置為進風節點數組中;當某一節點的所有流進該節點的分支都已繪製完成時,把該節點置為進風節點數組中;從進風節點數組和回風節點數組中各任選一節點,根據最長路徑法來確定這兩個節點最長路徑中所包含的節點的位置和形狀。直到所有節點都計算完成。
2.4 一些特殊分支的處理
(1)並聯分支的處理。用最長路徑法求出兩節點間的最長路徑時,得到的是所經過的分支的節點序列。再根據節點來確定分支時,如是並聯分支,應進行如下處理:如果並聯分支總數為奇數時,中間的分支設成直線,其餘分支設成弧線,並對稱的均勻排列在兩側;如果並聯分支總數為偶數時,所有分支都設成弧線,並對稱的均勻排列在兩側。經過這樣的處理,並聯分支不相互重疊,同時形狀又美觀。
(2)虛擬分支的處理。虛擬分支指虛擬的用於連接大氣節點的分支,是實際中不存在的巷道。由於虛擬分支的連接,整個網絡圖成了一個閉合的圖。
而最長路徑法確定節點的位置時,網絡中不能存在回路,所以在先建立拓撲關係時,虛擬分支不能包括在內。當其它分支繪製完成時,才處理虛擬分支。
由於當所有節點的位置都確定了時,虛擬分支的始末節點的位置也已確定,可根據凸率角度確定出虛擬分支的形狀。
(3)分支交叉的處理。為了使網絡圖更為美觀實用,可以對分支進行交叉判斷,通過修改分支的曲率來使分支之間的交點少。
2.5 通風網絡圖的編輯修改功能
為方便用戶對計算機自動生成的通風網絡圖進行修改和美化,程序提供了編輯修改通風網絡圖並實現網絡解算的功能。用戶可以方便的修改分支曲率,移動節點。當移動節點時,程序會自動搜索出與此節點相關的分支,所有與該節點有關的分支都按原有的曲率進行改變。
基於上述原理,筆者用VC開發出了自動生成通風網絡圖的程序。通過網絡圖的設置,用戶可以確定網絡圖的大概形狀。運用最長路徑法能方便的對每個節點進行定位,同時使整幅圖的形狀呈“橢圓形”,同時軟件具有方便強大的編輯修改功能,用戶對自動生成的網絡圖稍做修改,就可調整出符合自己需要的網絡圖,並進行通風網絡解算。
3 結 論
由通風網絡結構數據自動生成通風網絡圖並進行通風網絡解算,自動將解算結果在網絡圖上標誌出來,可以改變傳統的設計方法,簡化設計過程,節約手工勞動及工作時間,方便用戶的操作,提高了自動化程度,極大的提高勞動效率,從而使科技人員能更好的把精力放在方案的設計上。
參考文獻:
〔1〕 周心權,吳 兵.礦井通風基本概念的理論基礎03manbetx
〔J〕.中國礦業大學學報,2003(2).
〔2〕 王德明,周福寶.基於WINDOWS的礦井通風網絡解算軟件的研製〔J〕.中國礦業大學學報,2000(1).
〔3〕 高紅波,王躍明.礦井可視化通風係統的研究〔J〕.太原理工大學學報,2004(3).
〔4〕 黃力波,劉彥偉.礦井通風網絡圖〔J〕.焦作工學院學報(自然科學版),2002(1).
〔5〕 李湖生.由通風網絡結構數據自動生成曲線網絡圖〔J〕.煤礦安全,1998(1).
作者簡介:吳 兵(1967-),男,山西陽泉人,中國礦業大學(北京)副教授,博士,研究方向主要有礦山災害防治、礦井通風技術、礦山災害仿真和計算機應用等,已在國內外核心刊物上發表文章30餘篇。
