[發明專利]一種通信網絡中單鏈成環的構造算法有效
| 申請號： | 201710172490.7 | 申請日： | 2017-03-22 |
| 公開（公告）號： | CN106973000B | 公開（公告）日： | 2020-02-21 |
| 發明（設計）人： | 孫嚴智;胡勁松;劉宇明;田之俊;劉旋;羅海林;蔣麗瓊;劉問宇;李輝;崔晨 | 申請（專利權）人： | 云南電網有限責任公司 |
| 主分類號： | H04L12/44 | 分類號： | H04L12/44;H04L12/437 |
| 代理公司： | 北京弘權知識產權代理事務所(普通合伙) 11363 | 代理人： | 逯長明;許偉群 |
| 地址： | 650011*** | 國省代碼： | 云南;53 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 通信 網絡 中單鏈成環 構造 算法 | ||
1.一種通信網絡中單鏈成環的構造算法，將所述通信網絡的拓撲表示為G(V,E)，其中，節點集V為拓撲G中所有節點的集合，邊集E為拓撲G中所有邊的集合，其特征在于，
對所述節點集V中的節點進行遍歷計算，在所有節點中篩選出所有第一節點，其中，所述第一節點出發的路徑中至少有一個簡單圈、且至少有一個包含葉子鏈節點的簡單路徑；
定位通信網絡中的單鏈，其中，所述單鏈為從所述第一節點出發、且包含有葉子鏈節點的簡單路徑；
對每一個第一節點進行單鏈成環計算，獲取單鏈成環時所要增設的邊，并將增設的邊增加至拓撲G(V,E)的邊集E中，其中，所述單鏈成環計算包括：獲取第一節點的子拓撲Gi(Vi,Ei)以及子拓撲Gi中的非葉子鏈節點集Vi-f；根據第一節點的子拓撲Gi(Vi,Ei)以及子拓撲Gi中的非葉子鏈節點集Vi-f，計算子拓撲Gi中的終節點集Vi-t；計算包含終節點集Vi-t的無向完全圖的最小生成樹T，所述最小生成樹T的邊為單鏈成環時所要增設的邊；將所述最小生成樹T的邊增加至拓撲G(V,E)的邊集E中；
在所述節點集V中篩選出所有割點；
對每個所述割點進行割點處理，獲取每個所述割點對應的備用邊；
將所有割點對應的備用邊均加入至所述邊集E中。
2.根據權利要求1所述的通信網絡中單鏈成環的構造算法，其特征在于，所述對所述節點集V中的節點進行遍歷計算，在所有節點中篩選出所有第一節點，具體包括，
對所述節點集V中的節點進行遍歷計算，在所有的節點中篩選出所有的環節點，并將篩選出的環節點放入環節點集Vc中，其中，所述環節點為從該節點出發的路徑中有至少一個簡單圈的節點；
對環節點集Vc中的每個環節點進行遍歷計算，在所有的環節點中篩選出第一節點，其中，第一節點為從該節點出發的路徑中至少有一個包含葉子鏈節點的簡單路徑的環節點。
3.根據權利要求2所述的通信網絡中單鏈成環的構造算法，其特征在于，所述對所述節點集V中的節點進行遍歷計算，在所有的節點中篩選出環節點，具體包括，
從所述節點集V中選取一尚未訪問的節點；
對該節點進行遍歷計算；
根據遍歷計算的結果，判斷由該節點出發的路徑中是否存在簡單圈；
若由該節點出發的路徑中存在簡單圈，則將簡單圈上的所有節點均放入環節點集Vc中，并將該節點及簡單圈上的其他節點標記為已訪問；
若由該節點出發的路徑中不存在簡單圈，則將該節點標記為已訪問；
判斷所述節點集V中是否存在一尚未訪問的節點，若存在尚未訪問的節點，則返回至對節點進行遍歷計算的步驟。
4.根據權利要求1所述的通信網絡中單鏈成環的構造算法，其特征在于，根據第一節點的子拓撲Gi(Vi,Ei)以及子拓撲Gi中的非葉子鏈節點集Vi-f，計算子拓撲Gi中的終節點集Vi-t，具體包括，
計算子拓撲Gi中所有節點的集合Vi與子拓撲Gi中所有非葉子鏈節點集Vi-f之間的差集，計算所得的差集為子拓撲Gi中的終節點集Vi-t。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于云南電網有限責任公司，未經云南電網有限責任公司許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201710172490.7/1.html，轉載請聲明來源鉆瓜專利網。
