(3.235.245.219) 您好!臺灣時間:2021/05/10 01:57
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蔡佳礽
研究生(外文):Chia-Jeng Tsai
論文名稱:階層式自動機視覺化及其軟體平台設計
論文名稱(外文):Layer-based Visualization of Automata with Software Architecture Design
指導教授:顏嗣鈞
指導教授(外文):Hsu-chun Yen
口試委員:雷欽隆鄧德雋郭斯彥黃秋煌
口試委員(外文):Chin-Laung LeiDer-Jiunn DengSy-Yen KuoChua-Huang Huang
口試日期:2013-07-27
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:70
中文關鍵詞:自動機視覺化使用者介面線性佈局圓形佈局階層式佈局
外文關鍵詞:automata visualizationgraphical user interfacelinear layoutcircular layoutVaucanson
相關次數:
  • 被引用被引用:0
  • 點閱點閱:104
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在這篇論文中,我們提出基於VGI(Vaucanson Graphical Interface)為一自動機視覺化軟體,其中的軟體架構設計,以及視覺化的佈局演算法。在軟體架構部分,Vaucanson包含加權自動機(weighted automata)的計算處理功能,而VGI則提供圖形化的使用者界面。在視覺化部分,我們提出三個佈局演算法,線性佈局、圓形佈局以及這兩個佈局的階層式組合佈局,在這些佈局中,我們都希望能表現出自動機的特徵,例如形成強連通關係的狀態點(strongly connected component)。在階層式佈局中,則由使用者指定數個群集和其中包含的狀態點成員,並指定每個群集所使用佈局的方式,最後則指定整個自動機的佈局方式。透過階層性的佈局組合,自動機內部各個狀態點之間階層性的關係便能被表現在圖形上。

In this thesis, we first propose a software architecture to support the implementation of a graphical interface for Vaucanson, a software platform for manipulating weighted automata. The graphical interface aims to allow users to input and display a weighted automata in an intuitive and graphical way, as well as communicating with Vaucanson to support a wide variety of algorithms designed for weighted automata. Secondly, we implement several layout algorithms to visualize the structure of an automaton in ways to allow geometric features of an automaton to stand out. To this end, our approach is based on a layer-based layout, in which an automaton is locally clustered by users and then specific layout algorithms are applied to different layers/clusters to provide a higher degree of flexibility in displaying the detailed structure of an automaton. By the hierarchical combination of layouts, an automaton''s features can be easily perceived.

誌謝 i
摘要 iii
Abstract v
1 Introduction 1
2 Software Architecture of VGI 5
2.1 Automata 5
2.2 Vaucanson and VGI 6
2.3 Software Structure Design for Visualization in VGI 8
2.4 Projection: Coordinate Systems of Automata and JGraphAutomata 12
2.5 Layers of Style 13
3 Linear Layout and Circular Layout 17
3.1 LinearLayout 17
3.1.1 Ordering o fVertices 18
3.1.2 Route Edges 19
3.1.3 Result 24
3.2 CircularLayout 27
3.2.1 Ordering of Vertices 28
3.2.2 Route Edges 29
3.2.3 Result 32
4 Layer-based Layout 35
4.1 Bundle Vertices into Groups 39
4.2 Apply Overall Layouts 41
4.3 Sifting Vertices 41
4.3.1 Linear Sifting under LinearLayout 44
4.3.2 Circular Sifting under Linear Layout 45
4.3.3 Linear Sifting under Circular Layout 48
4.3.4 Circular Sifting under Circular Layout 50
4.4 Route Edges 53
4.4.1 LinearLayout 53
4.4.2 CircularLayout 54
4.5 Result 56
5 Conclusion and Future Work 67
Bibliography 69

[1] J. M. Six and I. Y. G. Tollis, “A framework for user-grouped circular drawings.,” in Graph Drawing (G. Liotta, ed.), vol. 2912, pp. 135–146, Springer Berlin Heidelberg, 2004.

[2] U. B. Michael Baur, “Multi-circular layout of micro/macro graphs,” in Graph Drawing (W. Q. Seok-Hee Hong, Takao Nishizeki, ed.), vol. 4875, pp. 255–267, Springer Berlin Heidelberg, 2008.

[3] S. Lombardy, Y. Regis-Gianas, and J. Sakarovitch, “Introducing Vaucanson,” Theoretical Computer Science, vol. 328, pp. 77 – 96, 2004.

[4] “Vaucanson.”http://www.vaucanson-project.org/.

[5] M. Garey, D. Johnson, and L. Stockmeyer, “Some simplified np-complete graph problems,” Theoretical Computer Science, vol. 1, no. 3, pp. 237 – 267, 1976.

[6] C. Papadimitriou, “The np-completeness of the bandwidth minimization problem,” Computing, vol. 16, no. 3, pp. 263–270, 1976.

[7] V. Dujmović and D. R. Wood, “On linear layouts of graphs,” Discrete Mathematics and Theoretical Computer Science, vol. 6, pp. 339–358, 2004.

[8] K. N. S. Masuda, T. Kashiwabara and T. Fujisawa, “On the np- completeness of a computer network layout problem,” in Proc. IEEE Intl. Symp. Circuits and Systems, pp. 292–295, 1987.

[9] M. Baur and U. Brandes, “Crossing reduction in circular layouts,” in Proc. Workshop on Graph-Theoretic Concpets in Computer Science, vol. 3353, pp. 332–343, Springer, 2004.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