You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Bastien 70450730cf update urls 2 years ago
doc import du wiki en tant que readme 3 years ago
doc-images Dossier pour les images 7 years ago
Bellmanford.cpp bellmanford compile mais a tester 7 years ago
CourtChemin.c ease enter the commit message for your changes. Lines starting 7 years ago
README.md update urls 2 years ago
automate_algo.png add 7 years ago
dijkstra.cpp Erreurs « bêtes » dans le calcul du poids. 7 years ago
dj.c Merge branch 'master' of ssh://ssh.confais.org/srv/git/graphes 7 years ago
djLast.c pas a pas 7 years ago
mvc.cpp Ajout de la licence 7 years ago
pap.c pas a pas 7 years ago
parcours_profondeur.cpp Merge branch 'master' of ssh://ssh.confais.org/srv/git/graphes 7 years ago
petri.png add 7 years ago

README.md

Rapport de Projet Technologique 2011-2012

Simulation Algorithmes Graphes

Groupe de projet C

Rendu en latex : https://git.confais.org/Bastien/graphes/raw/master/doc/rapport.pdf

Résumé

Au cours de ce projet nous nous sommes attelés à la conception d’un logiciel de gestion des GRAPHES. Après une première ébauche du cahier des charges, nous avons peaufinés celui à travers quelques réunions avec notre encadrant. Une fois la cahier des charge définis clairement nous nous sommes dont attaqués à la partie programmation. Ayant choisi de coder en C++, chacun a pu, à son rythme, assimiler les nouveautés de ce langage qui diffère du Java récurent dans notre cursus. Nous avons tout d’abord commencé par faire les bases, comme conseillé par notre encadrant afin de ne pas nous lancer sur de mauvaises pistes. Nous avons ensuite rajouté des fonctionnalités, ce qui a permis à notre programme d’avoir constamment une version fonctionnelle et nous a évité de rester bloqué. Cette partie nous à permis de peaufiner notre approche de la programmation, car nous n’avions pour la plupart jamais eut l’occasion de nous attaquer à de «gros» projet associant de nombreuses fonctionnalités et surtout plusieurs personnes. Nous avons dû apprendre à écrire du code lisible et réutilisable facilement par les autres membres du groupe, nous avons donc acquis une méthode de travail qui nous à appris à être efficace au sein d’une équipe de développement. En plus du réel intérêt sur le plan technique, ce projet nous à de surcroît permis d’acquérir une meilleur organisation. Il nous a appris à gérer notre temps et à répartir les charges en fonction des préférences et des compétences de chacun. Ces derniers points seront un vrai plus dans les prochaines semaines ou nous seront, pour la plupart, amenés à travailler en groupe au cours de notre stage.

Introduction

Afin d’appliquer les différentes notions enseignées au cours de notre formation à l’IUT Informatique de Nantes, nous nous sommes réunis en groupes et avons travaillés sur un projet informatique. Étendu sur une durée de 5 mois, nous avons eut à le mener à bien en parallèle de nos heures de cours, ainsi qu’à travers certains créneaux aménagés dans l’emploi du temps, le tout sous la tutelle d’un encadrant du corps enseignant.

Notre choix principal s’est porté sur la réalisation d’un logiciel de gestion de graphes, car ce sujet, tout en étant complet, nous laissait une grande liberté dans les choix techniques. Le but étant d’avoir, aux termes de ce projet, un logiciels permettant de créer des graphes à travers l’interface graphique, puis de leur appliquer différents algorithmes, et au final les sauvegarder dans un fichier.

À travers ce rapport nous développerons les différents points important de notre projet. Nous commencerons tout d’abord par énoncer les besoins inhérents et spécifiques au sujet choisi. Ensuite nous entrerons dans une partie plus technique où nous analyserons la conception du programme, à la suite de quoi nous expliciterons notre méthode de développement pour enfin nous diriger vers les différentes solutions techniques et les algorithmes apportés. Afin de compléter cette partie nous parlerons des différents problèmes rencontrés au cours de ce projet. Pour terminer, nous tirerons un bilan pour faire le point sur le résultat obtenu et sa concordance avec le sujet initial.

Agenda des phases du travail

Phases Dates
Réunion de démarrage (avec encadrant) 17 novembre
Analyse du sujet et rédaction du cahier des charges 28 novembre — 16 décembre
Rendu du cahier des charges 16 décembre
Premiers essais d'utilisation de la bibliothèque Graphviz pendant le mois de janvier
Réunion d'avancement du projet avec l'encadrant 20 janvier
Implémentation du pattern modèle-vue-contrôleur 22 janvier
Intégration de la bibliothèque Graphviz dans le modèle 23 janvier
Implémentation d'une vue provisoire afin de « tester » le modèle 28 janvier
Ajout de la possibilité de charger dynamiquement des algorithmes 10 février
Implémentation de la vue définitive 14 février
Réunion d'avancement du projet avec l'encadrant 15 février
Ajout de la documentation dans le programme 16 février — 1 avril
Implémentation de l'algorithme de parcours en profondeur 17 février
Implémentation de l'algorithme de dijkstra 6 mars
Implémentation des algorithmes de simulation 17 mars — 1 avril
Réunion d'avancement du projet avec l'encadrant 21 mars
Rendu du rapport 2 avril
Réalisation de la vidéo de démonstration 3 avril
Rendu capture vidéo de l'application 3 avril
Soutenance 5 avril après-midi

