report.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{hyperref}
\usepackage{xcolor}

\hypersetup{
    colorlinks=true,
    linkbordercolor = {white},
    linkcolor=black,
    urlcolor=cyan
}
\title{\Huge Problème de clique maximum}

\author{\texttt{reda-mohamed.drissi@isty.uvsq.fr}\\
        Drissi Mohamed Reda}
\date{19 Fevrier 2018}
\begin{document}
\makeatletter
    \begin{titlepage}
        \begin{center}
        	\includegraphics[width=40mm]{Report/uvsq-header.png}\par \vspace{1cm}
            {\@title }\\[4ex]
            {\@author}\\[4ex]
            {\@date} \\ [4ex]
        \end{center}
    \end{titlepage}
\makeatother
\thispagestyle{empty}
\newpage
\tableofcontents
\newpage
\section{Introduction}
Après avoir testé plusieurs algorithmes (glouton, Bron-Kerbosch, branch and bound), il parait que
l'algorithme Clique\_Max (trouvé sur wikipedia) en utilisant la coloration du graphe,
soit le plus rapide, (du moins au moment de l'implémentation).\\
Le but est d'utiliser l'algorithme approximé de coloration de graphes pour determiner une borne,
ce qui facilite la recherche d'une clique maximum.
\section{Théorie}
Soit un graphe $G=(V,E)$ tel que $V=\{1,2,3,4..,n\}$. Pour chaque sommet $v \in V$, $\Gamma(v)$
est l'ensemble de tous les voisins de $v$ donc deg$(v)=|\Gamma(v)|$.\\
Soit $G(R)=G(R,E\cap R\times R)$ le sous-graphe de $G$ comprenant tous les éléments de $R$, tel que
$R \subset V$.
\subsection{Algorithme De Coloration De graphe}
$Q$ est l'ensemble des sommets de la clique qui est actuellement construite, $Q_{max}$
est l'ensemble des sommets de la plus grande clique trouvée jusqu'à maintenant.\\
L'algorithme insère chaque sommet $v$ dans la première classe $C_k$ de couleur possible, si aucune
classe n'est possible, nous créons une nouvelle classe $C_{max\_no+1}$ puis nous y insérons $v$.\\
Pour notre cas nous remarquons que les sommets $ v \in R$ ayant une couleur $C(v) < |Q_{max}|-|Q|+1$
ne vont jamais être rajoutées à la clique actuelle ($Q$), donc nous calculons cette valeur
$k_{min}=|Q_{max}|-|Q|+1$ au début de l'itération, et nous initialisons le compteur de ces sommets à
$j \gets 0$.\\
Quand un sommet $v=R[i]$ est attribué à une classe $C_k$ et que $k<k_{min}$ nous décalons ce sommet
vers la position $j$, $R[j] \gets R[i]$, puis nous incrémentons $j$. \\
Une fois tous les sommets ont été attribués à une couleur, les sommets ayant $k<k_{min}$ sont au début
de $R$. Les autres sommets tel que $k \geq k_{min}$ sont copiés depuis les classes de couleurs $C_k$
vers $R$ dans un ordre croissant de $k$. Uniquement à ces sommets sont attribués des couleurs $C(v)=k$.
\newpage
\begin{algorithm}
\begin{algorithmic}
\Procedure{Coloration}{R,C}
  \State max\_no $\gets$ 1
  \State $k_{min}$ $\gets$ $|Q_{max}| - |Q|+1$
  \If{$k_{min} \leq 0$}
    \State $k_{min} \gets 1$
  \EndIf
  \State $j \gets 0$
  \State $C_1 \gets \emptyset$ $C_2 \gets \emptyset$
  \For{$ i \in [1,|R|-1]$}
    \State $p \gets R[i]$
    \State $k \gets 1$
    \While{$C_k \cap \Gamma(p) \neq \emptyset$}
      \State $k \gets k+1$
    \EndWhile
    \If{$k >$ max\_no}
      \State max\_no $\gets k$
      \State $C_{max\_no+1} \gets \emptyset $
    \EndIf
    \State $C_k \gets C_k \cup \{p\}$
    \If{$k < k_{min}$}
      \State $R[j] \gets R[i]$
      \State $j \gets j+1$
    \EndIf
  \EndFor
  \State $C[j-1] \gets 0$
  \For{$k \in [k_{min}$,max\_no]}
    \For{$i \in [1,|C_k|]$}
      \State $R[j] \gets C_k[i]$
      \State $C[j] \gets k$
      \State $j \gets j+1$
    \EndFor
  \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}
