臺灣博碩士論文加值系統

近年來雖然已經有一些軟體視覺化工具可以透過圖形來視覺化程式內部的資料以幫助程式設計師除錯，但它們在實用上還有許多限制，使得軟體視覺化工具無法成為程式設計人員每天使用的工具之一。軟體視覺化除錯工具xDIVA (eXtreme Debugging Information Visualization Assistant)[1]是一個具備彈性與實用性的工具用來幫助程式設計師進行除錯。xDIVA使用3D的圖形、顏色和動畫來視覺化資訊。
目前xDIVA系統在視覺化資料的過程中尚存在待開發的功能。如何依照人類熟悉的方式陳列視覺化物件(Layout)就是其一。目前xDIVA中為視覺化隱喻(Visualization Metaphors)所做的陳列演算法仍然不夠友善，也沒有足夠的互動性。因此本論文提出在xDIVA下，應用樣板設計模式(Template Design Pattern)實作出一個具有彈性架構讓未來的許許多多的陳列演算法可以輕鬆地擴充。在這樣的架構下，本論文也實做了一個可用來排列Graph類型的資料結構的陳列演算法，此演算法允許使用者進行積極的互動，其原理是借用物理的一些運動法則來展現具備真實感的動畫。

目錄
目錄 ........................................................................................... 2
圖目錄 ......................................................................................... 6
程式碼目錄 .................................................................................. 8
摘 要 ........................................................................................... 9
CHAPTER 1 緒論 .................................................................. 10
SECTION 1.1 OVERVIEW .................................................................. 10
SECTION 1.2 論文架構 ................................................................ 14
CHAPTER 2 研究背景 .......................................................... 16
SECTION 2.1 DEBUGGER .................................................................. 16
2.1.1 JDB ............................................................................... 16
2.1.2 GDB .............................................................................. 16
2.1.3 DDD .............................................................................. 16
2.1.4 ODB .............................................................................. 16
SECTION 2.2 VISUALIZATION TOOLS ................................................... 16
2.2.1 Graphviz ....................................................................... 17
2.2.2 BLOOM ......................................................................... 17
2.2.3 Vizz 3D ......................................................................... 18
SECTION 2.3 2D VS 3D .................................................................. 19
CHAPTER 3 XDIVA 架構 ........................................................ 24
SECTION 3.1 COMMAND AGENT ....................................................... 25
SECTION 3.2 WOPM ..................................................................... 27
SECTION 3.3 DIVA UI .................................................................... 28
SECTION 3.4 DIVA VM .................................................................. 29
SECTION 3.5 LAYOUT VM ................................................................ 30
SECTION 3.6 XDIVA 的LAYOUT 系統 .............................................. 30
SECTION 3.7 XDIVA 的LAYOUT 系統結構 ...................................... 33
3.7.1 物件導向設計原則 ..................................................... 33
3.7.2 樣板設計模式 ............................................................. 34
3.7.3 利用樣板設計模式 ..................................................... 34
3.7.4 陳列影響範圍Layout_influence_area ........................ 36
3.7.5 Layout 的動畫系統 ..................................................... 37
CHAPTER 4 GRAPH LAYOUT .................................................. 40
SECTION 4.1 GRAPH DRAWINGS ....................................................... 40
SECTION 4.2 GRAPH 的陳列 .......................................................... 41
SECTION 4.3 XDIVA 中的LAYOUT 需求 .......................................... 43
CHAPTER 5 GRAPH 的彈簧陳列方法 .................................... 45
SECTION 5.1 物理現象 ................................................................ 45
5.1.1 移動的發生與物理學的計量 ...................................... 45
5.1.2 位移 ............................................................................. 46
5.1.3 速度 ............................................................................. 46
5.1.4 加速度 ......................................................................... 47
5.1.5 資料結構：位置移動狀態PositionMoveState .......... 47
SECTION 5.2 力的發生與傳導 .................................................... 47
5.2.1 力 ................................................................................. 48
5.2.2 資料結構：力與移動 ................................................. 48
5.2.3 彈簧與虎克定律（Hooke's law） .............................. 49
5.2.4 方法：產生彈簧力crateSprForceFromVMtoVMs ...... 50
SECTION 5.3 牛頓運動定理 ........................................................ 51
5.3.1 牛頓第一運動定理 ..................................................... 52
5.3.2 牛頓第二運動定理 ..................................................... 52
5.3.3 牛頓第三運動定理 ..................................................... 52
SECTION 5.4 牛頓運動定理的影響 ............................................ 53
5.4.1 牛頓第一運動定理的影響 ......................................... 53
5.4.2 方法：慣性定律‐‐與前移動的結合 ........................... 53
5.4.3 牛頓第二運動定理的影響 ......................................... 54
5.4.4 方法：利用第二運動定理算出彈簧力的加速度 ...... 55
5.4.5 牛頓第三運動定律的影響 ......................................... 55
5.4.6 方法：作用力與反作用力 ......................................... 56
SECTION 5.5 摩擦力 ................................................................... 57
5.5.1 摩擦力加入位置移動狀態 ......................................... 58
5.5.2 動畫與摩擦力 ............................................................. 59
SECTION 5.6 成果 ....................................................................... 61
CHAPTER 6 結論與未來工作 ............................................... 63
SECTION 6.1 結論 ....................................................................... 63
SECTION 6.2 未來工作 ................................................................ 64
REFERENCE ................................................................................. 65

