# Présentation

###### tags: `CR`

[TOC]

https://docs.google.com/presentation/d/1n98iFgIPXL4NROdVE1E-T_06UbDOjg5PSTYLU8tROWc/edit?usp=sharing

## Planning de la semaine

## Introduction (rappel du cahier des charges) (Hugo)

### Definition du projet
Ce projet repond à la demande de notre professeure qui était de réaliser une bibliotheque permettant de manipuler des graphes orientés
- creation
- manipulation
- application algo
- interface graphique pour utiliser cette bibliothèque.

Il a été fondé dans le cadre universitaire lors de notre dernier semestre de licence informatique.

L'utilisateur aura la possibilité d'utiliser la bibliothèque afin de réaliser un projet centré autour des graphes oriéntés, cela necessite la bonne compréhension du langage de programmation.

L'interface graphique sera compréhensible par toutes et tous.

### Glossaire (definitions des termes du sujet)
Definissons les différentes termes de notre sujet ainsi que ses composants:
- Sommet : un point du graphe.
- Arc : relation entre deux sommets consécutifs. Il a obligatoirement un sens.
- Voisins : deux sommets sont voisins s’ils sont reliés par un arc.
- Successeur : t est successeur de s si il existe un arc entre les sommets s et t et que t se trouve à l’extrémité finale de l’arc.
- Prédécesseur : s est prédécesseur de t si il existe un arc entre les sommets s et t et que s se trouve à l’origine de l’arc.
- Graphe orienté : les sommets d’un graphe orienté sont reliés entre eux par des arcs qui ont un sens.
- Sous-graphe : graphe ayant pour sommets un sous-ensemble V des sommets d’un autre graphe G et pour arcs uniquementceux de ce même graphe G.
- matrice : tableau de nombres permettant d’interpréter en termes calculatoires ou opérationnels des résultats.
- matrice d’adjacence : matrice qui représente le graphe en indiquant si il existe un lien entre deux sommets.
- matrice d’incidence : c’est une matrice qui décrit le graphe en indiquant a quels sommets sont liés les arcs.
- un arbre : graphe particulier dont la racine est unique, ses sommets adjacents droits et gauches sont toujours de degréssupérieurs à 1 et ses feuilles sont de degré 1. Ici, dans l’univers des graphes orientés, on parlera d’arborescence ou d’anti-arborescence pour préciser le sens des branches de l’arbre.

Les sources du programme sont disponibles sur internet pour que n'importe quelle personne puisse utilisé notre application graphique et/ou notre bibliothèque pour s'exercer sur les graphes orientés ou bien produire son propre projet autour du notre.

## Description de l'architecture du projet (organigramme et tableaux des coûts)

### Organigramme (Camille)
Nous nous sommes basés sur cet organigramme tout au long du projet, nous l'avons suivi comme ligne directrice pour la création des différents modules, l'implémentation des fonctionnalités.

| 1 | Clics et touches du clavier |
| -------- | -------- |
| 2 | Affichage |
| 3 | Sommets sélectionnés, arcs sélectionnés, graphe,choix des interactions, taille du graphe |
| 4 | Graphe |
| 5 | Nom du fichier, graphe |
| 6 | Nom du fichier, message de validation (suppression, sauvegarde) ou contenu du fichier |
| 7 | Graphe, sommet du graphe, message de demande d'actions |
| 8 | Liste des sommets, sous-graphe, graphe, message de validation de l'opération
| 9 | Graphe modifié |
| 10 | Graphe

L'organigramme ci-dessus présente les quatre modules essentiels au développement de notre application et de notre bibliothèque. L'architecture de ces derniers est composé :
- d'une gestion de graphe, permettant de créer, supprimer et manipuler des graphes orientés.
- d'opération sur les graphes, dans lequel des algorithmes complexes sont implémentés pour être appliqués aux graphes.
- d'une interface graphique, le noyau de notre projet. Il communique avec tous les autres modules en interaction avec l'utilisateur.
- d'un système de gestion de fichiers, servant à stocker ou récupérer des données sauvegardées par l'utilisateur via la bibliothèque RapidJson.

### Tableaux des coûts

### Choix du langage

