%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id: graphs.tex,v 1.1.1.1 2004/10/04 17:25:16 nthiery Exp $
% File:		lib/COMBINAT/DOC/graphs.tex
% Authors:	Florent Hivert <florent.hivert@univ-mlv.fr>
%		Nicolas M. Thiéry <nthiery@users.sf.net>
% Purpose:	Documentation for the domain combinat::graphs
% Created:	Tue Apr 13 11:03:49 2004
% License:	LGPL
% Project:	MuPAD-Combinat, http://mupad-combinat.sf.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{graphs}{Florent Hivert and Nicolas M. Thiéry}
  [ImplState=stable,TestState=stable,DocState=beta]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{unlabelled graphs}
  \de{}
\end{MInfo}

\MDeclareOption{\Connected}{Connected}
\MDeclareOption{\CIIIFree}{C3Free}
\MDeclareOption{\CIVFree}{C4Free}
\MDeclareOption{\Bipartite}{Bipartite}
\MDeclareOption{\Biconnected}{Biconnected}
\MDeclareOption{\MinDegree}{MinDegree}
\MDeclareOption{\MaxDegree}{MaxDegree}
\MDeclareOption{\MinEdges}{MinEdges}
\MDeclareOption{\MaxEdges}{MaxEdges}
\MDeclareOption{\Quiet}{Quiet}
\MDeclareOption{\Straighten}{Straighten}
\MDeclareOption{\GengOptions}{GengOptions}

\begin{MIntro}
  \eng{\Mthis{} is an interface with the \texttt{Nauty} \texttt{C}
    library for manipulating unlabelled graphs.}
  \de{}
\end{MIntro}

\begin{MDetails}
  \eng{\Mthis{} provides a dynamic module interface with the
    \texttt{Nauty} library for counting, generating, and manipulating
    unlabelled graphs.}
  
  \eng{All functions for counting and generating accept the following
    optional constraints on the graphs: \Connected \CIIIFree, \CIVFree,
    \Bipartite, \Biconnected, \MinDegree, \MaxDegree, \MinEdges,
    \MaxEdges, whose respective meaning are self-explanatory.
    Furthermore, the options \Quiet{} and \GengOptions{} can be used
    to pass extra options to \texttt{Nauty}.}
  
  \eng{Unlabelled graphs are represented by a (canonical) labelled
    representative on the vertices $\{1,\dots,n\}$. Technically, they
    are stored as kernel objects; namely, they consist of \mupad{}
    cells of type \Mex{combinat::graphs} whose memory parts embed a
    \texttt{C} graph data structure, as used by \texttt{Nauty}.}
\end{MDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of graphs}
  \call{\Mtype{nonnegative integer} n \Mopt{, constraints}}
  \eng{Returns the number of graphs on \Mpar{n} vertices satisfying
    \Mpar{constraints}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the graphs}
  \call{\Mtype{nonnegative integer} n \Mopt{, constraints}}
  \eng{Returns the list of the graphs on \Mpar{n} vertices satisfying
    \Mpar{constraints}.}
\end{MMethodDetails}