Répartition des tâches

Présentation du besoin

Contexte

Dans le cadre du projet de deuxième année à l’IUT, nous avons réalisé une application permettant de manipuler des graphes. Elle devait comporter une interface graphique dans laquelle on puisse saisir et éditer un graphe. Cette interface devait également permettre d’exécuter des algorithmes sur le graphe, et d’afficher les résultats obtenu.

Nous avons choisi ce projet dans la liste des 23 projets possibles pour deux raisons :

  • c’était l’un des seuls sujets qui laissait la liberté de choix des outils utilisés : langage, bibliothèques et organisation,
  • le sujet était complet du point de vue des techniques à mettre en œuvre.

Énoncé du besoin

Lors de la première réunion, l’encadrant, M. Hue, a précisé en quoi consistait le projet.

L’objectif est de créer un programme qui doit permettre à l’utilisateur :

  • d’entrer un graphe soit :
    • en le saisissant graphiquement,
    • ou en le chargeant depuis un fichier.
  • De sélectionner un algorithme à exécuter et de l’exécuter pas à pas sur le graphe.
  • Il doit être également possible d’enregistrer le graphe.

L’encadrant du projet a également imposé quelques contraintes pour le développement. Il faut que le programme soit développé avec une approche objet, ce qui impose l’utilisation d’un langage orienté objet. La conception du programme doit se baser sur l’architecture Modèle-Vue-Contrôleur. Ici, nous avons approfondi ce que nous avions vu en cours d’IHM, car, dans notre cas, les entités modèle, vue et contrôleur doivent fonctionner indépendamment les unes des autres.

Enfin, le dernier objectif noté à cette réunion est le développement d’un algorithme de simulation qui permet de trouver un chemin le plus court entre deux sommets d’un graphe.

Spécifications

Pendant tout le mois de décembre, nous avons analysé les besoins, et nous en avons déduit les spécifications de l’application. Nous avons alors rédigé un cahier des charges initial pour le projet.

À cet effet, nous sommes partis de l’énoncé du besoin exprimé dans le sujet et des contraintes imposées par l’encadrant.

Analyse et conception architecturale

Le patron de conception Modèle-Vue-Contrôleur

Nous devons baser la conception de l’application graphique sur le patron de conception Modèle-Vue-Contrôleur.

Notre encadrant nous a expliqué le principe de ce patron de conception, et nous avons fait quelques recherches complémentaires pour déterminer la nature précise des signaux échangés par les différentes entités.

À ce moment dans l’année, nous n’avions pas encore abordé le sujet en cours.

Nous nous sommes basés sur la modélisation suivante pour réaliser l’application :

Le modèle sert à stocker les données de l’application et à les manipuler. Dans notre cas, il s’agit principalement de la structure de données représentant le graphe, et de celles manipulées par les algorithmes durant leur exécution.

La vue a pour rôle d’interagir avec l’utilisateur. Elle présente graphiquement les données du modèle, et transmet les actions de l’utilisateur au contrôleur.

Enfin, le contrôleur se place entre la vue et le modèle. Son rôle est de sélectionner la vue et de recevoir les événements qu’elle lui envoie, afin d’appeler des méthodes du modèle. C’est lui qui effectue la synchronisation entre les vues et le modèle, dans le cas où il y a plusieurs vues pour un même modèle.

Modèle MVC

Structure du programme

Structure statique

Dans notre cas, il y a deux contraintes supplémentaires. Chaque entité doit être indépendante et « vivre » toute seule. De plus, notre modèle ne doit pas être figé : en effet, il devra disposer de nouvelles méthodes, au fur et à mesure que l’on charge des algorithmes.

Chaque partie du patron de conception devra donc fonctionner dans un processus léger.

Les signaux à envoyer entre les entités ne seront pas de simples appels de méthodes. En effet, si nous avions procédé ainsi, la méthode serait exécutée dans le processus appelant. Par exemple, si le contrôleur avait fait un appel de méthode sur le modèle, cette méthode se serait exécutée dans le thread du contrôleur.

Nous avons donc décidé que des signaux seraient transmis par une variable partagée entre les deux entités concernées. Chaque entité devra donc observer l’état de cette variable ; l’accès en est protégé par un verrou.

L’application est ainsi divisée en trois parties, chacune fonctionnant dans un thread séparé.

“Le modèle” comporte les données de l’application. Cela correspond au graphe, ainsi qu’au code des algorithmes chargés dynamiquement. Ce modèle comporte également des méthodes de manipulation du graphe, permettant de charger un graphe et de l’éditer.

“La vue” est composée deux threads. Lorsqu’un premier thread entre dans la boucle de GTK, il n’est plus possible d’attendre l’arrivée de signaux. Un deuxième thread est donc nécessaire pour cela. Pendant que le premier thread s’occupe d’afficher la fenêtre, l’autre est en attente des signaux envoyés à la vue. Lorsqu’un signal arrive pour la vue, le thread qui traite le signal peut ensuite rafraîchir l’affichage géré dans l’autre thread.

“Le contrôleur” gère les signaux d’action sur le modèle. Lorsque la vue doit requérir une modification du graphe, par exemple, elle envoie un signal au contrôleur. Son rôle est ensuite d’envoyer les signaux nécessaires au modèle pour effectuer l’action. L’existence du contrôleur permet notamment de gérer plusieurs vues correspondant à un même modèle.

