\chapter{The AGD Server}

\section{Introduction}

The AGD server ({\em agd\_server\/}) is an executable program 
that allows to run all AGD algorithms from the command line.
The program reads the input graph in GML or GraphWin format 
from a given file and loads the corresponding options from a
second file. It runs the selected algorithm and writes the
result back to the same file. If an error occurs (e.g., if a
precondition is violated) a diagnostic message is written to 
this file. 

The program recognizes a special {\tt list} command
that prints a list of all available algorithms together 
with their default options. This command  can be used
to create an initial option file. The option file format 
is based on the GML format. 
The output of the {\tt list} command for the current {\em agd\_server\/}
version (1.4) is listed at the end of this section. 


The main reason for developing the AGD server program was to
create a file or socket interface that allows applications
implemented on different platforms (e.g., not based on  LEDA or
not written in \CC) to use the algorithms of the AGD library. 
Such a {\em client\/} application now can easily contact the
AGD {\em server\/} by writing the graph to be drawn to a temporary
file (either in GraphWin or GML format) running the {\tt agd\_server}
command with appropriate options on this file and reading the
result from the same file. The application may ask for the list
of all available AGD algorithms (e.g. for building a corresponding
pull-down menu) by using the {\tt list} command of the server.

\section{The GraphWin Client}
This client for {\tt agd\_server} is integrad in LEDA's graph editor 
GraphWin. It looks for {\tt agd\_server} in the user's command search 
path and, if successful, includes a sub-menu containing the names of all 
available AGD algorithms into the main {\em layout\/} menu. Now,
these algorithms can easily be applied to the current graph
by clicking on the corresponding menu item. This kind of interface
is very flexible. In particular, if a new AGD version is installed 
on the system the client automatically updates the list of algorithms 
and the corresponding menu of the editor.

To install  {\tt agd\_server} for GraphWin simply copy the
{\tt agd\_server} to a directory in your command search path or
set the environment variable AGD\_SERVER to the complete path 
name of the server.


\section{The Command Line}
The command line
\begin{quote}
\tt agd\_server list [\it optfile\/\tt]
\end{quote}

         writes the list of available AGD algorithms and their
         default options in GML format to file {\it optfile\/} or the
     standard output stream (if {\it optfile\/} is missing).

The command line to draw a graph using the {\tt agd\_server} has the following 
form
\begin{quote}
\tt agd\_server {\it alg gfile optfile iform oform}
\end{quote}
It
         reads a graph in format {\it iform\/} from file {\it gfile\/}, applies
         algorithm {\it alg\/} to it using the options from file {\it optfile\/},
         and writes the result in format {\it oform\/} back to {\it gfile\/}.
         There are two possible file formats for {\it iform\/} and {\it oform\/}:
         {\tt gw} for the GraphWin file format and {\tt gml} for the GML format.
         A default option file can be created by calling {\tt agd\_server
         list \it optfile\/} and edited as needed.

Example: Let "graph.gw" contain the graph we want to draw using
the {\tt agd\_server} in GraphWin file format. Suppose we want to use
the Sugiyama algorithm with the options in the standard options
file optfile. Then the corresponding command line looks as
follows.
\begin{verbatim} 
        agd_server Sugiyama graph.gw optfile gw gw
\end{verbatim}
 
If everything worked correctly the file "graph.gw" contains the
resulting layout of our input graph. If an error occured a
diagnostic message is written to the file "graph.gw" .
                                                      

\section{Algorithms}
Currently the following algorithms are available in the
AGD Server and can be used as parameter "alg".
 
\begin{itemize}
\item "de Fraysseix et al."
\item Schnyder
\item Convex
\item ConvexDraw
\item PlanarStraight
\item PlanarDraw
\item Mixed-Model
\item PureOrthogonal
\item QuasiOrthogonalLayout
\item OrthogonalLayout
\item TreeLayout
\item Sugiyama
\item Planarization
\item "Spring Embedder"
\item Tutte
\item  "Visibility Representation"
\end{itemize}
 
Example: To use the algorithm "de Fraysseix et al." on the graph graph.gml
in GML Format with the options file "optfile" write:  
\begin{verbatim}
       agd_server "de Fraysseix et al." graph.gml optfile gml gml
\end{verbatim}  
                     
\section{Option File Format}

The command 
\begin{verbatim}
       agd_server list optfile
