\documentclass[a4]{seminar}

\usepackage{./talkadvi}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[french]{babel}
\usepackage{pstricks}
\usepackage{pst-node}
%\usepackage{color}
\usepackage{alltt}
\usepackage{url}
\usepackage{amsmath}	
\usepackage{amssymb}	

\newcommand{\rouge}[1]{\color{red}#1}
\newcommand{\monvert}[1]{\color{ForestGreen}#1}
\newcommand{\motcle}[1]{{\color{Blue}#1}}
\newcommand{\ocamlgraph}{\textsf{OcamlGraph}}
\newcommand{\fleche}{\ensuremath{\rightarrow}}

\begin{document}
\sffamily
\parindent=0mm

\begin{slide}
~\vfill
\begin{center}
  \textcolor{red}{\rule{\linewidth}{0.1em}} \\[0.7em]
  \textcolor{red}{\Large\bfseries 
          Le foncteur sonne toujours deux fois} \\
  \textcolor{red}{\rule{\linewidth}{0.1em}} \\[2em]
  \textcolor{royalblue}{\large Sylvain Conchon, Jean-Christophe Filliâtre, Julien Signoles}
 \\[3em]
  \textcolor{orange}{{\large LRI -- CNRS 8623}}
\end{center}
\vfill\vfill
\end{slide}

\begin{slide}\slidetitle{Ocamlgraph}

  \begin{center}
  Une bibliothèque de graphes pour Ocaml

  ~\\[2em] 
  \pause
  \emph{Pourquoi ?}

\bigskip

  Contrairement à C++ ou Java, pas de telle bibliothèque
  \end{center}

\end{slide}

\begin{slide}\slidetitle{Caractéristiques}

  \begin{points}
  \item Nombreuses structures de données\medskip

    \begin{itemize}
    \item Persistantes
    \item Impératives
    \item Étiquetées ou non
    \item etc.
    \end{itemize}
    
    \pause
  \item Algorithmes « génériques » \medskip

    \begin{itemize}
    \item Flots
    \item Parcours
    \item Génération aléatoire
    \item etc.
    \end{itemize}
  \end{points}

  \pause
  \begin{center}
  \emph{Rendu possible par l'utilisation massive de foncteurs}
  \end{center}
\end{slide}

\talkpart{I}{Structures de données}

\begin{slide}\slidetitle{Interfaces}
  
Interface commune à tous les graphes :
\begin{alltt}
\motcle{module type} G = \motcle{sig} ... \motcle{end}
\end{alltt}

\pause
Interface des graphes persistants :
\begin{alltt}
\motcle{module type} P = \motcle{sig}
  \emph{include} G
  ...
\motcle{end}
\end{alltt}

\pause
Interface des graphes impératifs :
\begin{alltt}
\motcle{module type} I = \motcle{sig}
  \emph{include} G
  ...
\motcle{end}
\end{alltt}
\end{slide}

\begin{slide}\slidetitle{Partage du code}

Au total, \ocamlgraph\ implante \emph{18} structures de données
\pause

A priori, \emph{8} variantes d'interface \texttt{G} :
\begin{center}
  orienté ? $\times$ sommets abstraits ? $\times$ arêtes étiquetées ?
\end{center}
\pause

\begin{points}
\item \emph{8} persistantes : table ({\monvert\texttt{Map}}) associant
  à chaque sommet l'ensemble ({\monvert \texttt{Set}}) de ses
  successeurs
\item \emph{8} impératives : même chose avec {\monvert
    \texttt{Hashtbl}} au lieu de \texttt{Map}
\item \emph{2} impératives par matrices d'adjacence \linebreak 
  (sommets = entiers, pas d'étiquette) 
\end{points}

\pause
Mais partage du code maximal à l'aide de \emph{foncteurs}
\end{slide}

\begin{slide}\slidetitle{Code commun aux graphes persistants et impératifs}
\begin{points}

\item Uniformisation de {\monvert \texttt{Hashtbl}} et {\monvert
    \texttt{Map}} dans une signature commune

\begin{alltt}
\motcle{module type} HM = \motcle{sig}
  \motcle{type} \emph{'a return}
  \motcle{type} 'a t
  \motcle{type} key
  \motcle{val} add: key -> 'a -> 'a t -> \emph{'a return}
  \motcle{val} mem: key -> 'a t -> bool
  \motcle{val} find: key -> 'a t -> 'a
  (* ... *)
\motcle{end}
\end{alltt}
\adviwait
\item \texttt{Minimal} : opérations communes à toutes les structures
  de données 

\item \texttt{Pred} : opérations sur les
  prédécesseurs en utilisant les successeurs 

\item \texttt{Labeled} / \texttt{Unlabeled} : opérations communes aux
  arêtes (non) étiquetées 

\item \texttt{Make\_Abstract} : graphe abstrait à partir de sa version
  concrète
    
\end{points}
\end{slide}

\begin{slide}\slidetitle{Assemblage des briques}
\begin{alltt}
\motcle{module} Make
  (F: \motcle{functor}(X: COMPARABLE) \fleche\ HM \motcle{with type} key = X.t) = 
\motcle{struct}
  \motcle{module} Digraph = \motcle{struct}

    \motcle{module} Concrete(V: COMPARABLE) = \motcle{struct}
      \emph{include} ConcreteVertex(F)(V)
      \emph{include} Unlabeled(V)(HM)
      \emph{include} Minimal(S)(HM)
    \motcle{end}

    \motcle{module} ConcreteLabeled(V: COMPARABLE)(E: ORDERED_TYPE_DFT) = 
    ...
\end{alltt}
\end{slide}

\talkpart{II}{Algorithmes}

\begin{slide}\slidetitle{Programmation générique}

\bigskip
\begin{center}
Chaque algorithme est écrit indépendamment de la structure de graphe.

\bigskip

C'est un \emph{foncteur}.

\bigskip

Son argument contient uniquement les opérations dont il a besoin.
\end{center}

\bigskip
\pause
\emph{Intérêts :}

\begin{points}
\item Codage facilité.\medskip

\item Utilisation sur des structures autres que celles d'\ocamlgraph.
\end{points}
\end{slide}

\begin{slide}\slidetitle{Algorithmes fournis}

\begin{points}
\item 
Parcours : 7 DFS, 2 BFS, 2 détections de cycle

\item 
Constructions : 
\begin{itemize}
\item 4 classiques (ex. graphe de de Bruijn)
\item 2 aléatoires (ex. planaires) 
\end{itemize}

\item 
Plus court chemin (Dijkstra)

\item 
Composantes fortement connexes

\item 
Flot maximal (Goldberg, Ford-Fulkerson)

\item 
Tri topologique

\item 
Arbre couvrant minimal (Kruskal)

\item 
Opérations : clôture transitive, complémentaire, miroir, voisinages, etc.

\item 
Ensemble des séparateurs minimaux

\item 
Graphes sans cordes, cliques

\item 
Sortie DOT (Graphviz)
\end{points}
\end{slide}


\begin{slide}\slidetitle{Exemples}

\bigskip
\begin{points}
\item Algorithmes de flots : {\monvert Ford-Fulkerson \&  Goldberg}

\bigskip

Deux foncteurs à deux paramètres:

\medskip

\begin{itemize}
\item \texttt{G}: les fonctions de manipulation du graphe\medskip

\item \texttt{F}: les fonctions de représentation du flot
\end{itemize}

\bigskip
\bigskip

\item Algorithmes de {\monvert parcours en profondeur et en largeur}
\end{points}
\end{slide}



\talkpart{III}{Conclusion}

\newcommand{\present}{\monvert\large\boldmath $\surd$}
\newcommand{\absent}{\rouge\large\boldmath $\oslash$}

\begin{slide}\slidetitle{Comparaisons}

\bigskip
\begin{center}
  \begin{tabular}{|l||c|c|c|c|c|}
    \hline
     & langage     &P/I& algo gén & signature\emph{s} & str données \\\hline\hline
     LEDA & C++    & I & \absent  & \absent  & 1  \\\hline
     GTL & C++     & I & \absent  & \absent  & 1  \\\hline
     MLRisc & SML  & I & \absent  & \absent  & 1  \\\hline
     FGL & Haskell & P & \absent  & \absent  & 1  \\\hline
     Baire & Ocaml &P/I& ---      & \absent  & 8  \\\hline
     JDSL & Java   & I & \present & \present & 1  \\\hline
     BGL & C++     & I & \present & \present & 1  \\\hline
 OcamlGraph& Ocaml &P/I& \present & \present & 18 \\\hline
  \end{tabular}
\end{center}
\end{slide}

\begin{slide}\slidetitle{Chiffres}

\begin{points}
\item 6000 lignes (dont 1000 lignes de contribution)\bigskip

\item 9 personnes-semaines de travail\bigskip

\item Performances : peu de comparaisons à ce jour

\medskip
{\monvert Exemples} (sur Pentium 4 2.8 GHz) :
\medskip
\begin{itemize}
\item DFS sur 200\,000 sommets et 500\,000 arêtes : 0.63 s\medskip

\item Dijkstra 70\,000 s. et 210\,000 ar. : chemin de 400
  sommets en 1.38 s 
\end{itemize}

\end{points}
\end{slide}

\begin{slide}\slidetitle{Remarques concernant les foncteurs}

\bigskip
  \begin{points}

  \item Quelques limitations du système de modules nous ont gênés \linebreak
(bug report \#2049).

\bigskip
Principalement, ne pas pouvoir réunir deux structures ayant un type ou
un module en commun.

\bigskip
\item 
Trop de foncteurs dans l'interface = frein à l'utilisation d'\ocamlgraph\ ?
    
  \end{points}

\end{slide}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