\subsection{Trouver la clique max}
Nous initialisons :
\begin{itemize}
  \item $Q \gets \emptyset$
  \item $Q_{max} \gets \emptyset$
  \item ALLSTP $\gets 1$
  \item Tous les éléments de $S$ et $S_{old}$ sont initialisés à 0
\end{itemize}
Trier les sommets de $R$ selon leur degrés nous permet de gagner en performance en théorie, puisque
cela permet d'avoir une borne supérieure moins grande, et nous permet de réduire le nombre d'étapes
au minimum mais puisque cela prend un temps $O(|R|^2)$, nous ne gagnons en performance que quand
$R$ est assez large, donc uniquement dans les premières étapes.\\
En utilisant $lv$ nous comptons le nombre d'appels récursifs depuis la racine jusqu'à la feuille
actuelle. \\
Le nombre d'étapes max où nous n'allons pas trier $R$ doit être determiné dynamiquement, car la densité
est un plus grand facteur que la taille du graphe, dans la taille de la clique max.\\
Les variables $S[lv]$ et $S_{old}[lv]$ sont des variables globales qui nous permettrons de compter
le nombre d'étapes. La variable ALLSTP calcule le nombre d'étapes maximales.\\
À chaque étape nous calculons $S[lv]/$ALLSTP et nous le comparons à $T_{limit}$ qui est un paramètre
choisi en testant differents graphes, et en regardant sur internet. \\
Quand $S[lv]/$ALLSTP$ \geq T_{limit}$ nous ne trions pas $R$.\\
À chaque itération la fonction mets à jour $S$ et $S_{old}$ avec
\begin{displaymath}
  S[lv] \gets S[lv] + S[lv-1] -S_{old}[lv]
  S_{old}[lv]\gets S[lv-1]
