制作的圖形演算法設(shè)計(jì)與分析平臺(tái)

以Java製作的圖形演算法設(shè)計(jì)與分析平臺(tái)

Java-basedGraphAlgorithmsDesignandAnalysisPlatform(JGAP)碩士論文

指導(dǎo)教授：蔡鍚鈞1999年7月30日國(guó)際暨南國(guó)際大學(xué)科技大樓三館113室研究生：陳定彝國(guó)立暨南國(guó)際大學(xué)資訊管理學(xué)系1報(bào)告大綱研究動(dòng)機(jī)圖形表示法與資料結(jié)構(gòu)系統(tǒng)架構(gòu)系統(tǒng)使用範(fàn)例未來(lái)發(fā)展及研究方向2設(shè)計(jì)圖形演算法需要什麼圖形顯示能力圖形輸入能力效率評(píng)估能力3現(xiàn)有圖形演算法展示程式單一演算法展示程式缺點(diǎn)：其他演算法無(wú)法運(yùn)用AlgorithmAnimationscript

(如JAWAA、JSamba)共通的缺點(diǎn)不提供讓使用者自由輸入使用者必須自己處理顯示畫面無(wú)法評(píng)估演算法效率4JGAP的特性檔案處理圖形產(chǎn)生常用演算法演算法的執(zhí)行與顯示PerformanceMeter歷程記錄(HistoryList)網(wǎng)際網(wǎng)路顯示能力5Graph04213246813identity:0position:(x,y)color:white…………...From1,To2Weight6Color:Black……….6圖形表示法Edge-List圖形表示法AdjacencyList圖形表示法AdjacencyMatrix圖形表示法AdjacencyListArray圖形表示法7Edge-List圖形表示法Edge(0,1)Weight302134Edge(0,2)Weight41028Adjacency-List圖形表示法Edge(0,1)Weight302134Edge(0,2)Weight4102inout(0,1)(0,2)inout(0,1)inout(0,2)9Adjacency-Matrix圖形表示法02134012012Edge(0,1)Weight3Edge(0,2)Weight410Adjacency-Matrix圖形表示法02134012012Edge(0,1)Weight3Edge(0,2)Weight411各圖形表示法之

圖形方法的時(shí)間複雜度之比較12ListArray13ListItemObject(x,y)Link=falseprevXnextXprevYnextY14在ListArray中加入元素LI0Obj0(0)LI2Obj2(1)LI1Obj1(2)0123firstlast15在ListArray中刪除元素LI0Obj0(0)LI2Obj2(1)LI1Obj1(2)0123firstlast16ListArray217在ListArray2中加入元素LI0Obj0(0,2)LI1Obj1(1,0)LI2Obj2(2,1)LI3Obj3(2,2)01201218在ListArray2中加入LinkLI0Obj0(0,0)LI1Obj1(1,2)LI2Obj1(2,1)01201219在ListArray2中刪除元素LI0Obj0(0,2)LI1Obj1(1,0)LI2Obj2(2,1)LI3Obj3(2,2)20JGAP架構(gòu)圖algorithmJGAPUIUserInputGraphGeneratorPreviousOutput21ClassContainmentJGAPFrameJGAPMenuGraphCanvasAlgorithmMenuHistoryMenuDialogsinJGAP.UIGraphVertexEdgeShowGraphWindowGraphCanvasGraphVertexEdge22ClassHierarchyGenericFrameGenericDialogAlgorithmDialogsinAlgor.UIDialogsinJGAP.UIDialogsinUIJGAPFrameShowGraphWindowAlgorithmsinAlgor23圖形處理JGAP可以接受的圖形來(lái)源:手繪圖形隨機(jī)圖形產(chǎn)生器前一個(gè)演算法的產(chǎn)出結(jié)果24手繪圖形25隨機(jī)圖產(chǎn)生器26隨機(jī)bipartite圖產(chǎn)生器27圖形運(yùn)算(Union)01221010228圖形運(yùn)算(SymmetricDifference)01221010229HistoryList30Algorithm「卡匣」架構(gòu)圖AlgorithmCartridgealgorImplshowexecutesetArggraph,argumentgraph,argumentgetPreferedDialog31插入Algorithm卡匣32將Algorithm「銲」在JGAP上焊接三部曲做出一個(gè)新的MenuItem設(shè)定該MenuItem所對(duì)應(yīng)的動(dòng)作重新編譯程式33JGAP所提供的clab.Aclab.Algor.UIclab.Algor.Uclab.DataSclab.JGAPclab.JGAP.UIclab.Tclab.UI34PerformanceMeter示意圖RandomGraphGeneratorG1G1G2G2G3G3AlgorithmTimerAlgorithmLoaderAlgorithm35PerformanceMet