環(huán)狀給水管網(wǎng)自動生成樹的研究

趙星明，王 萱

(山東農(nóng)業(yè)大學(xué)水利土木工程學(xué)院，山東 泰安 271018)

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

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

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

1 環(huán)狀給水管網(wǎng)生成樹的方法

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

設(shè)T為G的一棵生成樹，管段eij的權(quán)為Wij，則T的權(quán)定義為:

(1)

所有生成樹中權(quán)重最小的是G的一棵最小生成樹，可以采用Kruskal等算法求得，剪枝環(huán)狀管網(wǎng)生成一棵最小樹。

2 Kruskal算法生成樹的實現(xiàn)

2.1 Kruskal算法的基本思想

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

2.2 Kruskal算法的實現(xiàn)方法

根據(jù)環(huán)狀給水管網(wǎng)圖構(gòu)建帶權(quán)的鄰接矩陣M，鄰接矩陣M由4個元素組成，其格式為：

管段編號，管段的起點，終點，管段權(quán)值

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

圖1 環(huán)狀給水管網(wǎng)圖Fig.1 The looped pipe network of water supply

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

表1 鄰接矩陣格式及數(shù)據(jù)Tab.1 Fortmat and data of adjacency matrix

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

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

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

對于圖1管網(wǎng)圖按照表1的鄰接矩陣，用Kruskal算法構(gòu)建最小生成樹T，則會完全保留權(quán)重為1的管段1、2、3、10和12，刪除權(quán)重為2的部分管段6、7、9、11。得到的生成樹T的管段集合M={1，2，3，10，12，4，5，8}，節(jié)點集合V與管網(wǎng)圖G相同。若對得到的生成樹不是很滿意，可修改管段的權(quán)重，也可增加管段權(quán)重的級數(shù)為3級或更多，權(quán)值改為1、2和3，把最想刪除的管段權(quán)重設(shè)置為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 ‘讀取管網(wǎng)圖的節(jié)點總數(shù)和管段總數(shù)

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, "管段編號", "起始節(jié)點", "終止節(jié)點", "管段權(quán)重"

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

自定義函數(shù)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平臺上搜索環(huán)狀管網(wǎng)生成樹的實現(xiàn)及算例研究

3.1 工程條件

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

表2 某市區(qū)供水管網(wǎng)鄰接矩陣Tab.2 The adjacency matrix of water supply pipe network

圖2 某市區(qū)供水管網(wǎng)現(xiàn)狀圖Fig.2 The water supply pipe network

3.2 在AutoCAD平臺上生成樹

首先使用前面的Kruskal算法程序，讀取某市區(qū)供水管網(wǎng)的鄰接矩陣，即表2的數(shù)據(jù)，判斷管段的2個節(jié)點的根結(jié)點是否相同，若相同則為應(yīng)刪除的連枝。根據(jù)歐拉公式，本算例有18個環(huán)，所以產(chǎn)生的連枝數(shù)也為18，具體刪除的管段見表3。

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

然后在AutoCAD平臺上遍歷搜索環(huán)狀給水管網(wǎng)的所有管段，用選擇集的方法識別管段編號，若遍歷的管段為表3中應(yīng)刪除的管段，則修改該管段到“0”圖層，也可直接刪除，非常直觀地實現(xiàn)了把環(huán)狀管網(wǎng)自動生成樹，生成的樹狀管網(wǎng)如圖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 '直線中點坐標(biāo)，要計算

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

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 某市區(qū)供水管網(wǎng)自動生成樹Fig.3 Automatic spanning tree of the water supply pipe network

groupCode = gpCode

dataCode = dataValue

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

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 "節(jié)點編號錯誤" '可能沒有編號，或者編號字體太大或者矩形選取框太小等原因

Exit For

End If

End If

Next Obj

End Sub

4 結(jié) 語

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

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

□

參考文獻：

[1] 趙星明,王 萱.環(huán)狀給水管網(wǎng)關(guān)聯(lián)矩陣的建立[J].中國農(nóng)村水利水電,2012,(11):129-131,135.

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

[3] 唐策善,李龍澍,黃劉生.數(shù)據(jù)結(jié)構(gòu)[M]. 北京：高等教育出版社,2000:123-135.

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

[5] 趙星明,王 萱.基于擴展數(shù)據(jù)的給排水管網(wǎng)拓撲關(guān)系的構(gòu)建[J].山東農(nóng)業(yè)大學(xué)學(xué)報(自然科學(xué)版),2012,43(4):549-554.

[6] 宋 芹,趙星明,艾典勝.輸水管道水錘分析與防護技術(shù)[J].山東農(nóng)業(yè)大學(xué)學(xué)報(自然科學(xué)版),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.