- langage orienté objet: graphe contient un grand nombre de caractéristiques et de fonctionnalités propres --> langages procéduraux qui ne possèdent pas les outils dont on avait besoin, plus de diificulté pour modifier en temps réel les graphes. (ex: sommet contient id, etiquette, map, liste arcs)
- Nous avons besoin d'objets initialisés avec des paramètres différents suivant l'utilisation demandée. Cela nécessite le polymorphisme et donc un langage orienté objet. (ex sommet qui peut être juste créé avec son id + position ou bien avec l'ensemble de ses paramètres(pert))
- De plus ces objets pourront être manipulés par les algorithmes qui nécessitent un paradigme procédural impératif.
- performance: graphes avec de nombreux sommets et arcs et des algos parfois en n! --> comparaison des langages: c++ plus performant et plus rapide sur les experimentations.

## Fonctionnalités (Description, Implémentation, Problèmes)

### Gestion de graphes (Salsa)
* **structure** : Vecteur - Ordonnacement
Ordonnancement est utile lors de l’implémentation de l’algorithme de PERT afin de g ́erer des tâches.

Vecteurs est utile pour stocker des données sur les Sommets et les Arcs. Elle sera gére par la structure Vector, déjà a implémentéee dans la bibliothèque de base du C++.

* **Classe Sommet :**
base d'un graphe.
* **Classe Arc**
On peut relier les objets sommets entre eux par le biais d'un arc.

* **Classe GrapheMatrice :**
Dans la classe Matrice :
la méthode conversionGraphe () renvoie un Graphe et necessite pour cela son constructeur.
Dans la classe Graphe :
dans les méthodes conversionversMatrice adj() et conversionversMatriceinc() on a besoin des constructeurs de Matrice.

--> Regrouper les classes Matrice et Graphe : GrapheMatrice.

### Opérations sur les graphes (Amandine, Vincent)
- Chaînes euleriennes
- Chaînes hamiltoniennes
- Arborescence et Anti-Arborescence
- Calcul des plus courts chemins
- Calcul des degrés d’un sommet
- Recherche de la connexité
- Ordonnancement (PERT)
************
- Coloration de graphe (Vincent)
- Détection de stables (Vincent)
- Détection de cliques (Vincent)
- Calcul des voisins d’un sommet (Vincent)
- Résolution du problème du postier chinois (Vincent)
- Résolution du problème de Little (Vincent)
- Gestion des flots (Vincent)

### Gestion de fichiers (Seb)

La plus grosse difficulte de ce module fût l'apprentissage de la bibliotheque rapidjson.

- Sauvegarde (classique & avancé)
La sauvegarde est composé de deux sous fonctionnalités:
- la sauvegarde dite classique
- la sauvegarde dite avancée
La sauvegarde dite classique enregistre un graphe dans le fichier et le repertoire indiqué dans l'attribut path du graphe passer en argument.
Les deux fonctions opèrent de la même manière, le graphe passer en paramètre est alors découpé en objet rapidjson pour les stocker dans le fichier .json a l'emplacement indiqué, certains de ces objets sont ensuite découpé en tableaux en fonction de leur structure.

- chargement (& verif_file)
Le chargement utilise la fonction verif_file qui grace au chemin du fichier peut savoir si ce fichier est au bon format, si il respecte le schema défini. La fonction de verification retourne un booléen. Lors de l'implémentation nous avons eu du mal avec le schéma car nous avons beacoup de tableaux et d'objet stocké dans notre fichier.
Le chargement quand à lui récupère le fichier d'un chemin donné, puis construis chaque élément d'un graphe qu'elle renvoie à la fin si tout c'est bien passer, dans l'autre cas le graphe renvoyer a pour étiquette "erreur".
Dans la premiere version rendue le fait que la fonction renvoie un graphe avec pour étiquette "erreur" n'était pas implémenté.

- suppression
Cette fonction est très simple elle supprime un fichier a l'emplacement donner en paramètre grâce à la fonction de la bibliothèque standard remove, la fonction renvoie 0 si le fichier est bien supprimer et -1 sinon.

### Interface graphique (Alexandre, Theo)
(slide avec le schéma de l'architecture du GUI)
L'architecture de l'interface graphique est divisée en plusieurs classes :
- La MainWindow qui hérite d'une QMainWindow dont tous les attributs et la construction proviennent de `mainwindow_copy.hh`.
- Elle permet de gérer les menus ainsi que la zone de dessin courantes et les onglets, on peut choisir quel algorithme appliquer sur les graphes modelisés ou généré aléatoirement.
- Elle permet d'afficher les caractéristiques de la sélection
- Elle permet d'afficher le résultat des algorithmes

- La QZoneDeDessin qui est un attribut de la mainwindow et qui hérite d'une QGraphicsView premettant de modéliser les graphes
- Elle permet de visualiser une QGraphicsScene sur laquelle est modélisée le graphe et de traduire les modifications graphiques en modifications dans l'objet graphe_dessine associé.
- Elle gère les clics permettant d'ajouter ou supprimer les arcs et sommets
- Elle gère la sélection de sommet
- Elle gère le dessin d'un objet graphe préexistant.
- Elle permet suite au double clic sur un sommet ou un arc d'ouvrir la fenêtre de MODialog permettant de modifier la charge utile embarquée par les sommets ou les arcs.

- Les objets graphiques QSommet et QArc héritant tout deux de QGraphicsItem
- Ces objets sont construit respectivement à partir d'un Sommet ou d'un Arc. Ils récupèrent leur IDs et leur positions ce qui permet de passer d'un objet classique à un objet graphique que l'on peut afficher dans la QGraphicsScene. Le fait qu'ils préservent le même ID permet de retrouver l'arc ou le sommet dans le graphe_dessine et donc d'y transférer les modifications effectuée sur le dessin.

- La fenêtre MODialog permettant de modifier les objets graphiques QDialog
- Cette fenêtre permet de modfier l'étiquette des arcs et sommets et leur charge utile via un formulaire.

- La fenêtre OCDialog permettant de créer des graphes de PERT QDialog.
- Cette fenêtre ouverte via MainWindow permet de générer un vecteur de pert_row utilisé pour générer un graphe grâce à l'algorithme de PERT.

## Conclusion (Guillaume)

### en Conclusion pour la partie technique
Le produit final de notre projet réponds bien aux objectifs attendus : la manipulation de graphes orientés et l'application d'algorithmes sur ceux-ci. Pour cela notre projet est divisé en deux parties, l'interface graphique et la bibliothèque. Nous avions choisis comme langage le C++, choix qui s'est avéré satisfaisant puisque nous n'avons eu aucun problème de ce côté là lors de l'implémentation.

Bibli : l'ensemble des tests de la bibliotheques sont réalisés avec succes
on a modifier quelques fonction par rapport au spé
au debut on a pris un ptit retard ratrapper assez rapidement
difficulter de certaines implémentations

Notre application qui est fonctionnelle.tous les tests sont réalisés avec succès (tous les tests de gestion de graphe, du système de gestion de fichier et des operations sur les graphes, sauf celui du problème de Little et une partie des tests de l'interface graphique).

Pour améliorer notre application, l'ajout de nouveaux algorithmes applicables sur les graphes orientés est une possibilité. On peut aussi envisager d'étendre la méthode PERT en ajoutant des contraintes de ressources. La représentation graphique du déroulement des algorithmes, étapes par étapes, peut aussi être réalisé, ce qui permettrait par exemple a des étudiants d'avoir une première approche de la théorie des graphes.

Le seul reel pb c'est l'algorithme de little

### Conclusion sur l'organisation interne au groupe

Tout au long de ce projet de derniere année de licence informatique, nous avons travaille en groupe de 9, ce qui est une première pour l'esemble des membres du groupe. Cette experience nous a permis de nous regrouper plusieurs fois par semaine, que ce soit en présentiel, ou a distance si la situation ne le permettait pas, afin de mettre nos idées en commun et débattre autour de notre sujet. Pendant la periode de confinement, nous avons réussi à garder des points quasiment quotidiens ce qui a permis d'apporter de l'aide le plus tot possible à ceux qui en avait besoin et ainsi d'avancer rapidement.
Lors des premières réunion, nous avons pris la décision de ne pas avoir de chef de projet afin que tous les membrres aient autant de responsabilités et que chacun puisse donner son avis. Cette décision s"esr avérée efficace, puisque la réalisation du projet dans l'ensemble s'est bien déroulé. En effet, chacun des membres du groupe a pris ses responsabilités, permettant ainsi au projet d'avance dans la bonne direction tout en gardant une entente amicale.