******************************************************************
*                                                                *
*         The Graph File Formats used by AGD Server              *
*         =========================================              *
*                                                                *
******************************************************************



1. The GraphWin File Format:
----------------------------

a) The LEDA graph input/output format

The following passage describes the format of the output produced 
by the function graph::write(ostream& out). The output consists of 
several lines which are separated by endl. Comment-lines have a 
# character in the first column and are ignored. The output can be 
partitioned in three sections:

i) Header Section
The first line always contains the string LEDA.GRAPH. If the graph
type is not parameterized, i.e. graph or ugraph, the following two
lines both contain the string void. In case the graph is 
parameterized ,i.e., GRAPH or UGRAPH, these lines contain a 
description of the node type and the edge type, which is obtained 
by calling the macro  LEDA_TYPE_NAME.

ii) Nodes Section
The first line contains n, the number of nodes in the graph. The 
nodes are ordered and numbered according to their position in the 
node list of the graph. Each of the following n lines contains the 
information which is associated with the respective node of the 
graph. When the information of a node (or an edge) is sent to an 
output stream, it is always enclosed by the strings  |{ and  }|. 
If the graph is not parameterized, then the string between these 
parantheses is empty, so that all the n lines contain the string  
|{}|.

iii) Edges Section
The first line contains m, the number of edges in the graph. The 
edges of the graph are ordered by two criteria: first according to 
the number of their source node and second according to their 
position in the adjacency list of the source node. Each of the next 
m lines contains the description of an edge which consists of four 
space-separated parts:
* the number of the source node
* the number of the target node
* the number of the reversal edge or 0, if no such edge is set
* the information associated with the edge (cf. nodes section)

Note:
For the data type  planar_map the order of the edges is important,
because the ordering of the edges in the adjacency list of a node
corresponds to the counter-clockwise ordering of these edges 
around the node in the planar embedding. And the information about 
reversal edges is also vital for this data type.


b) The GraphWin (GW) File Format

The gw-format is the external graph format of GraphWin.
It extends LEDA's graph format described in the previous section 
by additional parameters and attributes for describing graph 
drawings. Note that the gw-format was not defined to be a readable 
or easy to extend file format (in contrast to the GML format
that is also supported by GraphWin).

Each gw file starts with a LEDA graph followed by a 
(possibly empty) layout section. An empty layout section 
indicates that no drawing of the graph is known, e.g. in the input 
file of a layout algorithm. If a layout section is given, it 
consists of three parts:

1) global parameters  
2) node attributes
3) edge attributes


i) Global Parameters

The global parameter section consists of 7 lines (with an 
arbitrary number of inter-mixed comment-lines).

* version line
The version line specifies the version of of the gw-format. It 
consists of the string  GraphWin followed by a floating-point 
number (1.32 for the current version of GraphWin).

* window parameters
scaling wxmin wymin wxmax wymax
This line consists of 5 floating-point numbers specifiying the
scaling, minimal/maximal x- and y-coordinates of the window
(see the window class of LEDA).

* node label font
type size
This line defines the font used for node labels. The type
value of of type int. Possible values (see  gw_font_type}) are
0 ( roman_font})
1 ( bold_font})
2 ( italic_font})
3 ( fixed_font}).
The size value is of type int and defines the size of the font
in points.

* edge label font
type size
as above, but defines the font used for edge labels.

* node index format
format
This line contains a printf-like format string used
for constructing the index label of nodes (e.g.  %d}).

* edge index format
format
This line contains a printf-like format string used
for constructing the index label of edges (e.g.  %d}).

* multi-edge distance
dist
This line contains a floating-point parameter dist that
defines the distance used to draw parallel edges.


We close the description of the global parameter section
with an example.

# version
GraphWin 1.32
# window parameters
1.0 -10.0 -5.0 499.0 517.0
# node font
0 12
# edge font
0 12
# node index string
%d
# edge index string
%d
# multi-edge distance
4.0


ii) Node Attributes

The node attribute section contains for each node of the graph
a line consisting of the following attributes (separated by 
blanks). More precisely, the i-th line in this section defines 
the attributes of the i-th node of the graph.

* x-coordinate
an attribute of type double defining the x-coordinate of the 
center of the node.

* y-coordinate
an attribute of type double defining the y-coordinate of the 
center of the node.

* shape
an attribute of type  int
defining the shape of the node.
Possible values are  (see  gw_node_shape of GraphWin)
0 (circle_node)
1 (ellipse_node)
2 (square_node)
3 (rectangle_node)

* border color
an attribute of type int defining the color used to draw the 
boundary line of the node. Possible values are (see the LEDA  
color type)
 -1 (invisible)
 0 (black) 
 1 (white) 
 2 (red) 
 3 (green) 
 4 (blue) 
 5 (yellow) 
 6 (violet) 
 7 (orange)
 8 (cyan) 
 9 (brown) 
 10 (pink) 
 11 (green2) 
 12 (blue2) 
 13 (grey1) 
 14 (grey2) 
 15 (grey3)
 16 (ivory).


* border width
an attribute of type double defining the width of the  border line 
of the node. 

* radius1
an attribute of type double defining the horizontal radius of the 
node

* radius2
an attribute of type double defining the vertical radius of the 
node

* color
an attribute of type int defining the color used 
to fill the interior of the node. See the LEDA color type for
possible values.

* label type
an attribute of type int specifying the label type.
Possible values (see  gw_label_type of GraphWin) are
0 (no_label) 
1 (user_label)
2 (data_label)
3 (index_label). 

* label color
an attribute of type int defining the color used to draw the label 
of the node. See the LEDA color type for possible values.

