Ana səhifə

Introduction


Yüklə 3.14 Mb.
səhifə13/13
tarix24.06.2016
ölçüsü3.14 Mb.
1   ...   5   6   7   8   9   10   11   12   13

The High Level Architecture of the Constrained On-line Graph Framework (COGF)


A high level architecture of the proposed graph drawing framework includes three main components, namely server, visualization client, and graph drawing client components. The visualization clients are thin clients that run within Internet browsers and display the graph layouts. The graph drawing clients are stand-alone applications that allow end users to edit the graph layouts. The server component comprises two modules. The first module updates the graph model and interacts with the graph editing clients. The second module retrieves the graph layout information for the visualization clients for displaying the hierarchical graph layouts. Figure 16 shows the high-level architecture of the proposed graph drawing framework.



Figure 23. Client-server architecture of the proposed dynamic graph drawing framework

The Update Manager module in the server component is the core engine of the dynamic hierarchical graph drawing framework. It employs a modified version of the Sugiyama heuristic for the dynamic graph drawing framework and data from a relational database to update the graph layout locally and incrementally.

Since the aesthetic criteria influence the design of the dynamic graph drawing framework, the next section will review the aesthetic criteria prior to the design of the dynamic hierarchical graph drawing framework. The details of the software architecture will be discussed in a later section.

Design of the Constrained Dynamic Hierarchical Graph Framework


This section presents the design of the constrained graph framework; three components of the constrained graph framework are described in detail.

Server Component

In real world applications like enterprise processes, the number of end users who visualize the process information is much larger than the number of modelers who model the process flows. To enable the constrained graph framework to support multiple users in real-time environments and to render large graphs, the server component is decoupled into two different modules: (1) an update module, and (2) a visualization module. Also to improve the performance of both visualization and editing functionality, a relational database shall be utilized that captures the graph data. Both editing and visualization modules shall share the same database for their processing.



Update Manager

The Update Manager is a TCP server that handles the interactions between graph drawing clients using the TCP/IP protocol. Figure 17 illustrates the communications between the clients and the Update Manager.



Figure 24. Communication between the client and the Update Manager

The graph-editing client initiates a communication with the Update Manager by sending an update request to the server through the TCP protocol. Upon receiving the request from the graph-editing client, the Update Manager transforms the XML message into a relational query and executes the query to return the affected graph data. The Update Manager then updates the affected vertices using a modified version of the Sugiyama heuristic. The Update Manager next updates the database with the new graph structure and sends the result back to the client.

The protocol for communication message between the editing client and the server is in XML format. The request message includes information about the vertices and the type of operations. The response message includes information about the vertices along with their logical properties. The logical properties of a vertex include but are not limited to (1) its layer, (2) its ranking within the layer, (3) shape, (4) text. Table 1 shows the XML schema of the request message and response messages.

Table 1. XML schema for the message protocol between the editing client and the Update Manager module

The Update Manager supports the following operations:



    1. Inserting a vertex or pseudo-vertex and a given set of edges connecting the new vertex to existing vertices.

    2. Deleting a vertex and all its incident vertices.

    3. Adding an edge.

    4. Deleting an edge.

    5. Adding a constraint to a vertex

    6. Removing a constraint on a vertex

The Update Manager employs a modified version of the Sugiyama heuristic to update the graph model when required by update operations.

Visualization Manager

This module is a standard J2EE web application that runs on a J2EE web server and

handles HTTP requests and responses. The Visualization Manager accepts requests from graph visualization clients, transforms the requests into relational data queries, retrieves the graph data from the database, and returns a set of graph information in a XML format through the HTTP response. Figure 25 shows the communication between the visualization client and the Visualization Manager.



Figure 26. The communication between the visualization client and the Visualization Manager

Update Client


The Update Client is a standalone application that provides a graphical user interface that allows end users to edit graph layouts. The program supports the following functionalities:

    1. Inserting a vertex or pseudo-vertex and a given set of edges connecting the new node to existing vertices.

    2. Deleting a vertex and all its incident vertices.

    3. Adding an edge.

    4. Deleting an edge.

    5. Adding a constraint to a vertex

    6. Removing a constraint on a vertex

Visualization Client

The Visualization Client is a thin-client or web client application that will render the graph layout in the Internet browser. The thin client is a Java applet that supports viewing the graph layout.


Process of Collecting Graph Data




Testing and Evaluation

Resource Requirements


