[發(fā)明專利]一種基于SCC?DAG的圖計(jì)算迭代處理方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201611070021.6
• 申請(qǐng)日: 2016-11-28
• 公開（公告）號(hào): CN106776858A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計(jì)）人: 廖小飛;金海;石翔;張宇;李陳希
• 申請(qǐng)（專利權(quán)）人: 華中科技大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 華中科技大學(xué)專利中心42201
• 代理人: 趙偉

1.一種基于SCC-DAG的圖計(jì)算迭代處理方法，其特征在于，包括如下步驟：

(1)獲取給定的圖中所有的SCC，通過對(duì)SCC進(jìn)行拓?fù)渑判騺順?gòu)建SCC-DAG；

(2)按照SCC在SCC-DAG內(nèi)的拓?fù)漤樞蛞来卧谒鯯CC-DAG的各SCC內(nèi)進(jìn)行迭代，直至所有SCC收斂。

2.如權(quán)利要求1所述的圖計(jì)算迭代處理方法，其特征在于，所述步驟(2)包括如下子步驟：

(2.1)根據(jù)所述SCC-DAG中SCC的拓?fù)漤樞驈乃鯯CC-DAG中選定一個(gè)SCC；

(2.2)在選定的SCC中執(zhí)行實(shí)際需求實(shí)現(xiàn)所對(duì)應(yīng)的算法，并采用同步迭代或異步迭代對(duì)每個(gè)頂點(diǎn)進(jìn)行計(jì)算；

(2.3)判斷經(jīng)過步驟(2.2)處理后的SCC內(nèi)部所有頂點(diǎn)是否達(dá)到收斂；若是，則進(jìn)入步驟(2.4)；若否，則進(jìn)入步驟(2.2)；

(2.4)判斷是否SCC-DAG中所有的SCC都達(dá)到收斂；若是，則輸出收斂狀態(tài)的數(shù)據(jù)作為算法的運(yùn)行結(jié)果；若否，則返回步驟(2.1)。

3.如權(quán)利要求2所述的圖計(jì)算迭代處理方法，其特征在于，所述選定的SCC應(yīng)滿足：所述SCC的所有雙親SCC都達(dá)到收斂狀態(tài)、且所述SCC自身未達(dá)到收斂狀態(tài)。