\end{displaymath}
\begin{algorithm}
\caption{Clique\_Max(R,C,lv)}
\begin{algorithmic}
\Procedure{Clique\_Max}{R,C,lv}
  \State $S[lv] \gets S[lv] + S[lv-1] -S_{old}[lv]$
  \State $S_{old}[lv]\gets S[lv-1]$
  \While{$R\neq\emptyset$}
    \State Choisir un sommet $p$ ayant $C(p)$ max (dernier sommet) dans $R$
    \State $R \gets R \setminus \{p\}$
    \If{$|Q| +C$[index de $p$ dans $R$] $>$ $|Q_{max}|$}
      \State $Q \gets Q \cup \{p\}$
      \If{$R \cap \Gamma(p) \neq \emptyset$}
        \If{$S[lv]$/ALLSTP $<$ $T_{limit}$}
          \State Calculer le degré des sommets de G($R \cap \Gamma(p)$)
          \State Trier les sommets de $R \cap \Gamma(p)$ par ordre décroissant
          \State (selon leurs degrés)
        \EndIf
        \State \Call{Coloration}{$R \cap \Gamma(p)$,C'}
        \State $S[lv] \gets S[lv]+1$
        \State ALLSTP $\gets$ ALLSTP +1
        \State  \Call {Clique\_Max}{$R \cap \Gamma(p)$,C',lv+1}
      \ElsIf{$|Q| > |Q_{max}| $}
        $Q_{max} \gets Q$
      \EndIf
      \State $Q \gets Q\setminus \{p\}$
    \Else
      \State return
    \EndIf
  \EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}
\section{Implémentation en C++}
Pour compiler le projet nous pouvons utiliser le \texttt{Makefile}.\\
Puis pour exécuter nous pouvons suivre le format :
\begin{verbatim}
  ./maxc <fichier.ls|.mat|.clq>
\end{verbatim}
\paragraph{brock200\_1}
Commande :
\begin{verbatim}
  time ./maxc bingraph/brock200_1.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/brock200_1.clq
  |E| = 14834  |V| = 200 p = 0.7417
  etape n = 0 taille de clique max= 1
  etape n = 13 taille de clique max= 14
  etape n = 19 taille de clique max= 15
  etape n = 68 taille de clique max= 16
  etape n = 147 taille de clique max= 17
  etape n = 625 taille de clique max= 18
  etape n = 2675 taille de clique max= 19
  etape n = 11253 taille de clique max= 20
  etape n = 57248 taille de clique max= 21
  Clique Max: 134 102 85 39 150 92 136 68 186 178 135 94 90 93 20 18 73 87 81 142 108
  Taille = 21
  Nombre d'etapes = 232999
\end{verbatim}
Temps d'exécution
\begin{verbatim}
    real  0m0.410s
    user  0m0.400s
    sys   0m0.000s
\end{verbatim}
\paragraph{brock200\_2}
Commande :
\begin{verbatim}
  time ./maxc bingraph/brock200_2.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/brock200_2.clq
  |E| = 9876  |V| = 200 p = 0.4938
  etape n = 0 taille de clique max= 1
  etape n = 5 taille de clique max= 6
  etape n = 9 taille de clique max= 7
  etape n = 14 taille de clique max= 8
  etape n = 40 taille de clique max= 9
  etape n = 1166 taille de clique max= 10
  etape n = 1566 taille de clique max= 12
  Clique Max: 135 158 145 105 121 27 55 183 70 48 149 120
  Taille = 12
  Nombre d'etapes = 3606
\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  0m0.033s
  user  0m0.020s
  sys   0m0.000s
\end{verbatim}

\paragraph{brock400\_2}
Commande :
\begin{verbatim}
  time ./maxc bingraph/brock400_2.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/brock400_2.clq
  |E| = 59786  |V| = 400 p = 0.747325
  etape n = 0 taille de clique max= 1
  etape n = 17 taille de clique max= 18
  etape n = 29 taille de clique max= 19
  etape n = 184 taille de clique max= 20
  etape n = 3604 taille de clique max= 21
  etape n = 87268 taille de clique max= 22
  etape n = 665019 taille de clique max= 23
  etape n = 10259821 taille de clique max= 24
  etape n = 20022091 taille de clique max= 29
  Clique Max: 388 252 20 39 92 142 276 178 68 380 134 73 348 93 234 260 150 365 262 207 221 135
  18 304 90 108 311 85 186
  Taille = 29
  Nombre d'etapes = 44365961
\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  1m55.945s
  user  1m55.936s
  sys   0m0.000s
\end{verbatim}
\paragraph{brock400\_4}
Commande :
\begin{verbatim}
  time ./maxc bingraph/brock400_4.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/brock400_4.clq
  |E| = 59765  |V| = 400 p = 0.747062
  etape n = 0 taille de clique max= 1
  etape n = 15 taille de clique max= 16
  etape n = 20 taille de clique max= 17
  etape n = 54 taille de clique max= 18
  etape n = 104 taille de clique max= 19
  etape n = 199 taille de clique max= 20
  etape n = 309 taille de clique max= 21
  etape n = 24492 taille de clique max= 22
  etape n = 162628 taille de clique max= 23
  etape n = 1528510 taille de clique max= 24
  etape n = 1589415 taille de clique max= 25
  etape n = 50859228 taille de clique max= 26
  etape n = 51039931 taille de clique max= 33
  Clique Max: 161 362 353 294 266 157 393 135 241 324 17 7 343 270 202 112 267 380 389
  197 396 394 211 340 147 334 245 186 154 247 8 19 242
  Taille = 33
  Nombre d'etapes = 54362635
\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  2m1.055s
  user  2m0.996s
  sys   0m0.004s
\end{verbatim}
Nous faisons tourner ce dernier \texttt{brock800\_2} avec Valgrind
\paragraph{brock800\_2}
Commande :
\begin{verbatim}
  time ./maxc bingraph/brock800_2.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/brock800_2.clq
  |E| = 208166  |V| = 800 p = 0.650519
  etape n = 13 taille de clique max= 14
  etape n = 16 taille de clique max= 15
  etape n = 161 taille de clique max= 16
  etape n = 986 taille de clique max= 17
  etape n = 2943 taille de clique max= 18
  etape n = 49586 taille de clique max= 19
  etape n = 4320201 taille de clique max= 20
  etape n = 303732455 taille de clique max= 21
  etape n = 586725133 taille de clique max= 24
  Clique Max: 649 417 160 504 460 271 445 348 580 109 155 214 414 792 258 12 84 323 130 383 694 55 496 695
  Taille = 24
  Nombre d'etapes = 1315510644
\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  57m18.137s
  user  57m17.928s
  sys   0m0.008s
\end{verbatim}
\paragraph{brock800\_4}
Commande :
\begin{verbatim}
  time ./maxc bingraph/brock800_4.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/brock_800_4.clq
  |E| = 207643  |V| = 800 p = 0.648884
  etape n = 13 taille de clique max= 14
  etape n = 66 taille de clique max= 15
  etape n = 130 taille de clique max= 16
  etape n = 674 taille de clique max= 17
  etape n = 1263 taille de clique max= 18
  etape n = 139158 taille de clique max= 19
  etape n = 1189470 taille de clique max= 20
  etape n = 64329588 taille de clique max= 21
  etape n = 199277938 taille de clique max= 26
  Clique Max: 333 246 269 623 665 713 156 388 494 508 395 323 111 686 16 393 134 342 680 560 153 7 510 361 160 293
  Taille = 26
  Nombre d'etapes = 501919040
\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  27m25.811s
  user  27m25.664s
  sys   0m0.004s
\end{verbatim}
\paragraph{keller4}
Commande :
\begin{verbatim}
  time ./maxc bingraph/keller4.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/keller4.clq
  |E| = 9435  |V| = 171 p = 0.645349
  etape n = 0 taille de clique max= 1
  etape n = 10 taille de clique max= 11
  Clique Max: 130 162 48 152 65 44 49 138 68 135 147
  Taille = 11
  Nombre d'etapes = 8586
\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  0m0.014s
  user  0m0.012s
  sys   0m0.000s
\end{verbatim}
\paragraph{hamming8-4}
Commande :
\begin{verbatim}
  time ./maxc bingraph/hamming8-4.clq
\end{verbatim}
Résultat
\begin{verbatim}
  args = bingraph/hamming8-4.clq
  |E| = 20864  |V| = 256 p = 0.636719
  etape n = 0 taille de clique max= 1
  etape n = 11 taille de clique max= 12
  etape n = 30 taille de clique max= 13
  etape n = 316 taille de clique max= 16
  Clique Max: 95 162 139 212 60 183 45 158 197 240 99 118 17 8 249 74
  Taille = 16
  Nombre d'etapes = 11293
\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  0m0.041s
  user  0m0.032s
  sys   0m0.000s

\end{verbatim}
\section{Test de performance à l'aide de \href{http://www.valgrind.org/}{Valgrind ©}}
Nous allons tester notre programme avec plusieurs instances de \href{https://turing.cs.hbg.psu.edu/txn131/clique.html}{DIMAC}.\\
\paragraph{brock200\_4}
Commande
\begin{verbatim}
  time valgrind ./maxc bingraph/brock200_4.clq
\end{verbatim}
Résultat
\begin{verbatim}
  ==3793== Memcheck, a memory error detector
  ==3793== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
  ==3793== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
  ==3793== Command: ./maxc bingraph/brock200_4.clq
  ==3793==
  ==3793==
  ==3793== HEAP SUMMARY:
  ==3793==     in use at exit: 72,704 bytes in 1 blocks
  ==3793==   total heap usage: 61,477 allocs, 61,476 frees, 19,734,193 bytes allocated
  ==3793==
  ==3793== LEAK SUMMARY:
  ==3793==    definitely lost: 0 bytes in 0 blocks
  ==3793==    indirectly lost: 0 bytes in 0 blocks
  ==3793==      possibly lost: 0 bytes in 0 blocks
  ==3793==    still reachable: 72,704 bytes in 1 blocks
  ==3793==         suppressed: 0 bytes in 0 blocks
  ==3793== Rerun with --leak-check=full to see details of leaked memory
  ==3793==
  ==3793== For counts of detected and suppressed errors, rerun with: -v
  ==3793== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

\end{verbatim}
Temps d'exécution
\begin{verbatim}
  real  0m1.490s
  user  0m1.456s
  sys   0m0.032s
\end{verbatim}
\end{document}