---
# System prepended metadata

title: Affectation des algo
tags: [organisation]

---

# Affectation des algo
###### tags: `organisation`

## Algorithmes
- Suppression/Duplication/Matrice
- Conversion adjacence -> incidence
- calcul degrés entrant/sortant
- Liste de voisins
- Plus court chemin
- Arborescence de poid minimum
- Anti arborescence
- Coloration
- Stables/cliques
- PERT
- Gestion des flots
- Problème du voyageur de commerce
- Chaines eulériennes
- Chaine hamiltonienne

## Membre du groupe
### Guillaume
- Arborescence de poids minimum
Entrée : Graphe G
Pour chaque Sommet
    Prendre le plus petit poids d'arc entrant et le soustraire à chaque poids d'arc entrant
Fin pour
Créer un nouveau Graphe contenant tous les sommets et les arcs de poids 0 (si plusieurs arcs de poids 0 pour un sommet choisir arbitrairement)

Sortie : une Arborescence (Graphe)

- Anti arborescence
Inversion du sens des arcs + application de l'algo d'arborescence.
### Camille
- PERT

```
Algorithme: PERT
Entrée: 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 
    Pout tout sommet t
        Si s est un antécédent de t, ajouter t aux successeurs de s.
    Fin Pour
Fin Pour

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.
Fin Pour

Tant qu'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.
    Fin Pour
    
    Pour tout tâche t ayant plus d'une contraînte d'antériorité sur des tâches x1, x2, ..., xn toutes déjà traitées
        Si la postériorité du xi ayant la valeur au plus tôt la plus élevée est égal à 1, alors 
            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.
        Sinon 
            Créer un noueau 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.
    Fin Pour
Fin Tant que

Créer un sommet "arrivée", créer un arc fictif entre tous les sommets n'ayant aucun successeurs et ce sommet.
Affecter à arrivée la valeur de la date au plus tôt la plus élevée, 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 moin
    s la valeur de l'arc les rejoignant.
Fin Pour
        
```


### Hugo
- Gestion des flots


### Salsa
- Liste de voisins ( compléxité au dans le pire des cas O(Nb de sommets - 1))
        
        Entrées:  Sommet S, Graphe G
        Sorties: Liste de voisin du Sommet S
        Variable: Liste

        On initialise une liste L a NULL.

        Pour toutes les colonnes de la ligne de sommet S de la matrice d'adjcence :
            Si il existe un arc entre le sommet S et un sommet de la matrice:
                On ajoute à la liste L, le nom du sommet de la colonne.
            FinSi
        FinPour
        Return Liste L
            

### Sébastien

- Calcul degrés entrant/sortant

        Entrées: Sommet S, Graphe G
        Sorties: Degrés entrant, Degrés sortant, Nombre de voisins
        Variable: Successeur, Predecesseur, Nombre de voisins

        On initialise le successeur et le predeceseur a 0, ainsi que le nombre de voisin a 0.

        Pour toutes les ligne et les colonnes de la matrice d'adjcence jusqu'a la fin.
            Si il existe un arc entre le sommet S et un sommet de la matrice:
                On augmente le nombre de voisin pour le sommet ainsi que le nombre de successeurs.
            Fin Si
            
            Si il existe un arc entre un sommet de la matrice et le sommet S
                On augmente le nombre de voisin pour le sommet ainsi que le nombre de predecesseurs.
            Fin Si
        Fin Pour

- Conversion adjacence -> incidence

        Entrées: Matrice d'ajacence MA
        Sortie: Matrice d'incidence MI de taille n*m avec m le nombre d'arc dans le graphe et n le nombre de sommet

        Pour toutes les lignes de MA
            Pour toutes les colonnes de MA
                Si il existe un arc entre le sommet S et un sommet voisin T
                    On ajoute un arc dans la matrice d'incidence
                    Alors on met a 1 entre S et T
        2            Et -1 entre T et S
                Fin Si
            Fin Pour
        Fin Pour



### Alexandre
- Plus court chemin
Floyd-Warshall:  
    Entrée: Matrice d'adjacence A correpondante au graphe, Matrice pere MP
    Sortie: Matrice avec les distances et la matrice pere MP remplie
```
On copie la matrice MA dans la matrice MA'
pour tout les sommets K de la matrice
	pour toute les lignes S de la matrice 
		pour toute les colonnes T de la matrice
			On compare les chemins direct (entre S et T)
			et les chemins utilisant k comme intermediaire (S-K et K-T).
			Si le chemin intermediaire est plus court que le chemin
			direct on le remplace dans la matrice MA' et on K devient 
			le sommet pere de T dans la matrice MP
		Fin pour
	Fin pour
Fin pour 
```

