Week 2015/04/27 - 2015/04/30

Weekly report

What we did

• Wrote a shell script to automate diagram generation from AMZ files.
• Meet our Chalmers supervisor.
• Contacted other thesis students to attend their presentation. (June 8th)
• Registered for mandatory seminar. (May 12th)
• Read on UML component diagram standards.
• Finalized our planning report.
• Gathered preliminary ideas on diagram improvements.
• Researched papers on the topic of "component placement".
• Read Graphviz documentation to get familiar with the tools and options : dot, neato, smyrna, lefty, dotty and Cgraph.
• Read the research paper and placement algorithm on which graphviz dot is based.

Next week's goals

• Continue gathering information about component placement algorithms and graph generation tools.
• Start playing around with graphviz librairy.
• Fix the planning report if it needs it.
• Read up on what is "human readable", "what is a useful and readable diagram", "what factors are important and ease readability". Possibly contact experts in this domain.

A Technique for Drawing Directed Graphs

Summary of the document : A Technique for Drawing Directed Graphs 

The goal of this paper is having high-quality directed graphs in a quickly way. These four phases describes the algorithm that draws directed graphs.

1. Placing nodes in discrete ranks 
2. Ordering nodes within ranks to reduce crossings 
3. Finding optimal coordinates for nodes 
4. Making splines to draw edges

There are some aesthetic principles that they want to follow as much as possible:

1. Expose hierarchical structure in the graph
2. Avoid visual perversions like edge crossing and sharp bends.
3. Keep edges short
4. Favor symmetry and balance

And also for making optimal rank assignment:

1. Making the graph acyclic: Breaking cycles by reversing certain edges which is based on depth- first search.
2. Problem definition:  To make short edges, according to aesthetic principle 3, it is needed to find an optimal node ranking.  
3. Network simplex:  They described a simple approach to the problem based on network simplex formulation.

Link to the documentation: http://www.graphviz.org/Documentation/TSE93.pdf

Graphviz - Smyrna : Graph visualization application

Smyrna is an application for viewing graphs.

Users can open a window on a graph, navigate  around the graph (pan and zoom), select nodes and edge with the mouse.

Work for graphs up till 100 000 nodes.

Visualization modes : 2D, 3D, topological fisheye. The fisheye mode is especially useful for large graphs. It allows users to see an area of interest more clearly.

Smyrna also proposes tools to write queries (count nodes,...), modify the graph and create new graphs.

It can be an interesting tool to give the users a chance to improve the diagrams manually and make changes where the auto-generation tool failed.

Link to documentation : http://www.graphviz.org/pdf/smyrna.pdfa

Graphviz - Dot Guide

Summary of the document : Dot Guide - Graphviz

Graphviz is an open source solution to generate graphs from code. Here is a short summary of how the algorithm works and what is possible to do with it.

Component placement algorithm

The Dot component placement algorithm can be decomposed into five phases :

• Step 1 : Break all cycles by reversing some edge directions within cycles.
• Step 2 : Assign each node a rank level. This will determine the Y coordinates in a top to bottom drawing.
• Step 3 : Avoid crossings by rearranging nodes within ranks.
• Step 4 : Set X coordinates to keep edges short.
• Step 5 : Route edge splines.

This strategy is based on the work of Warfiel, Carpano and Surgiyama. See references below.

Dot tips and tricks - Layout

List of dot tips and tricks to customize and influence component placement in a graph.

• The ranks determine the nodes Y coordinates.
• 'Nodesep' and 'ranksep' attributes influence distances between nodes. 'Nodesep' acts on distances between two adjacent nodes within the same rank (horizontal) whereas 'ranksep' acts on distances between nodes of different ranks (vertical). p12
• 'Rankdir' attribute allows us to change the positioning from TopBottom to LeftRight (usefull when drawing timelines). p14
• Influence node ranks with attributes like 'rank' = same, min, source, max and sink. p15
• Influence edge weight : the heavier is an edge weight, the closer the node will be from each other. p15
• Group nodes together ('group') : It will keep edges as straight as possible and avoid crossings within the group.
• Node ports : define where the edge should land on a node. p18
• Clusters : define subgraphs in their own rectangle area. Possible to fill the rectangle with color for clarity. p19
• Concentrators : allow a technique of edge merging which can be useful in a dense layout. p24

Dot tips and tricks - Design

