Compte rendu du Devoir de Graphe
Contents
1. WER RIES Devoir de G Fi ssel We tn f FE j WI 7 Deplacer Sommet eil Sauvegarde Chargement ex05 Kosaraju Sharir Liste Kosaraju Sharir Matrice 5 10 3 W A S 6 01 23 ES C Windows system32 cmd exe java Fenetre D 0671172009 ED ECET ETE 067117200 HS Panneau java 96 11 2609 d Sommet class 86 11 2649 7 2 6 Sommet java 0671172009 Sommet java 0671172009 7 02 test 199 852 octets 640 octets libres sufI dans l ordre ZC 12 11 Les composantes fortement connex appartenant a la composante appartenant composante appartenant composante appartenant composante appartenant composante appartenant composante 6 E a D G sufI dans l ordre lt 11 12 3 5 6 CE E e s sont Lii 121 31 Graphe r duit du Graphe Figure1 Figure2 Nous voyons que nous obtenons bien le m me graphe r duit que lors du TD Nous avons ainsi pu valider notre programme gr ce a plusieur exemple de reduction de Graphe comme celui ci Nous avons aussi laisser les diff rents affichage quand nous effectuons le DFS et lorsque nous trouvons les composantes connexes l utilisateur pourra alors refaire lui m me la r duction du Graphe la main et l identique A noter que l utilisation de Kosaraju Sharir Matrice donne le meme resultat que Figure2 E R sultats obtenues sur les diff rentes instances Les instances que nous pr sentons sont des graphes propos s dans l nonc du T2. Arc Sommet depart Sommet arrivee Sommet getDepart void setDepart Sommet depart Sommet getArrivee void setArrivee Sommet arrivee Page 8 Devoir de Graphe Compte Rendu 2009 2010 3 La classe Graphe La classe Graphe est le c ur de notre application C est cette classe qui permet de cr er des graphes et de les manipuler afin de calculer leur DFS ou bien encore de d terminer leurs composantes fortement connexes gr ce l algorithme de Kosaraju Sharir C est ainsi que la classe graphe comporte de nombreux attributs et fonctions permettant ces traitements En premier lieu cette classe est compos e de plusieurs constructeurs diff rents afin de permettre l instanciation d un graphe partir de plusieurs structures de donn es diff rentes Ainsi on peut cr er un graphe partir d un doublet liste de sommets liste d arcs ou bien alors partir d un triplet matrice d adjacence nombre de sommets nombre d arcs Le constructeur qui utilise les listes cr era galement la matrice d adjacence associ e afin de pouvoir utiliser indiff remment l algorithme de Kosaraju Sharir sur les listes ou les matrices En outre lorsqu un graphe est initialis partir d une matrice les arcs et sommets sont galement cr s afin de pouvoir utiliser l algorithme de Kosaraju Sharir utilisant les listes ou utilisant les matrices N anmoins pour am liorer la complexit en espa
3. 2 appartenant a la composante 3 Page 23
4. Kosaraju Sharir correspond la taille de la matrice d adjacence Cette taille ne d pend uniquement du nombre de sommets et est ind pendante du nombres d arcs On a alors une complexit en taille de O n C Conclusion Il existe plusieurs fa ons d impl menter l algorithme de Kosaraju Sharir Selon les structures de donn es choisies les complexit s en temps et en espace sont affect es imm diatement Ainsi l impl mentation par matrice d adjacence en n est lourde Mais si elle peut faire gagner du temps lors de l ex cution de l algorithme elle peut tre tr s utile Il faut alors choisir la structure de donn es la plus adapt s l utilisation que l on souhaite faire de l algorithme Ainsi si le nombre d arcs est relativement faible par rapport au nombre de sommets il sera pr f rable d utiliser l impl mentation par listes En revanche si le nombre d arcs est relativement lev par rapport au nombre de sommets malgr le co t en espace il sera pr f rable d utiliser l impl mentation par matrice dont la complexit est ind pendante du nombre d arcs Page 14 Devoir de Graphe Compte Rendu 2009 2010 IV Mode d emploi D monstration Pas pas nous allons expliquer comment utiliser notre application Commen ons par la cr ation d un graphe A Cr ation d un graphe 1 Directement par impl mentation On peut cr er un graphe en utilisant les matrices d adjacences ou les lis
5. de la lecture de fichier d instances notamment nous avons rencontr s un probl me de droit Il tait alors impossible d ouvrir un fichier sur le disque de l ordinateur Ce probl me de droit venait du fait qu une Applet est cens e la base tre une application de type web Or en java une application de ce type doit tre sign e par son cr ateur L utilisateur client doit alors accepter le certificat cr e par cette signature afin d autoris l applet enregistrer ou lire des fichiers sur le disque du client Nous avons donc du convertir notre application afin de la faire fonctionner avec des JFrame Le souci a alors t r solu 2 Probl me d d indexage des sommets Typiquement les algorithmes en pseudo code comportent des tableaux indic s de 1 n Or en programmation imp rative les tableaux sont indic s de 0 n 1 Il a donc fallu faire tr s attention lors de l impl mentation des diff rents algorithmes bien manipuler les indices Dans notre architecture les sommets ont des indices de 1 n Mais les tableaux de pr fixes et de suffixes eux sont indic s de 0 n 1 Ainsi nous avons tach de faire attention bien changer de base lorsque nous passons d une structure une autre Et malgr toute notre volont il y a eu des erreurs faites lors de l impl mentation qu il a fallu retrouver Ceci a t fait et aujourd hui l application est fonctionnelle Page Devoir de Graphe Compt
6. graphe r duit parcours complet de la liste des arcs avec imbrication d une boucle parcourant la liste des composantes fortement connexes en pire cas tous les sommets sont isol es donc n tours de boucles qui est en O mn il vient une complexit totale de l ordre de O m2n O n O mn soit O m2n O mn 2 Complexit en espace La complexit en espace est relativement simple d terminer En effet si on suppose qu on a n sommets et m arcs alors on a une liste de sommets de n l ments On a galement une liste de m arcs Sachant qu un arc est compos de deux sommets on a une complexit en taille de O n O m B Impl mentation avec l utilisation de la matrice d adjacence 1 Complexit en temps Pour cr er le graphe r duit d un graphe courant partir de sa matrice d adjacence c est la fonction KosarajuSharirMatrice qui est appel e Elle se d compose en deux appels de fonctions savoir DFSMatrice et DFSMatricelnverse La premi re reprend dans les grandes lignes le m me principe que DES Elle appelle remplirCMatrice qui est en O n parcours de la matrice compl te pour d terminer les degr s sortant de chaque sommet Puis nitialiseNum fait n tours de boucles nouveau afin d initialiser le tableau num Ensuite DFSMatrice va faire n tours de boucles En pire cas elle fera n appels exploreMatrice Cette fonction va alors appeler tant que le sommet courant poss de de
7. 15 2 Par l interface Homme Machine ss 15 3 Par cr ation d un fichier d instance ss 15 B Manipulation des fichiers d Instances 15 1 Mise En forme sissies nina eai e aieiaiei aiia ls 15 2 Bouton Chargement iii 16 3 Bouton ET EE 16 C Les boutons d appel Kosaraju Sharir sssssssssssssssrsesrnssrnssrssrrssrnssrrssrnssrnssresssenssrns 17 1 Bouton parlist ssiciereansneear EES EES 17 Devoir de Graphe Compte Rendu 2009 2010 2 D E Soo a N Bo ton par Matrice E 17 Exemple d utilsati h sessies a raaa E a 17 R sultats obtenues sur les diff rentes instances 19 LL RS de ale g e RE 20 Instance e TE EN Instance e EE ER INSTANC EXO E 23 Page 4 Devoir de Graphe Compte Rendu 2009 2010 I Introduction Dans le cadre de notre formation d ing nieur nous sommes amen s suivre un cours d algorithmique des graphes A travers ce cours nous abordons des notions inh rentes aux graphes Nous sommes alors amen s manipuler des graphes afin de d terminer entres autres le plus court chemin entre deux sommets ou bien de d terminer les composantes fortement connexes Ainsi notre application permet de d terminer ces composantes Nous allons donc voir comment cela est fait en trois parties Nous commencerons par d crire le code de notre application Ensuite nous d terminerons la comp
8. D3 Ils sont reconnaissables par num ro d exercice Page 19 Devoir de Graphe Compte Rendu 2009 2010 1 Instance exo2 Lei z Deplacer Sommet Le Sauvegarde Chargement exo2 Kosaraju Sharir Liste Kosaraju Sharir Matrice 0 i i d g T t Deplacer Sommet Sauvegarde Chargement exo2 Kosaraju Sharir Liste Kosaraju Sharir Matrice CH C Windows system32 cmd exe java Fenetre num dans l ordre pre dans l ordre suf dans l ordre numI dans l ordre 2 sufl dans l ordre 2 sufl dans l ordre ZC 8 i 2 Les composantes fortement conn appartenant la composante appartenant la composante appartenant la composante appartenant la composante Ou Om x D KK la composante la composante la composante appartenant appartenant appartenant ans on sn en sn D DDR ODANA d h t a a a a appartenant a la composante a a a Page 20 Devoir de Graphe Compte Rendu 2009 2010 2 Instance exo5B Cette instance est diff rente de l instance exo5 utilis e dans la partie du mode d emploi En effet cette instance n utilise que le nombre de sommets d arcs et la matrice d adjacence pour tre cr e Voici le r sultat il est le m me qu avec l utilisation de exos Deplacer Sommet Sauvegarde Chargement exo5B _ Kosaraju Sharir Liste Kosaraju Sharir Matrice Deplacer Sommet b Sauvegarde Ch
9. Ing nieurs NOUS A RIS Galil e Institut Galil e INFO2 FOURNIER St phane ROUSSET Yohan Compte rendu du Devoir de Graphe Ann e 2009 2010 Devoir de Graphe Compte Rendu 2009 2010 Page 2 Devoir de Graphe Compte Rendu 2009 2010 Table des mati res Ee et EE 5 Il D scription dt ole ged enreeeges eee ease ege 6 A Description du probl me sisi sise sesssessrness 6 B liegt EE 6 C Architecture de application 8 1 larclasse Sommet terasse en sienne retient lentes te 8 ER 8 3 La class E LEE 9 4 Les classes Fenetre et Panneau ss 10 D Probl mes ege 11 1 Probl me au niveau de Applet 11 2 Probl me d indexage des sommets ss nssesnnssenenssennrsserenssernssernnssennnnsernnssennssssennns 11 II Aralysede la Compl xit 5 2 ee Seege el entendus 12 A Impl mentation par listes de sommets et d arcs 12 1 Cepmpleytteepnt nnfe Ae gedee red e Sie Edge ETAAEEE Ra 12 2 Compl xit en ES egeEedee eege nn tried en ENNEN ENEE Ee 13 B Impl mentation avec l utilisation de la matrice d adjacence ssssssssssessessssesee 13 1 Complexit en TEMPS insist cesse denses entendons enetieeneseirenenee seen raissa 13 2 Compl xit en Space EE 14 C Conclusion nn entente E te ei iiine 14 IV Mode d emploi D monstration 15 A Cr ation d up Stapbhe ee geee ie 15 1 Directement par impl mentation
10. argement ex05B Kosaraju Sharir Liste Kosaraju Sharir Matrice 6 f1 2 REI a composante a composante appartenant a composante appartenant a composante appartenant composante appartenant a composante Devoir de Graphe Compte Rendu 3 Cette instance utilise le bouton Kosaraju Sharir Matrice Deplacer Sommet Instance exo6 Sauvegarde Chargement SA Ge 2009 2010 Kosaraju Sharir Liste Kosaraju Sharir Matrice el Sauvegarde Lues L Chargement exo6 Kosaraju Sharir Liste Kosaraju Sharir Matrice 2 11 RM ooo D w 1 010 13 12 11 e EOR num dans l ordre pre da l ordre suf dans l ordre numI dans l ordre sufl dans l ordre sufI dans l ordre Les composantes lappa enant appartenant appartenant appartenant appartenant appartenant Page composante 3 composante composante composante 22 Devoir de Graphe Compte Rendu 2009 2010 4 Instance exo7 Deplacer Sommet v Sauvegarde Chargement ee Kosaraju Sharir Liste Kosaraju Sharir Matrice g Deplacer Sommet e Sauvegarde Chargement exo7 S Kosaraju Sharir Liste Kosaraju Sharir Matrice num dans l ordre pre dans l ordre suf dans l ordre nuni dans l ordre fI dans l ordre E fI dans l ordre CS Les composantes fortement connex appartenant a la composante 1 appartenant a la composante
11. au plus une fois un arc reliant deux sommets si le premier est marqu comme visit l arc ne pourra donc plus tre emprunt On alors une complexit pour DES en O m n gt Ensuite la liste des arcs doit tre invers e Cela compte donc pour un parcours complet de cette liste pour en cr er une nouvelle invers Cela co te m it rations gt Enfin la fonction DFSinverse est appel e Cette proc dure poss de une premi re boucle qui fait n tours de boucle A chaque it ration elle r cup re le successeur de plus grand suffixe Ceci coute un parcours sur la liste des sommets n tours de boucle Or chaque tour de boucle l algorithme verifie si le sommet appartient la liste des sommets marqu s La fonction de recherche du sommet non marqu s de plus suffixe est donc en Of n Si le sommet n a pas t explor num x 0 la fonction appelle la proc dure explorelnverse qui est le pendant de explore pour les arcs invers s Or un sommet ne peut tre explor qu une fois Donc en pire cas il peut y avoir m appels explore autant d appels qu il existe de successeurs et donc d arcs On a alors une complexit pour le DFS sur les arcs invers en O mn Page 12 Devoir de Graphe Compte Rendu 2009 2010 Pour r sumer la complexit de l algorithme de Kosaraju Sharir utilisant les listes d l ments est de O m n O m O mn En outre lorsqu on ajoute la complexit de la cr ation du
12. ce on peut simplement modifier le code de fa on n utiliser que l algorithme de Kosaraju Sharir sur les listes si le graphe est initialis avec des listes et que l algorithme de Kosaraju Sharir sur les matrices si le graphe est instanci partir d une matrice Dans un deuxi me temps une s rie d accesseurs ont t impl ment s afin de pouvoir diter ou r cup rer des valeurs importantes d un graphe tels que la liste des sommets la liste des arcs la matrice d adjacence un arc i j particulier de la matrice etc Ensuite diff rents algorithmes sont impl ment s afin de d terminer les composantes fortement connexes du graphe instanci Ainsi deux fonctions principales nomm es grapheReduit et grapheReduitMatrice permettent de renvoyer le graphe des connexit s fortes Comme leur nom peut permettre de voir grapheReduit s appliquera en utilisant les listes de sommets et d arcs tandis que grapheReduitMatrice utilisera la matrice d adjacence du graphe courant La fonction grapheReduit appelle dans un premier temps la fonction Kosaraju Sharir afin de d terminer les composantes connexes La fonction Kosaraju Sharir appelle quant elle appelle le DFS sur le graphe courant elle inverse les arcs puis appelle la fonction DFSinverse Les fonctions d exploration explore et explorelnverse sont impl ment es afin d tre utilis es par DFS et DFSinverse De la m me mani re la fonction grapheReduitMatr
13. e Rendu 2009 2010 HI Analyse de la Complexit Notre application permet d utiliser deux types d impl mentation de l algorithme de Kosaraju Sharir Nous verrons tout d abord la complexit de la version qui utilise les listes de sommets et d arcs Enfin nous verrons l impl mentation par matrice d adjacence A Impl mentation par listes de sommets et d arcs l algorithme de Kosaraju Sharir utilisant les listes d arcs et de sommets est impl ment travers la fonction KosarajuSharir Cette fonction permet applique les trois tapes vues pr c demment cf II B Ainsi nous allons analyser la complexit en temps et en espace de cet algorithme en analysant chacune de ses trois tapes 1 Complexit en temps Les trois tapes de l algorithme tant appliqu es la suite leurs complexit s s additionnent On notera n le nombre de sommet et m le nombre d arc du graphe On a alors gt DFS est la fonction qui permet de remplir les tableaux d entiers suf num et pre En outre elle initialise le tableau c des degr s sortant de chaque sommet ce qui correspond m tours de boucles Dans DFS chaque sommet est explor au plus une fois une fois qu un sommet est explor il est en quelque sorte marqu a Il ne sera plus visit En outre pour r cup rer le sommet explorer une fonction annexe est n cessaire cXiemeSuccesseur Cette fonction est en O m Par ailleurs chaque arc est explor aussi
14. e est aussi effectu e v Inversion de l orientation des arcs On cr alors un graphe invers Gi X U avec X l ensemble des sommets de G et U les arcs de G invers v Ex cution du DFS sur G en partant successivement du sommet non visit de plus grand indice dans la num rotation suffixe l algorithme d finissant la fonction DFS ainsi que la fonction auxiliaire d exploration explore appel par DFS sont ceux du cours Des fonctions suppl mentaires ont t n cessaires pour l impl mentation telle que la fonction d terminant le degr sortant de chaque sommet Page 6 Devoir de Graphe Compte Rendu 2009 2010 Algorithme du DFS DFS graphe G ke 0 fi Pour i 0 n Faire c i d i Fin Pour Pour i 0 n Faire num i 0 Fin Pour Pour i 0 n Faire Si num i 0 Alors k amp k 1 num i amp k prefixe i amp k explore G i Fin Si Fin Pour Fin DFS Algorithme de explore Proc dure explore graphe G sommet i Tant que c i gt 0 Faire S lectionner j le n i successeur de i n i amp c i 1 Si num i 0 Alors k ck 1 num j amp k prefixe j amp k explore G j Fin Si Fin Tant que suffixe i amp f fe NN Fin explore Page 7 Devoir de Graphe Compte Rendu 2009 2010 C Architecture de l application L application est compos e de plusieurs classes qui vont tre d finies dans cette partie Pour chacune d elles nous verrons les f
15. ication s utilise en lan ant l application comme suit java Fenetre Ceci aura pour effet de lancer l interface graphique et du m me coup l application de manipulation des graphes Cette interface permet alors par le biais de l utilisation du menu d roulant dans la partie sup rieur gauche l utilisateur de e Ajouter un sommet au graphe courant par simple clique e D placer un sommet pr alablement cr er par glisser d poser e Ajouter un arc entre deux sommets par un clique sur le premier sommet d part et un second clique sur le second sommet arriv e e D placer un graphe complet d un point un autre par glisser d poser e Effacer simplement le graphe courant Cette partie du devoir tant consid r e comme bonus nous n en d taillerons pas d avantage le code Celui ci est n anmoins accessible dans les fichiers impl mentant les classes Les algorithmes de trac de graphes sont situ s dans le fichier Panneau java N anmoins un exemple d utilisation de l interface est disponible la fin de ce rapport dans le mode d emploi Page Devoir de Graphe Compte Rendu 2009 2010 D Probl mes rencontr s Lors de l impl mentation de notre algorithme nous avons rencontr s certains probl mes qui ont pu tre r solu temps 1 Probl me au niveau de l Applet Nous avons eu un probl me lors de la cr ation de l Applet En fait lorsque nous avons commenc la cr ation de l criture et
16. ice cr er dans un premier temps la matrice d adjacence du graphe courant Ensuite elle appelle DFSMatrice avant d appeler DFSMatricelnverse Ces deux fonctions permettent alors de d terminer les connexit s fortes du graphe courant Dans les deux cas les fonctions permettant de cr er des graphes r duits parcourent la liste des arcs du graphe courant Pour chaque arc analys elle regarde si les sommets de d parts et d arriv es ne sont pas dans la m me composante fortement connexe Si tel est le cas alors il existe Page 9 Devoir de Graphe Compte Rendu 2009 2010 un arc reliant deux composantes fortement connexes diff rentes Cet arc est m moris et servira l affichage du graphe r duit Lorsque le traitement est termin la fonction renvoi un graphe qui a pour sommets la liste des indices des composantes fortement connexes et contenant un objet String dans lesquelles sont m moris s les sommets relatifs la composante en question N anmoins grapheReduitMatrice ne parcours pas directement une liste d arcs Elle doit en effet parcourir toutes la matrice la recherche des arcs Les fonctions de sauvegarde et de chargement ainsi que de traitement fichier seront trait plus tard cf IV B 4 Les classes Fenetre et Panneau Impl ment es dans les fichiers Fenetre java et Panneau java ces classes permettent de cr er une interface graphique afin de faciliter la manipulation de la classe Graphe Ainsi l appl
17. lexit des diff rents algorithmes impl ment s Enfin nous expliciterons l utilisation de notre application travers divers exemples Page 5 Devoir de Graphe Compte Rendu 2009 2010 UL Description du Code Avant toute chose il est important de pr ciser le probl me que permet de r soudre notre application A Description du probl me Le probl me r solu par notre application est celui de la recherche des composantes fortement connexes d un graphe orient Dans la suite on utilisera la d finition suivante des graphes G X U o X est l ensemble des sommets de G et U l ensemble de ses arcs Une composante fortement connexe est un ensemble de sommet o il existe pour chaque sommet appartenant une composante C un chemin vers un autre sommet de C Un exemple d utilisation des composantes fortement connexes est entres autres celui de la d termination des sens interdit dans un quartier En effet il est important de pr voir l avance qu on puisse atteindre malgr les sens interdit un point B partir d un point A B Algorithmes Un algorithme qui permet de d terminer les composantes fortement connexes d un graphe est celui de Kosaraju Sharir Ce dernier se d compose en trois tapes v Ex cution du DFS Deep First Search Recherche par Profondeur d Abord sur le graphe courant La fonction renvoi l ordre dans lequel les sommets ont t visit s La num ration suffixe et pr fix
18. on d un graphique par la matrice d adjacence Exemple Nombre de sommet 8 Nombre d arc 10 arc 1 2 are 1 3 arc 2 arc 2 5 arc 4 3 arc 4 5 arc 5 6 arc 5 7 arc 7 6 arc 8 7 atrice d adjacence 0 1 1 0 0 O O0 O 0 0 011 0 0 0 0 O0 0 0 O0 O0 0 0 0 0 1 0 1 O0 O0 O 00000110 00000000 00000100 00000010 2 Bouton Chargement Le bouton chargement de l interface graphique permet de r cup rer le contenu du champ texte situ cot de celui ci On appel alors la fonction chargement de la class Graphe Cette fonction permet de r cup rer le contenu du fichier dans une chaine de caract res Celle ci est utilis e comme argument de la fonction traitementFichier La fonction traitementFichier utilise un String Tokenizer C est dire que le fichier sera analys par mots On pourra alors r cup rer le nombre de sommets et le nombre d arcs afin d initialiser les listes aux bonnes valeurs La fonction peut alors adopter deux comportements diff rents Soit le fichier contient la liste d arcs du graphe Les arcs sont alors r cup r s et reconstruits Si la liste d arcs n est pas contenue dans le fichier un second comportement est adopt Celui ci permet alors de cr er les arcs du graphe partir de la matrice d adjacence 3 Bouton Sauvegarder Le bouton sauvegarde de l interface graphique permet de r cup rer le conten
19. onctions qu elle comporte ainsi qu une br ve explication pour chacune de ces fonctions Pour de plus amples informations il est recommand de consult les fichiers sources comment s fournis dans l archives 1 La classe Sommet La classe Sommet est la classe g n rique qui permet d utiliser des sommets dans notre classe Elle permet de m moriser pour un sommet donn diverses informations importantes Elle contient alors l indice du sommet courant deux entiers x et y qui sont les positions du sommet dans l espace deux dimensions et ventuellement un objet de type quelconque d o l utilisation de la g n ricit G n ralement la classe est utilis e pour cr er des sommets pouvant contenir des String Cela sera utile lors du dessin du graphe r duit notamment class Sommet lt T gt T objetContenu int indice int x y Sommet int i Sommet int i int x int y Sommet int i T o void setObjetContenu T objetContenu int getX int getY void setX int nx void setY int ny boolean equals Object obj String toString 2 La classe Arc La classe Arc utilise la classe Sommet pr c demment d finie Un arc est alors compos de deux sommets repr sentant les sommets de d part et d arriv e Cette classe est utilis e par la classe Graphe dans le but de m moriser les arcs d un graphe donn class Arc lt Sommet gt Sommet depart Sommet arrivee
20. s successeurs la fonction cXiemeSuccesseurMatrice afin de d terminer le prochain sommet explorer Cette fonction fait alors tr s exactement n tours de boucles Mais comme chaque sommet n est explor qu une fois il ne peut y avoir plus de n appels explore La complexit de DFSMatrice est donc en On Ensuite contrairement l impl mentation par listes il n est pas n cessaire d inverser les arcs En effet il suffit de lire la matrice en intervertissant les lignes et les colonnes Enfin KosarajuSharirMatrice va appeler la fonction DFSInverseMatrice afin de d terminer les composantes fortement connexes du graphe courant De la m me mani re cette fonction va initialiser le degr sortant de chacun des sommets On est donc en Ofn Ensuite cette fonction va parcourir le graphe invers en partant successivement du sommet de plus grand suffixe Pour r cup rer ce sommet on a besoin de parcourir tous les sommets On a alors n tours de boucles Pour chaque sommet non visit la fonction explorelnverseMatrice va tre appel e En pire cas elle peut tre appel n fois par le DFS invers Or cette fonction peut s appeler r cursivement si le sommet est non marqu On est alors en O n Donc la complexit de DFSinverseMatrice est en O ni Page 13 Devoir de Graphe Compte Rendu 2009 2010 En pire cas on est donc O n O n soit O n 2 Complexit en espace La complexit en espace de
21. se Graphe Comme vu dans la classe Graphe ci dessus La fonction grapheReduitMatrice appelle dans un premier temps la fonction KosarajuSharirMatrice afin de d terminer les composantes connexes La fonction KosarajuSharirMatrice appelle quant elle appelle la fonction DFSMatrice sur le graphe courant puis appelle la fonction DFSInverseMatrice a Les fonctions d exploration a exploreMatrice et explorelnverseMatrice a sont impl ment es afin d tre utilis es par DFSMatrice et DFSInverseMatrice On assigne alors le nouveau graphe r duit au graphe courant en ajoutant la liste des composantes fortement connexes aux noms des nouveaux sommets D Exemple d utilisation Afin d illustrer nos dires nous joignions un exemple d utilisation de notre programme Nous afin donc choisit d initialiser un Graphe semblable a celui vu dans le TD3 exercice n 5 Figure Page Devoir de Graphe Compte Rendu 2009 2010 em EE Sauvegarde Chargement InomFichier Kosaraju Sharir Liste Kosaraju Sharir Matrice Graphe du TD3 exercice n 5 Figure 1 Une fois le Graphe initialis gr ce l un des differents modes fichier d instance impl mentation ou par l IHM Nous cliquons donc sur le bouton Kosaraju Sharir Liste Une fois la fonction execut e nous obtenons le resultat ci dessous Figure2 Page 18 Devoir de Graphe Compte Rendu 2009 2010
22. t sur Effacer Une fois la fen tre vid e il devra se positionner dans l onglet ajouter sommet a du menu d roulant Un sommet est alors cr et positionn l endroit ou l utilisateur rel che la souris Une fois le minimum de deux sommets cr s il pourra alors cr er des arcs en se mettant dans l onglet ajouter arc a du menu d roulant Selon le m me principe il cliquera d abord sur le sommet de d part de l arc puis il s lectionnera le sommet d arriv Pour cela le programme utilise une fonction selectionne qui permet de trouver le sommet le plus proche de l ou a cliqu l utilisateur 3 Par cr ation d un fichier d instance Un graphe peut tre cr partir d un fichier texte Celui ci doit avoir une forme sp ciale afin que le programme puisse cr er le graphe que l utilisateur souhaite C est ce que nous allons voir dans la partie suivante B Manipulation des fichiers d instances 1 Mise en forme Le fichier d instance est format comme suis Nombre de sommet n Nombre d arc m Page Devoir de Graphe Compte Rendu 2009 2010 arc num ro du sommet de d part num ro du sommet d arrive Matrice d adjacence L utilisateur mettra donc dans un fichier les informations ci dessus Il pourra alors charger le fichier par le biais de l interface graphique L utilisateur pourra aussi choisir entre l utilisation du type arc dans le fichier ou alors le choix de constructi
23. tes de sommets et d arcs directement en le codant Ainsi des exemples de graphes ont t impl ment s dans le fichier Fenetre java partir de la ligne 425 Seul l exercice 5 du TD3 est d comment et est donc cr l instanciation de la fen tre Mais on peut alors simplement modifier le programme afin d utiliser les graphes impl ment s L utilisateur peut m me s il le d sire cr er le graphe de son choix en cr ant des sommets qu il ajoutera une ArrayList de Sommet et des arcs qu il ajoutera une ArrayList d Arc Une fois cela fait il ne lui reste plus qu a construire le graphe de son choix L utilisateur prendra le soin n cessaire indicer ses sommets de 1 n pour n sommets Les indices des sommets doivent tre deux deux diff rents et doivent tre indic s de fa on continue pas de 1 2 4 etc L utilisateur peut aussi directement cr er la matrice d adjacence Il suffira d appeler le constructeur de Graphe ad quat en n omettant pas de fournir le nombre de sommets et le nombre d arcs contenus dans sa matrice 2 Par l interface Homme Machine Afin que l utilisateur puisse facilement cr er un graphe sans avoir recourt au changement du code source nous avons mis en place un syst me interactif travers l utilisation de l interface graphique Ainsi l utilisateur pourra cr er un graphe directement a partir de l interface Pour cela il devra d abord effacer le graphe existant en se positionnan
24. u du champ texte situ cot de celui ci On appel alors la fonction sauvegarder de la class Graphe avec Page 16 Devoir de Graphe Compte Rendu 2009 2010 comme argument la chaine de caract res du champ texte Le programme va alors cr e un fichier du nom de la chaine de caract res Puis le programme qui contient la trame du fichier d instance va alors compl ter les l ments vides gr ce aux listes de sommets et d arcs du graphe La matrice d adjacence sera cr e gr ce un appel la fonction creeMatrice de la classe Graphe C Les boutons d appel Kosaraju Sharir 1 Bouton par liste Une fois se bouton appel on va appeler la fonction grapheRedu it de la classe Graphe Comme vu dans la classe Graphe ci dessus La fonction grapheReduit appelle dans un premier temps la fonction KosarajuSharir afin de d terminer les composantes connexes La fonction Kosaraju Sharir appelle quant elle appelle le DFS sur le graphe courant elle inverse les arcs puis appelle la fonction DFSInverse Les fonctions d exploration explore et explorelnverse sont impl ment es afin d tre utilis es par DFS et DFSInverse On assigne alors le nouveau graphe r duit au graphe courant en ajoutant la liste des composantes fortement connexes aux noms des nouveaux sommets Z Bouton par matrice Une fois se bouton appel on va appeler la fonction grapheReduitMatrice de la clas
Download Pdf Manuals
Related Search