畢業(yè)論文——基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)--可擴(kuò)展存儲(chǔ)結(jié)構(gòu)的圖組件

1、<p>　　本 科 畢 業(yè) 論 文</p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　——可擴(kuò)展存儲(chǔ)結(jié)構(gòu)的圖組件</p><p>　　Design Pattern Detecting System Using Subgraph Discovery</p><p>　　——A Graph Component Su

2、pporting Extendable</p><p>　　Storage Structures</p><p><b>　　姓名：</b></p><p><b>　　學(xué)號(hào)：</b></p><p><b>　　學(xué)院：軟件學(xué)院</b></p><p&

3、gt;<b>　　專業(yè)：軟件工程</b></p><p><b>　　年級(jí)：</b></p><p><b>　　指導(dǎo)教師：</b></p><p>　　二〇XX 年 X 月</p><p><b>　　摘要</b></p><p

4、>　　現(xiàn)代軟件工業(yè)已經(jīng)廣泛地應(yīng)用設(shè)計(jì)模式來重用成功的設(shè)計(jì)實(shí)踐以提高軟件系統(tǒng)的質(zhì)量，然而受制于軟件系統(tǒng)的規(guī)模和設(shè)計(jì)文檔的缺失，開發(fā)人員無法直觀地理解現(xiàn)有軟件系統(tǒng)中所應(yīng)用的設(shè)計(jì)模式。通過從現(xiàn)有的系統(tǒng)源代碼中提取出其所使用的設(shè)計(jì)模式，可以方便開發(fā)人員更容易理解源代碼中各個(gè)類在整個(gè)系統(tǒng)中的職責(zé)與作用，從而更好的對(duì)其進(jìn)行維護(hù)。源代碼中的設(shè)計(jì)模式識(shí)別是研究領(lǐng)域的關(guān)鍵課題。</p><p>　　本文中的 CodeMine

5、r 插件是用 Java 語言來開發(fā)的 Eclipse IDE 插件，它可將軟件源代碼的主要特征提取出來并整理成抽象語義圖。通過對(duì)設(shè)計(jì)模式與軟件項(xiàng)目源代碼進(jìn)行解析，可以生成相應(yīng)的抽象語義圖。通過對(duì)所得結(jié)果利用子圖比較的方式進(jìn)行挖掘，能識(shí)別出軟件項(xiàng)目源代碼中所使用到的設(shè)計(jì)模式，并確定各個(gè)類在對(duì)應(yīng)設(shè)計(jì)模式中所扮演的角色，從而為開發(fā)人員在維護(hù)軟件系統(tǒng)時(shí)理解源代碼提供幫助。而通過引入使用確定的有限自動(dòng)機(jī)，可以大幅度提高 CodeMiner 插件的

6、運(yùn)行效率，增加其可用性。</p><p>　　基于可擴(kuò)展存儲(chǔ)結(jié)構(gòu)的 MiningGraph 組件在 CodeMiner 插件系統(tǒng)中扮演底層組件的角色，它實(shí)現(xiàn)了圖的基本操作(如圖的創(chuàng)建、修改、遍歷等)、圖的同構(gòu)判斷以及圖同構(gòu)序列的定位等算法的實(shí)現(xiàn)，并為 CodeMiner 提供圖模型持久化服務(wù)。 MiningGraph 隱藏了圖的持久化細(xì)節(jié)，支持可擴(kuò)展的存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)了將圖保存</p><p&g

7、t;　　到文件或數(shù)據(jù)庫中，為 CodeMiner 實(shí)現(xiàn)子圖匹配算法在代碼中挖掘設(shè)計(jì)模式的使</p><p><b>　　用提供支持。</b></p><p>　　關(guān)鍵字：圖；圖同構(gòu)；數(shù)據(jù)庫</p><p><b>　　Abstract</b></p><p>　　Design patterns ha

8、ve been widely adopted by modern software industry in order to reuse successful practices and improve the quality of software systems. The identification of design patterns as part of the reengineering process can convey

9、 important information to the developers. However, many systems are of legacy and the design documents are usually missing. Besides, existing pattern detection methodologies generally have problems in dealing with one or

10、 more of the following issues: Identificat</p><p>　　The project CodeMiner mentioned in this article, is an Eclipse IDE plug- in developed in Java programming language. It can extract the characteristics of s

11、oftware source code and generate Abstract Semantic Graph. By analyzing the source code of Design Patterns and the software project to examine, corresponding Abstract Semantic Graphs can be generated. Then CodeMiner uses

12、subgraph discovery methodology to identify design patterns used in the software project and determine the role of each class </p><p>　　MiningGraph, a component aiming at supporting extendable storage structu

13、res, plays the role of the base part of CodeMiner. Besides providing basic operations of graph theory, MiningGraph also implements graph isomorphism detection and isomorphism matching location. MiningGraph hides implemen

14、tation details of graph persistence, and supports multiple storage structures such as GraphML format and database storage, meeting the requirements of CodeMiner for using subgraph discovery algorithm in sourc</p>

15、<p>　　Keywords: Graph; Graph Isomorphism; Database Storage.</p><p>　　TABLE OF CONTENTS</p><p><b>　　第一章 緒論</b></p><p><b>　　第一章緒論</b></p><p>

16、;　　設(shè)計(jì)模式是面向?qū)ο笤O(shè)計(jì)的一個(gè)高級(jí)抽象，是針對(duì)重復(fù)發(fā)生的軟件問題的標(biāo)</p><p>　　準(zhǔn)解決方案?，F(xiàn)代軟件工業(yè)已經(jīng)廣泛地應(yīng)用設(shè)計(jì)模式來重用成功的設(shè)計(jì)實(shí)踐和提</p><p>　　高軟件系統(tǒng)的質(zhì)量，使得軟件系統(tǒng)具有良好的可擴(kuò)展性，方便開方人員維護(hù)。然</p><p>　　而由于軟件系統(tǒng)的規(guī)模龐大和設(shè)計(jì)文檔的缺失，導(dǎo)致軟件系統(tǒng)的理解和維護(hù)也變</p>

17、<p>　　得越來越困難，因此從現(xiàn)有的系統(tǒng)源碼中抽取設(shè)計(jì)模式成為許多研究領(lǐng)域的關(guān)鍵</p><p>　　課題。這里我們將對(duì)目前相關(guān)領(lǐng)域的研究現(xiàn)狀以及存在的問題等進(jìn)行闡述，說明</p><p>　　MiningGraph 模塊所實(shí)現(xiàn)的功能，以及 MiningGraph 在整個(gè) CodeMiner 插件中的</p><p>　　作用，并對(duì)本文研究?jī)?nèi)容以及本

18、文結(jié)構(gòu)安排等進(jìn)行總體闡述。</p><p>　　1.1 研究背景及選題意義</p><p>　　由于現(xiàn)在的軟件項(xiàng)目大都包含數(shù)目眾多的組件，其結(jié)構(gòu)變得相當(dāng)復(fù)雜和混亂，從而不利于軟件系統(tǒng)的維護(hù)和改進(jìn)。在軟件系統(tǒng)的整個(gè)生命周期中，軟件維護(hù)是十分重要和復(fù)雜的階段，可以占據(jù)整個(gè)投入的 50%-70%，程序理解在軟件維護(hù)階段起著重要的作用，尤其當(dāng)程序結(jié)構(gòu)較復(fù)雜，而且相關(guān)的文檔與系統(tǒng)不同步。軟件工程數(shù)據(jù)

