Power-Programmierung/CD2.mdf/c/library/dos/diverses/leda/man/basics.tex

Text File | 1991-11-15 | 25.5 KB | 661 lines

{\magtwo 1. Basics}

We start with an example. The following program counts the number of
occurrences of each string in a sequence of strings

\#include $<$LEDA/d\_array.h$>$
\medskip
{\bf declare2}(d\_array,string,int)
\medskip
\cleartabs
\+main()\cr
\+$\{$\ \ &\cr
\+  &d\_array(string,int) $N(0)$;\cr
\smallskip
\+  &string $s$;\cr
\smallskip
\+  &{\bf while} &(cin $>>$ $s$ \&\& $s$ != ``stop'') $N[s]++$;\cr
\smallskip
\+  &{\bf forall\_defined}($s,N$)
            cout $<< s <<$ ``  " $<< N[s] <<$ ``$\backslash$n";\cr
\smallskip
\+\ $\}$\cr
\bigskip

The program can  be compiled using the LEDA library (cf. section 1.9). When
executed it reads a sequence of strings from the standard input
until the string ``stop'' is encountered and then prints the number
of occurrences of each string on the standard output. More examples
of LEDA programs can be found throughout this manual.

The program above uses the data type dictionary array ($d\_array$)
from the library. This is expressed by the include statement (cf.
section 1.8 for more details). The specification of the data type
$d\_array$ can be found in section~4.4. We use it also as a running
example to discuss the principles underlying LEDA in sections 1.1
to 1.6.


\bigskip
{\magonebf 1.1 Specifications}

In general the specification of a LEDA data type consists of five parts:
a definition of the set of objects comprising the (parameterized) abstract
data type, a description of how to derive a concrete data type from a
parameterized data type, a description of how to create an object of the data
type, the definition of the operations available on the objects of the data
type, and finally, informations about the implementation. The five parts
appear under the headers definition, type declaration, creation, operations,
and implementation respectively.



\bigskip
$\bullet$ {\bf Definition}
\smallskip
This part of the specification defines the objects (also called instances or
elements) comprising the data type using standard mathematical concepts and
notation.

{\bf Example}, the generic data type dictionary array:

An object $a$ of type $d\_array(I,E)$ is an injective function from the
data type $I$ to the set of variables of data type $E$. The types $I$ and
$E$ are called the index and the element type respectively, $a$ is called
a dictionary array from $I$ to $E$.


Note that the types $I$ and $E$ are parameters in the definition above.
A concrete dictionary array type is declared by a type declaration
which we discuss next.


\bigskip
$\bullet$ {\bf Type Declaration}
\smallskip
This part gives the syntax for deriving specific data types from
parameterized or generic data types, i.e., it shows how to set the
formal type parameters of a generic data type to concrete data types.
For a generic data type XYZ with $k$ type parameters the statement

{\bf declare}$k$(XYZ,$t_1,\dots,t_k$)

introduces a new data type with name ``XYZ($t_1,t_2,...,t_k$)'',
where $t_1,\dots,t_k$ are the names of the actual type parameters.
(Due to a limitation of the implementation language \CC, the number
$k$ of type parameters also appears in the name of the declare-macro.)
For example,

{\bf declare2}($d\_array,string,int$)

introduces a new data type with name ``$d\_array(string,int)$''. An object
of data type $d\_array(string,int)$ is a injective mapping from the set of
all strings to the set of variables of type $int$.


Only simple data types are allowed as actual type parameters in declarations
of parameterized data types. Simple data types are the \CC built in types
$char$ and $int$, all \CC pointer types, the LEDA types $bool$, $real$,
$string$, $vector$, and $matrix$ (cf. section~2), all basic two-dimensional
objects from section~6.1 ($point$, $segment$, $line$, $polygon$, $circle$),
and all item types (cf. section~1.5). In order to realize generic data types
with more complicated subtypes (such as dictionaries, lists, graphs, \dots)
pointers to these types must be used.


\bigskip
$\bullet$ {\bf Creation}
\smallskip
A variable of a (previously declared) data type is introduced by a \CC
variable declaration. For all LEDA data types variables are initialized
at the time of declaration. In many cases the user has to provide arguments
used for the initialization of the variable.  In general a declaration

XYZ($t_1,\dots,t_k$)\ \ \ $y(x_1,\dots,x_\ell)$;

