環狀給水管網自動生成樹的研究

趙星明，王 萱

(山東農業大學水利土木工程學院，山東 泰安 271018)

城鎮給水管網的投資占整個給水工程比例較大，因此其最優化設計一直受到重視。最優化設計的前提是對環狀給水管網的管段流量確定初分配方案，若給水管網的規模較小，可通過分析控制點位置以及大用戶的分布，確定主干管供水路線，較合理地分配管段流量。對于中等以上的城市，僅依靠主觀判斷分配給水管網的管段流量會造成較大誤差，不能滿足用戶的實際用水量，也不能實現最優化設計。

初始流量分配可以采用最小平方和的流量分配法和截面法等，最小平方和法分配的管段流量比較均勻而使管道主次不分，截面法分配的管段流量不能滿足節點流量平衡的條件。若采用圖論理論把環狀給水管網中的若干條管段刪除，生成樹后再進行初始流量分配，可符合節點流量連續性方程。把管網圖化為生成樹，須按照歐拉公式刪除與基環數一樣多的管段來破壞所有的環，并保持原管網的連通性，對一個規模較大的環狀給水管網，僅靠主觀判斷生成樹需花費很多時間。

本文根據Kruskal算法對環狀管網生成樹問題進行研究，利用帶權重的鄰接矩陣得到了最小生成樹，并在AutoCAD平臺上運用深度優化搜索方法，實現了刪除連枝自動生成樹，可方便管段初始流量的計算，提高環狀給水管網的設計計算效率和準確度。同時，通過人工干預保留一些管段流量易確定的連枝，以優化環狀給水管網布局。

1 環狀給水管網生成樹的方法

一個連通管網圖G(V，E)，由N節點和M管段構成，V和E為節點和管段的集合，根據圖論理論計算其內環數L=M-N+1。若想把G(V，E)生成一棵樹需刪除與內環數相等的L條管段，刪除的管段稱為連枝，保留下來的管段稱為樹枝。在環狀給水管網的工程設計中，連接管和末端管主要承擔本段沿線流量的分配，流量容易確定，可作為連枝刪除掉，一部分管段流量不易確定的主干管和轉輸管等作為樹枝保留下來，這些樹枝的管段流量可在生成樹管網圖上通過節點連續性方程求出。為了保留重要的主干管和轉輸管，把管網圖G(V，E)轉化為一個加權圖G(V，E，W)，W為管段權重Wij的集合，在此假設想保留下來管道的Wij=1，其權重最小，而其他管道的Wij>1，管道的權重越大越容易被刪除。需注意的是權重大于1的管道比需刪除的管段數L要多，所以權重大于1的管道不會全部刪除，也要保留一部分，哪些管道保留下來或被刪除掉是根據Kruskal算法確定的。

設T為G的一棵生成樹，管段eij的權為Wij，則T的權定義為:

(1)

所有生成樹中權重最小的是G的一棵最小生成樹，可以采用Kruskal等算法求得，剪枝環狀管網生成一棵最小樹。

2 Kruskal算法生成樹的實現

2.1 Kruskal算法的基本思想

含有n個節點的管網連通圖G(V，E，W)和其生成樹T的節點V集合相同，定義生成樹T(V，E，W)的初態為空集，即生成樹只是由n個節點構成而無任何邊的n個非連通圖T=(V，{φ}，{φ})，因節點之間沒有管段，故每個節點自成1個連通分量。先對環狀管網圖G中的管段進行分析和分類，人工賦予不同的權重。對管網圖G中的所有管段進行第1次遍歷，若遍歷到的管段的權重最小，即為保留管段，則將此管段直接加入到最小生成樹T中的E集合。再對權重較大的管段進行第2次遍歷，如果管段的2個節點依附于T的2個不同的連通分量，則將此管段加入最小生成樹T中的E集合，同時把2個連通分量連接為1個連通分量；若被遍歷到的2個節點同屬1個連通分量，說明連接此管段后會造成回路，故不連接這2個節點。遍歷所有管段后，可使T只有1個連通分量，便構建了1棵連通的生成樹，可用于管段流量的初分配。