Nous avons également ajouté une classe “documentation” qui permet d’afficher la fenêtre où se trouve les explications du programme. L’objet est créé uniquement lorsque depuis la vue on demande à afficher la documentation. Dans ce cas, on ne passe ni par le modèle ni par le contrôleur. Cette classe contient également une méthode evenement_bouton_compiler qui permet de recompiler le programme depuis le programme lui même.

Enfin nous avons une classe “equation” qui contient des méthodes permettant de trouver les racines de polynômes de degrés 1 à 4. Cela nous permet de résoudre une équation de degré 3 lors de la sélection d’une arête.

On a donc le diagramme de classes suivant :

Classes

Structure dynamique

Le programme peut se résumer par un automate de Harel. L’automate ci-dessous résume donc les différents appels aux différentes méthodes : Chaque « partie » de l’automate de Harel représente donc un thread et la synchronisation se fait avec les évènements. Chaque « partie » fonctionne donc de façon autonome.

Automate de Harel

Le système complet représenté sous forme de graphe est trop grand et complexe. C’est pourquoi on l’a divisé en trois parties qui représentent chacun un thread et forment ensemble le AND-STATE (et-état: représente un type de diagramme de Harel qui consiste à représenter l’état(STATE) d’un système complexe en le divisant en parties indépendantes qui tournent en parallèle et qui gèrent chacun un sous état du système. Chacun donne lieu ici à un thread). De plus l’état global est lui aussi géré par un thread afin d’assurer la synchronisation de ses sous états.

Modèle :

Modèle

Vue :

Vue

Vue GTK :

Vue GTK

Contrôleur :

Contrôleur

Méthodologie de développement

Cycle de développement logiciel

Pour le développement de l’application, notre encadrant de projet nous a conseillé de commencer par “faire simple” puis de rajouter des fonctionnalités au fur et à mesure que “ça fonctionne”. Il nous a donc demandé de faire des « maquettes » en apportant des améliorations à chaque fois. Ainsi nous avons plutôt fait un cycle de développement itératif. Pour chaque fonctionnalité, on s’est mis d’accord sur la façon de l’implémenter puis une fois le développement effectué nous avons vérifié que cela fonctionnait. Nous n’avons pas réalisé de tests formels et nous n’avons pas écrit de cas de tests pour des tests unitaires ou structurels. Nous nous sommes contentés de tester « intuitivement » le programme en essayant manuellement différent scénarios (rien de très pertinent ni de très exhaustif)

Les méthodes sont plutôt programmées de façon défensive, c’est à dire qu’on teste la valeur des données reçues pour vérifier que cela correspond à ce qu’on attend. Cependant dans certains cas où il était difficile pour l’utilisateur de passer « n’importe quoi » nous sommes parti du principe que la valeur reçue était correcte. (FIXME l’utilisateur ne doit pas affecter de poids négatif si il veut appliquer sur le graphe un algorithme comme dijsktra). Dans le modèle, nous avons essayé de limiter le nombre de méthodes. Ainsi la méthode ouvrir_graphe permet également de créer un nouveau graphe lorsqu’aucun nom de fichier n’est passé en paramètre (nous n’avons pas de méthode nouveau_graphe). De la même manière nous avons essayé de réduire le nombre de signaux. Ainsi le signal enregistrer_graphe permet de faire « enregistrer » et « enregistrer sous… » en fonction de ce qu’on trouve dans le pointeur de données du signal.

Temps de développement

Nous avons développé l’application principalement chez nous. Cependant, nous avons utilisé les heures prévues par l’emploi du temps pour mettre en commun le travail effectué et tenter de résoudre à plusieurs les problèmes que nous avons rencontrés. Ces heures ont également servies pour se mettre d’accord sur la manière de programmer : par exemple on s’est dit de terminer les noms des variables qui sont des pointeurs par « _p ».

Gestion des versions

Pour la gestion des versions, nous avons utilisé un dépôt git ce qui permet que tout le monde puisse travailler sur le code en même temps. Contrairement à subversion, les commit avec git sont locaux ce qui permet de travailler sans connexion à l’Internet. Cela permet également de pouvoir faire un commit sans passer du temps à résoudre les conflits. Ceux ci sont résolus uniquement lorsqu’on envoie l’ensemble des commits effectués sur le dépôt.

Solutions techniques et algorithmes développés

Choix du langage de programmation

Notre encadrant nous a laissé la liberté de choix du langage de programmation utilisé pour le projet.

Notre choix a été fait par l’analyse des critères suivants :

  • Nous avions besoin d’un langage gérant la concurrence, pour implémenter le modèle MVC.

  • Nous souhaitions avant tout contrôler l’exécution des différents threads, afin de comprendre ce que nous faisions, et donc de gagner du temps.

Le choix s’est donc rapidement placé entre C++ et Java, qui était suggéré. Nous avons envisagé l’exécution du projet du point de vue des deux langages et de leurs bibliothèques.

Nous avons noté que Java ne permet pas de contrôler le flot d’exécution du programme threadé. Les threads ne peuvent pas être gérés aussi finement, et surtout, explicitement, qu’avec des bibliothèques comme pthread disponibles en C++. Il était plus facile pour nous d’écrire explicitement le déroulement du programme dans les différents cas que d’écrire un ensemble d’écouteurs disparates.

Cela nous a notamment permis de mettre explicitement en pratique les notions de verrou et de sémaphore.