introduces a variable $y$ of the data type with name ``XYZ($t_1,\dots,t_k$)''
and uses the arguments $x_1,\dots,x_\ell$ to initialize it. For example,

$d\_array(string,int)$  $A(0)$

introduces $A$ as a dictionary array from strings to integers, and
initializes $A$ as follows: an injective function $a$ from $string$
to the set of unused variables of type $int$ is constructed, and is
assigned to $A$. Moreover, all variables in the range of $a$ are
initialized to 0.
The reader may wonder how LEDA handles an array of infinite size. The
solution is , of course, that only that part of $A$ is explicitly stored
which has been accessed already.

For most data types, in particular for the simple types, the assignment
operator is available for variables of that type. However, assignment is
in general not a constant time operation, e.g., if $s_1$ and $s_2$ are
variables of type $string$ then the assignment $s_1 = s_2$ takes time
proportional to the length of the value of $s_2$.

{\bf Remark}: For most of the complex data types of LEDA, e.g., dictionaries,
lists, and priority queues, it is convenient to interpret a variable name
as the name for an object of the data type which evolves over time by means
of the operations applied to it. This is appropriate, whenever the operations
on a data type only ``modify'' the values of variables, e.g., it is more
natural to say an operation on a dictionary $D$ modifies $D$ than to say that
it takes the old value of $D$, constructs a new dictionary out of it, and
assigns the new value to $D$. Of course, both interpretations are equivalent.
From this more object-oriented point of view, a variable declaration, e.g.,
$dictionary(string,int)$  $D$, is creating a new dictionary object with name
$D$ rather than introducing a new variable of type $dictionary(string,int)$;
hence the name ``creation'' for this part of a specification.



\bigskip
$\bullet$ {\bf Operations}
\smallskip
In this section the operations of the data types are described. For each
operation the description consists of two parts

\beginitem
\item {a)}
{The interface of the operation is defined using the \CC function declaration
syntax. In this syntax the result type of the operation ($void$ if there is
no result) is followed by the operation name and an argument list specifying
the type of each argument. For example,}
\item{}
{$list\_item$ $L$.insert ($E\ x,\ list\_item\ it,\ rel\_pos\ p=after$)\nl
defines the interface of the insert operation on a list $L$ of elements of type
$E$ .(cf. section~3.7). Insert takes as arguments an element $x$ of type $E$,
a $list\_item$ $it$ and an optional relative position argument $p$. It returns
a $list\_item$ as result.  }
\item{}
{$E\&$  $A[I\ x]$\nl
defines the interface of the access operation on a dictionary array $A$. It
takes an element of $I$ as an argument and returns a variable of type $E$.
}

\bigskip
\item {b)}
{The effect of the operation is defined.  Often the arguments have to
fulfill certain preconditions. If such a condition is violated the effect
of the operation is not defined. Some, but not all, of these cases result
in error messages and abnormal termination of the program (see also
section~7.5). }
\item{}
{For the insert operation on lists this definition reads:\nl
A new item with contents $x$ is inserted after (if $p=after$) or before
(if $p=before$) item $it$ into $L$. The new item is returned.
({\it precondition}: item $it$ must be in $L$)}
\item{}
{For the access operation on dictionary arrays the definition reads:\nl
returns the variable $A(x)$.
}
\enditem

\bigskip
$\bullet$ {\bf  Implementation}
\smallskip
The implementation section lists the data structures used to implement
the data type and gives the time bounds for the operations and the space
requirement. For example,

Dictionary arrays are implemented by red black trees. Access operations $A[x]$
take time $O(\log dom(A))$. The space requirement is $O(dom(A))$.


\bigskip
\bigskip
{\magonebf 1.2 Arguments}

\bigskip
$\bullet$ {\bf Optional Arguments}
\smallskip
The trailing arguments in the argument list of an operation may be optional.
If these trailing arguments are missing in a call of an operation the default
argument values given in the specification are used. For
example, if the relative position argument in the list insert operation
is missing it is assumed to have the value $after$, i.e.,
$L$.insert($it,y$) will insert the item $<y>$ after item $it$ into $L$.

\bigskip
$\bullet$ {\bf Argument Passing}
\smallskip
There are two kinds of argument passing in \CC, by value and by reference.
An argument $x$  of type $type$  specified by ``$type\ x$'' in the argument
list of an operation or user defined function will be passed by value, i.e.,
the operation or function is provided with a copy of $x$.
The syntax for specifying an argument passed by reference is ``$type\&\ x$''.
In this case the operation or function works directly on $x$ ( the variable
$x$ is passed not its value).