2.2 Kruskal算法的實現方法

根據環狀給水管網圖構建帶權的鄰接矩陣M，鄰接矩陣M由4個元素組成，其格式為：

管段編號，管段的起點，終點，管段權值

以圖1的環狀給水管網為例，其鄰接矩陣保存格式及數據如表1所示，管段1、2、3、10和12的權值最小，屬保留的管段，其他管段按照Kruskal算法刪除連枝以生成樹。

圖1 環狀給水管網圖Fig.1 The looped pipe network of water supply

在使用Kruskal算法對環狀連通管網圖生成樹的實現過程中，根據鄰接矩陣的格式，構建一個加權的2維管段數組Looped(Edge, 4)，分別儲存每個管段的編號、起點、終點和權值這4個元素，Edge為環狀管網的管段編號。還設置一個Root(VertexNum)數組，使用自定義函數Search搜索每個管段的起

表1 鄰接矩陣格式及數據Tab.1 Fortmat and data of adjacency matrix

點和終點所屬的連通分量，VertexNum為節點編號。Root(VertexNum)數組中每個節點VertexNum的初值為0，表示管網的各個節點在不同的連通分量上，遍歷到一條管段后，讀取管段的起點(StartVertex)和終點編號(EndVertex)，用Search自定義函數搜索2個節點所在樹的根結點，也就是在Root(VertexNum)數組中的序號。若StartVertex和EndVertex的根結點不同，表示所對應的管段不在同一連通分量上，則將這條管段存儲在生成樹Tree數組中，并把StartVertex的值賦給終點數組Root(EndVertex)，合并2個節點所屬的連通分量為1個連通分量。

鄰接矩陣的排列順序影響著生成樹過程中連枝的選擇，可以對鄰接矩陣的權值從小到大進行排序，僅遍歷一次便可構建最小生成樹。因在環狀管網生成樹過程中，只有人工干預保留部分管段，所以管段的權值只有1和2，權值為1的管段優先保留下來，權值為2的管段根據生成樹的算法再確定是否保留或刪除，為此可以對鄰接矩陣的權值不進行排序，只是對管段進行2次遍歷，第1次遍歷只把權值為1的管段直接存儲到Tree數組中，然后進行第2遍歷，把權值為2的管段根據Kruskal算法存儲到Tree數組。

用Kruskal算法實現的過程中，首先把鄰接矩陣的元素以文本文件形式保存，程序讀取所有管段的編號、起點、終點和權值到Looped(Edge, 4) 數組，然后根據優化搜索算法判斷每個管段是否在同一連通分量上，最后得到環狀管網圖的最小生成樹，以數組Tree(Edge, 4)的形式存儲并寫入交換格式文件中。

對于圖1管網圖按照表1的鄰接矩陣，用Kruskal算法構建最小生成樹T，則會完全保留權重為1的管段1、2、3、10和12，刪除權重為2的部分管段6、7、9、11。得到的生成樹T的管段集合M={1，2，3，10，12，4，5，8}，節點集合V與管網圖G相同。若對得到的生成樹不是很滿意，可修改管段的權重，也可增加管段權重的級數為3級或更多，權值改為1、2和3，把最想刪除的管段權重設置為3，再通過程序生成最小樹。Kruskal算法的主程序代碼如下：

Option Base 1

Sub main()

Dim Root() As Integer

Dim i As Integer, j As Integer, k As Integer

Dim StartVertex As Integer, EndVertex As Integer

Dim VertexNum As Integer, Edge As Integer

Dim Looped() As Integer, Tree() As Integer

Open ActiveDocument.Path & "in.csv" For Input As #1

Input #1, VertexNum, Edge ‘讀取管網圖的節點總數和管段總數

