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 plugandplay "server" for novice developers and for advanced developers with standard graphdrawing needs. The BLAG is also the easiest way to enhance legacy applications with graphdrawing 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
 The topology of the graph to be drawn is loaded from the input file.
 The layout directives and constraints to be applied are loaded from the configuration file.
 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).
 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
From the release 3.0 of GDToolkit you must specify a version in the configuration file format for BLAG. The current version is 1.1. If you want to use the syntax of the configuration file format for GDT 2.1 please, specify version 1.0. What follows is the configuration file format of BLAG.
"<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 anglesweep } "</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 preconditions.
Code 
Description 
Time 
Preconditions 
0 
QuickOrthogonal
Based on a visibility representation of the given embedding, with a bendminimization heuristic. A mincostflow compaction technique is also applied to minimize edge lengths. 
O(n) 
4degree AND biconnected. 
1 
OptimalOrthogonal
Based on a bendminimization mincostflow technique. A mincostflow compaction technique is also applied to minimize edge lengths. Returns the orthogonal layout with the minimum number of bends for the given embedding. 
O(n^{2} log n) 
No preconditions. 
2 
SlowOrthogonal
Based on a bendminimization mincostflow technique applied on embeddings generated with a branchandbound technique by means of an SPQRtree. A mincostflow compaction technique is also applied to minimize edge lengths. Returns the orthogonal layout with the minimum number of bends over all the planar embeddings. 
O(exp(n)) 
Biconnected AND planar. 
3 
OptimalUpward
Based on a bendminimization mincostflow technique. A mincostflow compaction technique is also applied to minimize edge lengths. Returns the quasiupward layout with the minimum number of bends for the given embedding. 
O(n^{2} log n) 
Directed. 
4 
SlowUpward
Based on a bendminimization mincostflow technique applied on embeddings generated with a branchandbound technique by means of an SPQRtree. A mincostflow compaction technique is also applied to minimize edge lengths. Returns the quasiupward layout with the minimum number of bends over all the planar embeddings. 
O(exp(n)) 
Biconnected AND directed AND bimodal AND planar. 
5 
OptimalUpwardVisbility
Oriented visibility representation of a layout generated by the OptimalUpward algorithm. 
O(n^{2} log n) 
Directed. 
6 
SlowUpwardVisibility
Oriented visibility representation of a layout generated by the SlowUpward algorithm. 
O(exp(n)) 
Biconnected AND directed AND bimodal AND planar. 
7 
Polyline
Based on the visibility algorithm. Returns a polyline layout with at most two bends per edge. 
O(n) 
Biconnected. 
8 
Visibility
Based on stnumbering. A mincostflow compaction technique is also applied to minimize edge lengths. Returns an unoriented visibility representation. 
O(n) 
Biconnected. 
9 
TreeCenterSons
Returns a hierarchical representation in which each node is above and horizontally centered with respect to its sons. 
O(n) 
Acyclic (regardless edge directions). 
10 
TreeCenterSubtree
Returns a hierarchical representation in which each node is above and horizontally centered with respect to its whole subtree. 
O(n) 
Acyclic (regardless edge directions).

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
