An interface to graph drawing with uDraw(Graph), the previous daVinci

provides: ----------------- user interface--------------------------; x-ozlib://niehren/davinci/manager.ozf; ----------------- examples--------------------------------; x-ozlib://niehren/davinci/examples/example1.oz; x-ozlib://niehren/davinci/examples/example2.oz; x-ozlib://niehren/davinci/examples/noonoo.gif; x-ozlib://niehren/davinci/examples/hi.xbm; x-ozlib://niehren/davinci/examples/quit.xbm; ----------------- implementation -------------------------; x-ozlib://niehren/davinci/layout-functions.ozf; x-ozlib://niehren/davinci/graphic-interface.ozf; x-ozlib://niehren/davinci/state.ozf; x-ozlib://niehren/davinci/coding.ozf; x-ozlib://niehren/davinci/actions.ozf; x-ozlib://niehren/davinci/commands.ozf
requires: uDrawGraph-3.11; mogul:/duchier/config; mogul:/niehren/base; mogul:/niehren/output; mogul:/niehren/inspector-space; mogul:/niehren/external-process

Purpose

This package provides a simple, flexible, and powerful interface to the graph drawing tool DaVinci. DaVinci is a professional graph drawing tool developped by Michael Fröhlich and Mattias Werner from the Group of Prof. Dr. Bernd Krieg-Brückner at University of Bremen in Germany.

To draw a graph, it is sufficient to specify its nodes and edges, and how to draw them (but not where to). The required graph specifiations can be defined on high level through Oz data-structures. These are automatically converted to strings in DaVinci's API-format and then send to an Oz-external DaVinci process that is created.

The interface also permits to define graph actions that are envoked by clicking on nodes or edges of the drawn graph. Specifications of actions can be defined through arbitrary Oz procedures. They may refer to the actual graph structure which is always memoized by the interface.

So far, the interface is available for Linux but soon, it will also be made available for Windows.

DaVinci

DaVinci displays a graph in its window after a term representation of the graph has been loaded from file. It is as well possible to communicate with daVinci directly via the shell by sending strings in the requisite syntax.

DaVinci was built with respect to the facility of connecting an extern application program that serves as a graph editor. The interface operates as the connector between daVinci and Oz datastructures that edit and modify graphs.

Layout principles

DaVinci visualizes graphs in a hierarchical manner, i.e. reflects the hierarchical relationships of a graph by arranging the nodes on horizontal levels in a way that all parent nodes are above their children nodes and edges point downwards (though it is possible to switch to the inverse bottom-up layout as well as to left-right or right-left layout). Cyclic graphs are handled with a trick.

Here is an example:

Attributes of a graph

Nodes can be labelled with text (edges as well in version 3.x) Nodes and edges can have other layout attributes (color, pattern, for more examples see below). The graph can be edited (move, remove and add edges and nodes, change attributes). Menus can be placed at nodes, edges and the graph displaying window.

Graph Specification in Oz

The vital principle of this interface is to seperate the topology of a graph and the attributes of nodes and edges. Attribute definitions are made simple by inheritance. The user can define sets of attributes called 'kinds' and use these kinds in nodes and edges. This defines the attributes oft nodes and edges by inheritance from their kinds.

Graphs can be modified at run time. Nodes and edges can be added and removed, and attributes can be changed. Every nodes always knows its ingoing and outgoing edges.

For all of the documentation below we recommand to consult one of the examples for illustration.

example1.oz (basic)

example2.oz (with actions)

Nodes and Edges

A graph consists of a list of nodes and a list of edges.

