Dynagraph is a platform-independent graph layout engine. Dynagraph calculates geometric coordinates for nodes and edges of a graph diagram. In its response to changes in the graph - insertion, deletion, or modification of nodes and edges - Dynagraph balances stability (unchanged parts of the graph should not change much) with readability (edges should be short and direct, and should cross each other as little as possible).
Dynagraph itself does not do actual rendering to a screen, graphic file, or printer, nor does it provide a GUI for editing graphs. Dynagraph only computes the coordinates, and front ends like Dynagraph for Windows (dgwin) and Grappa handle all the platform-specific rendering and GUI functions. (This document briefly describes how to use these front ends.) Since dynagraph shares its file format and most of the attributes with the other graphviz tools (dot,neato,lefty), those tools can also be used to render Dynagraph output.
This document is mostly concerned with how to connect programs to the Dynagraph layout engines. Dynagraph supports three ways to do this:
Although the programming models differ, the API for all of these is essentially the same. Even if you do not intend to write your own front end, you will need to know something of the API in order to specify the input.
Most likely you will not be writing your own front end to draw to the screen, graphics files, etc. We provide two front ends that you may want to use: dggrappa, a version of Grappa adapted for Dynagraph; and Dynagraph for Windows, which integrates Dynagraph with other OLE (ActiveX) applications such as the Microsoft Office suite.
Dynagraph for Grappa (dggrappa) (source available here) is a slightly modified version of Grappa with an extra module to interpret the incrface language. The dggrappa application spawns the Dynagraph executable in a separate process and communicates with it using pipes. Drawing commands in Grappa send incrface commands to Dynagraph; Dynagraph returns incrface events to which Grappa responds by updating the canvas. For example, pressing the shift key while clicking on the background or dragging between nodes sends "insert" commands to Dynagraph; they return as "insert" events and Grappa draws the new nodes and edges. Also dggrappa can be told to copy its standard input to the Dynagraph input (with "-i -"). Then you or your application can enter or change the graph by inputting incrface language commands to dggrappa.
The dggrappa application is a class called att.dggrappa.DGDemo. It requires one command-line parameter: the path to the Dynagraph executable. It will spawn dynagraph with the command line parameter -d, because Grappa uses dot-like coordinates (with the difference that the lower-left corner is not necessarily 0,0). By default it specifies the graph attributes [resolution="1,1",separation="24,24",engines="shapegen,fdp,voronoi,visspline"]
Dynagraph for Windows (dgwin) (binaries here, source here) is a full-featured, OLE-capable graph drawing application and control. It can be embedded in OLE applications such as the Microsoft Office suite, Web pages, and Visual Basic programs. It wraps the Dynagraph library in COM interfaces, so that the layout and content can be controlled from any ActiveX compatible language. Dynagraph for Windows is based on a general control container library called Montage, which can be used for creating other new OLE document types and applications.
At this time there is no built-in way to connect dgwin to a pipe to receive incrface commands. If this is the desired way to control the layout, the best way is to create an instance of the singleton Dynagraph.IncrClient class (CLSID_DGIncrClient). This class is intended to spawn an external graph server, and the method IDGIncrClient::Write sends text to that server. However, if the method IDGIncrClient::StartServer was not called, then Write sends the text directly to the incrface parser. Call IDGStringAttributes::get_Name on the layout engine to find out the name of the graph to use in the incrface commands.
Dynagraph for Windows consists of a large number of small objects. It is designed for super-modularity: not only can the visual elements be changed (e.g. Word documents for nodes), but the user interface itself can be changed, replacing, say, what happens when the user right-clicks an edge. The Montage object is a blank canvas with no interaction at all; on top of this are built configurations which add the visual and interactive behaviors we have come to expect from Windows programs. Instantiate the class DGM.Diagram (CLSID_DynagraphControl) to get a full-featured graph drawing control.
Every node and edge in a dgwin diagram has quite a few objects backing it up:
While it is possible to construct all of these objects and connect them directly, it requires quite a lot of code, especially considering that most of these also require a persistor object in order to be saved and loaded! The DGM.Drawer object handles all of this work. It holds pointers to OLE data objects which provide the controls to use for nodes, edges, and labels. (OLE data objects implement IDataObject; these are the basis of clipboard and drag-and-drop operations.) It also (of course) holds pointers to the Montage canvas and to the Dynagraph layout engine, as well as to a Montage data unpacker, which knows how to read the data objects.
If your application is going to use the default nodes and edges, it can use the Drawer as it is. First you'll need pointers to the layout engine and to the DGM Drawer object. Their internal names are "Graph Layout Engine" and "Graph Drawer"; get pointers to them by binding item monikers with these names or by calling IOleItemContainer::GetObject. Next, create the layout objects using IDGGraph::new_Node and ::new_Edge on the layout engine. Set any layout parameters using the interfaces IDGDrawnNode and IDGDrawnEdge on the layout objects. Then use the IDGMDrawer::NewNode and ::NewEdge methods to create the rest of the objects listed above.
To move objects around and to delete them, you have a choice of methods. The easiest way is probably to call methods on the Dynagraph objects. For example, calling IDGDrawnNode::Delete or IDGEdge::Delete will delete the object. To change a node's position, call IDGDrawnNode::put_Pos. But wait a second: that's a POINTD! Yes, Dynagraph uses floating point coordinates, and though the library is resolution-independent, Dynagraph for Windows uses units of one centimeter. Also, you'll find no "size" input; instead nodes have polygonal shapes, over which the DGM.NodeShadow expects to have control.
So the proper way to change the size of a node is to fire an event on the site. ("I thought objects fired their own events," you object. Well, COM actually leaves it open for other objects to fire those events. See or use Shared/fire*.h.) The relevant events are on IMCCSiteOwner; these make it possible for the Edit mode to move and delete objects without knowing about Dynagraph. And IMCCSiteOwner::Move accepts pixel or HIMETRIC (0.01cm) point, size, or rectangle coordinates.
a | All at once (batch). Equivalent to not specifying -t. |
n | Insert all nodes, then all edges. |
b | Breadth first search. |
d | Depth first search. |
r | Randomly insert edges. |
w | "Wandering" (not recommended). |
c | Crossing optimization |
t | Time usage breakdown |
d | Dynadag tallies |
g | Dump graph in dotfile format after every step |
q | Dump input queue before each step |
r | Output readability statistics |
s | Output stability statistics |
p | Report on progress |
b | Bug of the day: used for random debugging |
In this interface, the client and server communicate requests and modifications over pipes using a command language. The language is the same for client requests and server events, with the exception that the server does not emit the "segue" command. Many commands can accept attributes in the dot syntax, i.e. [attr=value,attr2="value with spaces or other parser-confusing stuff"]
This language can also be used for other incremental graph purposes. For example, a slightly augmented version is used by the Dinograph large graph server.
What follows is a transcript of a simple interaction with Dynagraph. In this example, the input text is in bold, the output text is normal, and comments are in italics.
open graph VThe Dynagraph library can be linked to a C++ program. The API for connecting with a Dynagraph layout server is defined in common/Dynagraph.h and auxiliary headers. There are two main libraries: the core library (in the subdirectory common) and the incrface library. Then there are four layout engines in separate libraries: dynadag, fdp, shortspline (visspline), and voronoi. (The graphsearch large graph server is undocumented.) This document does not address platform-specific issues such as how to build Dynagraph or link it. Automake files for Unix-like environments are included in the GraphViz source, and Microsoft Visual C++ projects are in the Dynagraph for Windows source.
The Dynagraph library provides a C++ API that blurs the difference between batch and incremental layout. (This is also the most powerful of the APIs, as this is the API that's used internally and it's not mediated by translation code.) You can choose whether or not to use the incrface library, which provides both naming services and the ability to receive commands using the incrface language.
createLayoutServer
from the incrface library to create the layout server. The composition of multiple servers into one using the class CompoundServer
is a detail which most applications won't need to change, but that function too can be re-written.
Include the main Dynagraph header and the header for createLayoutServer
:
#include "common/Dynagraph.h"
#include "incrface/createLayoutServer.h"
layout
and current
; layout
is where we create new elements, and current
is the subgraph which represents what is showing in the layout. Make current
a subgraph of layout
by specifying layout
in the constructor call, i.e.
Layout layout,current(&layout);
gd<GraphGeom>(&layout).resolution = Coord(0.1,0.1);
gd<GraphGeom>(&layout).separation = Coord(0.5,0.5);
ChangeQueue queue(&layout,¤t);
gd<StrAttrs>(&layout)["engines"] = "shapegen,fdp,voronoi,visspline";
createLayoutServer
:
Server *server = createLayoutServer(&layout,¤t)
Layout::Node *m = layout.create_node(),*n = layout.create_node();
gd<NodeGeom>(m).pos = Coord(10,10);
gd<NodeGeom>(n).pos = Coord(15,10);
queue.InsNode(m);
queue.InsNode(n);
server->Process(queue);
Between runs it's important to clear the ChangeQueue with the Okay command. Its sole parameter tells it whether to erase the nodes and edges marked for deletion. This choice depends upon whether there's a need for nodes and edges to live outside the current layout. For this example, there is no reason for them to:
queue.Okay(true);
Layout::Edge *e = layout.create_edge(m,n).first;
queue.InsEdge(e);
server->Process(queue);
// ... read changes from the queue ...
queue.Okay(true);
gd<NodeGeom>(n).pos = Coord(5,5);
queue.ModNode(n,DG_UPD_MOVE);
server->Process(queue);
Deletion is a little different, because the node or edge still has to exist while the engine is processing it. So mark it with DelNode
or DelEdge
and then use ChangeQueue.Okay(true)
or Layout::erase
after the engine has run. Also note that deleting a node causes any edges attached to it to be deleted.
queue.DelNode(n);
server->Process(queue);
// ... read changes from the queue ...
queue.Okay(true);
Layout::node_iter ni;
for(ni = queue.modN.nodes().begin(); ni!=queue.modN.nodes().end(); ++ni)
;// move graphical object associated with *ni to gd<NodeGeom>(*ni).pos;
To come: how to attach to the Dynagraph COM library (comdg) to do layouts without using Montage and the whole of Dynagraph for Windows.
There are three APIs to Dynagraph: the incrface language, whose string attributes (only accessed in graphviz/dynagraph/common/stringsIn.cpp, stringsOut.cpp, and ColorByAge.cpp) are mostly a subset of the dot language's attributes; the C++ API; and the COM API. This reference defines the parameters which are common to all three; specifics about how to use each API were laid out in the last three sections.
If the C++ entry says "use string attribute", that means you should manipulate the string name, e.g. with incrface:
Or without:StrAttrs attrs;
attrs["shape"] = "ellipse";
view->incr_ev_mod_node(nodename,attrs);
If the COM entry says this, use IDGStringAttributes, e.g. in ATL:StrAttrs attrs;
attrs["shape"] = "ellipse";
Q.ModNode(stringsIn(transform,n,attrs,false));
CComQIPtr<IDGStringAttributes> nstrings = n;
nstrings->SetAttr(CComBSTR("shape"),CComBSTR("ellipse"));
incrface attribute | C++ class and field | COM interface and method |
---|---|---|
(out) lines = "bB x1,y1 x2,y2 ...; bB x,y..." (in for nodes) boundary = "x0,y0 x1,y1 x2,y2 ..." (in,out for edges) pos = "x0,y0 x1,y1 x2,y2 ..." | (out) struct Drawn : Lines (in) Region NodeGeom::region Line EdgeGeom::pos |
interface IDGLayout [propget] HRESULT Lines([out,retval] DGSHAPESDESC **ret); interface IDGDrawnNode [propput] HRESULT Shape([in] DGSHAPESDESC *shapes); [propget] HRESULT Shape([out,retval] DGSHAPESDESC **ret); interface IDGDrawnEdge HRESULT SetPoints([in] DGSHAPEDESC *val); HRESULT GetPoints([out,retval] DGSHAPEDESC **ret); |
(in,out) On output, the lines or Bezier curves to draw. On input, the node shape to use for edge clipping, or a hint for where to draw the edge. In the string attribute, B specifies the Bezier degree, either 1 for lines or 3 for cubic Bezier curves. On the graph, this attribute is used only for debugging. On a node, this is a valid input only if shape generation is turned off; only the first poly(sp)line is used for edge clipping; and the points are relative to the node position. On an edge, only one poly(sp)line must be specified (note the different type of the C++ and COM versions). This parameter is ignored (?!) as an edge input in the string and COM versions, and in C++ unless EdgeGeom::manualRoute is true.
In Dynagraph, there is a one-to-one correspondence between graphs, layouts, and layout engines. Incrface calls the bunch a "view." These attributes belong to the layout graph and some are engine parameters.
incrface attribute | C++ class and field | COM interface and method |
---|---|---|
engines = "eng1,eng2,..." | use string attribute | use string attribute |
(in) Specifies which layout engines to use. Every time a change happens to the graph and the lock count is zero, these engines get called in the order listed here. This parameter should be specified when the graph is opened, e.g. in the open graph incrface command, or before IDGLayout::Initialize is called. (C++ programs: before DynaView::createServer or createLayoutServer.) This parameter may be changed after the graph is opened, with the effect that all nodes and edges get inserted as new objects using the new engines. To do this in COM, first set the string attribute and then call IDGLayout::Initialize again. To do this in C++ with incrface, use DynaView::incr_ev_mod_graph; without incrface, please consult the incrface or comdg code.
The most common settings are "shapegen,fdp,voronoi,visspline" for neato-like layouts, and "shapegen,dynadag" for dot-like layouts. The available engines are:
dynadag | DynaDAG tries to get edges to point downward and usually aligns them in rows. |
---|---|
fdp | Force-Directed Placement: uses a spring model to place nodes. They can still overlap, and this algorithm does not handle edges, so this is intended to be used with voronoi and visspline |
voronoi | Using a previously generated layout, tries to adjust the nodes so that they don't overlap, while keeping the same relative placement. |
visspline | Routes spline edges so as to avoid crossing nodes. Does not affect node positions. |
labels | Places node and edge labels; does not affect node or edge placement. |
shapegen | Generates shapes for nodes based on an interior (text) size, a minimum external size, and various shape parameters. |
colorbyage | Each time a layout happens, updates the colors of all nodes based on the graph agecolors attribute. |
defaultsize = "x,y" | Coord GraphGeom::defaultSize | N/A |
(in) The minimum size to use for nodes for which that parameter was not set. Because this gets checked when looking at the string attributres, this is only relevant for programs using incrface. Default: (1.5,1) without -d, (54,36) with.
resolution = "x,y" | Coord GraphGeom::resolution | interface IDGEngine [propget] HRESULT Resolution([out,retval] POINTD *ret); [propput] HRESULT Resolution([in] POINTD val); |
(in) The smallest increment to recognize in the internal model. For example, specify 1,1 for integer precision. Default: (0.1,0.1) without -d, (1,1) with.
separation = "x,y" | Coord GraphGeom::separation | interface IDGEngine [propget] HRESULT Separation([out,retval] POINTD *ret); [propput] HRESULT Separation([in] POINTD val); |
(in) The amount of separation to leave between elements of the layout. In dynadag, x specifies the horizontal gap left between nodes and/or edges, and y specifies the amount by which to multiply the edge length to get the minimum vertical displacement. Default: (0.5,0.5) without -d, (24,24) with.
N/A | Coord GraphGeom::labelGap | not available (!) |
(in) The amount of space to leave between labels and nodes, e.g. if a label is on the right of a node, label.left = node.right+labelGap.x.
Default: (0,0)
bb = "left,bottom,right,top" | Bounds GraphGeom::bounds | interface IDGLayout [propget] HRESULT Bounds([out,retval] RECTD *ret); |
(out) Reports the bounding box of the current layout.
changerect = "left,bottom,right,top" | Bounds GraphGeom::changerect | interface IDGLayout [propget] HRESULT ChangeRect([out,retval] RECTD *ret); |
(out) Supplies a rectangle which contains all of the changes just made to the layout
not available | float GraphGeom::splineLevel | interface IDGEngine [propget] HRESULT SplineLevel([out,retval] enum DG_SPLINELEVEL *ret); [propput] HRESULT SplineLevel([in] enum DG_SPLINELEVEL val); |
(in) How to draw edges, specifically, how much of the spline-drawing process to complete. Although this parameter produces "interesting" results it is probably more useful for debugging than for stylistic purposes. This parameter is only implemented in dynadag.
(N/A) | DG_SPLINELEVEL_VNODE | DGSL_VNODE | Draw straight lines between the nodes in the internal model. |
DG_SPLINELEVEL_BOUNDS | DGSL_BOUNDS | Draw the bounding polygon of the spline. | |
DG_SPLINELEVEL_SHORTEST | DGSL_SHORTEST | Draw the shortest straight-line paths within the bounds. | |
DG_SPLINELEVEL_SPLINE | DGSL_SPLINE | Draw edges with Bezier curves (default). |
not available | Orientation Translation::orientation | interface IDGEngine [propget] HRESULT Orientation([out,retval] enum DG_ORIENTATION *ret); [propput] HRESULT Orientation([in] enum DG_ORIENTATION val); |
(in) This feature is only complete in the COM library. Specifies the orientation of the graph, that is, which way edges should point in Dynadag. At the C++ API level, the layouts always are oriented downward: the heads of edges have lesser Y values than the tails, unless there are loops in the graph. It is a trivial matter to translate the coordinates to obtain different orientations, by inverting and swapping the x and y coordinates. (See graphviz/dynagraph/common/reorient.h.) Then offset the coordinates to bring them into the right quadrant.
The C++ Translation::orientation
attribute does not cause the coordinates to actually be translated, but the ShapeGenerator reads this and rotates the nodes' NodeGeom::region
the opposite way to cancel for the translation the client (or the COM library) will do.
agecolors = "color1,color2,..." | use string attribute | use string attribute |
Parameter to the colorbyage "layout" engine. If this parameter exists, then any node which does not have a color will receive color=color1, any node which has color=color1 will receive color=color2, etc.
ticks = float | float GraphGeom::ticks | use string attribute (!) |
(in) Specifies the elapsed time, in seconds, after which Dynagraph should hurry up and try to get a result. Not yet implemented.
incrface attribute | C++ class and field | COM interface and method |
---|---|---|
pos = "x,y" | Position NodeGeom::pos | interface IDGDrawnNode [propget] HRESULT Pos([out, retval] POINTD *ppos); [propput] HRESULT Pos([in] POINTD pos); |
(in,out) Specifies the position coordinate of the node. This is the offset for the lines and boundary parameters. If the string parameter is blank or pos.valid==false or IDGDrawnNode::Optimize(VARIANT_TRUE) has been called, the engine will choose a new position for the node without regarding the old one.
shape = shape-name | use string attribute | use string attribute |
(in) Specifies the name of the base shape, which will select the other shape generation values (which can be overridden). These are a subset of those offered by dot. Default: ellipse.
ellipse | The base shape is a Bezier spline approximation of an ellipse. |
---|---|
polygon | The base shape is a polygon, by default four-sided. |
hexagon | sides = 6 |
box | sides = 4 |
circle | regular = true isEllipse = true |
diamond | sides = 4 orientation = 90 |
doublecircle | isEllipse = true regular = true peripheries = 1 |
doubleoctagon | sides = 8 peripheries = 1 |
egg | isEllipse = true distortion = 1.3 orientation = 90 |
hexagon | sides = 6 |
house | |
invhouse | |
invtrapezium | |
invtriangle | sides = 3 orientation = 180 |
octagon | sides = 8 |
parallelogram | sides = 4 skew = 0.5 |
trapezium | |
triangle | sides = 3 |
tripleoctagon | sides = 8 peripheries = 2 |
labelsize = "x,y" | Coord PolyDef::interior_box | interface DIDGShapeDefinition [propget] HRESULT InsideWidth([out, retval] double *ret); [propget] HRESULT InsideHeight([out, retval] double *ret); HRESULT SetInside([in] double width,[in] double height); |
(in) The size of the text to fit within this shape. For consistent heights with different line lengths, the shape will be stretched to fit a square whose size is the smaller of x and y, and then stretched again to fit the larger. Default: (0,0).
width = float height = float | Coord PolyDef::exterior_box | interface DIDGShapeDefinition [propget] HRESULT OutsideWidth([out, retval] double *ret); [propget] HRESULT OutsideHeight([out, retval] double *ret); HRESULT SetOutside([in] double width,[in] double height); |
(in) Minimum external width and height. Defaults to the graph's defaultsize attribute.
sides = integer | int PolyDef::sides | interface DIDGShapeDefinition [propget] HRESULT Sides([out, retval] int *ret); [propput] HRESULT Sides([in] int val); |
(in) The number of sides of the polygon, when the shape is not "ellipse". Default: 4.
regular = true|false | bool PolyDef::regular | interface DIDGShapeDefinition [propget] HRESULT Regular([out,retval] VARIANT_BOOL *ret); [propput] HRESULT Regular([in] VARIANT_BOOL val); |
(in) If true, specifies that the aspect ratio of the shape will be 1:1. (i.e. if the shape is an ellipse, it will be a circle, rectangle a square.) Default: false.
peripheries = integer | int PolyDef::peripheries | interface DIDGShapeDefinition [propget] HRESULT Peripheries([out, retval] int *ret); [propput] HRESULT Peripheries([in] int val); |
(in) The number of extra borders to draw around the shape. Default: 0.
perispacing = float | double PolyDef::perispacing | interface DIDGShapeDefinition [propget] HRESULT Spacing([out, retval] double *ret); [propput] HRESULT Spacing([in] double val); |
(in) The distance between the parallel lines of the peripheries. Because Dynagraph is coordinate-independent, the default value for this parameter is 0, so if you don't set this, you won't see the peripheries!
orientation = float | double PolyDef::rotation | interface DIDGShapeDefinition [propget] HRESULT Rotation([out, retval] double *ret); [propput] HRESULT Rotation([in] double val); |
(in) The angle, in degrees, that the shape should be turned. By default, the rotation is 0, which means that the bottom line of a polygon is horizontal.
skew = float | double PolyDef::skew | interface DIDGShapeDefinition [propget] HRESULT Skew([out, retval] double *ret); [propput] HRESULT Skew([in] double val); |
(in) The amount to tilt the shape. Default: 0.
distortion = float | double PolyDef::distortion | interface DIDGShapeDefinition [propget] HRESULT Distortion([out, retval] double *ret); [propput] HRESULT Distortion([in] double val); |
(in) Make the top bigger than the bottom. Default: 0.
not available | NailType nail | not available |
(in) Specifies the mobility of the node. Only Y-axis nailing is available, and only in Dynadag. Default: none.
DG_NONAIL | The node can be positioned at the server's discretion. |
---|---|
DG_NAIL_X | The server attempts to keep the node at the same X position. |
DG_NAIL_Y | The Y position (rank) is fixed. |
DG_NAIL_BOTH | The node is immobile. |
incrface attribute | C++ class and field | COM interface and method |
---|---|---|
N/A | double EdgeGeom::minLength | interface IDGDrawnEdge [propget] HRESULT Length([out,retval] double *pWidth); [propput] HRESULT Length([in] double Width); |
(in) The minimum length of the edge. In dynadag, this is multiplied by GraphGeom::separation.y to determine the verticle displacement between the nodes at either end of this edge. Default: 1.0.
not available | bool EdgeGeom::constraint | interface IDGDrawnEdge [propget] HRESULT Constraint([out, retval] VARIANT_BOOL *pConstraint); [propput] HRESULT Constraint([in] VARIANT_BOOL Constraint); |
(in,out) In dynadag, if this flag is set to true, the edge will always point downward. If this flag is set to false, the edge can point upward when there is a cycle in the graph. Dynadag will set constraint==false if it finds a cycle while inserting the edge.
not available | Port EdgeGeom::tailPort,headPort; | interface IDGDrawnEdge [propget] HRESULT TailPos([out,retval] POINTD *ppos); [propput] HRESULT TailPos([in] POINTD tpos); [propget] HRESULT HeadPos([out,retval] POINTD *ppos); [propput] HRESULT HeadPos([in] POINTD pos); |
Offsets of the ends of the edge from the tail and head node positions.
not available | bool tailClipped,headClipped | not available |
Whether to clip this edge to the tail and head node regions.