19、，如代碼、代碼的修改歷史、執(zhí)行路徑以及錯(cuò)誤報(bào)告等，蘊(yùn)含著大量與項(xiàng)目管理、軟件平臺(tái)技術(shù)有關(guān)的信息和知識(shí)。如果可以從上述大量的數(shù)據(jù)中挖掘出潛在的具有高度價(jià)值的信息和知識(shí)，將更好地進(jìn)行項(xiàng)目管理，生產(chǎn)出高質(zhì)量的代碼。</p><p>　　設(shè)計(jì)模式是軟件設(shè)計(jì)中的一些普遍設(shè)計(jì)問題的解決方案，可以用統(tǒng)一的格式加以描述，主要有：意圖、動(dòng)機(jī)、適用性、結(jié)構(gòu)、參與者、協(xié)作、實(shí)現(xiàn)細(xì)節(jié)和代碼示例等.上述模板詳細(xì)地說明了設(shè)計(jì)問題以及如何用模

20、式中的類和對(duì)象來解決</p><p>　　問題的特定情景[1] ，記錄了設(shè)計(jì)產(chǎn)生的決定過程、選擇過程和權(quán)衡過程，指導(dǎo)開發(fā)人員進(jìn)行成功的系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)。設(shè)計(jì)模式已被現(xiàn)代軟件業(yè)廣泛采用以復(fù)用成功的設(shè)計(jì)和體系結(jié)構(gòu)以提高軟件系統(tǒng)的質(zhì)量。</p><p>　　在許多大型軟件項(xiàng)目中，設(shè)計(jì)文檔經(jīng)常缺失，即使設(shè)計(jì)文檔可用，也可能隨著系統(tǒng)的改變和遷移而變得過時(shí)，很多時(shí)候，開發(fā)人員受到工程截至日期的影響，&l

21、t;/p><p><b>　　--1--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　沒有對(duì)他們的軟件代碼進(jìn)行充分的文檔化，這些情況導(dǎo)致模式相關(guān)信息的丟失使</p><p>　　應(yīng)用設(shè)計(jì)模式的好處大打折扣，使后來的開發(fā)人員對(duì)系統(tǒng)的理解和維護(hù)變得很困</p><p>

22、<b>　　難[2]。</b></p><p>　　從軟件系統(tǒng)中的源碼中發(fā)現(xiàn)所使用的設(shè)計(jì)模式已經(jīng)成為許多研究領(lǐng)域的關(guān)鍵課題，如在反向工程和代碼重構(gòu)方面。通過發(fā)現(xiàn)軟件系統(tǒng)中使用的設(shè)計(jì)模式可以展現(xiàn)系統(tǒng)設(shè)計(jì)的結(jié)構(gòu)，幫助新系統(tǒng)開發(fā)人員更好地理解系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)決策。</p><p>　　另一方面，隨著包括化學(xué)情報(bào)學(xué)、生物信息學(xué)、計(jì)算機(jī)視覺、視頻索引、文本檢索以及 Web 分析

23、在內(nèi)的廣泛應(yīng)用，圖作為一種一般數(shù)據(jù)結(jié)構(gòu)在復(fù)雜結(jié)構(gòu)和它們之間相互作用建模中變得越來越重要。在各種各樣的圖模式匹配中，頻繁子結(jié)構(gòu)是可以在圖集合中發(fā)現(xiàn)的非?；镜哪Ｊ健ｎl繁子結(jié)構(gòu)可以用來刻畫圖集合的特征，區(qū)分不同的圖組群，對(duì)圖進(jìn)行分類和聚類，構(gòu)造圖索引和更方便地在圖數(shù)據(jù)庫中進(jìn)行相似性搜索。</p><p>　　CodeMiner 是在 Java 開發(fā)平臺(tái) Eclipse[3] 上開發(fā)的插件，通過利用子圖匹配的方式來提取

24、軟件項(xiàng)目的源代碼中所使用的設(shè)計(jì)模式，分析源代碼中各個(gè)類所扮演的角色，方便開發(fā)人員理解整個(gè)工程的整體架構(gòu)，明確各個(gè)類的職責(zé)與作用，從而更好的對(duì)工程進(jìn)行維護(hù)。</p><p>　　基于可擴(kuò)展存儲(chǔ)結(jié)構(gòu)的 MiningGraph 組件是作為 CodeMiner 系統(tǒng)的底層，隱藏了圖的持久化細(xì)節(jié)，支持可擴(kuò)展的存儲(chǔ)結(jié)構(gòu)，為 CodeMiner 提供解析工程源代碼及進(jìn)行設(shè)計(jì)模式匹配時(shí)所需的圖創(chuàng)建、修改、讀取、持久化、同構(gòu)判斷以

25、及同構(gòu)定位等相關(guān)操作，為完成整個(gè) CodeMiner 項(xiàng)目的實(shí)現(xiàn)奠定基礎(chǔ)。</p><p>　　1.2 研究現(xiàn)狀及存在問題</p><p>　　目前，設(shè)計(jì)模式發(fā)現(xiàn)技術(shù)在國際上得到普遍關(guān)注，現(xiàn)在的大多數(shù)研究沒有直</p><p>　　接從源代碼去發(fā)現(xiàn)設(shè)計(jì)模式，而是引進(jìn)了源代碼的中間表示，各種具體的設(shè)計(jì)模</p><p>　　式發(fā)現(xiàn)方法主要的差別

26、集中在源碼模型、模式模型、查找算法三個(gè)方面。本文中</p><p>　　闡述的 MiningGraph 組件著重完成圖論概念在 CodeMiner 程序中的應(yīng)用，提供</p><p>　　CodeMiner 所需的設(shè)計(jì)模式的圖的模型的建立。在數(shù)據(jù)結(jié)構(gòu)學(xué)科中，圖是一種比</p><p>　　線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)[4] 。對(duì)于一張圖而言，圖中的元素間的關(guān)系可以

27、</p><p><b>　　--2--</b></p><p><b>　　第一章 緒論</b></p><p>　　是多對(duì)多的，即任何兩個(gè)元素都有可能存在關(guān)系。在數(shù)據(jù)結(jié)構(gòu)中對(duì)圖的討論主要</p><p>　　側(cè)重于圖在計(jì)算機(jī)中的存儲(chǔ)方式和有關(guān)操作的算法。在這一節(jié)里面，將簡(jiǎn)要介紹</p>

28、;<p>　　現(xiàn)有的圖算法框架各自的特點(diǎn)與不足之處。</p><p>　　The Standford GraphBase[5] 是由斯坦福大學(xué)的 Donald Knuth 整理的處理圖</p><p>　　的程序和數(shù)據(jù)集的軟件包集合。這些程序是用 CWEBC[6] (一種 C 語言與 TeX 排版語</p><p>　　言的混合語言)語言進(jìn)行編寫的，

29、提供了如最小生成樹(Minimum Spanning Tree) 、</p><p>　　Dijkstra 最短路徑(Dijkstra's Shortest Paths)、進(jìn)程調(diào)度(Job Scheduling) 、</p><p>　　哈密頓圈(Hamiltonian Cycle)等大量經(jīng)典圖論問題的算法實(shí)現(xiàn)。由于程序使用</p><p>　　CWEB 語

30、言來編寫，The Standford GraphBase 軟件包具有程序執(zhí)行效率高，代碼</p><p>　　文檔清晰易懂等優(yōu)點(diǎn)，有很好的參考價(jià)值。但同時(shí)也因?yàn)樗玫木幊陶Z言的限制，</p><p>　　不能支持面向?qū)ο缶幊碳夹g(shù)，程序可擴(kuò)展性不強(qiáng)。</p><p>　　Boost Graph Library (BGL)[7] 是 Boost C++ Library

31、 的子項(xiàng)目，旨在充分</p><p>　　利用 C++的標(biāo)準(zhǔn)庫來提供性能效率更高的程序組件。BGL 的開發(fā)人員認(rèn)為，一個(gè)標(biāo)</p><p>　　準(zhǔn)的圖遍歷泛型接口對(duì)鼓勵(lì)開發(fā)人員實(shí)現(xiàn)重用圖的算法和數(shù)據(jù)結(jié)構(gòu)是至關(guān)重要</p><p>　　的。因此，通過使用 Standard Template Library (STL)[8] ，BGL 提供了一個(gè)公</p>

