# Explications Algorithmes

###### tags: `CR`
[TOC]

### Chaînes euleriennes (Amandine)
Passe par tout les Arcs du Graphe
*Renvoie* : Chaine affichée dans la console

Depuis le sommet de départ (0 ou celui sans prédécesseur) visite et marque tout les Arcs. Reviens en arrière si plus de chemin possible.

### Chaînes hamiltoniennes (Amandine)
Passe par tout les Sommets du Graphe
*Renvoie* : Chaine affichée dans la console

Depuis le sommet de départ (0 ou celui sans prédécesseur) visite et marque tout les Sommets. Reviens en arrière si plus de chemin possible.

### Arborescence et Anti-Arborescence (Amandine)
**Arborescence** : Sommet depuis lequel on peux accéder à tout les Sommets
*Renvoie* : Graphe formant l'arborescence (arbre)

**Anti-Arborescence** : Sommet depuis lequel on peux accéder à tout les Sommets en inversant les Arcs
*Renvoie* : Graphe formant l'anti-arborescence (arbre)

### Calcul des degrés d’un sommet (Amandine)
Calcul degré entrant + Calcul degré sortant
*Renvoie* : Degrés sur la console

### Calcul des plus courts chemins (Amandine)
**Floyd-Warshall** : Plus court chemin entre tout les Sommets du Graphe
*Renvoie* : paire de Matrices, Matrice de poids minimumpour aller d’un Sommet à un autre et la 2ème Matrice indique le prochain Sommet à atteindre pour effectuer le plus court chemin d’un Sommet.

- Matrice parent = prochain Sommet à atteindre (Matrice des successeurs pour chaque Sommet)
- Matrice de poids = Poids de chaque chemin. Initialisé à INFINI (pas de chemins), valeur des Arcs pour les chemins direct, et 0 (diagonales)

***
**Ford-Bellman** : Plus court chemin entre un sommet et tout les autres

Renvoie : Paire de vecteurs : les chemins pour aller du Sommet S vers les autres sommets du Graphe et la distance entre le Sommet S et les autres Sommets du Graphe.

Initialise les Sommet à INFINI et prédécesseur à -1. Vérifie qu'il n'y a pas de cycle négatif. Si il y a un Arc, calcul d'une nouvelle valeur inférieure et push dans une file.

### Recherche de la connexité (Amandine)
Vérifie si le graphe est connexe et donc pas de Sommet isolé. Tout les Sommets sont égalemment atteignavle par tout les autres Sommets.
*Renvoie* : Si le graphe n'est pas connexe

### Ordonnancement (PERT) (Amandine)
**Interface Graphique** : Fenêtre pour rentrer (id, étiquette,durée, taches antérieur)
-> valide + calcul postérité

**Calcul postérité** : Vérifie que toutes les tâches existent et pas de cycle
-> PERT

**PERT** : Lie chaque tâche avec un Arc vers sa/ses tâches antérieures et calcul date au plus tôt et date au plus tard

*Arc* = tache (durée, id)
*Sommet* = fin de la tâche, map = date + tôt, date + tard et tâche critique

- Date au + tôt = Durée de la tâche + date au plus tôt des sommets antérieurs
- Date au + tard = date + tard des Sommets postérieurs - la valeur de l'Arc entre les deux (Parcours en sens inverse des Arcs)
- Tâche critique = date au + tôt et au + tard égales donc pas de retards

***
* Pour un Arc avec plusieurs prédécesseurs : Choisis celui avec la date au + tards la plus faible.
* Si une tâche à plusieurs tâches comme prédécesseurs : Sélectionne celle avec la date au + tôt la plus élevée comme départ. Relie la tâche courante par un Arc fictif avec ses autres prédécesseurs.
* Présence d'un Sommet de Départ, Sommet de Fin et d'Arcs fictifs.
* Si pour une tâche pas de Successeurs : Arc fictif vers Fin.
* Fin : La date au + tôt la plus élevée est égale à la date au + tard.

************
### Coloration de graphe (Vincent)
entrée : Graphe
sortie: couleur du sommet(chaque case du vecteur contient la couleur du sommet)

Prend tous les sommets, et on les tries par ordre décroissant de degrées
Prend celui avec le plus grand degré -> Coloré avec premiere couleur
Vecteur comprenant l'id de tous nos sommets -> Sert de suivi pour la coloration

Tant que tous les sommet ne sont pas coloré -> Regarde les couleurs présente ainsi que le nombre sur les voisins du sommet non coloré
Choisi le sommet avec plus grand nombre de voisins colorées
Colorie le sommet avecc la plus petite couleur possible
### Détection de stables (Vincent)
entrée: Matrice
sortie: Stables du graphe

On appelle la fonction coloration d'abord
On trie les sommets en fonction de leur couleur
Dans chaque sous vecteur -> Liste d'id des sommets en fonction de leur couleur
### Détection de cliques (Vincent)
entrée: Matrice
sortie: cliques du graphe

Même fonction que pour les stables avec le graphe inverse

### Calcul des voisins d’un sommet (Vincent)
entrée: Matrice, Sommet
sortie: Liste des voisin du sommet

On fait un parcours de la matrice en récupérant la liste des voisins du sommet pris en entrée

### Résolution du problème du postier chinois (Vincent)
entrée : Matrice
sortie: Chaine eulérienne s'il existe (et bien une chaine, pas un cycle)

D'abord on effectue le calcul de Floyd Warshall pour obtenir la distance des plus courts chemins entre chaque pair de sommet de la matrice

On regarde la parité de tous les sommet du graphe

Cet fonction nous permet de trouver le plus court chemin passant par toutes les arêtes du graphe

### Résolution du problème de Little (Vincent)
entrée: Liste de Sommet, Matrice
sortie: Chemin le plus court entre ces sommets

Problème du voyageur de commerce : Trouver le plus petit chemin possible entre à partir d'une liste de sommet

On procède à une réduction de la matrice afin d'avoir des valeurs nulles sur chaque lignes et colonnes

On calcul le regret de chaque valeurs nulles (plus petite valeur de la ligne + colonne)

On prend le regret max trouvé, puis on créer un graphe binaire avec :
Sommet gauche : Valeur du sommet parent + réduction de la matrice + regret de l'arc choisi

Sommet droit = Valeur sommet parent + calcul de la nouvelle matrice sans l'arc choisi

- (A faire vérifier par Hugo et Guillaume quand algo fini)

### Gestion des flots (Vincent)
Algo Edmond Karp (parcours en largeur)
entrée : graphe ainsi que l'id du sommet puit et source
sortie: taille du flot du graphe

On procède à un parcours en largeur afin de trouver tous les flots partant de la source vers le puit tant qu'il trouve un chemin possible

Ensuite nous recherchons des chaines améliorantes
En procédant au même exercice avec la matrice résiduel

### Algo de Placement (Alexandre)
On compare les coordonnés de 2 sommets (2 boucles imbriqués) et on calcule une force de repulsion et d'attraction selon la distance qui les separe. la force d'attraction est calculé seulement quand les sommets on un arc qui les lies (ne fonctionne pas)
on fait ensuite le total de ces forces et on les applique au vecteur de direction du sommet a vers le sommet b.
On fait ça pour tout les sommet et on recommence jusqu'as ce qu'il n'y est plus de sommet qui se superpose