基本信息
- 項目名稱：
- 無向關系圖結點定位軟件
- 小類：
- 信息技術
- 大類：
- 科技發(fā)明制作A類
- 簡介：
- 《無向關系圖結點定位軟件》是將描述結點及其關系的無向關系圖的文本文件或數(shù)據(jù)庫文件讀入，再經(jīng)過軟件確定結點在某個二維矩形區(qū)域內(nèi)的坐標位置，最后按照這些坐標在屏幕上輸出結點并按關系連線，得到連線清晰化的無向關系圖的圖形化顯示結果，或者將這些坐標依照文本文件或數(shù)據(jù)庫文件的形式保存輸出，供下游軟件使用。
- 詳細介紹：
- 在計算機科學與技術中，描述一組對象之間的關系經(jīng)常用無向圖表示，而此類關系信息的獲取形式往往是無向圖的邏輯表示，如表格、數(shù)據(jù)庫、鄰接矩陣，這種邏輯表示很不直觀，所以人們喜歡用平面上的圖重新表示，將表示對象的結點用一個圓點或小圓圈表示，再將對象間的關系用一條條連接兩個結點的線表示。這種圖形化表示固然直觀，但存在一個問題：如果一開始結點的位置擺放得不好，畫連線時會產(chǎn)生縱橫交錯的結果，畫出來的圖關系不清晰，連線產(chǎn)生交叉、遠跨或重疊。所以結點的定位很重要，如果有一種能保證連線清晰的結點自動定位方法，那么在結點位置確定之后，根據(jù)無向關系將一對對的結點用直線段連接起來就行了。這就是我們項目所要研究的無向關系圖結點定位技術。 無向關系圖結點定位軟件主要用于基于無向圖的關系模型如產(chǎn)品關聯(lián)圖、文檔抄襲關系圖、數(shù)據(jù)引用圖、路由分布圖、知識點依賴圖、軟件工程PERT圖、組織關系圖、模塊關系圖等的圖形化輸出，通過結點坐標的合理確定，使關系連線清晰美觀，連通分支分離易辨。 我們可以將無向關系圖結點定位技術植入軟件工程、識別系統(tǒng)、Visio、Cisco Packet Tracer等應用技術、系統(tǒng)或軟件中去，使這些應用技術、系統(tǒng)或軟件更加自動化、智能化、高效率、實用化和人性化。
作品圖片
作品專業(yè)信息
設計、發(fā)明的目的和基本思路、創(chuàng)新點、技術關鍵和主要技術指標
- 目的：在計算機科學與技術中，表示對象之間的關系通常用無向圖表示。這種圖形化表示固然直觀，但存在一個問題：如果一開始結點的位置擺放得不好，畫出來的圖關系就會不清晰。如果有一個能保證連線清晰化的無向關系圖結點定位軟件，對一副關系混亂的無向圖重新確定結點位置后能使關系圖變得清晰美觀，將很大程度上便于我們分析和理解無向關系圖。而設計這款無向關系圖結點定位軟件就是本項目的目的。 基本思路：無向關系圖結點定位軟件采用圖內(nèi)割邊、團內(nèi)割點的識別技術，并基于樹型結構實現(xiàn)區(qū)域劃分，采用逐步清晰的方法，最終使無向關系圖達到視覺上清晰的目的。 創(chuàng)新點：（1）采用割邊割點識別技術，將連通圖分解為團與子團后再定位。 （2）非迭代方法，直接定位，比遺傳算法、模擬退火等進化算法要直接、快速得多。 技術關鍵和主要技術指標：軟件采用割邊割點識別技術，將連通圖分解為團與子團后再定位，可以使最終顯示的無向關系圖的關系連線盡量不交叉、不遠跨、不重疊，關系結點組匯聚成團，能清晰地看出結點間的連接關系和分組情況。定位結果既可以直接顯示，又可以通過文件接口輸出，支持文本文件和Access數(shù)據(jù)庫兩種格式。
科學性、先進性
- 本軟件采用的無向關系圖結點定位方法首先將無向關系圖去除孤立點、分離連通分支，并通過識別割邊將每個連通分支分解成一系列的團，每個團內(nèi)無割邊，這些團以樹型結構連接，然后通過識別割點和虛連線將每個團分解成子團，每個子團內(nèi)無割點，最后將子團內(nèi)頂點均勻分布在一個圓環(huán)上。該方法具有實現(xiàn)方便，方法簡單，運行高效，輸出結果美觀，易于并行化等優(yōu)點。
獲獎情況及鑒定結果
- 本項目是2009年度浙江省大學生科技創(chuàng)新活動計劃（新苗人才計劃）立項（項目編號：2009R424008）成果，該大學生科技創(chuàng)新活動計劃項目已于2010年12月通過溫州大學大學生科技評審委員會評審，并同意結題。 2011年3月在浙江省科技信息研究院做科技查新報告，查新結論：無向關系圖結點定位軟件在檢索到的相關國內(nèi)文獻中未見具體述及。 2011年3月在浙江省電子產(chǎn)品檢驗所做軟件鑒定評測。 2011年3月向中國版權保護中心申請軟件著作權登記，流水號：2011R11L015531。 2011年4月向國家知識產(chǎn)權局專利局申請發(fā)明專利。
作品所處階段
- 中試階段
技術轉讓方式
- 軟件銷售，專利轉讓。
作品可展示的形式
- 實物、產(chǎn)品；現(xiàn)場演示。
使用說明,技術特點和優(yōu)勢,適應范圍,推廣前景的技術性說明,市場分析,經(jīng)濟效益預測
- 使用說明：本軟件的功能是將一副無向關系圖讀入，通過結點坐標的合理定位使無向圖關系連線清晰可辨，或者將定位后的無向圖保存，供下游軟件使用。 技術特點和優(yōu)勢：（1）定位方法模型簡單，效率高，且屬于確定性方法。（2）支持多種格式的無向關系圖的數(shù)據(jù)文件。 適用范圍及推廣情景：我們可以將無向關系圖結點定位軟件植入軟件工程、識別系統(tǒng)、Visio、Cisco Packet Tracer等應用技術、系統(tǒng)或軟件中去，使這些應用技術、系統(tǒng)或軟件更加自動化、智能化、高效率、實用化和人性化。我們也可以將本軟件應用于數(shù)據(jù)挖掘、模式識別等領域。 市場分析和經(jīng)濟效益預測：一方面，Cisco Packet Tracer軟件和Visio軟件是應用很廣泛的軟件，但這兩款軟件沒有提供關系清晰化的技術，而我們的軟件彌補了這兩款軟件的不足，能使這兩款軟件使用起來更加方便。 另一方面，本軟件能用于超市等機構的產(chǎn)品間數(shù)據(jù)挖掘，使產(chǎn)品間的關系直觀、清晰，便于決策者做出正確的商業(yè)決策。
同類課題研究水平概述
- 目前，現(xiàn)有的無向關系圖結點定位方法各有所長，也各有所短。他們主要分為兩類，一類是基于最優(yōu)化方法的結點定位方法，該方法的特點是將無向關系圖結點定位問題轉發(fā)為函數(shù)優(yōu)化問題，用基于某種算法或模型求目標函數(shù)最優(yōu)解的近似解，從而改變結點位置。該方法的的優(yōu)點在于方法簡單，易于實現(xiàn)，普遍適用于不同特點的無向圖，缺點在于計算量大，最終結果不確定，且收斂性差。其中，基于遺傳算法實現(xiàn)無向關系圖結點定位的方法是該類方法中一種主流的方法。基于遺傳算法實現(xiàn)無向關系圖結點定位是將無向圖結點定位問題轉化為約束優(yōu)化問題，即轉化為計算某個帶有約束條件的函數(shù)的最小值或最大值。不同的結點定位方法其實質在于設計不同的目標函數(shù)。但遺傳算法屬于概率算法，算法執(zhí)行結果具有不確定性，同時，想要得到好的輸出結果，需要經(jīng)過相當長的時間演化，因此算法收斂性較差。 另一類方法是基于某類確定算法實現(xiàn)無向圖結點定位的方法。該方法的特點是經(jīng)過一個算法，最終確定結點的最后位置。相比于前者，該類方法的一個顯著優(yōu)點在于，計算量明顯減小，且最終結點位置確定，不會隨著執(zhí)行的次數(shù)不同而不同。但設計一個算法適用于不同特點的無向圖并非易事，這樣的結點定位方法往往對滿足某些特點的無向圖才能達到很好的效果。其中，該類方法中，比較有代表性的是將無向圖顯示在環(huán)上，根據(jù)每個結點的加權值確定其所占有的扇形區(qū)域，并將每個結點布局在其扇區(qū)的中心線上的方法。