32、<p>　　用的泛型接口供開發(fā)人員訪問圖的結(jié)構(gòu)，但將實(shí)現(xiàn)的細(xì)節(jié)隱藏起來。這樣的做法</p><p>　　在當(dāng)時(shí)面向接口編程還未廣泛流行的背景下是具有創(chuàng)造性的。通過使用 STL，BGL</p><p>　　在算法與數(shù)據(jù)結(jié)構(gòu)、訪問元、頂點(diǎn)與邊屬性這三個(gè)方面可以讓用戶自定義類型，</p><p>　　極大的豐富了程序的可擴(kuò)展性。BGL 在定義頂點(diǎn)和邊的時(shí)候使

33、用了 Map 映射，從</p><p>　　而允許開發(fā)人員自定義屬性的名稱，這一方面增加了程序的靈活性，另一方面也</p><p>　　要求開發(fā)人員必須了解其結(jié)構(gòu)以便正確維護(hù)程序。</p><p>　　LEDA[9] 全名為 Library for Efficient Data structures and Algorithms，</p><p

34、>　　它是一個(gè)商業(yè)化的常用 ADT 的 C++實(shí)現(xiàn)算法函數(shù)庫，主要提供了圖形和網(wǎng)絡(luò)問題，</p><p>　　幾何計(jì)算，組合優(yōu)化和其他與圖形相關(guān)的算法。LEDA 采用了面向?qū)ο蟮木幊趟枷耄?lt;/p><p>　　允許用戶對(duì)其自行擴(kuò)展，在追求方便易用的同時(shí)保證程序的運(yùn)行效率。LEDA 還提</p><p>　　供了網(wǎng)絡(luò)流，子圖同構(gòu)等復(fù)雜圖運(yùn)算的相關(guān)算法的實(shí)現(xiàn)，可以

35、廣泛應(yīng)用于電信，</p><p>　　地理信息系統(tǒng)，工作調(diào)度，交通規(guī)劃，計(jì)算生物學(xué)和電腦輔助設(shè)計(jì)等領(lǐng)域。LEDA</p><p>　　的官方網(wǎng)站提供了免費(fèi)的版本，但其功能有不少限制。</p><p><b>　　--3--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>

36、;　　JGraph[10] 是一個(gè)開源的，兼容 Swing[11] 的基于 Model-View-Control (MVC)</p><p>　　體系結(jié)構(gòu)的可視化圖形組件。它具有相當(dāng)高的交互性和自動(dòng)化，主要用途是在一</p><p>　　些需要表示圖結(jié)構(gòu)的應(yīng)用中，比如流程圖、UML、交通線路、網(wǎng)絡(luò)等等。JGraph</p><p>　　支持強(qiáng)大的布局算法，開發(fā)人

37、員無需熟悉圖論相關(guān)知識(shí)也能快速上手。JGraph 更</p><p>　　偏重于可視化圖形界面的實(shí)現(xiàn)。</p><p>　　JGraphT[12] 是個(gè)開源的 Java 圖形庫，它著重于數(shù)學(xué)中圖論概念在程序中的表</p><p>　　示，提供了大量經(jīng)典算法的實(shí)現(xiàn)，支持多種類型的圖形，功能強(qiáng)大，容易擴(kuò)展，</p><p>　　方便使用。適用于

38、處理圖數(shù)據(jù)結(jié)構(gòu)的大多數(shù)程序。JGraphT 本身并沒有提供圖形</p><p>　　界面，但配合 JGraph 可以輕松實(shí)現(xiàn)圖論算法的界面展示。JGraphT 的擴(kuò)展能力很</p><p>　　強(qiáng)，頂點(diǎn)與邊允許使用用戶自定義圖的類型。</p><p>　　GEF (Graphical Editor Framework)[13]是一個(gè)圖形化編輯框架，它允許開發(fā)<

39、/p><p>　　人員以圖形化的方式展示和編輯模型，從而提升用戶體驗(yàn)。GEF 最早是 Eclipse</p><p>　　的一個(gè)內(nèi)部項(xiàng)目，后來逐漸轉(zhuǎn)變?yōu)?Eclipse 的一個(gè)開源工具項(xiàng)目，Eclipse 的不</p><p>　　少其他子項(xiàng)目都需要它的支持。GEF 的優(yōu)勢(shì)是提供了標(biāo)準(zhǔn)的 MVC 結(jié)構(gòu)，開發(fā)人員</p><p>　　可以利用 GE

40、F 來完成以上這些功能，而不需要自己重新設(shè)計(jì)。與其他一些 MVC 編</p><p>　　輯框架相比，GEF 的一個(gè)主要設(shè)計(jì)目標(biāo)是盡量減少模型和視圖之間的依賴，好處</p><p>　　是可以根據(jù)需要選擇任意模型和視圖的組合，而不必受開發(fā)框架的局限(不過實(shí)際</p><p>　　上還是很少有脫離 Draw2D 的實(shí)現(xiàn))。</p><p>　　

41、Pajek (Program Analysis for Large Network)[14]是一項(xiàng)基于 Windows 的免費(fèi)社會(huì)科學(xué)軟件，由盧布爾雅那大學(xué)的 Vladimir Batagelj 和 Andrej Mrvar 于</p><p>　　1997 年 1 月 15 日正式發(fā)布 0.1 版，主要用于社會(huì)網(wǎng)絡(luò)分析，特點(diǎn)是可對(duì)數(shù)據(jù)進(jìn)</p><p>　　行可視化。通過可視化工具，擴(kuò)展

42、了人類的視覺功能。它允許人們對(duì)大量抽象的</p><p>　　數(shù)據(jù)進(jìn)行分析并通過可視化變成，在表面上看來是雜亂無章的海量數(shù)據(jù)中找出其</p><p>　　中隱藏的規(guī)律，為科學(xué)發(fā)現(xiàn)、工程開發(fā)、醫(yī)療診斷和業(yè)務(wù)決策等提供依據(jù)。</p><p>　　JUNG (the Java Universal Network/Graph Framework)[15] 是一個(gè)通用的可擴(kuò)

43、展</p><p>　　的，用來創(chuàng)建圖表的類庫。它提供了一種公共和可擴(kuò)展的框架來實(shí)現(xiàn)數(shù)據(jù)的建模，</p><p>　　分析和可視化展示并能夠被繪制成圖形或網(wǎng)絡(luò)。JUNG 側(cè)重于分析圖中實(shí)體之間</p><p>　　的關(guān)系，在數(shù)據(jù)挖掘和社交網(wǎng)絡(luò)分析中有著廣泛應(yīng)用。</p><p><b>　　--4--</b></p

44、><p><b>　　第一章 緒論</b></p><p>　　UCINET[16] 是目前最流行的社會(huì)網(wǎng)分析軟件。UCINET 網(wǎng)絡(luò)分析集成軟件包</p><p>　　括一維與二維數(shù)據(jù)分析的 NetDraw[17] ，還有正在發(fā)展應(yīng)用的三維展示分析軟件</p><p>　　Mage[18] 等，同時(shí)集成了 Pajek

45、 這一個(gè)用于大型網(wǎng)絡(luò)分析的免費(fèi)應(yīng)用軟件程序。</p><p>　　UCINET 通常用于社交網(wǎng)絡(luò)及其它相近數(shù)據(jù)分析，包含中心與連接性測(cè)量，方法</p><p>　　有測(cè)定位置和次群組、隨機(jī)模型、相似和相異性、多矩陣回歸(Multiple Matrix</p><p>　　Regression)等，并有多變量分析、群集分析等等。</p><p>

