[發(fā)明專利]一種基于譜分析的圖同構(gòu)判斷方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310357552.3
• 申請(qǐng)日: 2013-08-15
• 公開(kāi)（公告）號(hào): CN104376139B
• 公開(kāi)（公告）日: 2018-10-26
• 發(fā)明（設(shè)計(jì)）人: 曾璇;謝敏;楊帆
• 申請(qǐng)（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50
• 代理公司: 上海元一成知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31268
• 代理人: 吳桂琴

本發(fā)明屬于集成電路領(lǐng)域，涉及一種基于譜分析的圖同構(gòu)判斷方法；該方法將大規(guī)模純電阻網(wǎng)絡(luò)圖建模為非混合無(wú)向簡(jiǎn)單圖，將二維平面圖映射成一維分布，根據(jù)處理后的一維分布的情況來(lái)判定兩圖是否同構(gòu)。本發(fā)明方法對(duì)無(wú)向非混合簡(jiǎn)單圖具有判斷結(jié)果準(zhǔn)確、快速的特點(diǎn)，特別是對(duì)于大規(guī)模無(wú)向非混合簡(jiǎn)單圖，所述方法的速度明顯快于目前性能較好的Nauty方法，能很好地應(yīng)用于大規(guī)模集成電路中相同子電路的判定、有機(jī)化學(xué)中同分異構(gòu)體的判定等領(lǐng)域。

技術(shù)領(lǐng)域

本發(fā)明屬于集成電路領(lǐng)域，具體涉及一種基于譜分析的圖同構(gòu)判斷方法。

背景技術(shù)

隨著集成電路規(guī)模的日益增大，從門級(jí)到功能模塊級(jí)的子電路提取開(kāi)始應(yīng)用于EDA領(lǐng)域，相關(guān)算法將逐漸成為研究的熱點(diǎn)。所述提取的目的是檢測(cè)目標(biāo)電路中是否含有指定功能或結(jié)構(gòu)的模塊，并確定該模塊的數(shù)量和位置；但是，至今尚無(wú)高效的算法能夠滿足實(shí)際工程的需要。目前，解決上述問(wèn)題的思路通常都是將指定功能或者結(jié)構(gòu)的電路建模成圖，再通過(guò)判斷兩圖是否同構(gòu)來(lái)解決子電路提取的問(wèn)題。

所述“圖”是一種具有高度抽象和概括的圖形，簡(jiǎn)單地說(shuō)就是一些點(diǎn)以及將所述點(diǎn)在適當(dāng)?shù)牡胤竭B接起來(lái)得到的拓?fù)浣Y(jié)構(gòu)；而圖論正是研究這些圖性質(zhì)與應(yīng)用的學(xué)科。從1736年歐拉針對(duì)著名的七橋問(wèn)題發(fā)表的論文《依據(jù)幾何位置的解題方法》到1878年西爾威斯特第一次引入“圖”這一概念，再至哥尼希發(fā)表第一本圖論專著《有限圖與無(wú)限圖的理論》，經(jīng)過(guò)漫長(zhǎng)的發(fā)展，圖論理論在得到不斷豐富同時(shí)，已逐漸滲透到自然科學(xué)、工程技術(shù)、經(jīng)濟(jì)管理和社會(huì)問(wèn)題等領(lǐng)域并發(fā)揮著重要的作用，已經(jīng)成為數(shù)學(xué)的一個(gè)獨(dú)立分支，可應(yīng)用于研究任何一個(gè)包含某種二元關(guān)系的系統(tǒng)，正成為一門富有趣味而又應(yīng)用廣泛的學(xué)科。

圖論學(xué)科發(fā)展的整個(gè)過(guò)程中，學(xué)者在該領(lǐng)域中提出了不少問(wèn)題，有些已成功得到解決，而有些仍然有待深入探討。

而圖的同構(gòu)判定是圖論學(xué)科中的基本問(wèn)題之一，也是圖論學(xué)科中的諸多難題之一，由于其在電子工程中相同電路和開(kāi)關(guān)拓?fù)涞淖R(shí)別、有機(jī)化學(xué)中同分異構(gòu)體的判定、漢子研究中甲骨文的識(shí)別、機(jī)械設(shè)計(jì)中運(yùn)動(dòng)鏈的識(shí)別以及軟件設(shè)計(jì)中補(bǔ)丁的比較等很多領(lǐng)域有著廣泛的應(yīng)用，因此其又是有著很好應(yīng)用背景而值得研究的重要課題；而能夠找到高效的同構(gòu)判定算法，對(duì)解決上述實(shí)際問(wèn)題也具有重大意義。

目前理論上還無(wú)法證明圖的同構(gòu)問(wèn)題究竟屬于Np完全問(wèn)題還是P問(wèn)題，眾多學(xué)者對(duì)該問(wèn)題予以了關(guān)注和研究，提出了各種同構(gòu)判定算法。當(dāng)前圖的同構(gòu)判定算法主要有改進(jìn)的頂點(diǎn)順序交換法，頂點(diǎn)度數(shù)序列法，基于神經(jīng)網(wǎng)絡(luò)的算法，基于搜索的算法等幾類，其中基于搜索的算法在實(shí)際應(yīng)用中表現(xiàn)最佳。所述的基于搜索的算法主要有Ullmann算法、SD算法^[8]、VP算法和Nauty算法^[10]等；對(duì)上述算法的研究發(fā)現(xiàn)，該類算法的基本思路是在尋找同構(gòu)的過(guò)程中將頂點(diǎn)進(jìn)行細(xì)分，然后基于上述細(xì)分子集展開(kāi)搜索，通過(guò)搜索得到圖的頂點(diǎn)對(duì)應(yīng)關(guān)系來(lái)判定同構(gòu)。

目前，幾類同構(gòu)判定算法從不同的角度對(duì)圖的同構(gòu)判定展開(kāi)了研究；所述算法適用范圍也各不相同，在判定中體現(xiàn)出各自的優(yōu)勢(shì)的同時(shí)，也各有不足之處。一些算法對(duì)特定的圖判定速度快，但卻對(duì)其它類型的圖失效；一些算法雖然適用范圍廣，但速度普遍較慢；一些算法僅適用于小規(guī)模的圖等等；當(dāng)前還無(wú)法確定圖的同構(gòu)判定問(wèn)題已得到解決。雖然很難完全解決上述問(wèn)題，但是尋求該問(wèn)題的更好的方法很值得研究，下一步研究的方向是在現(xiàn)有基礎(chǔ)上實(shí)現(xiàn)判定范圍的擴(kuò)大和判定規(guī)模的增大及提高效率。

與本發(fā)明有關(guān)的參考文獻(xiàn)：

[1]李長(zhǎng)青.門級(jí)到功能模塊級(jí)子電路提取算法[D].中國(guó)科學(xué)院自動(dòng)化研究所,2007.

[2]Meynard T.A，F(xiàn)och H，F(xiàn)orest F，et al．Multi-cell converters:derivedtopologies[J]．IEEE Transactions on Industrial Electronics，2002，49(5):978-987．