[發(fā)明專利]一種軟件供應(yīng)鏈的圖布局可視化方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202210168079.3
• 申請(qǐng)日: 2022-02-23
• 公開（公告）號(hào): CN114549691A
• 公開（公告）日: 2022-05-27
• 發(fā)明（設(shè)計(jì)）人: 梁冠宇;周弦
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院軟件研究所;中科南京軟件技術(shù)研究院
• 主分類號(hào): G06T11/20
• 分類號(hào): G06T11/20;G06F8/70
• 代理公司: 南京鐘山專利代理有限公司 32252
• 代理人: 王磊

1.一種軟件供應(yīng)鏈的圖布局可視化方法，其特征在于，包括以下步驟：

步驟1：獲取待布局軟件供應(yīng)鏈的樹形布局；

步驟2：根據(jù)樹形布局中軟件包節(jié)點(diǎn)間的層級(jí)關(guān)系確定各節(jié)點(diǎn)的初始布局位置；

步驟3：依次遍歷各節(jié)點(diǎn)，計(jì)算各節(jié)點(diǎn)所受作用力并根據(jù)作用力計(jì)算移動(dòng)距離以更新各節(jié)點(diǎn)的布局位置；

步驟4：迭代執(zhí)行步驟3，直至達(dá)到迭代終止條件，所得節(jié)點(diǎn)布局為待布局軟件供應(yīng)鏈的最終圖布局。

2.如權(quán)利要求1所述的一種軟件供應(yīng)鏈的圖布局可視化方法，其特征在于，步驟1中，樹形布局中有且僅有一個(gè)根節(jié)點(diǎn)，節(jié)點(diǎn)所代表的軟件包間的依賴關(guān)系通過節(jié)點(diǎn)間的有向邊體現(xiàn)，節(jié)點(diǎn)A代表的軟件包依賴于節(jié)點(diǎn)B代表的軟件包表示為，節(jié)點(diǎn)A與節(jié)點(diǎn)B之間存在由節(jié)點(diǎn)A指向節(jié)點(diǎn)B的有向邊，節(jié)點(diǎn)A稱為節(jié)點(diǎn)B的前驅(qū)節(jié)點(diǎn)。

3.如權(quán)利要求2所述的一種軟件供應(yīng)鏈的圖布局可視化方法，其特征在于，步驟2中，

首先，將樹形布局中的節(jié)點(diǎn)分為普通節(jié)點(diǎn)和公共節(jié)點(diǎn)，僅有一個(gè)前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)為普通節(jié)點(diǎn)，具有多個(gè)前驅(qū)結(jié)點(diǎn)的節(jié)點(diǎn)為公共節(jié)點(diǎn)；

然后，對(duì)樹形布局中的節(jié)點(diǎn)進(jìn)行分層，根節(jié)點(diǎn)為第一層，與根節(jié)點(diǎn)連接的普通節(jié)點(diǎn)為第二層，與第二層普通節(jié)點(diǎn)連接的普通節(jié)點(diǎn)為第三層，依次類推，公共節(jié)點(diǎn)的層數(shù)等于與之相連的普通節(jié)點(diǎn)所在層數(shù)的平均值，樹形布局中的總層數(shù)depth為忽略公共節(jié)點(diǎn)后的節(jié)點(diǎn)最高層數(shù)；

最后，將位于同一層的普通節(jié)點(diǎn)的布局位置初始化為同一位置，

將位于同一層的公共節(jié)點(diǎn)的布局位置初始化為同一位置，

其中，v.pos_x與v.pos_y分別表示第i層普通節(jié)點(diǎn)的x坐標(biāo)和y坐標(biāo)，v_g.pos_x與v_g.pos_y分別表示第j層公共節(jié)點(diǎn)的x坐標(biāo)和y坐標(biāo)，W和H分別為屏幕顯示區(qū)域的寬和高，node_w為節(jié)點(diǎn)的顯示寬度。

4.如權(quán)利要求3所述的一種軟件供應(yīng)鏈的圖布局可視化方法，其特征在于，步驟3中某節(jié)點(diǎn)所受作用力的計(jì)算過程包括：

首先，確定節(jié)點(diǎn)間的理想距離，普通節(jié)點(diǎn)間以及普通節(jié)點(diǎn)與公共節(jié)點(diǎn)間的理想距離k表示為|V|為節(jié)點(diǎn)總數(shù)，area為屏幕顯示區(qū)域的面積；公共節(jié)點(diǎn)間的理想距離k_g表示為|V_g|為公共節(jié)點(diǎn)總數(shù)；

然后，對(duì)于存在連接關(guān)系的公共節(jié)點(diǎn)V_u和節(jié)點(diǎn)V_t，計(jì)算V_u和V_t間的松緊度strength，strength＝1/min(deg(v_u),deg(v_t))，deg(v_u)和deg(v_t)分別為V_u和V_t的度，度表示與該節(jié)點(diǎn)相連的節(jié)點(diǎn)個(gè)數(shù)；

最后，計(jì)算節(jié)點(diǎn)所受作用力，節(jié)點(diǎn)所受作用力包括節(jié)點(diǎn)間的引力和斥力，普通節(jié)點(diǎn)之間以及普通節(jié)點(diǎn)與公共節(jié)點(diǎn)之間的引力、斥力計(jì)算方式相同，為

其中，f_a(d)和f_r(d)分別表示兩節(jié)點(diǎn)間的引力和斥力，d為兩節(jié)點(diǎn)間的幾何距離；

公共節(jié)點(diǎn)間的引力、斥力計(jì)算方式為

其中，f_ag(d)和f_rg(d)分別表示兩節(jié)點(diǎn)間的引力和斥力；

沒有邊連接的節(jié)點(diǎn)間僅計(jì)算斥力。

5.如權(quán)利要求4所述的一種軟件供應(yīng)鏈的圖布局可視化方法，其特征在于，步驟4中利用模擬退火算法控制迭代次數(shù)，在迭代開始前，定義初始系統(tǒng)溫度和最小溫度，然后根據(jù)步驟3中作用力的計(jì)算依次獲取各節(jié)點(diǎn)的移動(dòng)距離以更新節(jié)點(diǎn)位置，每次迭代完成后更新系統(tǒng)溫度：T_n+1＝γT_n，T_n和T_n+1分別表示第n次和第n+1次迭代后的系統(tǒng)溫度，γ為冷卻系數(shù)，當(dāng)系統(tǒng)溫度小于最小溫度后停止迭代。