46、;　　總體而言，圖算法已經(jīng)趨于成熟并在各個(gè)領(lǐng)域得到廣泛的應(yīng)用，尤其近年的</p><p>　　研究呈現(xiàn)出利用圖匹配來進(jìn)行數(shù)據(jù)挖掘與社會(huì)網(wǎng)絡(luò)分析等大數(shù)據(jù)量運(yùn)算的趨勢(shì)。</p><p>　　但現(xiàn)在的框架都還存在著一些問題以待解決：</p><p>　　1、框架的互操作性有待加強(qiáng)。盡管大部分框架通過廣泛地使用泛型編程，將</p><p>　　圖的操

47、作與具體的實(shí)現(xiàn)分離開來，從而允許用戶根據(jù)自身需求對(duì)程序進(jìn)行定制，</p><p>　　增強(qiáng)了程序的可擴(kuò)展性，實(shí)現(xiàn)代碼的重用。但各框架的圖存儲(chǔ)格式依然存在差別，</p><p>　　框架之間相互調(diào)用首先需要調(diào)整圖的格式，還未形成一個(gè)完全統(tǒng)一的接口使得開</p><p>　　發(fā)人員無需修改已有代碼即可直接調(diào)用。</p><p>　　2、圖的持久化

48、存儲(chǔ)格式?jīng)]有統(tǒng)一的標(biāo)準(zhǔn)。泛型的運(yùn)用可以讓用戶使用自定義</p><p>　　類型來作為圖的元素，但大部分框架[5, 7, 12] 僅支持將一些簡(jiǎn)單數(shù)據(jù)類型的圖通過</p><p>　　文本矩陣的方式持久化到文件中，對(duì)于復(fù)雜的數(shù)據(jù)格式并沒有提供充分的支持。</p><p>　　3、處理大規(guī)模數(shù)據(jù)的能力各有差異。用于數(shù)據(jù)挖掘和社會(huì)網(wǎng)分析的框架[15]</p>

49、;<p>　　針對(duì)大規(guī)模數(shù)據(jù)處理作了優(yōu)化，而更多的框架側(cè)重于新算法的實(shí)現(xiàn)以及已有算法的改進(jìn)。以上的框架都沒有提供將圖保存到數(shù)據(jù)庫的接口，因此無法實(shí)現(xiàn)直接將圖的信息保存到數(shù)據(jù)庫中，僅在需要時(shí)才提取相關(guān)數(shù)據(jù)。</p><p>　　以上的框架都有著自身的特色和特定的使用對(duì)象，考慮到 CodeMiner 插件項(xiàng)</p><p>　　目的需求及特點(diǎn)，最終 MiningGraph 選擇以

50、 JGraphT 這個(gè)開源圖形庫為基礎(chǔ)進(jìn)行</p><p><b>　　擴(kuò)展開發(fā)。</b></p><p><b>　　--5--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　1.3 主要研究?jī)?nèi)容及特色</p><p>　　CodeMine

51、r 的研究?jī)?nèi)容是基于子圖發(fā)現(xiàn)和有限自動(dòng)機(jī)的設(shè)計(jì)模式識(shí)別。首先</p><p>　　采用抽象語義圖(Abstract Semantic Graph, ASG)來描述被研究的系統(tǒng)和設(shè)計(jì)模</p><p>　　式，將設(shè)計(jì)模式的識(shí)別就轉(zhuǎn)換為圖的子圖發(fā)現(xiàn)問題；其次，通過利用子圖匹配算</p><p>　　法來識(shí)別系統(tǒng)中的設(shè)計(jì)模式實(shí)例；最后，為了分析本方法實(shí)際效果，開發(fā)了<

52、;/p><p>　　Eclipse 平臺(tái)的插件 CodeMiner，并在 CodeMiner 進(jìn)行一系列的實(shí)驗(yàn)以評(píng)估該方法</p><p><b>　　和工具。</b></p><p>　　本文研究的主要內(nèi)容是如何實(shí)現(xiàn)圖的持久化存儲(chǔ)，以及圖同構(gòu)的判定算法的具體實(shí)現(xiàn)。由于 CodeMiner 采用的方法是基于圖的模式識(shí)別方法，需要實(shí)現(xiàn)基于可擴(kuò)展存儲(chǔ)結(jié)

53、構(gòu)的 MiningGraph 組件，用于保存表示系統(tǒng)源碼和設(shè)計(jì)模式的抽象語義圖，同時(shí)還需要提供圖論算法中圖運(yùn)算的基本操作。</p><p>　　在整個(gè) CodeMiner 項(xiàng)目中，MiningGraph 擔(dān)任著底層模塊的角色，提供一系列圖相關(guān)算法的操作，完成圖的創(chuàng)建，添加，修改以及圖的持久化等實(shí)現(xiàn)，為 CodeMiner 中設(shè)計(jì)模式的判定算法提供支持。</p><p>　　本文研究的著重點(diǎn)

54、是 MiningGraph 組件如何在 JGraphT 框架下進(jìn)行擴(kuò)展，實(shí)</p><p>　　現(xiàn)以下幾個(gè) CodeMiner 的需求：</p><p>　　對(duì) JGraphT 所提供的圖形接口進(jìn)行擴(kuò)展，以支持 CodeMiner 中抽象語義圖和有限自動(dòng)機(jī)圖的模型建立。</p><p>　　擴(kuò)展 JGraphT 中的 Exporter 接口，實(shí)現(xiàn)將圖以 GraphM

55、L 格式持久化到文件以及從文件中還原。</p><p>　　實(shí)現(xiàn)支持多種格式的存儲(chǔ)結(jié)構(gòu)，可將圖持久化到數(shù)據(jù)庫，從而僅在需要的時(shí)候才讀取相關(guān)的信息。</p><p>　　實(shí)現(xiàn)圖同構(gòu)的判定，以及確定同構(gòu)圖的對(duì)應(yīng)序列。</p><p><b>　　--6--</b></p><p><b>　　第一章 緒論</

56、b></p><p>　　1.4 本文結(jié)構(gòu)安排</p><p>　　第一章 緒論，介紹了本課題研究背景及實(shí)際意義、圖論算法國內(nèi)外研究現(xiàn)狀以及存在的問題等，最后闡述了本文的研究?jī)?nèi)容以及創(chuàng)新點(diǎn)，說明 MiningGraph 組件的在整個(gè)工程中的作用。</p><p>　　第二章 MiningGraph 的相關(guān)知識(shí)，介紹圖論的一些基本概念以及</p>

57、<p>　　MiningGraph 組件的相關(guān)知識(shí)。</p><p>　　第三章 MiningGraph 的總體架構(gòu)設(shè)計(jì)，說明 CodeMiner 挖掘代碼設(shè)計(jì)模式中的需求，對(duì)系統(tǒng)的總體架構(gòu)設(shè)計(jì)進(jìn)行了展示，闡述各個(gè)包的作用及在整個(gè)程序中的作用，以及持久化存儲(chǔ)與同構(gòu)判定的設(shè)計(jì)。</p><p>　　第四章 MiningGraph 的具體實(shí)現(xiàn)，詳細(xì)闡述 MiningGraph 將圖持

58、久化的意義和實(shí)現(xiàn)，以及 MiningGraph 中圖同構(gòu)判定算法的具體實(shí)現(xiàn)。</p><p>　　第五章 MiningGraph 的結(jié)果分析，分析 CodeMiner 在幾個(gè)不同規(guī)模的開源系統(tǒng)的源代碼上進(jìn)行實(shí)驗(yàn)所得出的結(jié)果，統(tǒng)計(jì)不同存儲(chǔ)結(jié)構(gòu)下的效率，并對(duì)本研究所采用方法的效果評(píng)估。</p><p>　　第六章對(duì)本論文的總結(jié)和展望，分析了本研究尚待優(yōu)化之處，對(duì)下一步研究的目標(biāo)進(jìn)行展望。<