Ensuite, Java a besoin d’une machine virtuelle (interpréteur) pour fonctionner, alors que C++ est compilable nativement. La machine virtuelle Java demande beaucoup de ressources, ce qui peut être limitant si on veut travailler avec des grands graphes. De plus, Java ne permet pas de contrôler explicitement l’allocation de la mémoire.

Notre choix s’est donc porté sur le langage objet C++. On a noté qu’il était facile d’y inclure du C, langage qui nous est familier. Par ailleurs les bibliothèques que nous avions en vue, à savoir Graphviz et GTK3, y sont bien intégrées.

Bibliothèques utilisées

Nous avons utilisé plusieurs bibliothèques logicielles externes pour la réalisation de ce projet.

“GTKmm”

Pour créer l’interface graphique dans la vue, nous avons utilisé la bibliothèque GTKmm. GTKmm est une interface orientée objet à GTK+.

“gtksourceviewmm”

Pour visualiser le code source de l’application dans elle-même avec de la coloration syntaxique, nous avons utilisé gtksourceviewmm.

“Graphviz”

La bibliothèque Graphviz permet traiter les graphes. L’avantage de cette bibliothèque est qu’elle fait le rendu du graphe automatiquement c’est à dire qu’on peut générer une image qui représente le graphe facilement. De plus cette bibliothèque à l’avantage de pouvoir ouvrir un graphe depuis un fichier « dot » ce qui nous simplifie le travail d’ouverture et d’enregistrement du graphe. Cette bibliothèque est très mal documentée. La documentation est composée de la liste de la signature des fonctions, cependant il est écrit ce que fait la fonction. Il a donc fallut faire plusieurs essais avant d’arriver à utiliser la bibliothèque.

Nous utilisons également la bibliothèque pthread. Celle ci nous permet de gérer les processus légers dans l’application. Cette bibliothèque propose de créer des threads et des mutex mais aussi des conditions pour réveiller les threads afin de ne pas faire de l’attente active. Ainsi grâce à cette bibliothèque, nous avons pû implémenter le patron de conception Modèle-Vue-Contrôleur avec 3 processus légers (enfin 4, il y en a deux pour la vue).

Enfin la bibliothèque dlfcn permet de réaliser l’édition de lien dynamiquement pendant l’exécution du programme. C’est grâce à cette bibliothèque que nous pouvons charger dynamiquement les algorithmes.

Ces trois dernières bibliothèques ne sont des bibliothèques proposant des fonctions utilisables en C89. Elles ne proposent pas d’approche objet mais sont tout à fait utilisables dans un programme écrit en utilisant l’approche objet.

Processus légers

Nous avons implémenté le modèle MVC grâce à trois threads (enfin 5 threads). Chaque thread gère une entité. Ainsi il y a un thread pour le modèle, un thread pour le contrôleur et deux threads pour la vue. (le cinquième thread, c’est le thread principal du programme). Nous avons dû utiliser deux threads pour la vue car le thread dans lequel se trouve la boucle GTK ne nous permet d’attendre la réception d’un signal. Ainsi il y a un thread qui s’occupe de l’interface graphique et un thread qui attend les signaux provenant des autres entités.

Lorsqu’une entité veut envoyer un signal à une autre, elle doit modifier la valeur d’une variable partagée afin d’indiquer le « type » de signal envoyé. Ensuite l’entité qui envoie le signal doit « réveiller » le thread qui reçoit le signal afin que celle ci aille lire la valeur de la variable partagée et effectue les actions. Ces actions sont regroupées dans la méthode « send_signal » de l’entité qui reçoit le signal. Ainsi il suffit d’appeler la méthode send_signal en passant de type de signal à envoyer.

Les mutex permettent de synchroniser les threads entre eux afin de ne pas « rater » l’arrivée d’un signal et de ne pas lire dans les variables partagées en même temps qu’un autre thread lit la valeur. On peut donc résumer ceci par le réseau de pétri suivant :

Réseau de Pétri

Ainsi le premier mutex (mutex1) sert à contrôler l’accès à la variable partagée. Cela évite d’avoir un thread qui modifie la valeur pendant qu’un autre la lit. Le second mutex (mutex2) évite qu’un signal ne soit pas traité. En effet sans ce mutex un premier thread pourrait modifier la variable partagée puis ensuite avant que la valeur ne soit lue, un autre thread vient rechanger la valeur en envoyant à son tour un signal. Ainsi le premier signal n’a pas été traité. Le second mutex permet de s’assurer que chaque signal est bien traité puisqu’il « bloque » la méthode send_signal tant que le signal précédemment envoyé n’ait été traité.

Le chargement dynamique des algorithmes

Le chargement des algorithmes se fait à l’aide de la bibliothèque dlfcn. Cependant cette bibliothèque est une bibliothèque utilisable en langage C. Elle n’est donc pas développée selon une approche objet.

Le modèle garde en mémoire un tableau des différents algorithmes chargés. Pour chaque algorithme il possède un pointeur vers l’objet de type algorithme ainsi qu’un pointeur vers le fichier compilé chargé en mémoire (pas clair). Ainsi lors du chargement d’un algorithme la fonction dlopen est appelée. C’est elle qui réalise l’édition des liens dynamiquement entre le programme en cours d’exécution et le nouveau code. Ensuite on appelle la fonction create() sur le code que l’on vient de charger. Cette fonction se charge de créer un nouvel objet du type de l’algorithme. Enfin le pointeur vers l’objet de type algorithme ainsi que le pointeur vers le code chargé sont stockés dans un tableau dans le modèle. La fonction create() est utilisée comme une factory car lorsqu’on charge le fichier, on ne sait pas de quel type doit être l’objet à instancier.

