text: \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: 
  