• Change node shape. p4
• Customize node labels. p6
• Edge label : add a line to link which label belongs to which edge - decorate attribute. p8
• Edge label : change the label orientation/distance with 'labelangle' and 'labeldistance' attributes. p8
• Change node color. p9

Link to Dot Guide

http://www.graphviz.org/pdf/dotguide.pdf

Papers to read later

M. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis.
IEEE Transactions on Software Engineering, SE-12(4):538–546, April 1980.Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Kiem-Phong Vo. A Technique for Drawing Directed Graphs. IEEE Trans. Sofware Eng., 19(3):214–230, May 1993.
[New89] Frances J. Newbery. Edge Concentration: A Method for Clustering Directed Graphs. In 2nd International Workshop on Software Configuration Management, pages 76–85, October 1989. Published as ACM SIGSOFT Software Engineering Notes, vol. 17, no. 7, Novem-ber 1989.
[Nor92] Stephen C. North. Neato User’s Guide. Technical Report 59113-921014-14TM, AT&T Bell Laboratories, Murray Hill, NJ, 1992.
[STT81] K. Sugiyama, S. Tagawa, and M. Toda. Methods for Visual Understanding of Hierarchical System Structures. IEEE Transactions on Systems, Man, and Cybernetics, SMC-11(2):109–125, February 1981.
[War77] John Warfield. Crossing Theory and Hierarchy Mapping. IEEE Transactions on Systems, Man, and Cybernetics, SMC-7(7):505–523, July 1977.

Chalmers supervisor meeting

First meeting with our thesis supervisor at Chalmers (Rogardt).

Meeting notes

• Introduction and presentation of ourselves
• Overview of the project - what it is about - not an easy project
• Rogardt mailed one of his contact, a specialist in the area, Leon Moonen, to get his thoughts about the project.
• Rogardt asked to meet our supervisor at Ericsson - send mail.
• Planning report draft to be sent for review after the meeting.

Tips from Rogardt 

Look at the Models conference papers about component placements. This shall help us to get familiar with the research which has been done in this area.

References

This post will list the resources that we have used during our thesis.

1. YAML :http://yaml.org/ Accessed: 12.3.201. AMZ is based on this format. Used to understand AMZ syntax.
2. Salome Maro, 2014. A DSL Supporting Textual and Graphical Views,University of Gothenburg, Chalmers University of Technology, Department of Computer Science and Engineering, Gothenburg, Sweden. Used for background study on automatic UML generation
3. Ralf Kollmann ,Martin Gogolla,2002.Metric-Based Selective Representation of UML Diagrams,University of Bremen ,Department of Computer Science, Bremen. Used for background study on automatic UML generation.
4. Hauke Fuhrmann, Reinhard von Hanxleden, 2010.Taming Graphical Modeling, Real-Time and Embedded Systems Group, Department of Computer Science, Kiel, Germany. Used for background study on automatic UML generation.
5. PlantUML :http://plantuml.sourceforge.net/ Accessed: 13.3.2015.
6. GraphViz :http://www.graphviz.org/ Accessed : 13.3.2015.
7. TextUML :http://abstratt.github.io/textuml/readme.html Accessed : 13.3.2015.
8. yUML :http://yuml.me/ Accessed : 13.3.2015. 
9. Umple :http://cruise.eecs.uottawa.ca/umple/ Accessed : 13.3.2015 
10. Martin Mazanec, Ondrej Macek, 2012. On General-purpose Textual Modeling Languages, Department of Computer Science, FEL, Czech Technical University, Praha, Czech Republic.
11. UML standards https://www.ibm.com/developerworks/rational/library/dec04/bell/ Accessed : 27.04.2015.
12. GraphViz Dot Guide : http://www.graphviz.org/pdf/dotguide.pdf - see post : http://betterumldiagrams.blogspot.se/2015/04/graphviz-dot-guide.html.

Week 1 : 2015/04/23 - 2015/04/24

The first week was really short, only two days.
We did :

• Set up our computers
• Set up git and clone the repository locally
• Booked an appointment with our Chalmers supervisor
• Wrote a planning report draft

Next week goals :

• Finalize the planning report
• Generate all component diagrams (6-8 files) - Write a bash script to do this automatically.
• Study the diagrams and together with our supervisor at Ericsson define areas of improvements (specifications) - see previous post for preliminary ideas -
• Get familiar with AMZ format, PlantUML and Graphviz to see what it is possible to do with these tools.