Ensuite si l’algorithme est sélectionné la méthode « init » est appelée. Cette méthode permet d’initialiser le contexte graphviz pour les deux graphes où l’on peut visualiser le déroulement de l’algorithme. Lorsqu’un autre algorithme est sélectionné, la méthode « tini » de l’algorithme précédemment sélectionné est appelée afin de décharger le contexte graphviz et de libérer la mémoire occupée par les deux graphes sur lesquels on a pu observer le déroulement de l’algorithme.

Exécution pas à pas

À chaque fois qu’on exécute un pas de l’algorithme, la méthode start() de la classe algorithme est appelée, ensuite celle ci appelle la méthode main_algorithme() de la classe de l’algorithme en question. L’algorithme possède un état qui peut prendre les valeurs : « initialisation », « debut », « en cours » ou « termine ». Ainsi pour commencer la méthode init() place l’état sur « initialisation ». Ainsi dans cet état, la méthode start() réalise une copie du graphe de l’éditeur. C’est sur cette copie que l’algorithme va travailler. Une fois la copie réalisée, l’état est placé sur « debut » et la méthode main algorithme() est appelée. Ainsi on sait dans l’algorithme qu’on est sur le premier pas. On pourra donc initialiser des variables propres à l’algorithme et placer l’état sur « en cours ».

Enfin lors du dernier pas de l’algorithme, l’état doit être placé sur « termine » afin que la méthode start libère la mémoire occupée par les deux graphes (la copie du graphe de l’éditeur et le graphe résultat) sur lesquels l’algorithme a travaillé.

Lorsqu’on réinitialise un algorithme qui n’est pas terminé, un appel à la méthode main_algorithme est effectué après avoir préalablement placé l’état sur « termine ». Cela permet de libérer les variables allouées par l’algorithme. Ainsi à cause de cela, il n’est pas possible de faire un « rendu » des graphes dans l’état terminé. De plus cela est effectué lorsque l’algorithme est déchargé. Or si on décharge l’algorithme car la fenêtre a été fermée, il n’est pas possible de faire un rendu alors que la fenêtre est fermée.

On a donc :

Automate

Problèmes rencontrés

La sélection des arêtes

Lorsque l’on clique sur le graphe, le modèle transmet les coordonnées du clic de la souris au contrôleur qui se charge à son tour de les transmettre au modèle.

Le modèle va d’abord vérifier si le clic ne se situe pas sur un sommet du graphe. Ainsi pour chaque sommet on récupère sa « largeur » ainsi que sa « hauteur » et la position de son centre (x,y). On vérifie alors que les coordonnées du curseur sont dans le rectangle formé des points A,B,C et D avec

A=(x-(½×largeur),y+(½×hauteur))

B=(x+(½×largeur),y+(½×hauteur))

C=(x+(½×largeur),y-(½×hauteur))

D=(x-(½×largeur),y-(½×hauteur))

Nous n’avons réalisé le calcul pour affiner la zone cliquable à l’ellipse. Ainsi on à :

Sommet

Sommet avec en rouge la bordure de la zone cliquable

Si la condition n’est pas vérifiée, alors on vérifie si le clic n’est pas situé sur une arête. Pour cela on parcourt pour chaque nœud, les arêtes qui « entrent » et qui sortent du « nœud ». Pour chaque arête, on récupère une liste de points (pouvant aller de 5 à une bonne dizaine de points). On cherche alors un rectangle qui contient tous les points (comme pour le sommet). Ensuite si le clic de la souris se situe dans le rectangle on continue les vérifications. On vérifie donc si l’arête est verticale, c’est à dire que tous les points ont la même abscisse. En effet les arêtes verticales ont le problème que abscisse du clic ne tombe jamais tout à fait sur l’arête (on ne peut pas avoir le « marge » en y), il faut donc laisser une marge en x. Ainsi lorsque l’arête est verticale, la zone de clic est un rectangle assez fin formé des points

A=(x - une_petite_marge, y_du_point_le_plus_haut_de_l_arête)

B=(x + une_petite_marge, y_du_point_le_plus_haut_de_l_arête)

C=(x + une_petite_marge, y_du_point_le_plus_bas_de_l_arête)

D=(x - une_petite_marge, y_du_point_le_plus_bas_de_l_arête)

Si l’arête n’est pas verticale, alors on utilise les courbes de Bézier. Comme le nombre de points est variable, il va falloir faire du collage de courbes de 4 points. On commence donc par choisir pour chaque morceau de courbe les points que l’on va utiliser. Ainsi pour le premier morceau de courbe, on utilise les 4 premiers points

A₁=premier_point_donne_par_graphviz

B₁=deuxieme_point_donne_par_graphviz

C₁=troisieme_point_donne_par_graphviz

D₁=quatrieme_point_donne_par_graphviz

Ensuite pour le deuxième morceau de la courbe on choisit

A₂=D₁ (pour le collage)

B₂=le symétrique de C₁ par rapport à D₁=A₂ (pour garder la tangente)

C₂=cinquieme_point_donne_par_graphviz