59、;/p><p><b>　　--7--</b></p><p>　　第二章 M iningGraph 的相關(guān)知識(shí)</p><p>　　第二章MiningGraph 的相關(guān)知識(shí)</p><p>　　MiningGraph 主要提供了圖論中的基本算法與圖同構(gòu)的判定算法的實(shí)現(xiàn)。在</p><p>　　本節(jié)

60、中，將介紹一些與 MiningGraph 相關(guān)的知識(shí)，包括圖論中的一些基本概念，</p><p>　　圖同構(gòu)的定義與判斷條件，以及選擇在 Java 開源框架 JGraphT 上進(jìn)行擴(kuò)展開發(fā)的</p><p><b>　　原因。</b></p><p>　　2.1 圖論基本概念</p><p>　　2.1.1圖的定義&l

61、t;/p><p>　　在數(shù)學(xué)上，一個(gè)圖是表示物件與物件之間的關(guān)系的方法，是圖論的基本研究對(duì)象。圖(graph)是由兩個(gè)集合 V 和 E 所限定的一種數(shù)據(jù)結(jié)構(gòu)，記作 G=(V，E)。其中：V 是構(gòu)成圖的頂點(diǎn)的非空有限集, E 是表示頂點(diǎn)之間關(guān)系的邊的集合。</p><p>　　在實(shí)際圖的應(yīng)用中，可能會(huì)同時(shí)接觸若干個(gè)圖，為了區(qū)別不同圖的頂點(diǎn)集和邊集，常常將圖記作 G=(V(G)，E(G))。<

62、;/p><p>　　圖是一種網(wǎng)狀的數(shù)據(jù)結(jié)構(gòu)，其形式化的定義如下：</p><p>　　Graph = (V,R)</p><p>　　= {x | x∈DataObject} R = {VR}</p><p>　　VR = {<x,y>|P(x,y)∧(x,y∈V)}</p><p>　　其中 DataObje

63、ct 為一個(gè)有限集合，該集合中所有元素具有相同的特性。VR是這樣的兩個(gè)元素之間的關(guān)系的集合。P(x,y)表示 x 和 y 之間有特定的關(guān)聯(lián)屬性</p><p><b>　　P。</b></p><p>　　一個(gè)圖看起來是由一些小圓點(diǎn)(稱為結(jié)點(diǎn)，Node)和連結(jié)這些圓點(diǎn)的直線或曲線(稱為邊， Edge) 組成。其中，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將</p&

64、gt;<p><b>　　--9--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　結(jié)點(diǎn)稱為頂點(diǎn)(Vertex)，邊是頂點(diǎn)的有序偶對(duì)，若兩個(gè)頂點(diǎn)之間存在一條邊，就</p><p>　　表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系。</p><p>　　圖 2-1:有向圖與無向圖</p&

65、gt;<p>　　圖中的頂點(diǎn)與邊通常都有 Name 和 Type 兩個(gè)屬性，用于與其它的頂點(diǎn)或邊區(qū)別開來。當(dāng)圖中的頂點(diǎn)和邊都屬于相同或者不考慮頂點(diǎn)的名字或類型時(shí)，這兩個(gè)屬性都可被忽略。如圖 2-1 就沒有對(duì)頂點(diǎn)和邊作區(qū)分。</p><p>　　在圖 2-1 的兩個(gè)圖結(jié)構(gòu)中，左邊的是有向圖，即每條邊都有方向，右邊的是無向圖，即每條邊都沒有方向。</p><p>　　在有向圖中，

66、通常將邊稱作弧，含箭頭的一端稱為弧頭，另一端稱為弧尾，</p><p>　　記作<vi，vj>，它表示從頂點(diǎn) vi 到頂點(diǎn) vj 有一條邊。</p><p>　　若有向圖中有 n 個(gè)頂點(diǎn)，則最多有 n(n-1)條弧。具有 n(n-1)條弧的有向圖又</p><p>　　稱作有向完全圖。以頂點(diǎn) v 為弧尾的弧的數(shù)目稱作頂點(diǎn) v 的出度，以頂點(diǎn) v 為弧&l

67、t;/p><p>　　頭的弧的數(shù)目稱作頂點(diǎn) v 的入度。在無向圖中，邊記作(vi，vj)，它蘊(yùn)涵著存在<vi，vj>和<vj，vi>兩條弧。若無向圖中有 n 個(gè)頂點(diǎn)，則最多有 n(n-1)/2 條邊。具有 n(n-1)/2 條邊的無向圖又稱作無向完全圖。與頂點(diǎn) v 相關(guān)的邊的條數(shù)稱作頂點(diǎn) v</p><p><b>　　的度。</b></p&

68、gt;<p>　　路徑長(zhǎng)度是指路徑上邊或弧的數(shù)目。若第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則</p><p>　　這條路徑是一條回路。若路徑中頂點(diǎn)沒有重復(fù)出現(xiàn)，則稱這條路徑為簡(jiǎn)單路徑。</p><p><b>　　--10--</b></p><p>　　第二章 M iningGraph 的相關(guān)知識(shí)</p><p>

69、;　　在無向圖中，如果從頂點(diǎn) vi 到頂點(diǎn) vj 有路徑，則稱 vi 和 vj 連通。如果圖中任</p><p>　　意兩個(gè)頂點(diǎn)之間都連通，則稱該圖為連通圖，否則，將其中的極大連通子圖稱為</p><p><b>　　連通分量。</b></p><p>　　在有向圖中，如果對(duì)于每一對(duì)頂點(diǎn) vi 和 vj，從 vi 到 vj 和從 vj 到 vi

70、 都有路徑，</p><p>　　則稱該圖為強(qiáng)連通圖；否則，將其中的極大連通子圖稱為強(qiáng)連通分量。</p><p>　　2.1.2圖的基本操作</p><p>　　(1) CreateGraph(G)</p><p>　　操作前提：已知圖 G 不存在。</p><p>　　操作結(jié)果：創(chuàng)建圖 G</p>&

71、lt;p>　　(2)DestoryGraph(G)</p><p>　　操作前提：已知圖 G 存在。</p><p>　　操作結(jié)果：銷毀圖 G</p><p>　　(3)LocateVertex(G,v)</p><p>　　操作前提：已知圖 G 存在，頂點(diǎn) v 值合法</p><p>　　操作結(jié)果：若圖 G 中

72、存在頂點(diǎn) v，則返回頂點(diǎn) v 在 G 中的位置。若圖中沒</p><p>　　有頂點(diǎn) v，則函數(shù)返回值為空。</p><p>　　(4) GetVertex(G,i)</p><p>　　操作前提：已知圖 G 存在。</p><p>　　操作結(jié)果：返回圖 G 中的第 i 個(gè)頂點(diǎn)的值。若 i 大于圖 G 中的頂點(diǎn)數(shù)，則</p>&

73、lt;p><b>　　函數(shù)返回值為空。</b></p><p>　　(5)FirstAdjVertex(G,v)</p><p>　　操作前提：已知圖 G 存在，頂點(diǎn) v 合法。</p><p><b>　　--11--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p&

74、gt;<p>　　操作結(jié)果：返回圖 G 中頂點(diǎn) v 的第一個(gè)鄰接點(diǎn)。若 v 無鄰接點(diǎn)或圖 G 中無</p><p>　　頂點(diǎn) v，則函數(shù)返回值為空。</p><p>　　(6)NextAdjVertex(G,v,w)</p><p>　　操作前提：已知圖 G 存在,w 是圖 G 中頂點(diǎn) v 的某個(gè)鄰接點(diǎn)。</p><p>　　操