[1] Yung-Pin Cheng, Jih-Feng Chen, Ming-Chieh Chiu,Nien-Wei Lai, and Chien-Chih Tseng. xDIVA: A debugging visualization system with composable visualization metaphors. In Proceedings of ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2008, Nashville, USA.
[2] T. Biedl ,McGill University. J. Marks,MERL. K.Ryall University of Virginia. S.Whitesides, McGill University. Graph Multidrawing: Finding Nice Drawings Without Defining Nice. TR-98-15 October 1998. MITSUBISHI ELECTRIC RESEARCH LABORATORIES CAMBRIDGE RESEARCH CENTER. .
[3] F. P. Brooks, No Silver Bullet – essence and accidents of software engineering, Proceedings of the IFIP Tenth World Computing Conference, Page: 1069-1076, 1996
[4] http://en.wikipedia.org/wiki/Unified_Modeling_Language
[5] Steven P. Reiss, An Overview of Bloom, Department of Computer Science Brown University
[6] M. Lanza, CodeCrawler – An Extensible and Language Independent 2D and 3D Software Visualization Tool, In Tools for Software Maintenance and Reengineering, page: 74 – 94, RCOST / Software Technology Series, Franco Angeli, 2005
[7] http://en.wikipedia.org/wiki/Software_metrics
[8] J. B. Rosenberg, How Debuggers Work: Algorithms, Data Structure, and Architecture, ISBN: 0-471-14966-7, John Wiley & Sons, 1996
[9] A. Kolawa, Parasoft, The Evolution of Sofrware Debugging, http://www.parasoft.com/jsp/products/article.jps?articleID=490
[10] B. Lewis, Debuggin backwards in time, in M. Ronsse, K. De Bosschere (eds), proceedings of the Fifth International Workshop on Automated Debugging, 2003
[11] H. Agrawal R. A. DeMillo and E. H. Spafford, An Execution-Backtracking Approach to Debugging, IEEE Software (1991), Page: 21-26, 1991
[12] P. Crescenzi, C. Demetrescu, I. Finocchi and R. Petreschi, Reversible Execution and Visualization of Programs with LEONARDO, Journal of Visual Languages & Computing, 11 (2000), pages: 125-150,2000
[13] R. M. Stallman, R. Pesch and S. Shebs, Debuggin with GDB: The GNU Source-Level Debugger, Copyright (C) 1988-2006 Free Software Foundation, Inc.http://www.gnu.org/software/gdb/documentation
[14] The Data Display Debugger (ddd), available on http://www.gnu.org/software/ddd
[15] Steven P. Reiss and Manos Renieris, Demonstration of jive and jove: Java as it happens. In ICSE ’05: Proceedings of the 27th international conference on Software engineering, New York,NY,USA,2005 ACM Press
[16] Wim De Pauw, Erik Jensen, Nick Mitchell, Visualization the Execution of Java Programs, IBM T.J. Watson Research Center
[17] Katharina Mehner. Javis: A uml-based visualization and debugging environment for concurrent java programs. In Software Visualization, pages 163–175, 2001.
[18] Graphviz, http://www.graphviz.org/
[19] Emden Gansner and Eleftherios Koutsofios and Stephen North, Drawing Graphs with DOT, 2006
[20] J. Carlsson, Optimisation of a Graph Visualization Tool: Vizz3D
[21] Projects using OGRE, http://www.ogre3d.org/wiki/index.php/Projects_using_ogre
[22] T. Biedl ,McGill University. J. Marks,MERL. K.Ryall University of Virginia. S.Whitesides, McGill University. Graph Multidrawing: Finding Nice Drawings Without Defining Nice. TR-98-15 October 1998. MITSUBISHI ELECTRIC RESEARCH LABORATORIES CAMBRIDGE RESEARCH CENTER. .
[23] Tyson R. Henry Scott E. Hudson Department of Computer Science University of Arizona, Tucson AZ 85721 * . Interactive Graph Layout. UIST’91 Hilton Head, South Carolina, Pages 55-64.
[24] David P. Dobkin *, Alejo Hausner t, Princeton University, Princeton, NJ 08544, dpd,ah@cs.princeton.edu. Emden R. Gansner, Stephen C. North, AT&T Laboratories, Florham Park, NJ 07932,{erg,north}@research.att.com. Uncluttering Force-Directed Graph Layouts.
[25] Toshiyuki MASUI, Software Research Laboratories,SHARP.Corporation2613-1 Ichinomoto-cho, Tenri, Nara 632, Japan. Evolutionary Learning of Graph Layout Constraints from Examples. UIST ’94 Marina del Rey, California. Page 103-108.
[26] JOSEP D´IAZ, JORDI PETIT AND MARIA SERNA, Universitat Polit`ecnica de Catalunya. A Survey of Graph Layout Problems. ACM Computing Surveys, Vol. 34, No. 3, September 2002, pp. 313–356.
[27] Prefuse, information visualization toolkit, http://prefuse.org/