[發明專利]一種拓撲網絡的兩級分塊方法

有效

• 申請號: 201310648160.2
• 申請日: 2013-12-03
• 公開（公告）號: CN103684942A
• 公開（公告）日: 2014-03-26
• 發明（設計）人: 李寬榮;韓雙立;高勇;趙光俊;劉哲甫;陸通
• 申請（專利權）人: 天津市普迅電力信息技術有限公司
• 主分類號: H04L12/28
• 分類號: H04L12/28
• 代理公司: 天津盛理知識產權代理有限公司 12209
• 代理人: 韓奎勇

技術領域

本發明屬于地理信息系統中海量拓撲數據的分塊操作技術領域，特別是一種拓撲網絡的兩級分塊方法。

背景技術

拓撲網絡分析是地理信息系統領域一個重要的內容，一般的分析算法是對整個拓撲網絡進行遍歷分析，然而在實際生產應用環境中，拓撲網絡往往比較復雜，遍歷整個拓撲網絡不僅占用內存大，而且分析效率低下，目前一種常用的拓撲網絡優化方法是根據連通性對拓撲結構進行分塊，建立一個個的孤島來減少遍歷的數據量，然而，如果整個網絡都是一個連通的整體，這種分塊方式就失去了優勢。

發明內容

本發明的目的在于針對現有技術的不足，提供一種拓撲網絡的兩級分塊方法。

本發明解決其技術問題是采取以下技術方案實現的：

一種拓撲網絡的兩級分塊方法，包括步驟如下：

（1）生成拓撲數據：遍歷圖形中的網絡節點，獲取節點之間的關聯信息；

（2）執行分塊操作：分塊操作共分為一級分塊和二級分塊，一級分塊是根據節點之間的連通性來劃分，二級分塊是根據設定的最大節點數來劃分；

（3）拓撲塊信息的更新與維護：在動態網絡中，節點是允許發生改變的，因此在編輯網絡時要保證相應拓撲塊信息的同步更新；

（4）基于兩級分塊的拓撲分析。

而且，所述步驟（1）生成拓撲數據的具體步驟如下：

①遍歷整個網絡，獲取節點之間的雙向關聯關系；

②將節點之間的所有關系存儲到內存數據結構節點關系表中，另外，為每一個節點創建狀態標識信息并存儲到數據結構節點狀態表中，并設定初始值為：未檢測狀態；

③創建執行分塊操作所需要的變量：

一級塊號，初始值為1，

二級塊號，初始值為1，

二級塊節點數目，

執行分塊操作所需要的變量：

二級塊信息存儲二級塊號與二級塊所包含的節點數目的對應關系信息；塊邊界關系存放二級塊與塊之間的邊界信息；鄰接塊信息存放與當前二級塊相連的其他二級塊的塊號及節點數目的對應關系；

④設置每個二級塊最多包含節點的數目為最大塊節點數目；

⑤判斷節點狀態表中是否存在狀態為未檢測狀態的節點，若存在則以此節點為起點開始探測并對探測到的節點執行分塊操作，，若不存在則表示所有的節點已經探測完成，此時將每個節點的塊信息以及塊與塊之間的邊界信息存儲到數據庫中。

而且，所述步驟（2）執行分塊操作的具體步驟是：

①從節點狀態表中獲取到狀態為未檢測狀態節點，然后將其加入到檢測隊列中，執行步驟②；

②判斷檢測隊列是否為空，若不為空，執行步驟③，若為空，執行步驟④；

③取檢測隊列第一個元素，定為當前節點，并將其從隊列中刪除，執行步驟⑤；

④隊列為空說明當前塊劃分完畢，比較二級塊節點數目與最大塊節點數目的一半的大小，若二級塊節點數目小于最大塊節點數目的一半，說明當前的二級塊包含的節點的數目還不足設定的最大數量值的一半，為了防止產生零碎的小塊，需要將當前的二級塊與相鄰的最小的二級塊進行合并，然后使一、二級塊號的值各自加1，此時保存當前二級塊號及二級塊節點數目到數據結構二級塊信息中，返回繼續判斷節點狀態表中是否有未檢測狀態的節點，若二級塊節點數目大于最大塊節點數目的一半，首先使一級塊號，二級塊號的值各自加1，此時保存當前二級塊號及二級塊節點數目到數據結構二級塊信息，然后執行步驟①，繼續判斷節點狀態表中是否有未檢測狀態的節點；

⑤在節點關系表中查找與當前節點直接相連節點數，執行步驟⑥；

⑥若直接相連節點數大于0，說明存在相連的節點，取出其中一個鄰接節點并查看其狀態，若為未檢測狀態，說明此節點尚未探測，執行步驟⑦；若為已檢測狀態，說明此節點已經被探測過，執行步驟⑧，若直接相連節點數等于0，說明當前節點的相連節點已經處理完成或者不存在相連節點，設置當前節點的狀態為已檢測狀態，設置當前節點的一級塊號和二級塊號分別為當前一級塊號和二級塊號的值，執行步驟②；

⑦比較二級塊節點數目與最大塊節點數目的大小；

A.若二級塊節點數目小于最大塊節點數目，說明當前的二級塊沒有達到個數限制，使直接相連節點數減1，并將當前節點加入隊列中，執行步驟⑥；

B.若二級塊節點數目大于最大塊節點數目，說明當前二級塊已經飽和，不能再加入新的節點元素，執行步驟⑧；

⑧判斷鄰接節點的二級塊號是否與當前二級塊號的值一致；