75、作結(jié)果：返回圖 G 中頂點(diǎn) v 的下一個(gè)鄰接點(diǎn)(緊跟在 w 后面的鄰接點(diǎn))。</p><p>　　w 是 v 的最后一個(gè)鄰接點(diǎn)，則函數(shù)返回值為空。</p><p>　　(7)InsertVertex(G,u)</p><p>　　操作前提：已知圖 G 存在,u 值合法。操作結(jié)果：將頂點(diǎn) u 添加到圖 G 中。</p><p>　　(8)Del

76、eteVertex(G,v)</p><p>　　操作前提：已知圖 G 存在,v 值合法。</p><p>　　操作結(jié)果：刪除圖 G 中的頂點(diǎn) v 及與頂點(diǎn) v 相關(guān)聯(lián)的邊。</p><p>　　(9)InsertEdge(G，v，w)</p><p>　　操作前提：已知圖 G 存在,v 值，w 值合法。</p><p&g

77、t;　　操作結(jié)果：在圖 G 中增加一條從頂點(diǎn) v 到頂點(diǎn) w 的邊。</p><p>　　(10)DeleteEdge(G，v，w)</p><p>　　操作前提：已知圖 G 存在,v 值，w 值合法,存在邊(v,w)。</p><p>　　操作結(jié)果：刪除圖 G 中從頂點(diǎn) v 到頂點(diǎn) w 的邊。</p><p>　　(11)TraverseE

78、dge(G)</p><p>　　操作前提：已知圖 G 存在。</p><p>　　操作結(jié)果：按照某種次序，對(duì)圖 G 中的每一個(gè)頂點(diǎn)訪問一次并且只訪問一</p><p><b>　　次。</b></p><p><b>　　--12--</b></p><p>　　第二章 M

79、 iningGraph 的相關(guān)知識(shí)</p><p>　　(11) IsIsomorphic(G, H)</p><p>　　操作前提：已知圖 G、圖 H 存在。</p><p>　　操作結(jié)果：若圖 G 與圖 H 是同構(gòu)的，函數(shù)返回值為 true，否則函數(shù)返回</p><p><b>　　值為 false。</b><

80、/p><p>　　2.1.3圖的存儲(chǔ)結(jié)構(gòu)</p><p>　　圖的存儲(chǔ)結(jié)構(gòu)描述的是圖在程序中的組織方式，通常會(huì)以鄰接矩陣、鄰接表、</p><p>　　十字鏈表或鄰接多重表的方式進(jìn)行存儲(chǔ)。</p><p><b>　　鄰接矩陣</b></p><p>　　圖的鄰接矩陣表示法(Adjacency Ma

81、trix)也稱作數(shù)組表示法，它采用兩個(gè)數(shù)組來表示圖：一個(gè)是用于存儲(chǔ)頂點(diǎn)信息的一維數(shù)組，另一個(gè)是用于存儲(chǔ)圖中頂點(diǎn)之間關(guān)聯(lián)關(guān)系的二維數(shù)組，這個(gè)關(guān)聯(lián)關(guān)系數(shù)組被稱為鄰接矩陣。鄰接矩陣結(jié)構(gòu)簡(jiǎn)單，使用方便，是處理小規(guī)模圖問題的首選存儲(chǔ)格式。</p><p>　　G 是一具有 n 個(gè)頂點(diǎn)的無權(quán)圖，G 的鄰接矩陣是具有如下性質(zhì)的 n×n 的矩</p><p><b>　　A：</

82、b></p><p>　　若圖 G 是一個(gè)有 n 個(gè)頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的 n×n 矩陣</p><p><b>　　：</b></p><p><b>　　A[i ,</b></p><p><b>　　j]</b></p>&

83、lt;p>　　?????wij ,<vi , v j >或(vi</p><p><b>　　???,反之</b></p><p><b>　　, vj</b></p><p><b>　　)</b></p><p><b>　　?VR</

84、b></p><p>　　圖 2-2 中的 A1，A2，A3 分別示意了無向圖 G1，有向圖 G2 和有向非聯(lián)通圖 G3 的鄰接矩陣的表示情況。</p><p><b>　　--13--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　圖 2-2:鄰接矩陣的圖表示</p>

85、<p><b>　　鄰接矩陣法的特點(diǎn)：</b></p><p>　　存儲(chǔ)空間：根據(jù)鄰接矩陣的特點(diǎn)，對(duì)于無向圖而言，它的鄰接矩陣是斜對(duì)稱矩陣，所以可采用壓縮存儲(chǔ)法(下三角法)，即僅存儲(chǔ)左下角的 n(n-1)/2 個(gè)元素的信息。因此，這樣的存儲(chǔ)空間只需 n(n-1)/2。但對(duì)于有向圖而言，因?yàn)樗幕∈怯蟹较虻?，它的鄰接矩陣不一定是?duì)稱矩陣，無法直接對(duì)其采用壓縮存儲(chǔ)法，所以需要 n2

86、 個(gè)存儲(chǔ)空間。</p><p>　　便于運(yùn)算：采用鄰接矩陣表示法，便于判定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連，即根據(jù) A[i，j]=0 或 1 來判斷。另外還便于求得各個(gè)頂點(diǎn)的度，或者找出頂點(diǎn)的鄰接點(diǎn)。如在采用鄰接矩陣存儲(chǔ)法表示的圖中，首先由 LocateVertex(G，</p><p>　　v)找到 v 在圖中的位置，即 v 在一維數(shù)組 vexs 中的序號(hào) i。二維數(shù)組 arcs 中第

87、i</p><p>　　行上第一個(gè) adj 域非零的分量所在的列號(hào) j，便是 v 的第一個(gè)鄰接點(diǎn)在圖 G 中的</p><p>　　位置。取出一維數(shù)組 vexs[j]中的數(shù)據(jù)信息，即與頂點(diǎn) v 鄰接的第一個(gè)鄰接點(diǎn)的</p><p><b>　　信息。</b></p><p><b>　　鄰接表</b>

88、;</p><p><b>　　--14--</b></p><p>　　第二章 M iningGraph 的相關(guān)知識(shí)</p><p>　　圖的鄰接表(Adjacency List)表示法實(shí)際上是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 它的基本思想是只存有關(guān)聯(lián)的信息，對(duì)于圖中存在的邊信息則存儲(chǔ)，而對(duì)于不相鄰接的頂點(diǎn)則不保留信息。在鄰接表中，對(duì)圖中的每個(gè)頂點(diǎn)建立

89、一個(gè)帶頭結(jié)點(diǎn)的邊鏈表，每個(gè)邊鏈表的頭結(jié)點(diǎn)又構(gòu)成一個(gè)表頭結(jié)點(diǎn)表。這樣，一個(gè) n 個(gè)頂點(diǎn)的圖的鄰接表表示由表頭結(jié)點(diǎn)表與邊表兩部分構(gòu)成。</p><p>　　在鄰接表中，第 i 個(gè)單鏈表中的結(jié)點(diǎn)表示關(guān)聯(lián)于頂點(diǎn) i 的邊(對(duì)有向圖則是以</p><p>　　頂點(diǎn) i 為始點(diǎn)的弧)。表 結(jié)點(diǎn)的結(jié)構(gòu)根據(jù)無權(quán)圖和有權(quán)圖而有所不同，無權(quán)圖的</p><p>　　表結(jié)點(diǎn)由三個(gè)域組成，

