[發(fā)明專利]分層簡(jiǎn)化大規(guī)模圖數(shù)據(jù)的運(yùn)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210176708.3
• 申請(qǐng)日: 2012-05-31
• 公開（公告）號(hào): CN102750460A
• 公開（公告）日: 2012-10-24
• 發(fā)明（設(shè)計(jì)）人: 毛國(guó)勇;張燕紅;張永春;徐磊;彭穎
• 申請(qǐng)（專利權(quán)）人: 常州工學(xué)院
• 主分類號(hào): G06F19/18
• 分類號(hào): G06F19/18
• 代理公司: 常州市江海陽光知識(shí)產(chǎn)權(quán)代理有限公司 32214
• 代理人: 湯志和

1.一種分層簡(jiǎn)化大規(guī)模圖數(shù)據(jù)的運(yùn)算方法，其特征在于包含以下步驟：

①對(duì)原始圖G₀進(jìn)行去除自回路和平行邊的預(yù)處理，得到第一級(jí)簡(jiǎn)化子圖G₁=（V₁，E₁），其中V₁為一級(jí)點(diǎn)的集合，E₁為一級(jí)邊的集合;?并設(shè)第i級(jí)簡(jiǎn)化子圖G_i為下一級(jí)簡(jiǎn)化子圖G_i+1的母圖G_Oi；i為初值等于1的整數(shù)；

②對(duì)所述母圖G_Oi進(jìn)行遍歷，并選擇其中具有最優(yōu)度的點(diǎn)作為遍歷的起點(diǎn)S_?i+1,設(shè)所述下一級(jí)簡(jiǎn)化子圖G_i+1=（V_?i+1，E_?i+1），其中V_?i+1為下一級(jí)點(diǎn)的集合，E_?i+1為下一級(jí)邊的集合；?

③將所述起點(diǎn)S_?i+1作為新加入點(diǎn)加入到所述下一級(jí)點(diǎn)的集合V_?i+1中；

④把所述新加入點(diǎn)及其直接鄰接點(diǎn)加入到一集合VT_?i+1中；

⑤遍歷所述集合VT_?i+1中的各直接鄰接點(diǎn)的所有鄰接點(diǎn)；若有一鄰接點(diǎn)不在所述集合VT_i+1中，則將與該鄰接點(diǎn)對(duì)應(yīng)的所述直接鄰接點(diǎn)加入到所述集合V_?i+1中，并連接所述步驟④中的新加入點(diǎn)與所述對(duì)應(yīng)的直接鄰接點(diǎn)，以生成一邊，將所述邊加入到所述下一級(jí)邊的集合E_?i+1中；

⑥從所述步驟⑤中得到的所述集合V_?i+1中的下一個(gè)加入點(diǎn)，重復(fù)所述步驟④、⑤，直至所述母圖G_Oi遍歷結(jié)束，以得到所述下一級(jí)點(diǎn)的集合V_?i+1和下一級(jí)邊的集合E_?i+1，構(gòu)成所述下一級(jí)簡(jiǎn)化子圖G_?i+1=（V_?i+1，E_?i+1）；

⑦設(shè)獲得的所述下一級(jí)簡(jiǎn)化子圖G_?i+1為再下一級(jí)簡(jiǎn)化子圖的母圖G_O(i+1)，重復(fù)所述步驟②至⑥直至得到最優(yōu)簡(jiǎn)化子圖G。

2.根據(jù)權(quán)利要求1所述的運(yùn)算方法，其特征在于：獲得所述步驟②中最優(yōu)度的點(diǎn)的方法，包括如下步驟：

先選擇度最多的點(diǎn)作為所述最優(yōu)度的點(diǎn)；

若含有度最多的點(diǎn)有多個(gè)，則依次比較各點(diǎn)的各級(jí)鄰接點(diǎn)的度的總和，取所述總和最小的點(diǎn)作為所述最優(yōu)度的點(diǎn)。

3.根據(jù)權(quán)利要求1或2的所述運(yùn)算方法，其特征在于：所述步驟⑥中的所述遍歷結(jié)束是所述集合VT_?i+1中的點(diǎn)與該級(jí)母圖中的點(diǎn)的集合V_i相等。