D₂=sixieme_point_donne_par_graphviz

On continue comme ça jusqu’au dernier morceau. Si sur le dernier morceau il manque des points alors on complète avec le dernier point donné par graphviz.

Ensuite, pour chaque série de 4 points, on calcule les coefficients du polynôme de la fonction t→x(t) ainsi que du polynôme de la fonction t→y(t)

La formule est déjà écrite dans le programme. Juste pour savoir d’où ça vient, nous sommes parti de la formule classique

P(t)=P₁(1-t)³ + 3P₂t(1-t)² + 3P₃t²(1-t) + P₄t³

On développe :

P₁(1-t)³ = -P₁t³ +3P₁t² -3P₁t +P₁

3P₂t(1-t)² = 3P₂t³ -6P₂t² +3P₂t

3P₃t²(1-t) = -3P₃t³ + 3P₃t²

P₄t³ = P₄t³

D’où

P(t)=-P₁t³ +3P₁t² -3P₁t +P₁+3P₂t³ -6P₂t² +3P₂t-3P₃t³ + 3P₃t²+P₄t³

On regroupe les termes suivant la puissance de t

P(t)= -P₁t³+3P₂t³-3P₃t³+P₄t³ + 3P₁t²-6P₂t²+3P₃t² -3P₁t+3P₂t +P₁

P(t)= (-P₁+3P₂-3P₃+P₄)t³ + (3P₁-6P₂+3P₃)t³ + (-3P₁+3P₂)t + P₁

On remplace donc P₁, P₂, P₃, P₄ par x₁,x₂,x₃,x₄ pour trouver x(t) et par y₁,y₂,y₃,y₄ pour trouver y(t) On calcule donc x(t). On fait ensuite une résolution d’équation pour trouver pour quelles valeurs de t, x(t) est égal à l’abscisse du clic de la souris (ou plutôt pour quelles valeurs de t, x(t)-l’abscisse_du_clic=0). Puis pour chaque t trouvé, on calcule y(t). Si y(t) est proche (à 10 pixels près) de l’ordonnée du clic de la souris, on déduit que le clic a été effectué sur l’arête.

Il reste un dernier problème qui n’a pas encore été résolu. En effet lorsque l’arête passe très près d’un sommet alors un point de ce sommet est utilisé par graphviz pour son tracé, or quand on regarde la liste des points, ces points supplémentaires n’y figurent pas. Ainsi on se retrouve avec par exemple :

Problème 1

En rouge la zone cliquable déterminée à l’aide de la formule de Bézier

Avant de réaliser cela, nous avons essayé avec la formule de Lagrange, cependant l’arête « calculée » ne se superposait pas du tout avec l’arête du dessin :

Problème 2

En bleu, l’arête dessinée à l’aide d’un polynôme de Lagrange

Problème 3

La même arête dessinée à l’aide de la formule de Bézier

Obstacles de mise en pratique

Support des threads dans Xlib et GTK

Nous avons rencontré quelques surprises liées à l’implémentation des bibliothèques que nous utilisions dans notre application threadée.

Nous avions besoin d’effectuer des modifications de l’image du graphe dans la fenêtre GTK, lorsqu’il était modifié. Le modèle envoie dans ce cas un signal au second thread de la vue, qui les attend.

Ce second thread modifie alors l’image du graphe dans la fenêtre GTK. Mais à ce point nous obtenions des plantages.

La solution était de bloquer le thread GTK avec la méthode « gdk_threads_enter() », de modifier l’image, puis de libérer le thread GTK, avec la méthode « gdk_threads_leave() ».

Ensuite, nous obtenions toujours des erreurs au moment de la communication entre les deux threads de la vue, mais cette fois ne provenant pas de GDK.

La solution était d’utiliser l’instruction « XInitThreads() », qui permet d’activer le support nécessaire.

Le transfert de l’image du graphe

Pour le transfert de l’image générée par le modèle vers la vue, nous avons envisagé plusieurs alternatives.

Idéalement, nous souhaitions passer un pointeur d’image en mémoire par un signal. Cependant, la bibliothèque GTKmm nous a posé un petit problème : il n’est pas possible d’afficher une image passée par pointeur.

Nous avons contourné ce problème en passant par un fichier temporaire pour afficher le graphe.

Bilan

Pour conclure, un projet avec une difficulté élevée ne peut être que bénéfique de plusieurs manières pour les différents membres. Le choix de la difficulté de notre sujet a été volontaire puisque cela représente un vrai challenge à relever pour nous. Il est plus intéressant d’apprendre avec de la difficulté pour réfléchir aux différentes solutions ensemble. ce projet nous a donc permis de parfaire nos connaissances dans différents points.

D’abord sur le plan de la spécification du projet, et les différentes techniques qui s’y rapportent. Par exemple, il fallait réfléchir si on partait sur une version basique, qui sera améliorée au fur-et-à-mesure de l’avancement, ou alors s’il fallait directement proposer une version plus finalisée du programme. Un oeil extérieur a été décisif puisque notre professeur encadrant, Monsieur Hüe, n’a pas hésité à nous conseiller dans nos prises de décisions afin de mieux nous orienter.

