[發(fā)明專利]一種錯誤親緣關(guān)系環(huán)深度優(yōu)先檢測方法和裝置

無效

• 申請?zhí)枺?/td>: 201310582087.3
• 申請日: 2013-11-20
• 公開（公告）號: CN103632042A
• 公開（公告）日: 2014-03-12
• 發(fā)明（設(shè)計）人: 倪龍
• 申請（專利權(quán)）人: 寧波保稅區(qū)攀峒信息科技有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種錯誤親緣關(guān)系環(huán)深度優(yōu)先檢測方法，其特征在于包括以下步驟：

第一步，進行初始化，創(chuàng)建一個檢測分支棧并將第一個分支入棧成為棧頂分支，設(shè)置一個關(guān)系長度最高允許值，為棧頂?shù)谝粋€分支創(chuàng)建相應(yīng)的關(guān)系長度計數(shù)器并置為零及創(chuàng)建一個為空的關(guān)系人集合、一個空的親緣關(guān)系數(shù)據(jù)集合及一個該親緣關(guān)系數(shù)據(jù)數(shù)據(jù)集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記；

第二步，將開始檢測的第一個親緣關(guān)系數(shù)據(jù)放入棧頂?shù)谝粋€分支相應(yīng)的親緣關(guān)系數(shù)據(jù)集合，并標記為該集合當前關(guān)聯(lián)數(shù)據(jù)，然后提取數(shù)據(jù)中參與親緣關(guān)系的兩個關(guān)系人，如果不相同則均放入棧頂?shù)谝粋€分支相應(yīng)的關(guān)系人集合并將第一個分支相應(yīng)的關(guān)系長度計數(shù)器加1，然后將相應(yīng)的親緣關(guān)系數(shù)據(jù)集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為已處理；如果相同則得出檢測結(jié)果是檢測出錯誤親緣關(guān)系環(huán)且出錯的數(shù)據(jù)集合在上述親緣關(guān)系數(shù)據(jù)集合中，檢測過程結(jié)束；

第三步，如果棧為空則檢測過程結(jié)束；如果不為空對于且棧頂分支相應(yīng)的親緣關(guān)系數(shù)據(jù)集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為已處理，則按照確定的親緣關(guān)系方向往上或往下（均可包括平行方向）取棧頂分支下一個關(guān)聯(lián)的同種類親緣關(guān)系數(shù)據(jù)，否則直接執(zhí)行第五步；

第四步，如果沒有關(guān)聯(lián)數(shù)據(jù)則得出檢測結(jié)果是棧頂分支沒有檢測出錯誤親緣關(guān)系環(huán)，然后將棧頂分支出棧；如果有關(guān)聯(lián)數(shù)據(jù)，第一個關(guān)聯(lián)數(shù)據(jù)作為棧頂分支的延續(xù)繼續(xù)使用棧頂分支的計數(shù)器、兩個集合及當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記等資源，如果有兩個或以上關(guān)聯(lián)數(shù)據(jù)，則另外分別為第二個及以上的關(guān)聯(lián)數(shù)據(jù)創(chuàng)建一個分支并入棧同時復(fù)制一個相同的資源備份為本分支所有，以后所有操作中各個分支均為操作本分支所有的關(guān)系人集合和親緣關(guān)系數(shù)據(jù)集合，然后分別將各個關(guān)聯(lián)數(shù)據(jù)放入本分支所有的親緣關(guān)系數(shù)據(jù)集合，并標記為該集合的當前關(guān)聯(lián)數(shù)據(jù)，同時將該集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為未處理；

第五步，提取棧頂分支相應(yīng)的親緣關(guān)系數(shù)據(jù)集合的當前關(guān)聯(lián)數(shù)據(jù)中參與親緣關(guān)系的另一個關(guān)系人，如果本分支所有的關(guān)系人集合中不存在該關(guān)系人則將其放入該集合并將關(guān)系長度計數(shù)器加1但連續(xù)第二個及以上的平行方向關(guān)聯(lián)情況的關(guān)系長度計數(shù)器不再增加，如果本分支關(guān)系長度計數(shù)器已達關(guān)系長度最高允許值，則得出檢測結(jié)果是棧頂分支未檢測出錯誤親緣關(guān)系環(huán)，然后將棧頂分支出棧；如果關(guān)系人集合中已存在該關(guān)系人則得出檢測結(jié)果是檢測出錯誤親緣關(guān)系環(huán)且出錯的數(shù)據(jù)集合在棧頂分支所有的親緣關(guān)系數(shù)據(jù)集合中，然后將棧頂分支出棧；否則將當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為已處理，然后回到第三步。