Passing by reference must always be used if the operation is to change the
value of the argument. It should always be used for passing large objects
such as lists, arrays, graphs and other LEDA data types to functions.
Otherwise a complete copy of the actual argument is made, which takes time
proportional to its size, whereas  passing by reference always takes constant
time.


\bigskip
$\bullet$ {\bf Functions as Arguments}
\smallskip
Some operations take functions as arguments. For instance the bucket sort
operation on lists requires a function which maps the elements of the list into
an interval of integers. We use the \CC syntax to define the type of a function
argument $f$:
$$T\ \ (*f)(T_1, T_2,\dots, T_k)$$ declares $f$ to be a function
taking $k$ arguments of the data types $T_1$, \dots, $T_k$,
respectively, and returning a result of type $T$, i.e,
$f: T_1 \times \dots \times T_k \longrightarrow T$ .


\bigskip
\bigskip
{\magonebf 1.3 Overloading}

Operation and function names may be overloaded, i.e., there can be different
interfaces for the same operation. An example is the translate operations
for points (cf. section~6.1).
\smallskip
$point$  $p$.translate($vector\ v$)\nl
$point$  $p$.translate($real\ \alpha,\ real\ dist$)

It can either be called with a vector as argument or with two arguments
of type $real$ specifying the direction and the distance of the translation.

An important overloaded function is discussed in the next section: Function
$compare$, used to define linear orders for simple data types.

\vfill\eject

\bigskip
\bigskip
{\magonebf 1.4 Linear Orders}

Many data types, such as dictionaries, priority queues, and sorted sequences
require linearly ordered subtypes. Whenever a type $T$ is used in such a
situation, e.g. in $declare2(dictionary,T,\dots)$ the function
$$int\ \ compare(T\&,T\&)$$ must be declared and must define a linear order on
the data type $T$.

A binary relation $rel$ on a set $T$ is called a linear order on $T$ if for
all $x,y,z\in T$:
\smallskip
1) $x$ $rel$ $y$\nl
2) $x$ $rel$ $y$ and $y$ $rel$ $z$ implies $x$ $rel$ $z$\nl
3) $x$ $rel$ $y$ or  $y$ $rel$ $x$\nl
4) $x$ $rel$ $y$ and $y$ $rel$ $x$ implies $x = y$

\medskip
A function $int$ $compare(T\&,T\&)$ is said to define the linear order
$rel$ on $T$ if
$$compare(x,y)\ \ \cases{ < 0, &if $x$ $rel$ $y$  and  $x\ne y$\cr
                       = 0, &if $x = y$\cr
                       > 0, &if $y$ $rel$ $x$  and  $x\ne y$\cr} $$


For each of the simple data types $char$, $int$, $real$, $string$, and $point$
a function $compare$ is predefined and defines the so-called default ordering
on that type. The default ordering is the usual $\le$ - order for $char$,
$int$, and $real$, the lexicographic ordering for $string$, and for $point$
the lexicographic ordering of the cartesian coordinates.
For all other simple types $T$ there is no default ordering, and the user has
to provide a $compare$ function whenever a linear order on $T$ is required.



{\bf Example}: Suppose pairs of real numbers shall be used as keys
in a dictionary with the lexicographic order of their components.
First we declare type $pair$ as the type of pointers to pairs of real
numbers, and then we define the lexicographic order on $pair$ by declaring
an appropriate compare function.


\bigskip
\cleartabs
\+{\bf struct} Pair $\{$\cr
\+\quad $real\ \ x$;\cr
\+\quad $real\ \ y$;\cr
\+$\}$;\cr
\+\cr
\+{\bf typedef} Pair$*$ \ $pair$;\cr

\vfill\eject

\+$int$\  \ \ compare($pair\&\ p,\ pair\&\ q$)\cr
\+$\{$\ \ &{\bf if} ($p\rightarrow x < q\rightarrow x$) {\bf return } -&1;\cr
\+        &{\bf if} ($p\rightarrow x > q\rightarrow x$) {\bf return }  &1;\cr
\+        &{\bf if} ($p\rightarrow y < q\rightarrow y$) {\bf return } -&1;\cr
\+        &{\bf if} ($p\rightarrow y > q\rightarrow y$) {\bf return }  &1;\cr
\+        &{\bf return} 0;\cr
\+$\ \}$\cr