Ce projet nous a aussi permis d’améliorer nos capacités à travailler en équipe. Un projet de cette envergure nécessite une bonne ambiance de travail au sein de l’équipe. Il faut être à la fois respectueux et attentif envers les choix des différents membres de l’équipe, et à la fois savoir imposer ses idées, ses convictions. Il faut donc trouver un équilibre entre ses 2 points essentiels pour la réussite. Par exemple, différents langages d’implémentation existent et faire le bon choix est très important dans la suite du développement. Il fallait donc se mettre d’accord sur ce point.

Le travail en équipe doit aussi permettre d’alléger le travail de chacun en se répartissant les tâches. Cela est un point très important dans un projet de groupe puisque si une personne se trouve en difficulté, un membre du groupe ayant plus de connaissances peut, dans le besoin épauler l’autre. Cela permet donc, par la même occasion de travailler l’organisation au sein d’une équipe.

Ensuite, la mise en application de nos connaissances acquises pendant les cours dispensés à l’IUT a été un apport en plus pour notre projet. Cela nous permet de valider les acquis et de s’en servir, en simulant un environnement du monde du travail, et non plus cet aspect scolaire. En effet, par exemple nous avons écrit le cahier des charges en suivant la méthodologie du cours. De même nous avons utilisé le cours sur les courbes de Béziers afin de réaliser la méthode permettant de sélectionner les arêtes du graphe.

Mais ces seules connaissances ne sont pas parfois suffisantes, il faut donc aller au delà de cela, et apprendre de nouvelles techniques et autres. Effectivement, dans le monde du travail, il faudra savoir adapter nos bases acquises à l’IUT puisqu’on ne rencontrera pas forcément les langages, ou les méthodes de spécification que l’on a étudié. Il faut savoir s’adapter à tout milieu. Par exemple, nous avons approfondi d’autres notions telles que le patron de conception Modèle-Vue-Contrôleur. En effet en classe nous n’avions pas utilisé ce patron avec plusieurs threads. Ce projet nous a également permit d’apprendre les bases du langage de programmation C++. Nous avons également appris à utiliser des bibliothèques telles que Graphviz ou GTKmm.

Si nous devions recommencer le projet, nous referions la même chose au niveau du développement. Cependant nous détaillerons l’architecture de l’application dès le cahier des charges. En effet le cahier des charges n’était pas assez précis et la structure d’un graphe que nous avions décrit n’a servi à rien puisqu’on a utilisé la structure fournie par la bibliothèque Graphviz. Enfin nous ferions au moins quelques tests fonctionnels afin de nous assurer que l’application est conforme au cahier des charges.

Pour finir, nous tenons à remercier notre professeur encadrant, Monsieur Hüe, qui a su répondre à nos questions, nos guider afin de répondre au mieux possible à la spécification de notre programme, nous conseiller afin de présenter un programme original.

Annexes

Documentation utilisateur

Interface

L’onglet éditeur permet de créer ou de modifier un graphe. Les onglets algorithme et résultat représentent la copie du graphe en cours de traitement par l’algorithme en cours d’exécution.

Le format DOT

La bibliothèque graphviz utilise le langage de description dot pour enregistrer les graphes. Le format dot est un format texte qui permet de décrire des graphes orientés ou non. Il possède une syntaxe simple : on définit dans un premier temps des options sur le graphe, les arêtes et les nœuds puis ensuite on donne la liste des nœuds voisins en précisant le poids.

Par exemple :

digraph G {
 graph [overlap=true, splines=true];
 node [label="\N", shape=ellipse, color=lightblue2, style=filled];
 edge [label=1, weight=1]
 A -> B [weight="2"];
 B -> C [weight="3"];
}

Dans les options au début du fichier on a

« overlap=true » ce qui permet aux nœuds de se superposer

« splines=true » qui permet de rendre des arêtes « courbes » et qui contournent les sommets

« label=\N » permet de mettre par défaut un label vide sinon il n’est pas possible de gérer les labels dans le graphe

« shape=ellipse » permet de définir la forme des nœuds

« style=filled, color=lightblue2 » permet de définir la couleur et le mode de remplissage

enfin pour les arêtes « label=1 » permet de placer un label à 1 par défaut sur chaque arête, « weight=1 » permet de définir un poids de 1 par défaut également.

Création d’un algorithme

Chaque algorithme doit hériter de la classe « Algorithme ». En effet cette classe générique contient le code qui permet de réaliser une copie du graphe situé dans l’éditeur ainsi que des méthodes abstraites que l’on doit redéfinir dans chaque algorithme :

  • une méthode main_algorithme() dans lequel on place les instructions à effectuer pour réaliser un seul pas de l’algorithme
  • une méthode nom() qui retourne le nom de l’algorithme (pour l’afficher dans le menu)

On doit également créer deux fonctions qui servent à créer et à détruire l’objet :

  • une fonction create() qui retourne un pointeur sur un objet de l’algorithme (c’est une factory…)
  • une fonction destroy() pour supprimer l’objet. Ces fonctions sont situées en dehors de la classe car elles sont appelées depuis la bibliothèque dlfcn qui est une bibliothèque écrite en C. De plus dans le modèle on ne connaît pas le nom de la classe (c’est déjà écrit dans la partie conception)

On a donc plus ou moins implémenté le patron de conception « Strategy », mais quand nous avons fait cela, nous ne connaissions pas ce patron.

Le code minimal pour un algorithme (en C++) :