\begin{MMethodDetails}{size}
  \infoEng{number of vertices of a graph}
  \call{\Mtype{dom} g}
  \eng{Returns the number of vertices of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{getVertices}
  \infoEng{vertices of a graph}
  \call{\Mtype{dom} g}
  \eng{Returns the list of the vertices of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{getEdges}
  \infoEng{edges of a graph}
  \call{\Mtype{dom} g}
  \eng{Returns the list of the edges of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{getEdgeNumber}
  \infoEng{number of edges of a graph}
  \call{\Mtype{dom} g}
  \eng{Returns the number of edges of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{outDegree}
  \infoEng{out degree}
  \call{\Mtype{dom} g, \Mtype{vertex} i}
  \eng{Returns the out degree of the vertex \Mpar{i} of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{outDegrees}
  \infoEng{out degrees}
  \call{\Mtype{dom} g}
  \eng{Returns the list of the out degrees of the vertices of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{addEdges}
  \infoEng{adding edges}
  \call{\Mtype{dom} g, \Mtype{list of edges} edges}
  \eng{Returns a copy of \Mpar{g} with the edges in \Mpar{edges} added.}
\end{MMethodDetails}

\begin{MMethodDetails}{removeEdges}
  \infoEng{removing edges}
  \call{\Mtype{dom} g, \Mtype{list of edges} edges}
  \eng{Returns a copy of \Mpar{g} with the edges in \Mpar{edges} removed.}
\end{MMethodDetails}

\begin{MMethodDetails}{directSum}
  \infoEng{direct sum of two graphs}
  \call{\Mtype{dom} g, \Mtype{dom} h}
  \eng{Returns the direct sum of \Mpar{g} and \Mpar{h}; it is obtained
    by a copy of \Mpar{g}, with the vertices relabelled
    according to the permutation \Mpar{p}; that is, the node \Mex{i}
    of the new graph corresponds to the node \Mex{p[i]} of \Mpar{g}.}
\end{MMethodDetails}

%\begin{MMethodDetails}{contraction}
%  \infoEng{contraction}
%  \call{\Mtype{dom} g, \Mtype{edge} e}
%  \eng{Returns a copy of \Mpar{g} with the edge \Mpar{e} contracted.}
%\end{MMethodDetails}

\begin{MMethodDetails}{relabel}
  \infoEng{relabelling of the vertices}
  \call{\Mtype{dom} g, \Mtype{standard permutation} p}
  \eng{Returns a copy of \Mpar{g}, with the vertices relabelled
    according to the permutation \Mpar{p}; that is, the node \Mex{i}
    of the new graph corresponds to the node \Mex{p[i]} of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{sublabel}
  \infoEng{relabelling of the vertices}
  \call{\Mtype{dom} g, \Mtype{vertices} p}
  \eng{Returns an isomorphic copy of the induced subgraph of \Mpar{g}
    on the vertices \Mpar{vertices}. The node \Mex{i} of the new graph
    corresponds to the node \Mex{vertices[i]} of \Mpar{g}.}
  \eng{When \Mex{p} is a standard permutation, this is equivalent to
    \Mex{relabel} above.}
\end{MMethodDetails}

\begin{MMethodDetails}{straighten}
  \infoEng{canonical representative}
  \call{\Mtype{dom} g}
  \eng{Returns a canonical isomorphic copy of \Mpar{g}.}
\end{MMethodDetails}

\begin{MMethodDetails}{removeIsolatedVertices}
  \infoEng{removing isolated vertices}
  \call{\Mtype{dom} g}
  \eng{Returns an isomorphic copy of \Mpar{g} with the isolated
    vertices removed.}
\end{MMethodDetails}


\begin{MExample}{ex-basic}
  \eng{Here is the list of all $11$ unlabelled unoriented loopfree
    simple graphs on $4$ vertices:}
  \begin{Mexin}
combinat::graphs::list(4)
  \end{Mexin}
  \begin{Mexout}
[[[], [], [], []], [[], [], [4], [3]], [[], [4], [4], [2, 3]],

   [[4], [4], [4], [1, 2, 3]], [[2], [1], [4], [3]],

   [[3], [4], [1, 4], [2, 3]], [[], [3, 4], [2, 4], [2, 3]],

   [[4], [3, 4], [2, 4], [1, 2, 3]],

   [[2, 3], [1, 4], [1, 4], [2, 3]],

   [[3, 4], [3, 4], [1, 2, 4], [1, 2, 3]],

   [[2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3]]]
  \end{Mexout}
  \eng{Let's take the $4$-th one:}
  \begin{Mexin}
g := combinat::graphs(4)[4]
  \end{Mexin}
  \begin{Mexout}
                  [[4], [4], [4], [1, 2, 3]]
  \end{Mexout}
  \eng{It is displayed using adjacency lists: for each vertex, the list
    of its neighbors is given. Some basic accessors, named as in the
    \Mup{Graph} library, allow to retrieve information from the graph:}
  \begin{Mexin}
combinat::graphs::getVertices(g)
  \end{Mexin}
  \begin{Mexout}
                         [1, 2, 3, 4]
  \end{Mexout}
  \begin{Mexin}
combinat::graphs::getEdgeNumber(g)
  \end{Mexin}
  \begin{Mexout}
                               6
  \end{Mexout}
  \begin{Mexin}
combinat::graphs::getEdges(g)
  \end{Mexin}
  \begin{Mexout}
       [[1, 4], [2, 4], [3, 4], [4, 1], [4, 2], [4, 3]]
  \end{Mexout}
  \begin{Mexin}
combinat::graphs::outDegrees(g)
  \end{Mexin}
  \begin{Mexout}
                         [1, 1, 1, 3]
  \end{Mexout}
\end{MExample}

\begin{MChanges}
  \version{3.1}
  \eng[New domain]{\Mthis{} is a new domain} %
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 
