Présentation 26-02

# Présentation 26-02 ###### tags: `présentation` [TOC] ## Organigramme (Sébastien) ### Légende 1: clics et touches du clavier 2: affichage (pixel)/rien 3: sommets selectionnés, arcs selecttiones, graphe, choix des interactions, taille du graphe 4: graphe, ?rien dans la supression? 5: nom du fichier, graphe 6: nom du fichier, message de validation (supression, suavegarde) ou contenu du fichier 7: graphe, sommet du graphe, message de demande d'actions 8: liste de sommets, sous-graphe, graphe, message de validation de l'operation (ex: si on le nombre chromatique du graphe) 9: graphe modifié, 10: graphe #### Entrées/Sorties - Les entrées/soties (2) de l'application sont transmis au travers des clics et des touches des claviers. Les inputs seront traités dans l'interface graphique. - Dans l'autre sens l'interface graphique (1) ne renvoie rien (ou elle affiche les pixels a l'écran). #### IG -- Gestion de graphe - Les messages entre l'interface graphique et la gestion de graphes transmettent dans le sens IG -> Gestion de Graphe (3) les sommets, les arcs, les intercations souhaitées selectionés par l'utilisateur. La taille d'un graphe pour la création. - Dans l'autre sens (4), le systeme de gestion de graphe renvoie le graphe souhaité, la liste de sommets, arcs, interactions selectionées. Elle peut aussi renvoyer des messages de validation. Bien évidement, les graphes crées a partie du systeme de gestion de graphe sont renvoyer. #### IG -- Gestion de fichiers - Les messages entre l'interface graphique et la gestion de fichiers transmettent dans le sens IG -> Gestion de fichiers (6), le nom du fichier, un message de validation dans le cas de la supression et de la sauvegarde, le contenu du fichier pour sauvegarder un graphe. - Dans l'autre sens (5), on utilisera le contenu du fichier afin de le charger dans l'IG, donc le graphe. #### IG -- Opérations sur les graphes - Les messages entre l'interface graphique et les opérations sur les graphes transmettent dans le sens IG -> Opérations sur les graphes (7), le graphe a traité, les sommets, les arcs, choix d'interactions. - Dans l'autre sens (8), on utilisera donc le graphe, sous graphe, liste de sommets, stable, clique. #### Gestion de graphe -- Opérations sur les graphes Les informations transitants entre ces deux modules sont des graphes essentiellement, en effet lors de l'utilisation des opérations sur les graphes nous pouvons être amené a modifier un graphe ou créé un autre graphe induit du graphe passer en paramètre. ## Modules (Alexandre) ### Manipulation de base #### Entrée/Sortie ##### Entrée : Matrice de taille NxM, Sommet S de la matrice M ##### Sortie : Adresse d'un sommet, matrice d'adjacence, matrice d'incidence, codage de Prüfer, Matrice de taille NxM #### Fonctionnalités - Création d’une matrice d’adjacence(simple, complet, biparti, cycle…) Prend en entrée la taille de ma matrice NxN. ##### Métrique: - Vérifier si la matrice générée correspond au type de graphe demandé - Complet : Matrice d'adjacence sans poids symétrique - Biparti : Matrice bipartie - Commun : Matrice qui respecte la logique des matrices d'adjacence et les futurs règles de stockage. - Modification de matrice Prend en entrée la matrice d’adjacence du graphe et le numéro du sommet N. Au niveau de la ligne et colonne N x N, on renvoie l’adresse de l’objet sommet. ##### Métrique: - Si les valeurs ont changé comme souhaité - Si nouveaux sommets la taille de la matrice a changée. - Suppression de matrice ##### Métrique: - Si y'a plus la matrice c'est bon - Duplication de matrice Instancie une nouvelle matrice M2 à partir de la matrice M1 passée en argument. ##### Métrique: - Si la matrice retournée est identique à celle d'origine - Conversion d'un arbre en codage de Prüfer ##### Métrique: - Vérifier la correspondance entre la matrice d'adjacence mère et la liste de Prüfer - Vérifier que cet algorithme s’exécute dans le cas où le graphe est un arbre. - Conversion d’un arbre en codage de Prüfer et inversement ##### Métrique: - obtention d'une liste ou d'une matrice en fonction du résultat demandé. Conversion inverse, vérifier si on obtient le même arbre. --- ### Opérations sur les graphes (Algorithmes choisis) (Amandine) #### Matrice d'incidence : *O(n2)* - Conversion d'une matrice d'adjacence en matrice d'incidence : Prend en paramètre une matrice d'adjacence M1 et permet de la convertir dans la matrice d'incidence M2 équivalente. ##### Métrique: - Vérifier la correspondance entre la matrice d'adjacence mère et la matrice d'incidence fille #### Degrés entrants et sortants : *O(n2)* Calcul le degré pour 1 sommet et appel dans interface logiciel pour calculer tout les sommets. ``` a b c d e f a 0 1 1 1 0 1 b 1 0 0 1 0 1 c 0 0 0 1 1 0 d 1 0 1 0 1 0 e 0 1 1 1 0 1 f 1 0 0 1 0 0 ``` Pour b par exemple on parcours de position(b) de 0 à n et de 0 à n position(b) ``` Algorithme (Qui affiche le degrès entrant/sortant/nb_voisin total) --------------------------------------------------------------- Entrée : k = position(sommet), MA[n][n] (matrice d'adjacence) succ = 0; pred = 0; nb_voisin = 0; Pour i de 0 à n | Si (MA[i][k] == 1) | | succ++; | | nb_voisin++; | Fin Si | Si (MA[k][i] == 1) | | pred++; | | nb_voisin++; | Fin Si Fin Pour Afficher(succ); Afficher(pred); Afficher(nb_voisin); ``` Sinon appliquer l'algo pour tout les sommets et mettre les résultats dans une matrice (N x 3) (ou plus suivant les informations à sauvegarder) #### Liste de voisins : *O(n)* *Entrée : Graphe / Sortie : liste de voisins (txt)* Calcul pour 1 sommet et appel dans interface logiciel pour tout les sommets. #### Plus court chemin : *Entrée : Graphe, sommet de départ / Sortie : Matrice de sommets pères* - Tout les sommets : Floyd-Warshall car il permet de trouver l'ensemble des plus courts chemins. *O(n3)* - Un sommet vers tout les autres : Ford-Bellman pour les plus courts chemins d'un somet vers tous les autres car contrairement à Dijkstra il permet les poids négatifs sur les arcs. *O(n2)* - Entre deux sommets : Ford-Bellman *O(n2)* **(Guillaume)** *Floyd-Warshall* ``` Matrice Adjacence Matrice Sommet Père(not Floyd-Warshaliser) a b c d e f a b c d e f a 0 1 1 1 0 1 a 0 b c d 0 f b 1 0 0 1 0 1 b a 0 0 d 0 f c 0 0 0 1 1 0 => c 0 0 0 d e 0 d 1 0 1 0 1 0 d a 0 c 0 e 0 e 0 1 1 1 0 1 e 0 b c d 0 f f 1 0 0 1 0 0 f a 0 0 d 0 0 ``` ``` Algo Floyd-Warshall ------------------------------------------------------------------------------- Entrée: MA[n][n] (matrice d'adjacence),MP[n][n] (Matrice Sommet Père) W = MA (si MA[i][j] == 0 alors W[i][j] = infini, si i==j alors W[i][j] = 0 ) Pour k allant de 1 à n | Pour i allant de 1 à n | | Pour j allant de 1 à n | | | si (W[i,j] > W[i,k] + W[k,j]) | | | | W[i,j] = W[i,k] + W[k,j] | | | | MP[i,j] = MP[i,k]; | | | Fin Si | | fin pour | fin pour fin pour ``` *Ford-Bellman* ``` Entrée : (G,w,s) Pour tout sommet v appartenant à V | [v] = +infini | pi[v] = NULL d[s] = 0, L = {S} Tant que L ! 0 ``` #### Arborescence de poids minimal : *O(EV)* *Entrée : Graphe (Matrice) / Sortie : Sous-graphe (matrice)* L'Algo D'Edmonds a été choisis, il fournit une arborescence couvrante de poids minimal. C'est l'algorithme le plus communément utilisé. E : ensemble des arcs, V : ensemble des sommets #### Anti-arborescence couvrante : *O(NEV)* *Entrée : Graphe (Matrice) / Sortie : Sous-graphe (matrice)* A ce jour, il n'a pas été trouvé d'algorithmes permettant d'obtenir directement une anti-arborescence couvrante. Nous proposons d'inverser les arcs à partir de l'arborescence de poid minimal. #### Coloration de graphes : *O(n 2)* (Camille) *Entrée : Graphe / Sortie : Matrice 2D avec la couleur de chaque sommets.* DSATUR donne une coloration moins mauvaise que Welsh-Powell dans le pire des cas (par-exemple si le graphe G a la structure de couronne à n sommets). ``` Algorithme : DSATUR -------------------- - Trier les sommets par ordre de degrés décroissants - Attribuer au premier sommet A une première couleur - Choisir le sommet avec le plus couleurs différentes dans les sommets adjacents et le colorer avec la plus petite couleur possible - En cas d'égalité choisir le sommet de degré maximum ``` #### Stables : *O(n 2)* DSATUR car le problème de stable est en réalité un problème de coloration. #### Cliques : *O(n 2)* Algo invertion graphe + DSATUR #### Optimisation des tâches : Algorithme qui reprends la méthode PERT Entrée: | Code de la tache | Durée | Antériorités | |:----------------:|:-----:|:------------:| | A | 12 | - | | B | 15 | - | | C | 17 | A, B | | D | 8 | B | - Création du sommet Départ - On parcours la liste des sommets, si il n'y a pas de contraintes d'antériorités, on créé un arc entre Départ et ce sommet, avec pour valeur la durée. On ajoute la valeur au plus tôt pour le nouveau sommet avec pour valeur la durée - Si il y a une antériorité, on créé un arc entre le sommet antérieur et le nouveau sommet, avec pour valeur la durée. On ajoute la valeur au plus tôt qui est égale à la somme de la durée et de la valeur au plus tôt du sommet antérieur. - Si il y a plusieurs antériorités, on créé un arc entre le sommet antérieur ayant la plus grande valeur au plus tôt et le nouveau sommet. On ajoute la valeur au plus tôt qui est égale à la somme de la durée et de la valeur au plus tôt du sommet antérieur. On créé des arcs informels de valeur 0 qui partent de tous les sommets antérieurs non utilisés vers le sommet antérieur utilisé. - Une fois qu'on arrive au dernier sommet, sa valeur au plus tard est égale à sa valeur au plus tôt - Pour chaque sommet, sa valeur au plus tard est égale au minimum de la valeur au plus tard de ses successeurs moins la valeur de l'arc. #### Gestion des flots : *O(n m2)* (Hugo) Edmond-Karp est l'algorithme choisis puis-ce que celui ci permet de trouver le chemin le plus court contrairement à l'algorithme de Ford-Fulkerson qui qui donne un résultat qui n'est pas forcément optimal. ``` Algorithme : Edmond-Karp ------------------------- 1) procédure principale initialisation : flot nul. répéter fin=parcours ( ) si fin=1, alors retourner f m=∞ u=t tant que u s m=min(m,c(p[u],u) u=p(u) fin tant que u=t tant que u s f(p[u],u)= f(p[u],u)+m c(p[u],u)=c(p[u],u)-m c([u,p[u])=c(u,p[u])+m u=p[v] fin tant que fin répéter 2) procédure parcours initialisation: pour tous les sommets p(u)=-1 Q=[s] tant que Q ∅ u= dépiler Q pour chaque v tel que (u,v) arête, c(u,v)>0 et p(v)=-1 p[v]=u si v=t, alors retourner 1 ajouter v à la fin de Q fin pour fin tant que retourner 0. ``` #### Problème du voyageur de commerce : *O(n2)* Algorithe de Little car il résout le problème en temps linéaire par rapport aux nombre de sommets entrés. De plus, l'algorithme de Chistofides donne une solution approximative et se résout en compléxité cubique. ``` Algorithme : Little -------------------- maxi = +inf s[racine] = ville de depart calculer e[racine] visiter la racine visiter un noeud n : SI e[n] <= maxi ALORS SI s[n] != ville de depart ALORS POUR toutes les liaisons s[n] -> v possibles calculer le regret de s[n] -> v FIN POUR soit s[n] -> v une liaison de regret maximal r créer les fils v et V de n s[v] = v calculer e[v] visiter v s[V] = s[n] e[V] = e[n] + r visiter V SINON maxi = max[maxi, e[n]) FIN SI FIN SI ``` #### Chaine Eulérienne *Entrée : Graphe / Sorie : liste (vide ou non) + algo si liste vide* ``` Eulérien G(X,Y) ---------------- parcours eulerien= principe: on marque tous les arcs utilisé si tous marqué alors chaine eulerienne sinon on insert un cycle dans cette chaine ``` #### Chaine hamiltonienne *Entrée : Graphe / Sortie : liste (vide ou non) + algo si liste vide* --- ### Algorithmes non choisis (Théo) #### Calcul du plus court chemin *Dijkstra* ``` 1 function Dijkstra(Graph, source): 2 3 create vertex set Q 4 5 for each vertex v in Graph: 6 dist[v] ← INFINITY 7 prev[v] ← UNDEFINED 8 add v to Q 10 dist[source] ← 0 11 12 while Q is not empty: 13 u ← vertex in Q with min dist[u] 14 15 remove u from Q 16 17 for each neighbor v of u: // only v that are still in Q 18 alt ← dist[u] + length(u, v) 19 if alt < dist[v]: 20 dist[v] ← alt 21 prev[v] ← u 22 23 return dist[], prev[] ``` #### Coloration de graphe et nombre chromatique - Welsh et Powell *O(n\*m)* ou *O(n ln(n) +m)* ``` - Trier les sommets par ordre de degrés décroissants - Attribuer au premier sommet A une première couleur - suivre la liste en attribuant la même couleur au premier sommet B non adjacent à A - Continuer à parcourir la liste en attribuant la couleur aux sommets non adjcents à ceux déjà colorés - Lorsque la liste est finie prendre une deuxième couleur et repartir du début de la liste ``` - Algorithme glouton *O(n\*m)* ``` On regarde l'ensemble des couleurs déjà attribuées aux voisins de s et on en déduit le plus petit entier naturel qui n'appartient pas à cet ensemble ``` #### Stables - Stable maximale *O(n^2) ``` Entrées : un graphe G = (X, A), non orienté Sorties : un stable maximal S de G Pour chaque sommet x de G faire marque[x] ← FAUX S←∅  tant qu'il existe un sommet x sommets non marqué faire S ← S ∪ {x}  marque[x] ← V RAI  pour chaque y ∈ Γ(x) faire marque[y] ← V RAI Retourner S ``` - Luby's Algorithm *O(log n)* ``` Algorithm 1 MIS(G=(V,E)) Maximal Independant Set 1: Add all singletons to I 2: I ← ∅ 3: Chaque v choisit une valeur aléatoire P (v) ∈ [0, 1] 4: Si P(v) < P(w), Pour tous w ∈ N(v) then 5: Ajoutez v into I 6: Fin Si 7: V ′ = V \ (I ∪ N(I)) 8: E′=E\Bords(I ∪ N(I)) 9: Return I ∪ MIS(G′ = (V ′, E′)) ``` - Random-priority parallel algorithm *O(n)* ``` Initialisez I, un ensemble vide While V est non vide , Pour chaque noeud v Faire : Selectionner un nombre aléatoire r(v) dans [0,1] et l'envois. à ses voisins; Si r(v) est plus petit que les nombres de tous les voisins de v, alors v s'insère dans I, se retire de V et en informe ses voisins. Si v a appris qu'un de ses voisins est entré dans I, alors v se retire de V. Return I. ``` #### Gestion des flots *Ford-Fulkerson : Complexité de *O(n m2)** ``` Algorithme Ford-Fulkerson (Graphe G) Entrée : Un graphe G = (V,E). Sortie : Un graphe avec le flot. Exécution : Initialiser le flot f à 0 sur tous les arcs Tant qu'il existe une chaîne améliorante δ = min (min (Capacité restante sur les arcs sortants), min (flot sur les arcs entrants)) augmenter f de δ sur les arcs sortants de la chaîne. diminuer f de δ sur les arcs sortants de la chaîne. Fin tant que; Fin Exécution; ``` ``` Algorithme recherche chaîne améliorante Entrée : Graphe G = (V, E) avec son flot Sortie :liste des arcs de la chaîne améliorante Exécution : Z est une file vide Marquer s (sommet de départ) et le mettre dans le file Tant que Z non vide Si le premier sommet de Z, x, est marqué retourner la chaîne améliorante Fin Si retirer x de Z Pour tout successeur y de x faire si y est non marqué et le flot est inférieur à la capacité alors marquer y et le mettre dans Z Fin si Fin pour Pour tout prédécesseur y de x faire Si y est non marqué et le flot est positif alors Marquer y et le mettre dans Z Fin si Fin pour Fin tant que Fin exécution ``` #### Le problème du voyageur de commerce - Explication du problème Le problème du voyageur de commerce est le problème suivant: pour un réseau de sommets donné avec des arcs pondérés, comment effectuer le cycle le plus court possible ? - Algoritme de Chirstofides En pseudo-code : - Calculer un arbre couvrant de poids minimal T de G ; - Soit I l'ensemble des sommets de degré impair dans T, calculer un couplage parfait M de poids minimum dans le sous-graphe induit par les sommets de I ; - On définit un multigraphe H à partir des arêtes issues de M et T ; - Trouver un cycle eulérien dans H (H est eulérien car il est connexe et tous les sommets sont de degrés pairs) ; - Transformer le cycle eulérien en un cycle hamiltonien en supprimant les éventuels passages en double sur certains sommets. c'est un algorithme de complexité cubique. Cependant, il est important de préciser que c'est un algorihme d'approximation. C'est à dire que l'on s'approche du résultat de manière assez importante sans pour autant y parvenir. ### Interface graphique (Salsa) #### Entrée/Sortie ##### Entrée : Les interactions de l'utilisateur ##### Sortie : L'écran #### Fonctionalités - Affichage global ##### Métrique: - Avoir un graphe affiché - Ne pas avoir de sommets et d'arrêtes qui se croisent sur l'interface ( x,y) ( donc pas de graphes superposés ) - ##### Algorithme d'affichage Pour afficher un graphe correctement lorsque ce dernier n'est pas dessiné par l'utilisateur il est nécessaire d'utiliser un algorithme de placement pour permettre que le graphe reste lisible avec un grand nombre de sommets. Pour cela nous utiliserons un algorithme de force dont voici le principe : 1. Tous les nœuds se repoussent entre eux, respectant le principe des aimants. Plus les noeuds sont éloignés, moins ils se repoussent. 2. Les liens servent de ressort entre deux nœuds. 3. À chaque passe de l'algorithme, on applique la somme des forces sur chacun des nœuds. On déplace ces nœuds jusqu'à trouver un état stable. Plusieurs algorithmes utilisant le principe de force existe, pour ne citer qu'eux : - Fruchterman Reingold, de complexité n2 qui est considéré comme obsolète - Yifan Hu, spécialisé dans les petits graphes (moins de 1000 sommets) de complexité `O(N*log(N))` - Force Atlas 2 de complexité `O(N*log(N))` qui permet de gérer des graphes allant de 1 à 1 000 000 de sommets Nous avons choisis Force Atlas 2 comme algorithme car il permet de gérer un grand nombre de sommets sans être trop complexe. - Possibilité de déplacer/ajouter/supprimer un arc ou un sommet : Possiblité de selectionner un arc ou un sommet avec le curseur et de le faire glisser. ##### Métrique: - Vérifier graphiquement que l'arc ou le sommet ont été correctement déplacé. - Vérifier graphiquement que l'arc ou le sommet ont été correctement supprimé. - Vérifier graphiquement que l'arc ou le sommet ont été correctement ajouté. - Vérifier graphiquement que l'arc ou le sommet selectioné par le curseur est correct. - Afficher les valeurs (poids des arcs, nom des sommets) ##### Métrique: - Vérfier graphiquement que les nom des sommets et que le poid des arcs soient afficher - Selection d'un ou de plusieurs sous graphe (minimum 2 sommets et un arc) ##### Métrique: - Vérifier que le/les sous graphe(s) selectionné(s) graphiquement soient effectivement ceux qui sont récupérés - Changer les valeurs (poids, nom des sommets) ##### Métrique: - Vérifier qu'après modification, les noms et poids soient changé. - Test d'algo de superposition ##### Métrique: - Vérifier que les graphes ne se superpose pas en un seul sommet, vérifier la lisibilité des graphes - Selectionner un algorithme et l'appliquer sur un graphe ou un sous graphe ##### Métrique: - Vérifier que les résultats renvoyés correspondent à l'algorithme appliqué sur le graphe. - Afficher les résultats de l'algorithme ##### Métrique: - Sous forme de liste - Sous forme de sommets colorés - Sous forme de tableau ### Système de gestion de fichier (Vincent) #### Entrée/Sortie ##### Entrée Nom de fichier, graphe, chemin du fichier ##### Sortie Signal de validation, Informations contenue dans le fichier (graphe, position des sommets et arcs, informations sur les arcs, information des sommets) #### Fonctionalités - Sauvegarde normale: Permet de créer un fichier de sauvegarde avec le graphe passé en paramètre et d'écraser le précédent fichier de sauvegarde. On cherche à créer des fichiers qui restent lisible sans passer par le logiciel. ##### Métriques - Vérifier qu'il soit au bon format - Vérifier qu'il écrase au bon endroit (dans le cas de la sauvegarde simple) - Vérifier que la sauvegarde écrit correctement le fichier (respect la syntaxe) - Suppression: Permet de supprimer un fichier dont le chemin est passé en paramètre ##### Métriques - Vérifier le chemin - Vérifier la suppression du fichier - Chargement: Permet de charger le ou les graphes présent dans le fichier dont le chemin est passé en paramètre et de les afficher. ##### Métriques - Vérifier que le fichier soit au bon format - Vérifier la validité du chemin - Vérifier la cohérence des données chargées et de celle présente dans le fichier. - Enregistrer sous : Permet de sauvegarder un fichier sur un nouveau chemin ##### Métriques - Vérifier qu'il soit au bon format - Vérifier qu'il écrase au bon endroit (dans le cas de la sauvegarde simple) - Vérifier que la sauvegarde écrit correctement le fichier (respect la syntaxe) #### Contraintes pour les fichiers: - Nombre de sommets négatifs - Taille du fichier - Format du fichier (nombre de colonne / ligne )