#include "mvc.cpp"
class mon_algorithme : public algorithme {
 private:
  … // on place les variables pour lesquelles on souhaite garder la valeur entre chaque pas de l'algorithme
 public:
  char* nom() {
   return "le nom de mon algorithme"; // le nom de l'algorithme tel qu'il sera affiché dans le menu
  }
 void main_algorithme() {
   if(this->etat==debut) {
    … // les instructions que l'on exécutera que lors du premier pas de l'algorithme
    this->etat=en_cours;
   }     
   if(this->etat==en_cours) {
    … // les instructions pour chaque pas de l'algorithme
    if(…) { // la condition de fin
     this->etat=termine
    }
   }
   if(this->etat==termine) {
    free(…); // on libère les variables que l'on a allouées
    …
   }
 }
};


extern "C" mon_algorithme* create() {
 return new mon_algorithme;
}
extern "C" void destroy(mon_algorithme* p) {
    delete p;
}

La bibliothèque dlfcn permet de charger dynamiquement du code écrit dans n’importe quel langage.

On peut donc, théoriquement développer les algorithmes dans tout les langages turing-complets tels que python, java… Seulement dans la pratique cela est délicat. En effet il faut que le programme principal écrit en C++ instancie et utilise un objet écrit dans un autre langage. De même la classe écrite dans un langage doit pouvoir hériter de la classe « algorithme » écrite en C++. Elle devra pouvoir aussi faire des appels aux fonctions de la bibliothèque graphviz écrite en C.

Bien que cela soit possible, c’est assez compliqué c’est pourquoi nous n’avons pas essayé d’écrire un algorithme dans un autre langage que le C++.

Explications des algorithmes implémentés

Algorithme de Dijkstra

L’algorithme de Dijkstra, crée par un informaticien Autrichien Edsger Dijkstra en 1956. Ce dernier permet de définir les plus courts chemin entre une nœud vers les autres sommets d’un graphe pondéré avec des poids positif ou nul.

Algorithme

Le nœud initial est appelé le nœud source. l’algorithme repose sur le fait de supposer des poids et de les réformer étape par étape. On suppose initialement que touts les nœuds ont un poids infini.

  Fonction Dijkstra (nœuds, fils, distance, début, fin)
     Pour n parcourant nœuds
         n.parcouru = infini             // Peut être implémenté avec -1 (*)
     Fin pour
     début.parcouru = 0
     pasEncoreVu = nœuds
     Tant que pasEncoreVu != liste vide
         n1 = minimum(pasEncoreVu)      // Le nœud dans pasEncoreVu avec parcouru le plus petit
         pasEncoreVu.enlever(n1)
         Pour n2 parcourant fils(n1)    // Les nœuds reliés à n1 par un arc
             Si n2.parcouru > n1.parcouru + distance(n1, n2)   // distance correspond au poids de l'arc reliant n1 et n2
                 n2.parcouru = n1.parcouru + distance(n1, n2)
             Fin si
         Fin pour
     Fin tant que

Dijkstra

Aglorithme du plus Court Chemin

l’algorithme du plus Court Chemin permet de définir le plus court chemin d’un nœud à un autre nœud d’un graphe. Il consiste à inonder un graphe pondérer avec des poids positifs d’éléments dont on va gérer l’avancement grâce à un compteur qui va tourner parallèlement.

Algorithme

  Fonction CourtChemin (nœuds, fils, distance, début, fin)
     avancement=0
     derniers_élément = début;
     Tant que fin != atteint                                                        //tant qu'on a pas atteint le nœud qu'on veut atteindre
      pour n parcourant derniers_éléments;
       si derniers_éléments(n).poids = avancement                                   //si l'avancement atteint le poids de l'élément 
        pour n2 parcourant successeur(derniers_éléments(n));
         si (!appartient(n2,derniers_éléments) + !parcouru(n2))alors                //si son successeur n'est pas déjà parcouru
          nouveaux_élément = élément(n2,somme(n2.poids, derniers_éléments(n).poids);//on crée un nouvelle élément qui va garder ses antécédents
          ajout(nouveaux_élément, derniers_éléments);
         Fin si
        Fin pour
       Fin si
      Fin pour
      avancement + 1;
     Fin tant que

Algorithme du plus court chemin

Bibliographie


FIXME : Notes en vrac : parler de la répartition des tâches, (git ?), expliquer les algorithmes, tests et validation, format dot, implémentation d’un nouvel algorithme, api, commentaires dans le code source, description du format dot, explication pour créer un algorithme, doc utilisateur en annexe, le rôle de la classe équation, faire toute une partie sur la méthodologie de développement (cycle en v, précondition, quantité de travail dans la semaine)… Finir l’automate de Harel et l’expliquer arbre des appels Préconditions, postconditions

Rendu en latex (18 mars) : {{:projet:rapport.pdf|}} (source : projet:rapport:latex)

Rendu en latex (20 mars) : {{:projet:rapport2.pdf|}}

Rendu en latex (25 mars) : {{:projet:rapport3.pdf|}} (source : projet:rapport:latex3)

Rendu en latex (31 mars) : {{:projet:rapport4.pdf|}} (source : projet:rapport:latex4)

Rendu en latex (31 mars) : {{:projet:rapport5.pdf|}} (source : projet:rapport:latex5)

Rendu en latex (1 avril) : {{:projet:rapport6.pdf|}} (le même que le 5 avec le cahier des charges)

Rendu en latex : {{:projet:rapport_final.pdf|}}

Rapport à rendre pour le 2 avril à 19h. Vidéo pour le 3.