請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/53647
標題: | 利用力模型畫群集圖 Drawing Clustered Graphs Using a Force-directed Placement Algorithm |
作者: | Yu-Jung Ko 柯有容 |
指導教授: | 顏嗣鈞 |
關鍵字: | 圖形繪製,力模型演算法,蓋應力函數極小化,旋轉直覺方法,具群集關係圖, graph drawing,force-directed algorithms,stress majorization,rotation heuristics,clustered graphs, |
出版年 : | 2015 |
學位: | 碩士 |
摘要: | 我們提出一個新的繪製具有群集的圖的演算法。其中以 stress model 表示單一群集圖內的點,以類似彈簧及靜電斥力的力模型來表示群集間的關係。擺放群集內的點及群集間的基本概念來自於對 stress model 做 majorization 以及參考模擬退火法的力導向演算法。我們的演算法加入由群集中心施予群集內點的力,將連外群集較多的點往群集邊界推,而連外較少的點往中心點靠。此外,在擺放群集的過程中,考慮力矩平衡來旋轉群集,以達成縮短群集間連結邊的長度來減少邊的交疊。在論文的末章展示我們演算法繪製一些例圖以及實際被記錄的資料的結果,並與 full stress majorization 進行邊交疊數目和複雜度比較。 We propose a novel layout algorithm to draw clustered graphs. The algorithm views intra-cluster graphs as stress models and inter-cluster graphs as spring and electrical force models. The basic idea of placement is based on stress majorization and force-directed placement algorithms using simulating annealing. It integrates the force from the center to push and pull the intra- cluster vertices based on their outside connectivity, referred as outside constriants, to modify the original stress model. And it applies the idea of torque equilibrium, coupled with some heuristics, to realize our force-directed placement algorithm. We demonstrate some contrived and real-world data with our algorithm, and compare our results with that of full stress majorization with respect to the running time and the number of edge crossings. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/53647 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 1.82 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。