ReDim Root(VertexNum)

ReDim Looped(Edge, 4)

ReDim Tree(Edge, 4)

For i = 1 To Edge

Input #1, Looped(i, 1), Looped(i, 2), Looped(i, 3), Looped(i, 4)

Next i

Close #1

For i = 1 To VertexNum

Root(i) = 0

Next i

Open ActiveDocument.Path & "out.csv" For Output As #2

Write #2, "管段編號", "起始節點", "終止節點", "管段權重"

For k = 1 To 2

For i = 1 To Edge

StartVertex = Search(Root, Looped(i, 2))

EndVertex = Search(Root, Looped(i, 3))

If (StartVertex = EndVertex) And Looped(i, 4) = 2 Then

Debug.Print Looped(i, 1) '刪除的連枝

End If

If (StartVertex <> EndVertex) And Looped(i, 4) = k Then

Root(EndVertex) = StartVertex

For j = 1 To 4

Tree(i, j) = Looped(i, j)

Write #2, Tree(i, j),

Next j

Print #2,

End If

Next i, k

Close #2

End Sub

自定義函數Search的代碼：

Function Search(Root() As Integer, VertexNum As Integer) As Integer

Dim i As Integer

i = VertexNum

Do While Root(i) > 0

i = Root(i)

Loop

Search = i

End Function

3 在AutoCAD平臺上搜索環狀管網生成樹的實現及算例研究

3.1 工程條件

某市區供水管網如圖2所示。在AutoCAD平臺上，假如所有管道的圖層為“鑄鐵管”，可采用遍歷技術對管段和節點進行自動編號，形成不帶權的3元素鄰接矩陣，以.csv交換格式文件形式保存[1,5]。對需保留的管道，手動選擇并改變其圖層為“Tree”。為表示管道的不同權重，設定“Tree”圖層的線寬為0.35 mm，定義在該圖層的管道權值為1，設定“鑄鐵管”圖層的線寬為0.2 mm，表示管道權值為2。用Excel修改3元素鄰接矩陣，增加每條管道的權重元素，形成帶權的4元素關聯矩陣，即其矩陣元素仍按表1的格式存儲，數據內容見表2。

表2 某市區供水管網鄰接矩陣Tab.2 The adjacency matrix of water supply pipe network

圖2 某市區供水管網現狀圖Fig.2 The water supply pipe network

3.2 在AutoCAD平臺上生成樹

首先使用前面的Kruskal算法程序，讀取某市區供水管網的鄰接矩陣，即表2的數據，判斷管段的2個節點的根結點是否相同，若相同則為應刪除的連枝。根據歐拉公式，本算例有18個環，所以產生的連枝數也為18，具體刪除的管段見表3。

表3 刪除的管段Tab.3 The deleted pipe section

然后在AutoCAD平臺上遍歷搜索環狀給水管網的所有管段，用選擇集的方法識別管段編號，若遍歷的管段為表3中應刪除的管段，則修改該管段到“0”圖層，也可直接刪除，非常直觀地實現了把環狀管網自動生成樹，生成的樹狀管網如圖3所示，程序代碼如下：

Sub 刪除連枝()

Dim Linea As AcadLine

Dim Obj As AcadEntity '遍歷圖形對象用

Dim SSetColl As AcadSelectionSets '定義選擇集集合

Dim ssetObj As AcadSelectionSet '選擇集對象

Dim name As String '選擇集名稱

Dim Textobj As AcadText '寫直線編號用的文字對象

Dim Sp As Variant, Ep As Variant '直線兩端點

Dim Cp As Variant '直線中點坐標，要計算

Dim Lp As Variant, Rp As Variant '為形成一個選擇框，定義左上角和右下角坐標

Dim TextHeight As Single '定義管段編號的文字高度

ReDim Cp(0 To 2) As Double

ReDim Lp(0 To 2) As Double

ReDim Rp(0 To 2) As Double

Dim gpCode(0) As Integer

