# Algorithmes retirés du cahier des charges (LaTeX)
###### tags: `document interne`

\begin{minipage}[c]{0.47 \linewidth}
    \begin{algorithm}[H]
        \Entree {Sommet S, Graphe G} 
        \Sortie {Degrés entrants, Degrés sortants}
        Initialisation du successeur et du prédécesseur a 0\;
        \Pour {toutes les lignes de la matrice de G}
        {
            \Pour{toutes les colonnes de la matrice de G}
            {
             \Si{il existe un arc entre S et un autre sommet du graphe G}{
                Augmenter que le nombre de successeurs
              }
              \Si{il existe un arc entre un sommet du graphe G et le sommet S}
              {
                Augmenter le nombre de pr\'ed\'ecesseurs
              }
            }
        }
        \caption{Calcul de degrés entrants et sortants d'un sommet}
    \end{algorithm}
\end{minipage}
\hfill
\begin{minipage}[c]{0.47\textwidth}
    \begin{algorithm}[H]
            
        \Entree {Matrice d'adjacence A du graphe G}
        \Sortie {Matrice d'incidence I du graphe G}
        \Pour{toutes les lignes de A}
        {
            \Pour{toutes les colonnes de A}
            {
                \eSi {il existe un arc entre le sommet S et un sommet voisins T}
                {
                  Ajouter 1 dans la matrice I entre S et T ainsi que -1 entre T et S  
                }
                {
                    Ajouter 0 dans la matrice I entre S et T et T et S
                }
            
            }
        }
        
        \caption{Conversion d'une matrice d'adjacence en matrice d'incidence}
    \end{algorithm}
\end{minipage}

\begin{algorithm}
\caption{Calcul d'un flot maximal - algorithme d'Edmond-Karp}


\Entree {graphe G, S la source et P le puits}
\Sortie {Flot maximum F}
F est fixé à 0. \\
\Tq {il existe un chemin améliorant}
    {
    Un parcours en largeur à partir du sommet S \\
        \eSi{il existe un chemin améliorant entre S et P}
        {
        - on ajoute la valeur du chemin améliorant au flot maximum \\
        - on met à jour les valeurs  résiduelles de chacun des arcs du chemin améliorant
        }
        {
          {On s'arrête}
        }
    }

\end{algorithm}


\begin{algorithm}
\caption{DSATUR}
\Entree{Liste L des sommets du graphe G}
\Sortie{Liste des sommets et leur couleur associée}

L = Ordonner L par ordre décroissant de degrés

S = Sommet de degré maximum dans L
Colorer S avec la couleur 1

\Tq {tous les sommets de L ne sont pas colorés}{
    S_0 = Sommet \ avec \ le \ DSAT \ le \ plus \ important \ dans \ L \ (Si \ égalité \
          prendre \ le \ sommet \ de \ degrés \ maximum) \\

    Colorer \ S_0 \ avec \ la \ plus \ petite \ couleur \ possible \ (absente \ de \ son \ voisinage) \\
}


Retourner la liste des sommets et de leur couleur associée
\end{algorithm}

\begin{algorithm}
\caption{Fonction de calcul de DSAT}
\textit{DSAT(S)= nombre de couleurs différentes dans les sommets adjacents à S}
\end{algorithm}

\begin{algorithm}
\caption{Inversion de graphe}
\Entree{Matrice M d'adjacence}
\Sortie{Matrice W d'adjacence du graphe inversé}
\Tq{Toute la matrice M n'a pas été parcourue}{
        Remplacer 1 par 0 \\
        Remplacer 0 par 1 sauf sur la diagonale}
        
\textit{Renvoyer W matrice inverse de M}

\end{algorithm}

-------
\begin{algorithm}
\caption{PERT}
\Entree{nom et durée des tâches, contraintes d'antériorité} 
\Sortie {graphe avec date au plus tôt et au plus tard, tâche et chemin critique} 

\Pour{tous sommet s}{\Pour{tout sommet t}{Si s est un antécédent de t, ajouter t aux successeurs de s.}}  

Créer le graphe G.

Créer un sommet "départ" et lui affecter la valeur 0 comme date au plus tôt. 

\Pour{toute tâche t n'ayant aucune contrainte d'antériorité}{Créer le sommet t et un arc a allant de départ vers t.\\
    Affecter à a la durée de t.\\
    La date au plus tôt de t est égale à la durée de t.} 

\Tq{il existe une tâche non traitée}{\Pour{ toute tâche t ayant une unique contrainte d'antériorité sur une tâche x déjà traitée}{ Créer le sommet t et un arc a allant du sommet x vers s.\\
        Affecter à a la durée de t.\\
        La date au plus tôt de t est égale à la date au plus tôt de x plus la durée de t.}
 
    
   \Pour{ tout tâche t ayant plus d'une contrainte d'antériorité sur des tâches x1, x2, ..., xn toutes déjà traitées}{\eSi{la postériorité du xi (avec \textit{1 $\leq$ i $\leq$ n}) ayant la valeur au plus tôt la plus élevée est égal à 1}{Créer le sommet t et un arc allant du sommet xi ayant la date au plus tôt la plus élevée au nouveau sommet.\\
            Créer un arc fictif entre chaque sommet antérieur et le sommet xi.\\
            Affecter à a la durée de t.\\
            La date au plus tôt de t est égale à la date au plus tôt de x plus la durée de t.} 
            { Créer un nouveau sommet x1 + x2 ... + xn = SS.\\
            Créer un arc fictif entre chaque sommet antérieur et le sommet SS.\\
            Affecter au nouveau sommet SS la valeur de la date au plus tôt du sommet xi le plus grand.\\
            Créer un nouveau sommet t et un arc a allant du sommet SS au sommet t.\\
            Affecter à a la durée de t.\\
            La date au plus tôt de t est égale à la date au plus tôt de SS plus la durée de t.}}}


Créer un sommet "arrivée", créer un arc fictif entre tous les sommets n'ayant aucun successeurs et ce sommet.\\
Affecter au sommet arrivée la valeur de la date au plus tôt la plus élevée de ses prédécesseurs, comme date au plus tôt et au plus tard.\\
\Pour{chaque sommet s} {
    la date au plus tard de s est égale à la date au plus tard la moins élevée de ses successeurs moins la valeur de l'arc les rejoignant.
}

\Pour{tout sommet s}{\Si{la date au plus tôt est égale à la date au plus tard}{s est une tâche critique}}
falu

\end{algorithm}

\begin{algorithm}
\caption{DSATUR}
\Entree{Liste L des sommets du graphe G}
\Sortie{Liste des sommets et leur couleur associée}

L = Ordonner L par ordre décroissant de degrés

S = Sommet de degré maximum dans L
Colorer S avec la couleur 1

\Tq {tous les sommets de L ne sont pas colorés}{
    S_0 = Sommet \ avec \ le \ DSAT \ le \ plus \ important \ dans \ L \ (Si \ égalité \
          prendre \ le \ sommet \ de \ degrés \ maximum) \\

    Colorer \ S_0 \ avec \ la \ plus \ petite \ couleur \ possible \ (absente \ de \ son \ voisinage) \\
}


Retourner la liste des sommets et de leur couleur associée
\end{algorithm}

\begin{algorithm}
\caption{Fonction de calcul de DSAT}
\textit{DSAT(S)= nombre de couleurs différentes dans les sommets adjacents à S}
\end{algorithm}

\begin{algorithm}
\caption{Inversion de graphe}
\Entree{Matrice M d'adjacence}
\Sortie{Matrice W d'adjacence du graphe inversé}
\Tq{Toute la matrice M n'a pas été parcourue}{
        Remplacer 1 par 0 \\
        Remplacer 0 par 1 sauf sur la diagonale}
        
\textit{Renvoyer W matrice inverse de M}

\end{algorithm}