The following resources will be utilized in this research:

  • Hardware: A desktop computer that serves as a web server that hosts the graph visualization application, and a database server that stores the graph model. Laptops will be used as clients connecting to the graph framework.

  • Software: Java Development Kit (JDK), Apache Tomcat Servlet engine, MySQL relational database server, Java open source graph libraries.

  • Graph Data: NIST source and synthetic

  • Participant: The author is the only researcher for this project

Summary

References


Battista, G. D., Eades, P., Tamassia, R., & Tollis, I. (1999).  Graph drawing algorithms for the visualization of graphs.  New Jersey: Prentice Hall.

Bohringer, K., & Newbery, P. (1990).  Using constraints to achieve stability in automatic graph layout algorithms.  Proceedings of ACM CH 90, 43-51.

Brandes, U., & Wagner, D. (1997).  A Bayesian paradigm for dynamic graph layout.  Proc. Measures for GSymp. Graph Drawing GD '97, pp. 236-247.

Bridgeman, S., & Tamassia, R. (2002).  A user study in similarity measures for graph drawing. Journal of Graph Algorithms and Applications, 6(3), 225-254.

Buchsbaum, A. L., & Westbrook, J. R. (2000).  Maintaining hierarchical graph views.  Proceedings of the Eleventh Annual ACM-Siam Symposium on Discrete Algorithms. 566-575.

Catarci, T. (1988).  The assignment heuristic for crossing reduction.  IEEE Trans. Syst. Man Cybern. 25(3), 515-521.

Coffman, E. G., & Graham, R. L. (1972).  Optimal scheduling for two processors systems. Acta Informica 1, pp. 200-213.

Cohen, R. F., Battista, G. D., Tamassia, R., Tollis, I. G., & Bertolazzi, P. (1992).  A framework for dynamic graph drawing.  Annual Symposium on Computational Geometry: Proceedings of the Eighth Annual Symposium On Computational Geometry (pp. 261-270). Berlin: ACM.

Davidson, R., & Harel, D. (1996).  Drawing graphs nicely using simulated annealing. ACM Transaction on Graphics, 15(4):301-331.

Demetrescu, C., & Finocchi, I. (2003).  Combinatorial algorithms for feedback problems in directed graphs.  Information Processing Letters, 86(3), 129-136.

Diehl, S., Görg, C., Kerren, A. (2000).  Foresighted graph layout.  Technical Report, FR Informatik, Saarland University.

Diehl, S., Görg, C., Kerren, A. (2001).  Preserving the mental map using foresighted layout.  In Proceedings of the Joint Eurographics -- IEEE TCVG Symposium on Visualization. Switzerland.

Diehl, S., & Görg, C. (2002).  Graphs, they are changing.  Lecture Notes In Computer Science Vol. 2528 (23-30).

Eades, P., & Kelly, D. (1984). The Marey graph animation tool demo.  Proceedings of the 8th International Symposium on Graph Drawing, 396 - 406.

Eades, P., & Kelly, D. (1986). Heuristics for reducing crossings in 2-layered networks, Ars combin., pp. 187-191.  Proceedings of the Australian Computer Science Conference, 327-334.

Eades, P., Lin, X. Y, & Smith, W. (1993).  A fast and effective heuristic for the feedback arc set problem.  Information Processing Letters, 12-15.

Finocchi, I. (2002). Hierarchical decompositions for visualizing large graphs.  Ph. D thesis. Università̀ degli Studi di Roma, Rome.

Forster, M. (2004). A fast and simple heuristic for constrained two-layered crossing reduction. Proc. Graph Drawing, GD 2004, 206-216.

Frishman, Y., Tal, A. (2007). On-line dynamic graph drawing. Eurographic/ IEEE-VGTC

Symposium on Visualization.

Gansner, E. R., North, S. C., & Vo, K. P. (1993).  A technique for drawing directed graphs.  IEEE Transactions on Software Engineering, 19(3), 214-230.

Garey, M. R., & Johnson, D. S. (1979).  Computers and intractability: A guide to the theory of NP-complete.  New York: W. H. Freeman.

Garey, M. R., & Johnson, D. S. (1983).  Crossing number is NP-complete.  SIAM Journal on Algebraic and Discrete Methods, 312-316.

Gorg, C., Birke, P., Pohl, M., & Diehl, S. (2004).  Dynamic graph drawing of sequences of orthogonal and hierarchical graphs.  Proceedings of 12th International Symposium on Graph Drawing.

Gorg, C. (2005).  Offline drawing of dynamic graphs.  Ph. D Dissertation.

He, W., & Marriott, K. (1998). Constrained graph layout. An International Journal, 3, 289-314. Boston: Kluwer Academic Publishers.