90、其中鄰接頂點(diǎn)域(adjvex)存儲(chǔ)與頂點(diǎn) i 鄰接的頂點(diǎn)的編號(hào)</p><p>　　(即該頂點(diǎn)在圖中的位置)，鏈域(next)指向頂點(diǎn) i 的單鏈表中的表示關(guān)聯(lián)于頂點(diǎn)</p><p>　　的下一個(gè)表結(jié)點(diǎn)。而對(duì)于有權(quán)圖，為了表示邊上的權(quán)，則表結(jié)點(diǎn)中增設(shè)了存儲(chǔ)該邊上權(quán)值的域(weight)。每個(gè)單鏈表附設(shè)一個(gè)頭結(jié)點(diǎn)，頭結(jié)點(diǎn)中除了設(shè)有指向單鏈表的第一個(gè)表結(jié)點(diǎn)的鏈域(first)外，還設(shè)有存儲(chǔ)第

91、i 個(gè)頂點(diǎn)信息的數(shù)據(jù)域</p><p><b>　　(data)。</b></p><p>　　表頭結(jié)點(diǎn)表：由所有表頭結(jié)點(diǎn)以順序結(jié)構(gòu)的形式存儲(chǔ)，以便可以隨機(jī)訪問任</p><p>　　一頂點(diǎn)的單鏈表。表頭結(jié)點(diǎn)有兩部分構(gòu)成，其中數(shù)據(jù)域(vexdata)用于存儲(chǔ)頂點(diǎn)的</p><p>　　名或其它有關(guān)信息；鏈域(firsta

92、rc)用于指向鏈表中第一個(gè)頂點(diǎn)(即與頂點(diǎn) vi 鄰</p><p>　　接的第一個(gè)鄰接點(diǎn))。表頭結(jié)點(diǎn)結(jié)構(gòu)為：</p><p>　　vexdatafirstarc</p><p>　　邊表：由表示圖中頂點(diǎn)間鄰接關(guān)系的 n 個(gè)邊鏈表組成。它由三部分組成，其</p><p>　　中鄰接點(diǎn)域(adjvex)用于存放與頂點(diǎn) vi 相鄰接的頂點(diǎn)在圖中的

93、位置；鏈域</p><p>　　(nextarc)用于指向與頂點(diǎn) vi 相關(guān)聯(lián)的下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域(info)用于</p><p>　　存放與邊或弧相關(guān)的信息(如賦權(quán)圖中每條邊或弧的權(quán)值等)?；〗Y(jié)點(diǎn)結(jié)構(gòu)為：</p><p>　　adjvexinfonextarc</p><p>　　對(duì)于用鄰接表方式存儲(chǔ)的有向圖，求頂點(diǎn)的入度并不方

94、便，它需要掃描整個(gè)</p><p>　　鄰接表才能得到結(jié)果。一種解決的方法是建立逆鄰接表。可以對(duì)每一頂點(diǎn) vi 再建</p><p>　　立一個(gè)逆鄰接表，即對(duì)每個(gè)頂點(diǎn) vi 建立一個(gè)所有以頂點(diǎn) vi 為弧頭的表，這樣求頂</p><p>　　點(diǎn) vi 的入度即是計(jì)算逆鄰接表中第 i 個(gè)結(jié)點(diǎn)的邊鏈表中的結(jié)點(diǎn)個(gè)數(shù)。</p><p><b&g

95、t;　　--15--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　圖 2-3 是一張有向圖的鄰接表與逆鄰接表示意圖。</p><p>　　圖 2-3 ：有向圖的鄰接表與逆鄰接表</p><p>　　鄰接表具有以下特點(diǎn)：</p><p>　　存儲(chǔ)空間：對(duì)于有 n 個(gè)頂點(diǎn)，e

96、 條邊的無向圖而言，若采取鄰接表作為存儲(chǔ)結(jié)構(gòu)，則需要 n 個(gè)表頭結(jié)點(diǎn)和 2e 個(gè)表結(jié)點(diǎn)。</p><p>　　無向圖的度：在無向圖的鄰接表中，頂點(diǎn) vi 的度恰好就是第 i 個(gè)邊鏈表上結(jié)點(diǎn)的個(gè)數(shù)。</p><p>　　有向圖的度：在有向圖中，第 i 個(gè)邊鏈表上頂點(diǎn)的個(gè)數(shù)是頂點(diǎn) vi 的出度。要想求得該頂點(diǎn)的入度，則必須遍歷整個(gè)鄰接表。在所有單鏈表中查找鄰接點(diǎn)域的值為 i 的結(jié)點(diǎn)并計(jì)數(shù)求和。

97、</p><p><b>　　十字鏈表</b></p><p>　　十字鏈表(Orthogonal List)是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?？梢园阉闯墒菍⒂邢驁D的鄰接表和逆鄰接表結(jié)合起來形成的一種鏈表。有向圖中的每一條弧對(duì)應(yīng)十字鏈表中的一個(gè)弧結(jié)點(diǎn)，同時(shí)有向圖中的每個(gè)頂點(diǎn)在十字鏈表中對(duì)應(yīng)有一個(gè)結(jié)點(diǎn)，叫做頂點(diǎn)結(jié)點(diǎn)。</p><p><b&g

98、t;　　弧結(jié)點(diǎn)的結(jié)構(gòu)如下：</b></p><p>　　tailvexheadvexhlinktlinkinfo</p><p>　　在弧結(jié)點(diǎn)中，tailvex 表示弧尾頂點(diǎn)在圖中的位置，headvex 表示弧頭頂點(diǎn)在圖中的位置，hlink 指向與此弧的弧頭相同的下一條弧，tlink 指向與此弧的弧尾相同的下一條弧，info 指向該弧的相關(guān)信息。</p>

99、<p><b>　　--16--</b></p><p>　　第二章 M iningGraph 的相關(guān)知識(shí)</p><p>　　頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)如下：</p><p>　　datafirstinfirstout</p><p>　　在頂點(diǎn)結(jié)點(diǎn)中，data 域用來存儲(chǔ)與頂點(diǎn)相關(guān)的信息，如頂點(diǎn)的名字等，</

100、p><p>　　firstin 域(鏈域)用于指定以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)，firstout 域(鏈域)</p><p>　　用于指定以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)。</p><p>　　圖 2-4 是一張十字鏈表的示意圖</p><p>　　圖 2-4 ：十字鏈表示意圖</p><p>　　十字鏈表具有以下特點(diǎn)：<

101、;/p><p>　　在十字鏈表中既能夠很容易地找到以 vi 為尾的弧，也能夠容易地找到以 vi</p><p>　　為頭的弧，因此對(duì)于有向圖，若采用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，則很容易求出頂點(diǎn)</p><p><b>　　vi 的度。</b></p><p><b>　　鄰接多重表</b></p>

102、<p>　　鄰接多重表(Adjacency Multi_list)是無向圖的另外一種存儲(chǔ)結(jié)構(gòu)。使用鄰接多重表這種存儲(chǔ)結(jié)構(gòu)是因?yàn)樗軌蛱峁└鼮榉奖愕倪吿幚硇畔?。鄰接多重表是指將圖中關(guān)于一條邊的信息用一個(gè)結(jié)點(diǎn)來表示，圖中的每一個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)頂點(diǎn)結(jié)點(diǎn)。</p><p>　　鄰接多重表的邊結(jié)點(diǎn)的結(jié)構(gòu)如下：</p><p><b>　　--17--</b><

103、;/p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　markivexilinkjvexjlinkinfo</p><p>　　在邊結(jié)點(diǎn)中，mark 是標(biāo)志域，可用來標(biāo)記該條邊是否已經(jīng)被搜索過；ivex</p><p>　　jvex 為該邊依附的兩個(gè)頂點(diǎn)在圖中的位置；ilink 用于指向下一條邊依附于頂點(diǎn) ivex 的

104、邊；jlink 用于于指向下一條邊依附于頂點(diǎn) jvex 的邊；info 包含著該邊的信息。</p><p>　　鄰接多重表的頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)如下：</p><p>　　datafirstedge</p><p>　　在頂點(diǎn)結(jié)點(diǎn)中，data 域用來存儲(chǔ)與頂點(diǎn)相關(guān)的信息，如頂點(diǎn)的名字等，</p><p>　　firstedge 域用于指向第一條依

