The \emph{LEDA Extension Package for GraphML} (GraphML LEP) enables LEDA
users to import and export graphs in GraphML format.
Nodes and edges of these graphs may be labeled with any number of
attributes of elementary type.  Note that for reading GraphML, the 
GraphML LEP requires Xerces, a general XML parser.\footnote 
{Xerces is developed by and freely available from the Apache Software
 Foundation at \url{http://xml.apache.org/xerces-c/}.
}


\section{GraphML}
% -----------------------------------------------------------------

GraphML (Graph Markup Language) is a comprehensive and easy-to-use file
format for graphs.  It consists of a language core (known as the 
\emph{Structual Layer}) to describe 
structural properties of one or more graphs and a flexible extension
mechanism, e.g.\ to add application-specific data.  Its main features 
include support of
\begin{itemize}
\item directed, undirected, and mixed multigraphs,
\item hypergraphs,
\item hierarchical graphs,
\item multiple graphs in a single file,
\item application-specific data, and
\item references to external data.
\end{itemize}
Two extensions, adding support of meta-information for light-weight
parsers (\emph{Parse Extension}) and typed attribute data 
(\emph{Attributes Extension}) are currently part of the GraphML
specification. 

Unlike many other file formats for graphs, GraphML
does not use a custom syntax.  Instead, it is defined as an XML\footnote
{Extensible Markup Language, see \texttt{http://www.w3.org/XML/}.} 
sublanguage and hence ideally suited as an exchange format for all kinds
of services generating or processing graphs.

The majority of tools will hardly ever deal with graphs other
then mixed multigraphs with attribute data for nodes and edges.  In
GraphML, such a data structure is represented as follows.
{\footnotesize\begin{verbatim}
<?xml version="1.0"?>
<graphml
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns="http://graphml.graphdrawing.org/xmlns/1.0rc"
       xmlns:xlink="http://www.w3.org/1999/xlink" 

       xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0rc
                             graphml-structure.xsd
                           http://graphml.graphdrawing.org/xmlns/1.0rc
                             graphml-attributes.xsd"
>
  <desc>a simple flow network</desc>

  <key id="k0" for="edge" attr.name="capacity" attr.type="int">
   <desc>(upper) capacity constraint on edge</desc>
   <default>1</default>
  </key>
  <key id="k1" for="node" attr.name="demand" attr.type="int">
   <desc>flow demand at node</desc>
   <default>0</default>
  </key>

  <graph edgedefault="undirected">
    <node id="v0">
      <data key="k1">-2</data>
    </node>
    <node id="v1"/>
    <node id="v2">
      <data key="k1">2</data>
    </node>

    <edge source="v0" target="v1"/>
    <edge source="v0" target="v1" directed="true"/>
    <edge source="v1" target="v2">
      <data key="k0">3</data>
    </edge>
   </graph>

</graphml>
\end{verbatim}}
Anyone using GraphML can define extensions that add XML attributes
to GraphML elements, or redefine the content of \texttt{data} elements.

Work on GraphML was initiated in a workshop
during the 2000 Graph Drawing Symposium in Williamsburg, 
and a proposal for the structural layer was presented at the 
2001~Graph Drawing Symposium in Vienna~\cite{brandes_etal:gd01}.  
The above extensions were introduced in early~2002.  All specifications
are currently release candidates under public review.

The next major steps will be 
extensions for abstract graph layout information and templates 
to transform such information into a variety of graphics formats.
We refer to 
\begin{center}
\texttt{http://graphml.graphdrawing.org/}
\end{center}
for up-to-date information on GraphML.


\section{GraphML LEP}
% -----------------------------------------------------------------

This first version of the GraphML LEP supports only the most common
types of graphs.  Since there is no LEDA data structure for mixed
graphs, all graphs must be either directed or undirected.\footnote
{If a graph read from a GraphML file contains both directed and 
 undirected edges, all edges are interpreted according to the 
 \texttt{edgedefault} attribute of GraphML element \texttt{graph}.}
Only the first graph in a file is read, and node ports, hyperedges,
nested graphs, and links to external elements are ignored altogether.

Nodes and edges may be labeled with an arbitrary number of attributes
of elementary type.\footnote
{As specified in the GraphML Attribute Extension 
 (\texttt{graphml-attributes}).  Admissible types correspond to
 \texttt{bool}, \texttt{int}, \texttt{long}, \texttt{float}, 
 \texttt{double}, and \texttt{string}.}
When writing an (attributed) graph to a file, additional information 
that may be useful for light-weight parsers can be added.\footnote
{As specified in the GraphML Parseinfo Extension 
 (\texttt{graphml-parseinfo}).}

\begin{table}[h!]
\centerline{\begin{tabular}{|l|c|}\hline
directed graphs & +\\
undirected graphs & +\\
mixed graphs & -\\
multiple graphs & -\\
ports & -\\
hyperedges & -\\
hierarchical graphs & -\\
external data & -\\\hline
attributes extension & for nodes \& edges\\
parse extension & write-only\\
layout extension & -\\\hline
\end{tabular}}
\caption{\label{TAB:features}
 Features currently supported.\protect\footnotemark\protect}
\end{table}
\footnotetext{Note that, while this document is being prepared, 
 the GraphML Layout Extension (\texttt{graphml-layout}) is not yet available.}


\subsection{Requirements}
% -----------------------------------------------------------------

Though the GraphML LEP has been developed for LEDA~4.4, it should work
with earlier versions as well.  It can be installed to be used for
writing graphs to GraphML files only.  If reading graphs from GraphML 
files is desired as well, a working installation of Xerces, a general
XML parser freely available from the Apache Software Foundation, is
required (version~2.2 or higher).


\subsection{Installation}
% -----------------------------------------------------------------
\begin{itemize}
\item
cd to GraphML-root directory \begin{tt}graphml\_root\end{tt}

\item
execute \begin{tt}./bootstrap\end{tt}
\item
execute \begin{tt}./configure [OPTIONS]\end{tt}

\begin{tt}./configure --help\end{tt}
displays configuration options.
\item
Example: If 
\begin{tt}\$LEDAROOT\end{tt} and
\begin{tt}\$XERCESCROOT\end{tt} are set, then
\begin{tt}./configure --prefix=<installation\_directory>\end{tt}
generates \begin{tt}Makefile\end{tt}
for installation of 
header files in \begin{tt}installation\_directory/include\end{tt},
library files in \begin{tt}installation\_directory/lib\end{tt},
and demo executables (\begin{tt}add\_parseinfo\end{tt} and 
\begin{tt}graphml\_gw\end{tt}) in \begin{tt}graphml\_root/demo\end{tt}.

\item
execute \begin{tt}make install\end{tt}
\end{itemize}


\subsection{Usage}
% -----------------------------------------------------------------

See demo programs \begin{tt}./demo/add\_parsinfo.cc\end{tt} and
\begin{tt}./demo/graphml\_gw.cc\end{tt} and this documentation
Chapters 2 and 3.

\begin{verbatim}
\end{verbatim}

\paragraph*{Acknowledgments.}
We are grateful to Marco Gaertler and Thomas Willhalm 
for valuable comments and suggestions.