Ford-Bellman: 
	Entrée: Le graphe G sans cycle absorbant, un sommet choisis, les poids des arcs.
	Sortie: Tableau des distance(TD) entre S et tout les autres sommets T. Tableau des chemins(TC) entre S et tout les autre sommet T.
```
Pour tout les sommets T
	On met la case du TD a l'infini
Fin pour

On met la case S du TD a 0
On repete un nombre de fois egal au nombre de sommet
	Pour tout les arcs (T, U) de G
		La distance dans le TD a la case U est egal au minimum entre 
		la valeur deja presente dans cette case et la valeur dans la
		case T + le poids de l'arc (T, U).
	Fin pour
	Si il n'y a eu aucun changement de valeur lors du dernier passage
	on arrete l'algorithme.
Fin repetition


```
	

### Théo
- Coloration
```
Algorithme : 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

Tant que 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)
Fin Tant que

Retouner la liste des sommets et de leur couleur associée
```

Fonction de calcul de DSAT :
```
  DSAT(S)= nombre de couleurs différentes dans les sommets adjacents à S
```


- Stables/cliques
    - Stables : On utilise DSATUR
    - Clique : On inverse le graphe et on applique DSATUR
    ```
    Algorithme : Inversion de graphe
    Entree : Matrice M d'ajacence
    Sortie : Matrice W d'adjacence du graphe inversé
    ---------------------------------------------------------------------
    Parcourir la matrice M:
        Remplacer 1 par 0
        Remplacer 0 par 1 sauf sur la diagonale
    
    Renvoyer W matrice inverse de M
        
    ```

### Amandine
- Chaine eulérienne

```
Algorithme : EULERIEN
Entrée : Sommet S, Graphe G
Sortie : Liste de sommets formant une chaine Eulérienne (vide ou non)
---------------------------------------------------------------------
Si S est isolé
    Retourne le circuit sous forme de liste.
Fin Si

Sinon
    Sauvegarde du circuit qui contient le sommet S.
    Sauvegarde du graphe G' qui prends la valeur de G sans le circuit qui contient le sommet S.
   
    Parcours des sommets du circuit qui contient le sommet S :
        Concaténation du circuit qui contient le sommet S + ALGORITHME EULERIEN sur G' et le sommet parcouru.
Fin Sinon

```

- Chaine hamiltonienne O(n2) ?
```
Algorithme : HAMILTONIEN
Entrée : Graphe G
Sortie : Liste de sommets formant une chaine Hamiltonienne (vide ou non)
Variable : Sommet S
------------------------------------------------------------------------

Parcours de la matrice du graphe horizontalement et verticalement :

    Si tout les sommets sont marqué
        Retourne la liste de sommets.
    Fin Si
    
    Si S est isolé et tout les sommets ne sont pas marqués 
        Retourne une liste vide.
    Fin Si

    Si S non marqué
        Marque le sommet.
    Fin Si
    
    Si le sommet S+1 parcouru horizontalement est successeur du sommet S sur lequel on se trouve verticalement et non marqué
        Marque le sommet successeur S+1.
        Concaténation de la liste de sommet avec ce même sommet S+1.
        Continue le parcours de la matrice depuis ce sommet S+1.
    Fin Si
    
Fin Boucle
```

### Vincent
- Problème du voyageur de commerce.
```
Algorithme : LITTLE
Entréee : Graphe G, Arbre A
Sortie : Arbre binaire avec le coût total pour chaque feuille de l'arbre
Variable : entier T
------------------------------------------------------------------------

Si la matrice du graphe est nulle
    Renvoie A
    
Sinon
    Parcours de la matrice du graphe horizontalement et verticalement :

    Si il n'y a pas d'arc de poids nul à partir du sommet
        Cherche l'arc de poids le plus faible et on soustrait son poids à tous les arcs partant de ce sommet
        Ajoute son poids dans T
    Fin Si
    
    Racine de A prend la valeur T
    
    Pour chaque arc de poids nul dans notre matrice
        Calcul du regret associé (Ajout du poids le plus faible de la ligne et de la colonne autre que l'arc sélectionné)
    Fin Pour
        
    On sélectionne l'arc avec le plus grand regret
    
    Création de deux feuilles
    Fils gauche prend la valeur du parent plus le regret (cas trajet exclu)
    Fils droit prend en récursif l'algorithme de Little avec l'arbre A et la matrice du graphe sans l'arc choisi (cas trajet inclus)
    Fin Si
```

###  Truc a ne pas oublier dans le cdc:
- Manque certaines complexité
- Faire la conclusion
- voir les info sur les modules (a appronfondir potentiellement)
- 