{\bf declare2}($dictionary,\ pair,\ \dots\ $);


\bigskip
Sometimes, a user may need additional linear orders on a simple data type
$T$ which are different from the order defined by $compare$, e.g., he might
want to order points in the plane by the lexicographic ordering of their
cartesian coordinates and by their polar coordinates. In this example, the
former ordering is the default ordering for points. The user can introduce
an alternative ordering on the data type $point$ (cf. section 6.1) by defining
an appropriate comparing function $int$ $cmp(point\&,point\&)$ and then
declaring the type $POINT(cmp)$ with ``declare($POINT,cmp$)''. $POINT$  is a
parameterized data type (cf.  section 1.1) with one parameter which must be
the name of a comparing function. All data types $POINT(cmp)$ derived from
$POINT$ are equivalent to the data type $point$, with the only exception that
if $POINT(cmp)$ is used as an actual parameter in a type declaration, e.g. in
``declare2($dictionary,POINT(cmp),\dots$)'', the resulting type (
$dictionary(POINT(cmp),\dots)$) is based on the linear order defined by $cmp$.
For every simple data type $t$ (except of pointer types) there exists such an
equivalent parameterized type $T$ which can be used to define additional linear
orders on $t$ by declaring types $T(cmp)$ as described for points. The name of
$T$ is always the name of $t$ written with capital letters.


In the example, we first declare a function $pol\_cmp$ and the type
$POINT(pol\_cmp)$.

\+$int$  $pol\_cmp(point\&\ x,\ point\&\ y)$\cr
\+$\{$\ //lexicographic ordering on polar coordinates\cr
\+\ $\}$\cr
\+\cr
\+{\bf declare}($POINT,\ pol\_cmp$)\cr

Now, dictionaries based on either ordering can be defined.

\+{\bf declare2}($dictionary,\ point,\ \dots\ $) \cr
\+{\bf declare2}($dictionary,\ POINT(pol\_cmp),\ \dots\ $)\cr

\vfill\eject

\cleartabs
\+main()\cr
\+$\{$\ &\cr
\+   &dictionary($POINT(pol\_cmp),\ int$) $D_1$; \quad &//polar ordering\cr
\smallskip
\+   &dictionary($point,\ int$) $D_0$;                 &//default ordering\cr
\smallskip
\+\ $\}$\cr

{\bf Remark}: We have chosen to associate a fixed linear order with most of
the simple types (by predefining the function $compare$). This order is used
whenever operations require a linear order on the type, e.g., the operations
on a dictionary. Alternatively, we could have required the user to specify a
linear order each time he uses a simple type in a situation where an ordering
is needed, e.g., a user could define
\smallskip
\cleartabs
\+\quad\quad\quad &declare3(dictionary,point,lexicographic\_ordering,\dots)\cr
\+and\cr
\+                &declare3(dictionary,point,polar\_ordering,\dots)\cr

This alternative would handle the cases where two or more different orderings
are needed more elegantly. However, we have chosen the first alternative
because of the smaller implementation effort.




\bigskip
\bigskip
{\magonebf 1.5 Items }

Many of the advanced data types in LEDA (e.g. dictionaries), are defined in
terms of so-called items. An item is a container which can hold an object
relevant for the data type. For example, in the case of dictionaries a
$dic\_item$ contains a pair consisting of a key and an information.
A general definition of items will be given at the end of this section.

We now discuss the role of items for the dictionary example in some detail.
A popular specification of dictionaries defines a dictionary as a partial
function from some type $K$ to some other type $I$, or alternatively, as a
set of pairs from $K\times I$, i.e., as the graph of the function. In an
implementation each pair $(k,i)$ in the dictionary is stored in some location
of the memory. Efficiency dictates that the pair $(k,i)$ cannot only be
accessed through the key $k$ but sometimes also through the location where it
is stored, e.g., we might want to lookup the information $i$ associated with
key $k$ (this involves a search in the data structure), then compute with the
value $i$ a new value $i\'$, and finally associate the new value with $k$.
This either involves another search in the data structure or, if the lookup
returned the location where the pair $(k,i)$ is stored, can be done by direct
access. Of course, the second solution is more efficient and we therefore
wanted to provide it in LEDA.