Huang, W., Eades, P. (2005). How people read graphs. Asia Pacific Symposium on Information Visualization (APVIS 2005). Australia.

Eiglsperger, M., Siebenhaller, M., & Kaufmann, M (2005).  An efficient implementation of Sugiyama’s algorithm for layered graph drawing.  Journal of Graph Algorithms and Applications, 9(3), 305-325.

Junger, M., & Mutzel, P. (1997).  2-layer straightline crossing minimization: Performance of exact and heuristic algorithms.  J. Graph Algorithms and Applications, 1(1), 1-25.

Lam, S., & Sethi, R. (1979).  Worst case analysis of two scheduling algorithms.  SIAM Journal on Computing, 6(3), 518.

Lee, Y. Y., Lin, C. C., & Yen, H. C. (2006). Mental map preserving graph drawing using simulated annealing. Vol. 60 of Conferences in Research and Practice in Information Technology.


Li, X. Y., & Stallmann, M. (2002).  New bounds on the barycenter heuristic for bipartite graph drawing.  Information Processing Letters, 82(6), 293-298. Amsterdam: Elsevier.

Lin, X. Y. (1992). Analysis of algorithms for drawing graphs. PhD thesis, Department of Computer Science, University of Queensland, Queensland, Australia.

Luder, P., Ernst, R., & Stille, S. (1995).  An approach to automatic display layout using combinatorial optimization algorithms.  Software – Practice and Experience (25)11, 1183-1202.

Marti, R., & Laguna, M. (2003).  Heuristics and meta-heuristics for 2-layer straight line crossing minimization.  Discrete Applied Mathematics, 12(3), 665-678.

Matuszewski, C., Schönfeld, R., & Molitor, P. (1999). Using sifting for k-layer straightline crossing minimization.  Lecture Notes in Computer Science; Vol. 1731: Proceedings of the 7th international symposium on graph drawing (pp. 217-224). London: Springer-Verlag.

Miriyala, K., & Tamassia, R. (1993). An incremental approach to aesthetic graph layout.  Computer-Aided Software Engineering, Proceeding of the Sixth International Workshop, Vol., Iss.

North, S. C. (1995). Incremental layout in DynaDAG.  Software and Systems Research Center.  AT & T Bell Laboratories.

North, S. C., & Woodhull, G. (2001). On-line hierarchical graph drawing.  Lecture Notes in Computer Science; Vol. 2265: Revised papers from the 9th international symposium on graph drawing (pp. 232-246). London: Springer-Verlag.

Patarasuk, P. (2004). Crossing reduction for layered hierarchical graph drawing.  Masters thesis, Florida State University, Tallahassee, Florida.

Rabani, Y., (2003). Approximation Algorithms Lectures. Retrieved May 02, 2007 from http://www.cs.technion.ac.il/~rabani/236521.04.wi.html

Raitner, M. (2004).  Maintaining hierarchical graph views for dynamic graphs.  Technical Report, MIP-0403, University of Passau, Passau, Germany.

Rudell, R. (1993). Dynamic variable ordering for ordered binary decision diagram. In Proc. International Conference on Computer-Aided Design (pp. 42-47).

Ryall, K, Marks, J., & Shieber, S. (1997).  An interactive constraint-based system for drawing graphs.  Mitsubishi Electric Research Laboratory.

Stallman, M., Brglez, F., Ghost, D. (2001).  Heuristics, experimental subjects, and treatment evaluation in bigraph crossing minimization.  Journal of Experimental Algorithmics (JEA), 6(8).

Stedile, A. (2001).  JMFGraph - A modular framework for drawing graphs in Java.  Masters thesis, Graz University of Technology, Graz, Austria.

Sugiyama, K., Tagawa, S., & Toda, M. (1981).  Methods for visual understanding of hierarchical systems.  IEEE Trans. On System, Man, and Cybernetics, (2), 109-125.

W3C. (1999) Glossary of Terms for Device Independence. Retrieved March 20, 2007 from http://www.w3.org/TR/di-gloss/
Weisstein, E. W. (2003). Independent Set. MathWorld--A Wolfram Web Resource. Retrieved October 20, 2006 from http://mathworld.wolfram.com/IndependentSet.html

West, D. B. (2001).  Introduction to graph theory.  New Jersey: Prentice Hall.

Yehuda, B. (2000). One for the price of two: A unified approach for approximating

covering problems, Algorithmica 27(2), 2000, 131-144.



1   ...   5   6   7   8   9   10   11   12   13

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©atelim.com 2016
rəhbərliyinə müraciət