\end{verbatim} g
enerates an initial 
option file {\it optfile\/}. The contents of this file (for the current version 
of {\tt agd\_server}) is listed below.
A detailed description of the various options is given in the
section of each algorithm. 
You can, of course, change the options using an ordinary text editor. 
Client programs, as for instance the GraphWin client, can offer more
convenient interactive dialog boxes for editing the options file.

\begin{verbatim}
Creator "AGD_SERVER"
Version 1.4
AGD_function_list [
        function "de Fraysseix et al."
        function "Schnyder"
        function "Convex"
        function "ConvexDraw"
        function "PlanarStraight"
        function "PlanarDraw"
        function "Mixed-Model"
        function "PureOrthogonal"
        function "QuasiOrthogonalLayout"
        function "OrthogonalLayout"
        function "TreeLayout"
        function "Sugiyama"
        function "Planarization"
        function "Spring Embedder"
        function "Tutte"
        function "Visibility Representation"
]
AGD_option_list [
        function "de Fraysseix et al." [
                work_infos "false"
                infos [
                        name: "de Fraysseix, Pach, Pollack"
                        author: "H. de Fraysseix, J. Pach, R. Pollack"
                        Implementation: "C. Gutwenger"
                        date: "february 1997"
                        version: "1.0"
                ]
        ]
        function "Schnyder" [
                work_infos "false"
                infos [
                        name: "Schnyder"
                        author: "W. Schnyder"
                        Implementation: "D. Ambras, D. Alberts"
                        date: "February 1997"
                        version: ""
                ]
        ]
        function "Convex" [
                size_opt "true"
                base_ratio 0.330000
                work_infos "false"
                infos [
                        name: "Convex (Kant)"
                        author: "G. Kant"
                        Implementation: "C. Gutwenger"
                        date: "March 1997"
                        version: "2.0"
                ]
        ]
        function "ConvexDraw" [
                size_opt "true"
                tside_opt "false"
                base_ratio 0.330000
                work_infos "false"
                infos [
                        name: "ConvexDraw (Chrobak/Kant)"
                        author: "M. Chrobak, G. Kant"
                        Implementation: "C. Gutwenger"
                        date: "March 1997"
                        version: "2.0"
                ]
        ]
        function "PlanarStraight" [
                size_opt "true"
                max_outer "true"
                base_ratio 0.330000
                work_infos "false"
                infos [
                        name: "PlanarStraight (Gutwenger/Mutzel)"
                        author: "C. Gutwenger, P. Mutzel"
                        Implementation: "C. Gutwenger"
                        date: "March 1997"
                        version: "2.0"
                ]
        ]
        function "PlanarDraw" [
                size_opt "true"
                side_opt "false"
                max_outer "true"
                base_ratio 0.330000
                work_infos "false"
                infos [
                        name: "PlanarDraw (Gutwenger/Mutzel)"
                        author: "C. Gutwenger, P. Mutzel"
                        Implementation: "C. Gutwenger"
                        date: "March 1997"
                        version: "1.0"
                ]
        ]
        function "Mixed-Model" [
                base_ratio 0.330000
                work_infos "false"
                infos [
                        name: "Mixed-Model (Gutwenger/Mutzel)"
                        author: "Carsten Gutwenger, Petra Mutzel"
                        Implementation: "Carsten Gutwenger"
                        date: "june 1998"
                        version: "2.5"
                ]
        ]
        function "PureOrthogonal" [
                check "true"
                work_infos "false"
                infos [
                        name: "Pure Orthogonal Drawing Algorithm (Tamassia)"
                        author: "R.~Tamassia"
                        Implementation: "G.~W.~Klau"
                        date: "XI 1998"
                        version: "2.0"
                ]
        ]
        function "QuasiOrthogonalLayout" [
                check "true"
                work_infos "false"
                infos [
                        name: "Quasi-Orthogonal Drawing Algorithm"
                        author: "G.~W.~Klau, P.~Mutzel"
                        Implementation: "G.~W.~Klau"
                        date: "XI 1998"
                        version: "0.5"
                ]
        ]
        function "OrthogonalLayout" [
                check "true"
                work_infos "false"
                infos [
                        name: "Orthogonal Drawing Algorithm"
                        author: "G.~W.~Klau, P.~Mutzel"
                        Implementation: "G.~W.~Klau"
                        date: "XI 1998"
                        version: "0.2"
                ]
        ]
        function "TreeLayout" [
                sib_separation 4.00000
                subtree_separation 4.00000
                level_separation 4.00000
                left_margin 0.00000
                upper_margin 0.00000
                work_infos "false"
                infos [
                        name: "Layout algorithm for general trees"
                        author: "E. Reingold, J. Tilford, J. Q. Walker II"
                        Implementation: "S. Leipert"
                        date: "May 1997"
                        version: "0.1"
                ]
        ]
        function "Sugiyama" [
                ranking [
                        ranking_wahl 0
                        ranking_lst [
                                lst "Hierarchical"
                                lst "DFS"
                        ]
                ]
                heuristic [
                        heuristic_wahl 0
                        heuristic_lst [
                                lst "Split"
                                lst "Barycenter"
                                lst "Median"
                                lst "Greedy Insert"
                                lst "Greedy Switch"
                        ]
                ]
                fixed_level_distance "false"
                node_distance 3.00000
                level_distance 3.00000
                work_infos "false"
                infos [
                        name: "Sugiyama"
                        author: "K. Sugiyama, S. Tagawa, M. Toda"
                        Implementation: "C. Gutwenger, M. Kr�ger"
                        date: "March 1998"
                        version: "2.0"
                ]
        ]
        function "Planarization" [
                layouter [
                        layouter_wahl 8
                        layouter_lst [
                                lst "de Fraysseix et al."
                                lst "Schnyder"
                                lst "Convex"
                                lst "ConvexDraw"
                                lst "PlanarStraight"
                                lst "PlanarDraw"
                                lst "Mixed-Model"
                                lst "PureOrthogonal"
                                lst "QuasiOrthogonalLayout"
                                lst "OrthogonalLayout"
                        ]
                ]
                work_infos "false"
                infos [
                        name: "Planarization"
                        author: ""
                        Implementation: "C. Gutwenger"
                        date: "decembre 1997"
                        version: "1.0"
                ]
        ]
        function "Spring Embedder" [
                noise "true"
                iterations 400
                work_infos "false"
                infos [
                        name: "Spring Embedder (Fruchterman/Reingold)"
                        author: "T. Fruchterman, E. Reingold"
                        Implementation: "S. N�her, D. Alberts"
                        date: "April 1997"
                        version: ""
                ]
        ]
        function "Tutte" [
                work_infos "false"
                infos [
                        name: "Tutte"
                        author: "W. T. Tutte"
                        Implementation: "D. Alberts"
                        date: "April 1997"
                        version: ""
                ]
        ]
        function "Visibility Representation" [
                work_infos "false"
                infos [
                        name: "Weak Visibility Representation"
                        author: "P. Rosenstiehl, R. E. Tarjan"
                        Implementation: "D. Alberts"
                        date: "1996/1997"
                        version: ""
                ]
        ]
]

