Graph Drawing Toolkit

• Introduction
• Input File Format
• Configuration File Format
• Layout algorithm specs
• Output file format
  

Introduction

BLAG is a batch application which reads an input file describing the topology of the graph to be drawn, applies the algorithms and the constraints specified in a configuration file, and generates an output files defining a layout if the input graph (i.e. providing coordinates for its nodes and bends).

BLAG is provided as a plug-and-play "server" for novice developers and for advanced developers with standard graph-drawing needs. The BLAG is also the easiest way to enhance legacy applications with graph-drawing capabilities. Finally, application developers can read the source code of BLAG as an example of how easy and effective the GDT Graph API is.

Usage: blag input_file_path configuration_file_path

Operations

1. The topology of the graph to be drawn is loaded from the input file.
2. The layout directives and constraints to be applied are loaded from the configuration file.
3. Preconditions are checked against the layout algorithm specified in the configuration file (an error message is generated when any of the preconditions is not satisfied).
   
4. Three output files are generated, with the same name of the input one, and with three different extension: a .gdt file (in the standard GDT format for drawable graphs), a .exp file (in a simplified export format, specifically designed to interface external applications), and a .fig file (the own file format of the application "xfig" under Unix).

Input File Format

What follows is the input file format of BLAG.

file   =
"<UNDISECTION>"
"<NODELIST>"
{ "<NODE>"   nodeId   [ adjacentEdgesList ]   "</NODE>" }
"</NODELIST>"
"</UNDISECTION>"

adjacentEdgesList   =

{ "<EDGE>"   edgeId   edgeDirection }

nodeId   =   integer number
edgeId   =   integer number
edgeDirection   =   "--"   |   "<-"   |   "->"

Note: the sequence of the edges within each adjacentEdgesList defines the embedding of the input graph. Such embedding is either preserved or potentially changed by the selected layout algorithm according to a specific parameter in the configuration file.

Configuration File Format

"<BOFF VERSION="version"/>"
file   =
"<BEGIN_OPTIONS>"
"<ALGORITHM>"   algorithmCode   "</ALGORITHM>"
["<CHECKING>"   operationalMode   "</CHECKING>"]
["<PLANARIZATION>"   planarizationMode   "</PLANARIZATION>"]
["<COMPACTION>"   compactionMode   "</COMPACTION>"]
["<EXTERNAL_FACE>"   nodeId   edgeId   "</EXTERNAL_FACE>"]
["<TREE_ROOT>"   nodeId   "</TREE_ROOT>"]
[constraintsList]
[nodesDimensionsList]
"<END_OPTIONS>"

Note: the <EXTERNAL_FACE> tag fixes as external the face visibile on the right while traversing the specified edge starting from the specified node (which has to be one of the edge extremals).

constraintsList   =  

"<CONSTRAINTS>"
[bendConstraintsList]
[crossConstraintsList]
[nodeFaceConstraintsList]
[orderedNodeFaceConstraintsList]
"</CONSTRAINTS>"

bendConstraintsList   =  

"<BENDS>"
[anyBendConstraintsList]
[noneBendConstraintsList]
[directionBendConstraintsList]
"</BENDS>"

anyBendConstraintsList   =  

"<ANY>"   edgesList   "</ANY>"

noneBendConstraintsList   =  

"<NONE>"   edgesList   "</NONE>"

directionBendConstraintsList   =  

"<DIRECTION>" { "<DIR>"   nodeId   edgeId } "</DIRECTION>"

crossConstraintsList   =  

"<UNCROSSABLE_EDGES>"   edgesList   "</UNCROSSABLE_EDGES>"

nodeFaceConstraintsList   =  

"<SAME_FACE_NODES>" { "<NODE>"   nodeId   nodeSetId } "</SAME_FACE_NODES>"

Note: the <SAME_FACE_NODES> constraint tag forces all the nodes with the same nodeSetId to belong to the same face. Please refer to the constraints management section for a complete description of all the available constraints.

orderedNodeFaceConstraintsList   =  

"<SAME_FACE_ORDERED_NODES>" { "<SAME_FACE>"   nodeList   "<SAME_FACE>" } "</SAME_FACE_ORDERED_NODES>"

nodeDimensionsConstraintsList   =  

"<NODE_DIM NODE_ID=nodeId WIDTH=width HEIGHT=height />"

anglesConstraintsList   =  

"<ANGLES>" { "<ANGLE_SWEEP>"   nodeId   edgeId   angle-sweep } "</ANGLES>"

version   =   a version number

edgesList   =   { "<EDGE>"   edgeId }

edgeId   =   integer number

nodeId   =   integer number

nodeSetId   =   integer number

width   =   integer number

height   =   integer number

angle_sweep   =   integer number taken in the set {0, 90, 180, 270, 360}

algorithmCode   =   "0" .. "10"

Note: some layout directives and constraints only apply on a subset of the available algorithms, and are ignored when the selected one does not support them. Please refer to the specific section for a complete description of all the algorithms exposed by BLAG (along with their preconditions and time complexities).

operationalMode   =   testOnly | testAndLayout
testOnly   =   "t"
testAndLayout   =   "l"

planarizationMode   =   preserveEmbedding | doNotPreserveEmbedding
compactionMode   =   "0" .. "7"

doNotPreserveEmbedding   =   "0"
preserveEmbedding   =   "1"

Layout algorithm specs

What follows is a list of layout algorithms available using BLAG. For each algorithm we give: code, short description, time complexity notes, and pre-conditions.

Output File Format

What follows is the output file format of BLAG (standard extension .exp).

file   =
"<NODELIST>"
{ "<NODE>"   id   position   width   heigth   "</NODE>" }
"</NODELIST>" "<EDGELIST>"
{ "<EDGE>"   id   direction   [bendsList]   "</EDGE>" }
"</EDGELIST>"

direction   =   "--"   |   "<-"   |   "->"

bendsList   =   { "<BEND>"   position   }
position   =   "("   xCoord   ","   yCoord   ")"

id   =   integerNumber
width   =   realNumber
heigth   =   realNumber
xCoord   =   realNumber
yCoord   =   realNumber