* label position
an attribute of type int defining the label position.
Possible values (see gw_position of GraphWin) are 
0 ( central_pos)
1 ( northwest_pos)
2 ( north_pos)
3 ( northeast_pos)
4 ( east_pos)
5 ( southeast_pos)
6 ( south_pos)
7 ( southwest_pos)
8 ( west_pos).

* user label
an attribute of type  string defining the user 
label of the node.
 

We close this section with an example of a node attribute line
that describes a circle node at position (189,260) with
border color black, border width 0.5, horizontal and
vertical radius 12, interior color ivory, label type
index_label, label position east_pos, and
an empty user label.

# x   y     shape b-clr b-width radius1 radius2   clr l-type l-clr l-pos l-str
189.0 260.0 0     1     0.5     12.0    12.0      16  3      -1    4


iii) Edge Attributes:

The edge attribute section contains for each edge of the graph
a line consisting of the following attributes (separated by 
blanks). More precisely, the i-th line in this section defines the 
attributes of the i-th edge of the graph.

* width
an attribute of type  double defining the width of the edge.

* color
an attribute of type  color defining the color of the edge.

* shape
an attribute of type int defining the shape of the edge. 
Possible values (see  gw_edge_shape of GraphWin) are
0 (poly_edge)
1 (circle_edge)
2 (bezier_edge)
3 (spline_edge).

* style
an attribute of type int defining the line style of the edge.
Possible values (see the LEDA  line_style type) are
o (solid)
1 (dashed)
2 (dotted)
3 (dashed_dotted).

* direction
an attribute of type int defining whether the edge is 
drawn as a directed or an undirected edge. 
Possible values (see  gw_edge_dir of GraphWin) are
0 (undirected_edge)
1 (directed_edge)
2 (redirected_edge)
3 (bidirected_edge).

* label type
an attribute of type int defining the label type of the edge.
Possible values (see  gw_label_type  of GraphWin) are
0 (no_label)
1 (user_label)
2 (data_label)
3 (index_label).

* label color
an attribute of type int defining the color of the edge label.
See the LEDA color type for possible values.

* label position
an attribute of type int defining the position of the label. 
Possible values (see gw_position of GraphWin) are 
3 (central_pos)
4 (east_pos)
5 (west_pos blue ).

* source anchor 
an attribute of type point defining the starting point of the 
edge relative to the position of the source node and the radii 
r1 and r2 of the node. Let (x,y) be the position of the source 
node of the edge and r1 and r2 the corresponding radii. Then 
the source anchor (dx,dy) means that the edge starts at 
(x + dx*r1, y + dy*r2)

* target anchor 
an attribute of type point defining the ending point of the 
edge relative to the position of the target node and the radii 
r1 and r2 of the node. Let (x,y) be the position of the target
node of the edge and r1 and r2 the corresponding radii. Then 
the target anchor (dx,dy) means that the edge ends at 
(x + dx*r1, y + dy*r2)

* polyline
an attribute of type list<point> defining the polyline used to
draw the edge. The list is represented by the number n of elements
followed by n points (x_i,y_i) for i=1,...,n. The first
element of the list is the point where the edge leaves the
interior of the source node, the last element is the point where
the edge enters the interior of the target node. The remaining
elements give the sequence of bends (or control points
in case of a bezier or spline edge). 

* user label
an attribute of type  string defining the user 
label of the edge.


We close this section with an example of an edge attribute line
that describes a blue solid polygon edge of width 0.5 drawn 
directed from source to target, with a black user-defined label 
"my label" at position east_pos, centered source and target 
anchors, and with a bend at position (250,265).

# width clr shape style dir ltype lclr lpos sanch tanch poly lstr
  0.5   4   0     0     1   1     1    4    (0,0) (0,0) 3 (202.0,262.0)
(250.0,265.0) (328.0,274.0)  my label


iv) A complete example:

Here is a complete example of a graph in LEDA GraphWin format:

LEDA.GRAPH
void
void
5
|{}|
|{}|
|{}|
|{}|
|{}|
7
1 2 0 |{}|
1 3 0 |{}|
2 3 0 |{}|
3 4 0 |{}|
3 5 0 |{}|
4 5 0 |{}|
5 1 0 |{}|
# version string
GraphWin 1.320000
# scaling  wxmin  wymin  wxmax  wymax
1.117676 -10 -5.6875 499.8828 517.6133
# node label font and size
0 13.6121
# edge label font and size
0 11.79715
# node index format
%d
# edge index format
%d
# multi-edge distance
4.537367
# 
# node infos
# x y shape bclr bwidth r1 r2 clr ltype lclr lpos lstr
189.4805 260.8828 0 1 0.544484 12.70463 12.70463 16 4 -1 4 
341.5508 276.0898 0 1 0.544484 12.70463 12.70463 16 4 -1 4 
384.4883 175.9023 0 1 0.544484 12.70463 12.70463 16 4 -1 4 
294.1406 114.1797 0 1 0.544484 12.70463 12.70463 16 4 -1 4 
186.7969 114.1797 0 1 0.544484 12.70463 12.70463 16 4 -1 4 
# 
# edge infos
# width clr shape style dir ltype lclr lpos sanch tanch poly lstr
0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (202.122,262.147) (328.9092,274.8257) 
0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (201.1272,255.8074) (372.8415,180.9778) 
0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (346.5554,264.4124) (379.4837,187.5797) 
0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (373.998,168.7357) (304.6309,121.3463) 
0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (372.361,172.116) (198.9242,117.966) 
0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (281.436,114.1797) (199.5015,114.1797) 
0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (187.0292,126.8822) (189.2481,248.1803) 