In LEDA items play the role of positions or locations in data structures.
Thus an object of type $dictionary(K,I)$, where $K$ and $I$ are types, is
defined as a collection of items (type $dic\_item$) where each item contains
a pair in $K\times I$. We use $<k,i>$ to denote an item with key $k$ and
information $i$ and require that for each $k\in K$ there is at most one
$i\in I$ such that $<k,i>$ is in the dictionary. In mathematical terms this
definition may be rephrased as follows: A dictionary $d$ is a partial
function from the set $dic\_item$ to the set $K\times I$. Moreover, for each
$k\in K$ there is at most one $i\in I$ such that the pair $(k,i)$ is in $d$.

The functionality of the operations
\smallskip
\+\quad\quad &$dic\_item$ &$D$.lookup($K\ k$)\cr
\+           &$I$         &$D$.inf($dic\_item\ it$)\cr
\+           &$void$      &$D$.change\_inf($dic\_item\ it,\ I\ i\'$)\cr
is now as follows:
$D$.lookup($k$) returns an item $it$ with contents $(k,i)$, $D$.inf($it$)
extracts $i$ from $it$, and a new value $i\'$ can be associated with $k$ by
$D$.change\_inf($it,i\'$).


Let us have a look at the insert operation for dictionaries next:
\smallskip
\+&$dic\_item$ &$D$.insert($K\ k,\ I\ i$)\cr

There are two cases to consider. If $D$ contains an item $it$ with contents
$(k,i\')$ then $i\'$ is replaced by $i$ and $it$ is returned. If $D$ contains
no such item, then a new item, i.e., an item which is not contained in any
dictionary, is added to $D$, this item is made to contain $(k,i)$ and is
returned. In this manual (cf. section 4.3) all of this is abbreviated to

\smallskip
\+&\cleartabs
   $dic\_item$\ \ \ $D$.insert($K\ k,\  I\ i$) \quad
                         &associates the information $i$ with the key $k$.\cr
\+&                      &If there is an item $<k,j>$ in $D$ then $j$ is\cr
\+&                      &replaced by i, else a new item $<k,i>$ is added\cr
\+&                      &to $D$. In both cases the item is returned.\cr


We now turn to a general discussion. With some LEDA types $XYZ$ there is an
associated type $XYZ\_item$ of items. Nothing is known about the objects of
type $XYZ\_item$ except that there are infinitely many of them. The only
operations available on $XYZ\_items$ besides the one defined in the
specification of type $XYZ$ is the equality predicate ``=='' and the assignment
operator ``='' . The objects of type $XYZ$ are defined as sets or sequences of
$XYZ\_items$ containing objects of some other type $Z$. In this situation an
$XYZ\_item$ containing an object $z\in Z$ is denoted by $<z>$. A new or unused
$XYZ\_item$ is any $XYZ\_item$ which is not part of any object of type $XYZ$.

{\bf Remark}: For some readers it may be useful to interpret a $dic\_item$ as
a pointer to a variable of type $K\times I$. The differences are that the
assignment to the variable contained in a $dic\_item$ is restricted, e.g., the
$K$-component cannot be changed, and that in return for this restriction the
access to $dic\_items$ is more flexible than for ordinary variables, e.g.,
access through the value of the $K$-component is possible.



\bigskip
\bigskip
{\magonebf 1.6 Input and output}

Some parameterized data types (e.g. $list$) provide the operations $print$ and
$read$ for printing their contents to an output stream and for initializing
an instance of this type by inserting elements read from an input stream.
There are two overloaded functions which can be used for defining input and
output functions for user-defined pointer types which are used by $read$ and
$print$ operations (and sometimes for error messages).

$void$\ \  $Read(T\&,\ istream\&)$  $\{$ \dots $\}$\nl
defines an input function for reading objects of type $T$ from an input stream.

$void$\ \  $Print(T\&,\ ostream\&)$  $\{$ \dots $\}$ \nl
defines an output function for printing objects of type $T$ to an output stream.

\bigskip
{\bf Example}: We declare the data type $list(pair)$ (see section~3.7)
and want to read and print lists of pairs. Note that the $Read$ and $Print$
functions have to be declared before the declaration of the list type.

$void$ $Read(pair\&\ p,\ istream\&\ IN)$  $\{$  $IN >> p\rightarrow x  >> p\rightarrow y $; $\}$

$void$ $Print(pair\&\ p,\ ostream\&\ OUT)$ $\{$  $OUT << p\rightarrow x << $" "$ << p\rightarrow y $; $\}$

{\bf declare}(list, pair)
\smallskip
\vdots
\smallskip
\cleartabs
\+&\ \ \ &list(pair) $L$;\cr
\smallskip
\+&      &$L$.read(``L = '');\cr
\+&      &$L$.print(``L = '');\cr



\bigskip
\bigskip
{\magonebf 1.7 Iteration}

For many data types LEDA provides iteration macros. These macros can be
used to iterate over the elements of lists, sets and dictionaries or
the nodes and edges of a graph. Iteration macros can be used similarly to
the \CC {\bf for} statement. Examples are
\smallskip
for lists and sets:
\smallskip
{\bf forall}($x,L$) $\{$ the elements of $L$ are successively assigned
to $x \}$
\smallskip
for graphs:
\smallskip
{\bf forall\_nodes}($v,G$) $\{$ the nodes of $G$ are successively
assigned to $v \}$
\smallskip
{\bf forall\_adj\_nodes}($w,v$) $\{$ the neighbor nodes of $v$ are
successively assigned to $w \}$

{\bf Note}: Update operations on an object $x$ are not allowed inside
the body of an iteration statement for $x$.


\bigskip
\bigskip
{\magonebf 1.8 Header Files}

LEDA data types and algorithms can be used in any \CC program as described
in this manual. The specifications (class declarations) are contained
in header files. To use a specific data type its header file has to be
included into the program. In general the header file for data type XYZ is
$<$LEDA/XYZ.h$>$. Exceptions are


\smallskip
$<$LEDA/basic.h$>$

This header file contains the declarations for the simple data types
$bool$, $real$, $string$ (section~2), and the functions, macros, and stream
data types described in section~7.


\smallskip
$<$LEDA/graph.h$>$

contains the declarations of data types $graph$, $GRAPH$, $node\_array$
and $edge\_array$ (section~5).

\smallskip
$<$LEDA/ugraph.h$>$

contains the declarations of types $ugraph$ and $UGRAPH$ (section~5).


\smallskip
$<$LEDA/graph\_alg.h$>$

contains the declarations of all graph and network algorithms and predefines
some node/edge array types (see section~5.12).


\smallskip
$<$LEDA/plane.h$>$

contains the two-dimensional objects $point$, $segment$, $line$, $polygon$,
and $circle$ (section~6)


\smallskip
$<$LEDA/plane\_alg.h$>$

contains some algorithms fortwo-dimensional geometry (section~6.1).


\vfill\eject


\bigskip
\bigskip
{\magonebf 1.9 Libraries}

The implementions of all LEDA data types and algorithms are precompiled and
contained in 5 libraries (libL.a, libG.a, libP.a, libWs.a, libWx.a)
which can be linked with \CC application programs. In the following
description it is assumed that these libraries are installed in one of the
systems default library directories (e.g. /usr/lib), which allows to use
the ``-l\dots'' compiler option.

\medskip
a) {\bf libL.a}
is the main LEDA library, it contains the implementations of all simple
data types (section~2), basic data types (section~3), dictionaries and priority
queues (section~4). A program $prog.c$ using any of these data types has to
linked with the libL.a library like this:

CC $prog.c$ -lL


\medskip
b) {\bf libG.a}
is the LEDA graph library. It contains the implementations of all graph
data types and algorithms (section~5). To compile a program using any graph
data type or algorithm the libG.a and libL.a library have to be used:

CC $prog.c$ -lG -lL


\medskip
c) {\bf libP.a}
is the LEDA library for geometry in the plane. It contains the
implementations of all data types and algorithms for two-dimensional
geometry (section~6). To compile a program using two-dimensional data
types or algorithms the libP.a, libG.a, libL.a and maths libraries have
to be used:

CC $prog.c$ -lP -lG -lL.a -lm

\medskip
d) {\bf libWs.a}, {\bf libWx.a}
are the LEDA libraries for graphic windows under the SunView or X11
(xview) window systems. Application programs using data type $window$
(cf. section~6.7) have to be linked with one of these libraries:

\beginitem
\item{ a)}
For the SunView window system:\nl
CC $prog.c$ -lWs -lP -lG -lL -lm  -lsuntool -lsunwindow -lpixrect

\item{ b)}
For the X11 (xview) window system:\nl
CC $prog.c$ -lWx -lP -lG -lL -lm  -lxview -lolgx -lX11

\enditem

Note that the libraries always must be given in the order -lW? -lP -lG -lL.

\vfill\eject