[發明專利]一種有向循環圖的展示方法及其應用

有效

• 申請號: 201611186459.0
• 申請日: 2016-12-20
• 公開（公告）號: CN106874339B
• 公開（公告）日: 2020-12-08
• 發明（設計）人: 張創偉;孫明東;鮑寧
• 申請（專利權）人: 北京華宇信息技術有限公司
• 主分類號: G06F16/904
• 分類號: G06F16/904;G06F11/34;H04L29/08
• 代理公司: 北京睿邦知識產權代理事務所(普通合伙) 11481
• 代理人: 張麗新

1.一種有向循環圖的展示方法，其中所述有向循環圖包括多個連通有向循環子圖，所述方法包括：

將所述有向循環圖以多叉樹的形式展示，其中多叉樹的根結點表示增加的虛擬訪問入口，根結點的下一級子結點包括所述多個連通有向循環子圖的起始頂點，所述根結點到其下一級子結點的路徑稱為起始路徑，所述起始路徑的權重是所述起始頂點在所述有向循環圖中作為起始頂點出現的次數，所述多叉樹中根結點之外的結點之間的跳轉路徑對應于所述有向循環圖中相應結點之間的路徑，該跳轉路徑的父結點為所述有向循環圖中相應路徑的起點，該跳轉路徑的子結點為所述有向循環圖中相應路徑的終點，所述跳轉路徑的權重對應于所述多叉樹的路徑對應地在所述有向循環圖中出現次數，

“將所述有向循環圖以多叉樹的形式展示”包括以下步驟：

形成起始樹，所述起始樹包括根結點和下一級子結點，所述根結點的下一級子結點為所述有向循環圖中多個連通有向循環子圖的起始頂點，所有起始頂點根據遍歷的順序按照起始頂點所對應的起始路徑的權重從大到小排列，

將所述有向循環圖涉及的每個頂點形成一棵子樹，該子樹包括在以該頂點為終點的所有路徑中權重最大的路徑的起點作為父結點，在統計權重時起始頂點的父結點視為根結點來計算起始路徑的權重，和以該頂點為起點的所有路徑中的終點為子結點，并且所有子結點根據遍歷的順序按所述子結點所對應的路徑的權重從大到小排列，

從根結點開始按照層次優先算法對起始樹進行樹的遍歷，并且適用以下規則中的一個或多個：

遍歷到某個結點時，如果該結點對應的子樹中該結點的父結點是當前所遍歷的樹中該結點的父結點，則將該結點對應的子樹掛到當前所遍歷的樹中；

遍歷到某個結點時，如果該結點對應的子樹中該結點的父結點不是當前所遍歷的樹中該結點的父結點，則判斷該結點是否屬于某個環，如果該結點不屬于某個環，則將當前結點表示為訪問終點，不再對該結點進行進一步的遍歷；

遍歷到某個結點時，如果該結點對應的子樹中該結點的父結點不是當前所遍歷的樹中該結點的父結點，則判斷該結點是否屬于某個環，如果該結點屬于某個環，則將該結點對應的子樹掛到當前所遍歷的樹中的當前結點，繼續對該結點的子結點進行進一步的遍歷，并且任選地將該子樹中該結點的父結點變更為當前所遍歷的樹中該結點的父結點，

所述方法還包括將表示為訪問終點的結點以虛線顯示，而非訪問終點的表示相同訪問頁面的結點以實線顯示。

2.根據權利要求1所述的方法，其中所述權重采用路徑的特征來表示，所述路徑的特征包括選自以下的至少一種：路徑的顏色，路徑的粗細，路徑上的數字，及其組合。

3.根據權利要求1或2所述的方法，其中

對所述多叉樹的每個子結點分別進行樹的遍歷，如果該子結點的父結點到該子結點的路徑的權重及該子結點以下的所有路徑的權重低于閾值，則刪除該子結點及其下的所有子結點，然后展示所述多叉樹的剩余部分。

4.根據權利要求1所述的方法，其中

“判斷該結點是否屬于某個環”的步驟包括：在所有的子樹構成的森林中，從該結點對應的子樹出發，依次向上查找，任選地適用以下規則至少之一：

如果在N次查找之內找到了該結點本身，則該結點就屬于某個環，否則就不屬于某個環；和

如果在N次查找之內找到了起始點，則該結點不屬于某個環。

5.根據權利要求1所述的方法，其中所述遍歷的順序為從左到右或者從右到左。