daVinci's Concepts

• Graphs
• Applications using daVinci's API
• Graph Layout
• Visualization definition
• Fine Tuning of a Layout
• Graph Status
• Interactions
• Multi-Graph / Multi-View
• Drawing Technology and Pixmap Caching
• Drag and Drop

Although hierarchical visualization is only possible for non-cyclic graphs, daVinci is also able to handle cyclic graphs with a trick: A cycle analysis inverts one edge of each cycle internally by exchanging parent and child node (i.e. the parent becomes the child of the edge and vice versa). This way, a cyclic graph is transformed into an acyclic one which can be handled by the hierarchical layout algorithm. Afterwards, the arrows of inverted edges will be drawn at the opposite "wrong" side (i.e. they point to the parent) to invert the direction for a second time such that it will point to the original direction in the visualization.

Graphs are loaded in daVinci using a format called term representation which is explained in the reference. Note: Files containing a daVinci term representation should always have suffix .daVinci. The term representation format supports all kind of directed graphs: cyclic or acyclic graphs, empty graphs, graphs with only one level (a list of nodes without any edges), multi-edges (two or more edges between two nodes) or even self-edges (edges where the parent and child node are the same). The term representation is a plain text ASCII format, so daVinci graphs can even be created with an arbitrary text editor. But normally, one will not do this by hand. Instead, graphs are usually generated automatically by some application program.

Applications using daVinci's API

At start time, the editor adds some menus to daVinci's user interface, e.g. to insert or delete nodes and egdes or to change their attributes. Application menus are attached to the Edit menu, but there is no function behind these menus in daVinci. Instead, the API sends menu events to the graph editor to inform about interactions. For example, when the user selects a node (1. event) and chooses the previously attached menu 'Edit/Delete Node' (2. event), then the editor knows by these two events that the user would like to remove the specified node. The editor has its own graph data structure which needs to be modified by the editor to reflect the events. After modification, the editor will send the actual graph back to daVinci to update the visualization.

This principle can be used by any application program that is connected to daVinci's API. Note that the application is exclusively responsible for controlling the graph structure. daVinci is not able to modify the graph on its own. This is important when daVinci is the graph user interface on top of an arbitrary application program. On the other side, by separating the representation layer (daVinci) from the control layer (application connected to the API), the application programmer is relieved from dealing with graph layout algorithms and computer graphics, so he/she can concentrate on his/her true work.

Graph Layout

After loading a graph, a simple layout algorithm will be applied without processing an edge crossing minimization. That means all child nodes of a graph are drawn in the initial order found in the term representation. An edge crossing minimization is an expensive, lengthy operation and therefore need to be started by the user with menu Layout/Improve All. This operation calculates a new graph layout with (probably) fewer edge crossings by rearranging the order of nodes at each level. Afterwards, a bend minimization phase will reduce the number of edge bends. The graph layout algorithm of daVinci is based on the heuristical approach of Sugiyama et al. ([STT81], [SM91]) and was refined by a non-deterministic component to get better results (discussed in [FW94b], [Frö97]). Due to this random component, two layout calculations of the same graph may yield different results. The advantage of this technique is that the average number of crossings is usually smaller.

For all trees (i.e. graphs where all nodes have only one parent), there is a more efficent tree layout algorithm implemented in daVinci. This algorithm with linear complexity is based on the work of Juutistenaho ([Juu94]) and was refined to pass the tree only one time. daVinci automatically selects the appropriate layout algorithm, depending on whether the graph is a tree or not.

In daVinci V2.x, it is possible to set the orientation of a graph layout. The default orientation is top-down to get horizontal levels and edges pointing downwards. The other three layout orientations left-to-right, right-to-left and bottom-up can be set with submenu Layout/Orientation.

After calculating the layout, the graph will be drawn in a window. The visualization of nodes and edges (e.g font, color, shape, icon, line pattern, etc) is determined by their attributes in the term representation. A string, taken from attribute OBJECT, is placed inside each node, whereby the nodes size is adapted to match the actual extension of the text. Multi-line text is also supported. For the layout, the minimal distance between nodes at the same level and the distance between levels (called gap width and height) can be set with menu Options/Layout Dimensions....

If a node is selected by the user with the mouse, it will be drawn with a shadow. For visualizations in a reduced scale, selected nodes are only drawn inverted. Many nodes may be selected at a time. Edges can be selected, too, but only one at a time (i.e. multiple selection for edges is currently not possible). Edge selection is a useful trick to trace the route and find the parent/child node of very long edges.

Incremental Graph Layout

Graph updates sent to the daVinci API are now inserted into the existing graph layout incrementally instead of forcing a completely new layout. So the layout before the update is preserved as much as possible in order to support layout stability. Of course, after doing some incremental updates, the graph layout may be getting worse, so a new global graph layout might be required. The user can do this at any time with menu Layout/Improve All.

This new feature isn't only used for API updates, but also after executing or undoing abstraction operations, for vertical fine tuning, or for the new functions Layout/Improve Edges and Layout/Improve Selected Nodes.

Visualization definition

Note: In future versions of daVinci these visualization definitions should be loadable from a file. In the current version V2.1 visualization definitions can only be set and changed by API commands of category Visual.

Attribute evaluation order

If someone has many graphs with attributes defined for each node and edge from former versions of daVinci, it would be impossible to use the new visualization definitions with these graphs. Therefore the attribute evaluation order can be controlled by setting API command set(rules_first(true)). In this case the visualization rules are considered before the individual node or edge attributes and before the default values.

Fine Tuning of a Layout