2.一種錯誤親緣關(guān)系環(huán)深度優(yōu)先檢測裝置，其特征在于，該裝置具備：

至少一個處理器；及

至少一個存儲器，含有計算機程序代碼，所述至少一個存儲器和計算機程序代碼被配置為利用所述至少一個處理器使得所述裝置

第一步，進行初始化，創(chuàng)建一個檢測分支棧并將第一個分支入棧成為棧頂分支，設(shè)置一個關(guān)系長度最高允許值，為棧頂?shù)谝粋€分支創(chuàng)建相應(yīng)的關(guān)系長度計數(shù)器并置為零及創(chuàng)建一個為空的關(guān)系人集合、一個空的親緣關(guān)系數(shù)據(jù)集合及一個該親緣關(guān)系數(shù)據(jù)數(shù)據(jù)集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記；

第二步，將開始檢測的第一個親緣關(guān)系數(shù)據(jù)放入棧頂?shù)谝粋€分支相應(yīng)的親緣關(guān)系數(shù)據(jù)集合，并標記為該集合當前關(guān)聯(lián)數(shù)據(jù)，然后提取數(shù)據(jù)中參與親緣關(guān)系的兩個關(guān)系人，如果不相同則均放入棧頂?shù)谝粋€分支相應(yīng)的關(guān)系人集合并將第一個分支相應(yīng)的關(guān)系長度計數(shù)器加1，然后將相應(yīng)的親緣關(guān)系數(shù)據(jù)集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為已處理；如果相同則得出檢測結(jié)果是檢測出錯誤親緣關(guān)系環(huán)且出錯的數(shù)據(jù)集合在上述親緣關(guān)系數(shù)據(jù)集合中，檢測過程結(jié)束；

第三步，如果棧為空則檢測過程結(jié)束；如果不為空對于且棧頂分支相應(yīng)的親緣關(guān)系數(shù)據(jù)集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為已處理，則按照確定的親緣關(guān)系方向往上或往下（均可包括平行方向）取棧頂分支下一個關(guān)聯(lián)的同種類親緣關(guān)系數(shù)據(jù)，否則直接執(zhí)行第五步；

第四步，如果沒有關(guān)聯(lián)數(shù)據(jù)則得出檢測結(jié)果是棧頂分支沒有檢測出錯誤親緣關(guān)系環(huán)，然后將棧頂分支出棧；如果有關(guān)聯(lián)數(shù)據(jù)，第一個關(guān)聯(lián)數(shù)據(jù)作為棧頂分支的延續(xù)繼續(xù)使用棧頂分支的計數(shù)器、兩個集合及當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記等資源，如果有兩個或以上關(guān)聯(lián)數(shù)據(jù)，則另外分別為第二個及以上的關(guān)聯(lián)數(shù)據(jù)創(chuàng)建一個分支并入棧同時復(fù)制一個相同的資源備份為本分支所有，以后所有操作中各個分支均為操作本分支所有的關(guān)系人集合和親緣關(guān)系數(shù)據(jù)集合，然后分別將各個關(guān)聯(lián)數(shù)據(jù)放入本分支所有的親緣關(guān)系數(shù)據(jù)集合，并標記為該集合的當前關(guān)聯(lián)數(shù)據(jù)，同時將該集合當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為未處理；

第五步，提取棧頂分支相應(yīng)的親緣關(guān)系數(shù)據(jù)集合的當前關(guān)聯(lián)數(shù)據(jù)中參與親緣關(guān)系的另一個關(guān)系人，如果本分支所有的關(guān)系人集合中不存在該關(guān)系人則將其放入該集合并將關(guān)系長度計數(shù)器加1但連續(xù)第二個及以上的平行方向關(guān)聯(lián)情況的關(guān)系長度計數(shù)器不再增加，如果本分支關(guān)系長度計數(shù)器已達關(guān)系長度最高允許值，則得出檢測結(jié)果是棧頂分支未檢測出錯誤親緣關(guān)系環(huán)，然后將棧頂分支出棧；如果關(guān)系人集合中已存在該關(guān)系人則得出檢測結(jié)果是檢測出錯誤親緣關(guān)系環(huán)且出錯的數(shù)據(jù)集合在棧頂分支所有的親緣關(guān)系數(shù)據(jù)集合中，然后將棧頂分支出棧；否則將當前關(guān)聯(lián)數(shù)據(jù)是否已處理的狀態(tài)標記設(shè)置為已處理，然后回到第三步。