\end{verbatim}



\section{The LEDA graph input/output format}\label{leda-format}

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

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

\subsection{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 {\tt |\{} and {\tt \}|}. If the graph
is not
parameterized, then the string between these parantheses is empty,
so
that all the n lines contain the string {\tt |\{\}|}.

\subsection{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:
\begin{description}
\item{(a)} the number of the source node
\item{(b)} the number of the target node
\item{(c)} the number of the reversal edge or 0, if no such edge is
set
\item{(d)} the information associated with the edge (cf. nodes
section)
\end{description}

{\bf Note}:
For the data type {\tt 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.


\section{ The GraphWin (GW) File Format}

The $gw$-format is the external graph format of {\em 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:
\begin{enumerate}
\item global parameters  
\item node attributes
\item edge attributes
\end{enumerate}


\subsection{Global Parameters}

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

\begin{enumerate}
\item version line\\
The version line specifies the version of of the gw-format. It
consists
of the string {\tt GraphWin} followed by a floating-point number
($1.4$ for the current version of GraphWin).

\item 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).

\item {node label font}\\
$type$ $size$\\
This line defines the font used for node labels. The $type$
value of of type $int$. Possible values (see {\tt gw\_font\_type})
are\\
0 ({\tt roman\_font})\\
1 ({\tt bold\_font})\\
2 ({\tt italic\_font})\\
3 ({\tt fixed\_font}).
The size value is of type $int$ and defines the size of the font
in points.

\item {edge label font}\\
$type$ $size$
as above, but defines the font used for edge labels.

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

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

\item {multi-edge distance}\\
$dist$\\
This line contains a floating-point parameter $dist$ that
defines the distance used to draw parallel edges.

\end{enumerate}

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

\begin{verbatim}
# version
GraphWin 1.4
# 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
\end{verbatim}




\subsection{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 (see section~\ref{leda-format}).

\begin{description}

\item{x-coordinate}\\
an attribute of type $double$ defining the x-coordinate of the
center 
of the node.

\item{y-coordinate}\\
an attribute of type $double$ defining the y-coordinate of the
center 
of the node.

\item{shape}\\
an attribute of type {\tt int} 
defining the shape of the node.
Possible values are  (see {\tt gw\_node\_shape} of GraphWin)\\
0 ({\tt circle\_node})\\
1 ({\tt ellipse\_node})\\
2 ({\tt square\_node})\\
3 ({\tt rectangle\_node}.


\item{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 {\tt 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$).


\item{border width}\\
an attribute of type $double$ defining the width of the  border line
of the node. 

\item{radius1}\\
an attribute of type $double$ defining the horizontal radius of the
node

\item{radius2}\\
an attribute of type $double$ defining the vertical radius of the
node

\item{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.

\item{label type}\\
an attribute of type int specifying the label type.
Possible values (see {\tt gw\_label\_type} of GraphWin) are\\
0 ({\tt no\_label})\\ 
1 ({\tt user\_label})\\
2 ({\tt data\_label})\\
3 ({\tt index\_label}). 

\item{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.

\item{label position}\\
an attribute of type $int$ defining the label position.
Possible values (see {gw\_position} of GraphWin) are\\ 
0 ({\tt central\_pos})\\
1 ({\tt northwest\_pos})\\
2 ({\tt north\_pos})\\
3 ({\tt northeast\_pos})\\
4 ({\tt east\_pos})\\
5 ({\tt southeast\_pos})\\
6 ({\tt south\_pos})\\
7 ({\tt southwest\_pos})\\
8 ({\tt west\_pos}).


\item{user label}\\
an attribute of type {\tt string} defining the user 
label of the node.
 
\end{description}

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.
\begin{verbatim}
# 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
\end{verbatim}





\subsection{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 (see section~\ref{leda-format}).

\begin{description}

\item{width}\\
an attribute of type {\tt double} defining the width of the edge.

\item{color}\\
an attribute of type {\tt color} defining the color of the edge.

\item{shape}\\
an attribute of type $int$ defining the shape of the edge. 
Possible values (see {\tt gw\_edge\_shape} of GraphWin) are\\
0 ({\tt poly\_edge})\\
1 ({\tt circle\_edge})\\
2 ({\tt bezier\_edge})\\
3 ({\tt spline\_edge}).


\item{style}\\
an attribute of type $int$ defining the line style of the edge.
Possible values (see the LEDA {\tt line\_style} type) are\\
o ({\tt solid})\\
1 ({\tt dashed})\\
2 ({\tt dotted})\\
3 ({\tt dashed\_dotted}).

\item{direction}\\
an attribute of type $int$ defining whether the edge is 
drawn as a directed or an undirected edge. 
Possible values (see {\tt gw\_edge\_dir} of GraphWin) are\\
0 ({\tt undirected\_edge})\\
1 ({\tt directed\_edge})\\
2 ({\tt redirected\_edge})\\
3 ({\tt bidirected\_edge}).



\item{label type}\\
an attribute of type $int$ defining the label type of the edge.
Possible values (see {\tt gw\_label\_type}  of GraphWin) are\\
0 ({\tt no\_label})\\
1 ({\tt user\_label})\\
2 ({\tt data\_label})\\
3 ({\tt index\_label}).


\item{label color}\\
an attribute of type $int$ defining the color of the edge label.
See the LEDA $color$ type for possible values.


\item{label position}\\
an attribute of type $int$ defining the position of the label. 
Possible values (see {gw\_position} of GraphWin) are\\ 
0 ({\tt central\_pos})\\
4 ({\tt east\_pos})\\
8 ({\tt west\_pos $blue$ }).

\item{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\ldots 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). 


\item{user label}\\
an attribute of type {\tt string} defining the user 
label of the edge.

\end{description}

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)$.
\begin{verbatim}
# 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
\end{verbatim}

\section{A complete example}
\begin{verbatim}
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.40000
# 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) 
\end{verbatim}