Dim dataValue(0) As Variant

Dim groupCode As Variant, dataCode As Variant

gpCode(0) = 0

dataValue(0) = "TEXT"

圖3 某市區供水管網自動生成樹Fig.3 Automatic spanning tree of the water supply pipe network

groupCode = gpCode

dataCode = dataValue

TextHeight = 100 '管段編號和節點編號的文字高度

name = "SSET" '選擇集名字

Set SSetColl = ThisDrawing.SelectionSets

On Error Resume Next

For Each Obj In ThisDrawing.ModelSpace

If Obj.ObjectName = "AcDbLine" Then

Set Linea = Obj

Sp = Linea.Startpoint: Ep = Linea.Endpoint

Cp(0) = (Sp(0) + Ep(0)) / 2: Cp(1) = (Sp(1) + Ep(1)) / 2: Cp(2) = (Sp(2) + Ep(2)) / 2 '直線中點，即管段編號插入點

'以下為選擇集定義容錯處理的代碼

If Not IsNull(SSetColl.Item(name)) Then

Set ssetObj = SSetColl.Item(name)

ssetObj.Delete

End If

Set ssetObj = SSetColl.Add(name)

Lp(0) = Cp(0) - TextHeight: Lp(1) = Cp(1) + TextHeight: Lp(2) = Cp(2) '在直線中點形成一個矩形選擇框

Rp(0) = Cp(0) + TextHeight: Rp(1) = Cp(1) - TextHeight: Rp(2) = Cp(2)

ssetObj.Select acSelectionSetWindow, Lp, Rp, groupCode, dataCode

If ssetObj.Count = 1 Then

Set Textobj = ssetObj.Item(0)

If InStr("[12][16][17][21][29][31][34][38][45][46][50][56][58][60][61][62][63][65]", Textobj.TextString) Then

Debug.Print Textobj.TextString

Linea.Layer = "0" '修改連枝到“0”圖層，也可直接刪除

Textobj.Layer = "0"

End If

Else

MsgBox "節點編號錯誤" '可能沒有編號，或者編號字體太大或者矩形選取框太小等原因

Exit For

End If

End If

Next Obj

End Sub

4 結 語

本文根據Kruskal最小生成樹算法的基本思想，對環狀給水管網的鄰接矩陣進行深度優化搜索，篩選出連枝而實現了自動生成樹的目的。在AutoCAD平臺上遍歷所有管段可自動生成帶權重的鄰接矩陣，根據Kruskal算法篩選出應刪除的管段，使環狀管網直觀地生成樹。程序能夠根據每個管段的權重，識別人為保留的管段，生成的樹得到優化，有助于提高大規模環狀管網的設計效率。

在節點流量和連枝流量已知的情況下，滿足節點流量平衡的條件，利用Kruskal算法自動生成樹，使管段流量初分配很容易實現。

□

參考文獻：

[1] 趙星明,王 萱.環狀給水管網關聯矩陣的建立[J].中國農村水利水電,2012,(11):129-131,135.

[2] 嚴煦世,劉遂慶.給水排水管網系統[M]. 3版. 北京:中國建筑工業出版社,2014:79-80.

[3] 唐策善,李龍澍,黃劉生.數據結構[M]. 北京：高等教育出版社,2000:123-135.

[4] 盧有杰, 吳煒煜.C語言高級程序設計[M]. 北京:清華大學出版社, 1991:19-86.

[5] 趙星明,王 萱.基于擴展數據的給排水管網拓撲關系的構建[J].山東農業大學學報(自然科學版),2012,43(4):549-554.

[6] 宋 芹,趙星明,艾典勝.輸水管道水錘分析與防護技術[J].山東農業大學學報(自然科學版),2017,48(1):84-87.

[7] SeijiKataoka,TakeoYamada.Algorithms for the minimum spanning tree problem with resource allocation[J].Operations Research Perspectives, 2016,(3):5-13.