臺灣博碩士論文加值系統

在這篇論文中，我們提出基於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.