type Graph= unit(nodes:list(Node) 
                 edges:list(Edge)

A node is specified by a record of node features that define the node's id, kinds, and attributes. For conveniance, an optional feature edges is offered by node specifications where some of the outgoing edges of the node can be specified.

type Node = unit(id      : Atom 
                 edges   : list(Edge)
		 kind    : Atom
		 kinds   : list(Atom)	   
                'OBJECT' : VirtualString
	 	 menu    : list(MenuEntry)
	         ... )

This is only a small collection of possible node features. There may be many more useful node attributes. These are defined by actual DaVinci tool used. A set of such node attributes is also explained in Node Attributes

An edge is a record with features for specifying the edge's id, kinds, end-node and attributes.

type Edge <= unit(id     : Atom 
                 'from'  : Atom
                 to      : Atom 
		 kind    : Atom
		 kinds   : list(Atom)	   
                'OBJECT' : VirtualString
	 	 menu    : list(MenuEntry)
	         ... )

The edge feature 'from' can be ommited in edge specifications that are embedded into the specification of that node where the edge starts. The above types lists only a small collection of possible edge features. For additional features, we refer to Edge attributes

Graph and Window Parameter

The nodes and edges of a graph and also the window in which it resides usually depend on a large number of parameter. They serves for specifying the layout of the daVinci window, i.e. how certain kinds of edges and nodes will be drawn. They also specify menus or other actions such as for reacting to mouse-clicks at the graph window. Parameters can be specified by a record of the following type where all features are optional.

type Parameters = unit(layout          : Layout
                       actions         : Actions
		       configuration   : Configuration
		       debugging       : Bool)

type Layout = unit(node  : Layouts
                   edge  : Layouts
	           window: WindowProperties)

Attribute Inheritance via Kinds

The node or edge layouts define different kinds of nodes and edges.

type Layouts = unit(default: Kind
                    atom   : Kind
	              .       .
		      .       .
		      .       .
                    atom   : Kind)

A kind specifies values for a set of node resp. edge attributes.

type Kind = unit(attribute : Value
                   .           .
      	           .           .
		   .           .
                 attribute: Value)

A node or edge inherits the values of all attributes of its kinds. The complete list of kinds of a node or edge is defined by the values of the two features kind and kinds. If both values are available, the overall list is obtained by prepending the value of kind to the values of kinds.

The attributes of the kinds of a node are inherited in that order in which the kinds occur in the overall list of kinds. Note that multiple inheritance may overwrite values inherited earlier.

The types of attributes of nodes and edges where already discussed in the subsection on nodes and edges. The features id, edges, kind, and kinds have special meanings, i.e., the are not attributes in the sense of DaVinci's specification.

Node and edge attributes that are left unspecified will be given default values. The defaults can be definded by the user, as it is given by the value of the default feature of Layouts.

Window Properties

The WindowProperties describes the desired features of the daVinci window the graph will be drawn in.

type WindowProperties = unit(menu : list(MenuEntry)
                             icons: list(Icon))

Menu Entries and Menu Actions

The list of MenuEntries represents the entries of the edit menu in the daVinci window, while Icons represents the icons to be found at the left side of the daVinci window.

type MenuEntry        = menu_entry(MenuAction VirtualString)  
                        + submenu_entry(MenuLabel list(MenuEntry))  
                        + blank 
type MenuAction       = NodeMenuAction + EdgeMenuAction + WindowMenuAction
type NodeMenuAction   = Node x DaVinci -> 
type EdgeMenuAction   = Edge x DaVinci -> 
type WindowMenuAction = DaVinci ->

A MenuAction identifys the action to be executed when choosing the correspinding menu entry. A VirtualString represents the label of this entry (i.e. what is shown at the menu bar). For specification of VirtualString cf. The Oz Base Environment . A MenuAction receives one or two arguments. The last argument is always the actual DaVinci. The first of two arguments specifies either the node or edge to which the menu belongs. WindowMenuActions only have one argument. The blank serves as a seperator of menu entries.

Window Icons

The DaVinci window can be equipped with Icons by which to raise actions.

type Icons      = list(IconEntry)
type IconEntry  = icon_entry(IconAction URI IconLabel)
type IconAction = Node x DaVinci ->
type IconLabel  = VirtualString

IconAction specifies the desired action, which receives two arguments: the actual node and the actual DaVinci.

URI adresses the bitmap of the icon in X-Window Bitmap format (.xbm format) of size 18x18 pixel. The URI is resolved to a filename by the Mozart resolver.

IconLabel should be a short description of the semantic of the icon which will be displayed in the footer area of the daVinci window as soon as the mouse-pointer is over the icon.

Window, Node, and Edge Actions

Actions specify the reactions to messages from DaVinci. DaVinci will send messages when the user clicks at the graph window. There are predefined defaults for reactions on single and double clicks on nodes and edges. Other DaVinci messages are ok and commmunication_error which comment on the messages which were sent from the interface to Davinci. The default reaction on these commenting messages has no effect. It is possible to define procedures which will overwrite the defaults. Here are the types:

type Actions = unit(nodeDoubleClick:     Node x DaVinci ->
                    edgeDoubleClick:     Edge x DaVinci ->
                    nodeSingleClick:     Node x DaVinci ->
		    edgeSingleClick:     Edge x DaVinci ->
                    ok:                  DaVinci ->
                    communication_error: Value x DaVinci ->
		   )

Please confer example2.oz.

The State of the Graph

Actions often depend on the actual state of the graph in the window. DaVinci.state can provide you with that information.

type DaVinci.graph = unit(inEdges  : Node -> list(Edge)
                          outEdges : Node -> list(Edge)
                          reachable: list(Node) ->  list(Node)
                          %% conversion of the graph
                          toNodes  : -> list(Node)
                          toEdges  : -> list(Edge)    
                          %% implementation
                          nodes    : dictionary
                          edges    : dictionary
                          toNode   : atom -> Node
                          toEdge   : atom -> Edge
                          handle   : ( -> ) ->
			  ...)

The function DaVinci.graph.inEdges maps a node to the list of ingoing edges, and the function DaVinci.graph.outEdges to the list of outgoing edges. These function are implemented via dictionaries DaVinci.graph.nodes and DaVinci.graph.edges that hash nodes and edges via their ids. The type of dictionaries used are defined in the package mogul:/niehren/base. These dictionaries can be converted into the actual list of nodes and edges by applying the functions DaVinci.graph.toNodes and DaVinci.graph.toEdges.

It is also possible at each time point to retrieve the actually selected edge or the set of actually selected nodes of the graph:

	type DaVinci.getSelectedNodes = -> list(Node)

returns a list containing of all nodes that are currently selected in the graph window

	type DaVinci.getSelectedEdge  = -> Edge + NoEdge
        type NoEdge = Name

returns the currently selected edge in the graph window

Configuration

type Configuration = [DVCommand1 ... DVCommandN] DVCommand is a daVinci command of category 'set' (cf. DV-Documentation http://www.tzi.de/daVinci/docs/reference/api/api_set_cmd.html).

A possible configuration could be:

configuration: ['set(font_size(12))'
		'set(gap_width(6))'
		'set(gap_height(18))']

Debugging

type Debugging = Bool

If Debugging is set to true, a large set of debugging information will be displayed by the Oz Inspector. These values may also be of interest if you want to understand more about what this interface is doing internally. By default, the value of this feature is false.

How to use the Interface

The following interactions with the user interface are provided by the functor manager.ozf.

Window Creation

	[Interface] = {Link ['manager.ozf']}
	DaVinci = {Interface.new Parameters}

This functor exports a procedure Interface.new; it needs Parameters (as defined above) and returns a record with features stated below. Suppose you invoke manager.ozf as follows:

Graph Creation

The procedure DaVinci.newGraph draws a newly specified graph. {DaVinci.newGraph Graph} Graph is a graph specification in the form described above. A graph with the given parameters will be drawn into a daVinci window. Next, we can add a subgraph that my be connected to the actual graph.

Editing the Graph

As mentionned above, DaVinci allows you to edit a graph once drawn. You can add or remove subgraphs, nodes, or edges, and change their attributes. These procedures apply to the current state of the graph that is memoized oz Oz-side through the given interface.

First of all you can add nodes, edges, or graphs:

         {DaVinci.add.nodes list(Node)}
         {DaVinci.add.edges list(Edge)}
 	 {DaVinci.add.graph Graph}

Second, you can remove nodes, edges or the subgraph below some node:

	{DaVinci.remove.subgraph Node}
	{DaVinci.remove.nodes [Node1 ... NodeN]}
	{DaVinci.remove.edges [Edge1 ... EdgeN]}

Third, you can change the attributes of nodes and edges:

	{DaVinci.change AttribChanges}
	type AttribChanges = list(AttribChange)
	type AttribChange  = node(Node Kind) + edge(Edge Kind)

The Kinds specify new values for some node or edge attributes.

Changing Parameter

You can also change the window and graph parameters. This can change the behaviour of the function DaVinci.newGraph and of the menu independent actions.

	{DaVinci.configure NewParameters}
	NewParameters = unit(parameter: Parameters
                             actions  : Actions)

The procedure DaVinci.configure receives a record of parameters to be changed. The record has two features: at the first you can give the whole parameters; the second provides the possibility to only change the actions. If no parameters or actions are given, the old ones are taken. For types of Parameters and Actions see specification above. {DaVinci.improveAll} is a functionality provided by daVinci which reduces edge crossings. (cf. DV documentation). {DaVinci.setTitle 'Desired title'} setTitle allows you to entitle the daVinci window {DaVinci.setSize Int#Int} setSize allows you to determine the size of the daVinci window. The first integer is the new window width (in pixel) and the second is the new height. Do not use negative values or values larger than the screen.

Access to the Implementation

{DaVinci.execute 'DV-Command'} enables you to send daVinci commands in daVinci syntax directly to daVinci API. The DV-Command must be set into single quotes. Using DaVinci.execute is dangerous since the actual state of DaVinci may get inconsistent with respect to its image memoized on the Oz-side. Even more libarally,

     DaVinci.gi

makes the whole implementation of the graphic interface available.

Installation

Download the file daVinci.pkg, invoke ozmake and execute in a shell ozmake --freshen --package=niehren-davinci-x.x.x.pkg ozmake --extract --package=niehren-davinci-x.x.x.pkg The second command will provide the necessary file in the current directory.
Then you can open the example files and feed them to the compiler. In case that did not already install ozmake on your machine, note that it is also available in the Mogul archive.

Joachim Niehren.