Fine tuning is done by selecting a node with the left mouse button. The button need to be pressed while the mouse is moved to a new position (dragging). Both horizontal and vertical fine tuning is implemented in the current release. Regular nodes can be moved in both directions, but the invisible dummy nodes can only be moved horizontally on a level. Fine tuning in daVinci is more than just trivial adjustment of a node's position. Moving a node may have an immediate influence on the rest of the graph layout. For example, if a node is moved horizontally and will touch its left or right neighbour node, then either both nodes have to exchange their position (modify node order) or the neighbour node has to be moved as well (preserve node order), depending on the current fine tuning mode (see below). Furthermore, if a node is moved to the next or previous level, then the child- or parent subgraphs may need to be moved as well to keep the layout hierarchically (i.e. all edges have to point downwards).

For horizontal fine tuning (i.e. moving a node on a level to the left or to the right), there are three modes that can be set with menu Options/Layout Algorithm.... A more comfortable way to set the fine tuning mode is by using the last three icons of daVinci's icon bar. The fine tuning mode defines the behaviour when a moved node touches its left or right neighbour node at the same level. A neighbour node is touched when the minimal node distance is reached by the mouse pointer.

• In default mode Preserve Node Order, the touched node is moved as well to keep the order of nodes on a level.
• In mode Modify Node Order, the moved node and the touched node will exchange their position as soon as there is enough space to do so. This mode is useful to modify the order of nodes on a level, e.g. to remove edge crossing by hand.
• In the third mode Fixed Neighbour Nodes, fine tuning will stop as soon as a neighbour node is touched. This is useful to protect the position of all neighbour nodes.

Important notes about fine tuning:

• After starting the layout algorithm, the x-coordinates and order of all nodes will be recalculated, but their current level will be kept. This preserves the vertical fine tuning, but eliminates the horizontal. If you want to place the nodes back to their default level, you have to deselect checkbox Keep Nodes at Levels in the Options/Layout Algorithm... dialog.
• Modifying the layout dimensions with the Options/Layout Dimensions... dialog eliminates previous horizontal fine tuning operations. So, the final dimensions should be set before starting with extensive fine tuning.
• In daVinci V2.1 you'll find no more left and right borders for fine tuning, as in previous versions, where you couldn't enlarge the visualization during fine tuning. But please note, that unnecessary space to the left and the right of the visualization is removed immediately after you've released the mouse button.

Note: A status file contains information that is specific for a particular daVinci release. Usually, the data stored in status files is extended with each new release, to consider new features. This means that a particular daVinci release, for example V1.4.x, cannot read a status file that was generated by a future release, e.g. V2.1.x. But the status files of earlier releases can always be read in future releases by using a compatibility mode. You can determine the release of a status file by looking at the beginning of the file with the more command.

Interactions

Scaling (menu View/Scale...) can be used to get an overview of a graph that does not fit in a window. The scale of a window can be set to any rate between 1% and 100%. In reduced scales smaller than 100%, some details are not shown (e.g. the text of nodes), but all operations are still available. There is a very efficient implementation for scaling in daVinci. Further, scaling does not affect the layout, so do not hesitate to change the scale frequently in a session.

Abstraction operations (menu Abstraction) are implemented to hide uninteresting or confusing details of a graph for some time. At the moment, two abstractions are available: Subgraph hiding and edge hiding. By hiding a subgraph, all child nodes are removed from the visualization that can only be reached (via edges) from the selected node. The other abstraction, edge hiding, removes all incoming and outgoing edges of a node from the visualization. Both abstractions can be undone with appropriated menu functions.

Some useful navigation and find features are available in menu Navigation. With the navigator, a user can browse in a graph by moving to the nearest neighbour- or relative node of a currently selected node. Selection functions show the parents, siblings or children of a selected node. Finally, a find function can be used to search in a graph for nodes with a particular text.

Multi-Graph / Multi-View

The user is able to open an additional view of a graph from any base window by using menu View/Open New View. This opens a second coupled window showing the same graph. Interactions in one view of the graph (e.g. fine tuning) manipulate the other views, too. One exception is the scale, so each view may have its own scale. The current fine tuning mode is also set independently for each view.

A special view with additional functionality is the survey view which can be opened from any base window (called detail view) with menu View/Open Survey View. A survey view shows the graph of the detail view in a reduced scale such that it is completely visible, even if the window size is changed for the survey view. The visible area of the graph in the detail view is visualized in the survey view with a continuously updated blue rectangle. When the user selects a node in the survey view, daVinci will scroll to this node in the detail view using animation. This behaviour can be switched off in dialog Options/General Settings... by deselecting checkbox On selection in Survey View.

A second, independent graph can be loaded with menu File/Open... in each view. The new graph is only displayed in the view where the load operation was triggered and not in the other views. So technically, a view of a graph is disconnected from the other views of the same graph as soon as a new graph is loaded there. For example, when you have only one window (i.e. no views) and would like to visualize a second graph simultaneously, then open a view to get a second window and load the new graph there. The maximal number of opened base windows in daVinci for multi-view and multi-graph is 64.

Drawing Technology and Pixmap Caching

The pixmaps of all drawn segments are kept in a memory cache as long as the scale of the visualization is not modified and the graph layout does not need to be recalculated. Pixmap caching accelerates the scrolling performance when the user scrolls back into previously visible areas of the graph. The pixmap cache can be switched off with dialog Options/General Settings.... This should be done when problems with not enough memory occur (daVinci will crash with a X Error: BadAlloc message as soon as no more memory is available).

Drag and Drop