105、附于該頂點(diǎn)的邊。</p><p>　　圖 2-5 是一張鄰接多重表示意圖：</p><p>　　圖 2-5 ：鄰接多重表表示意圖</p><p>　　鄰接多重表具有以下特點(diǎn)：</p><p>　　節(jié)省空間，每個(gè)結(jié)點(diǎn)只保存了圖中的頂點(diǎn)與邊的相關(guān)信息，不會(huì)造成額外的</p><p><b>　　空間浪費(fèi)。<

106、/b></p><p><b>　　--18--</b></p><p>　　第二章 M iningGraph 的相關(guān)知識(shí)</p><p>　　操作方便，既能夠很容易地找到以 vi 為尾的弧，也能夠容易地找到以 vi 為頭的弧，因此對(duì)于無向圖，若采用鄰接多重表作為存儲(chǔ)結(jié)構(gòu)，則很容易求出頂點(diǎn) vi 的度。</p><p&

107、gt;　　對(duì)于這幾種不同的存儲(chǔ)方式，都有著各自獨(dú)特的優(yōu)缺點(diǎn)，不同的算法應(yīng)根據(jù)自身特點(diǎn)來選擇具體的存儲(chǔ)方式以獲得最佳的效果。表 2-1 描述了這幾種存儲(chǔ)方式的優(yōu)缺點(diǎn)及運(yùn)算時(shí)的時(shí)間復(fù)雜度。</p><p>　　表 2-1：各種圖存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)比較</p><p>　　2.2圖同構(gòu)定義及判定條件</p><p>　　同構(gòu)(Isomorphism)是在數(shù)學(xué)對(duì)象之間定義的

108、一類映射，它能揭示出在這些對(duì)象的屬性或者操作之間存在的關(guān)系。若兩個(gè)數(shù)學(xué)結(jié)構(gòu)之間存在同構(gòu)映射，那么這兩個(gè)結(jié)構(gòu)叫做是同構(gòu)的(Isomorphic)。如果兩個(gè)結(jié)構(gòu)是同構(gòu)的，那么其上的對(duì)象會(huì)有相似的屬性和操作。一般來說，如果忽略掉同構(gòu)的對(duì)象的屬性或操作的具體定義，單從結(jié)構(gòu)上講，同構(gòu)的對(duì)象是完全等價(jià)的。</p><p>　　圖的同構(gòu)判定問題是圖論學(xué)科中的基本問題之一。其嚴(yán)格的定義如下：</p><p&g

109、t;<b>　　--19--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　定義 1. 圖 G(V,E) 和 G′(V′,E′) 同構(gòu)，若存在 V 到 V′的一個(gè)雙射φ ，使得 P ( u,v) ∈E ] (φ ( u),φ ( v) ) ∈E′，且( u , v) 的重?cái)?shù)和(φ ( u) ,</p><p>

110、　　( v) ) 的重?cái)?shù)相同。</p><p>　　在圖論中，如果存在兩張圖是同構(gòu)的，那么這它們必須同時(shí)具備以下幾個(gè)條</p><p><b>　　件：</b></p><p><b>　　圖的頂點(diǎn)相同</b></p><p><b>　　圖的邊相同</b></p>

111、<p>　　存在對(duì)應(yīng)的拓?fù)浣Y(jié)構(gòu)，使得兩張圖具有相同的序列。</p><p>　　2-6 演示了兩個(gè)同構(gòu)的圖。</p><p><b>　　v1v3</b></p><p>　　v2 v3v1 v2</p><p>　　圖 2-6 ：完全同構(gòu)圖</p><p>　　在

112、判斷兩張圖是否同構(gòu)時(shí)，由于頂點(diǎn)和邊可以具有不同的屬性，需要根據(jù)需</p><p>　　求對(duì)相應(yīng)的頂點(diǎn)和邊的屬性進(jìn)行比較來判斷頂點(diǎn)或邊是否相同。如圖 2-7 中的兩</p><p>　　個(gè)圖 G1 和 G2，G1 的頂點(diǎn)為灰色的實(shí)心圓，邊為實(shí)線有向邊，而 G2 的頂點(diǎn)為空心藍(lán)</p><p>　　色五邊形，邊為折虛線有向邊。如果考慮它們的頂點(diǎn)或邊的屬性，則這兩張圖是&

113、lt;/p><p>　　不同構(gòu)的。但如果僅考慮其圖形組織結(jié)構(gòu)而忽略頂點(diǎn)和邊的屬性，G1 和 G2 兩張圖</p><p>　　都可以抽象成相同的五邊形，在這樣的情況下，認(rèn)為 G1 和 G2 是同構(gòu)的。</p><p><b>　　--20--</b></p><p>　　第二章 M iningGraph 的相關(guān)知識(shí)</

114、p><p><b>　　G1G2</b></p><p>　　圖 2-7：同構(gòu)待判定圖</p><p>　　這也說明在判斷圖同構(gòu)時(shí)需要指定所比較的頂點(diǎn)和邊的屬性。又如圖 2-8，</p><p>　　頂點(diǎn)包含了名字和性別兩個(gè)屬性，如果僅比較頂點(diǎn)中的性別屬性可得到兩個(gè)相同</p><p>　　的“(男

115、)→(女)→(男)”序列，即認(rèn)為這兩個(gè)圖是同構(gòu)的。如果同時(shí)比較頂點(diǎn)中</p><p>　　的名字和性別屬性，將得到“(張明，男)→(王娟，女)→(劉磊，男)”的序列和</p><p>　　“(李平，男)→(張媛，女)→(陳軍，男)”兩個(gè)不同的序列，此時(shí)則認(rèn)為兩圖不</p><p><b>　　同構(gòu)。</b></p><p&g

116、t;<b>　　張明男</b></p><p><b>　　李平男</b></p><p><b>　　王娟女</b></p><p><b>　　張媛女</b></p><p><b>　　劉磊男</b></p>

117、;<p><b>　　陳軍男</b></p><p>　　圖 2-8：同構(gòu)判定需要指定屬性</p><p>　　圖同構(gòu)既未被歸入 P 問題，也未被歸入 NPC 問題，是一個(gè)尚未解決的問題[19] ，</p><p>　　理論上可以證明圖同構(gòu)判定算法屬于 NP 問題，即它的結(jié)果的驗(yàn)證時(shí)間為多項(xiàng)式</p><p

118、><b>　　--21--</b></p><p>　　基于子圖發(fā)現(xiàn)的設(shè)計(jì)模式識(shí)別系統(tǒng)</p><p>　　級(jí)，但是仍然沒有對(duì)它的求解復(fù)雜度的證明。也就是說目前既不能說它的復(fù)雜度是多項(xiàng)式級(jí)，也不能說一定不是多項(xiàng)式級(jí)。多年來，人們一直在尋找一種有效的同構(gòu)判定方法，但是至今為止對(duì)于圖的匹配目前還沒有一個(gè)多項(xiàng)式級(jí)的好算法。</p><p>　　

119、在關(guān)于圖同構(gòu)的研究中，有人試圖用圖的一組不變量來確定圖的同構(gòu)，如回</p><p>　　路數(shù)、樹數(shù)、連通片數(shù)等，這些嘗試都?xì)w于失敗[20] 。因?yàn)椴煌瑯?gòu)的圖也會(huì)出現(xiàn)完</p><p>　　全相同的不變量，有人曾經(jīng)認(rèn)為圖的鄰接矩陣的特征多項(xiàng)式和特征值可能是圖的</p><p>　　同構(gòu)判據(jù)，結(jié)果依然失敗了，因?yàn)椴煌瑯?gòu)的圖也可能有相同的特征多項(xiàng)式和特征</p&g