# Présentation du 12/02
###### tags: `présentation`
[TOC]
## Objet du projet
### Objectif (Théo)
Notre objectif est de créer une biliothèque logicielle permettant à un développeur tier de manipuler les graphes orientés sans avoir à les re-implémenter. Cette bibliothèque permettra donc une manipulation aisée des graphes orientés dans d'autre programme, dit *consommateur*, grâce à une interface logicielle.
Pour accompagner la bibliothèque nous allons aussi créer une application graphique de création de graphe permettant de modéliser toute sortes de graphes orientés et d'y appliquer des algorithmes. Cette application permettra à un utilisateur lambda de créer des graphes orientés et de les manipuler.
### Périmètre
Nous avons donc besoin de deux périmètres, celui de l'application et celui de la bibliothèque.
La bibliothèque doit permettre :
- De créer, supprimer et modifier des graphes
- D'appliquer un algorithme sur le graphe complet ou un sous graphe
- De sauvegarder les graphes et de les charger

L'application doit permettre :
- De dessiner graphiquement les graphes
- Séléctionner graphiquement les sommets d'un graphe pour en faire un sous graphe
- De choisir quel algorithme appliquer au graphe
- De lancer la sauvegarde

## Définition des clients et des partis prenantes(Salsa)
### Parties prenantes
Les deux parties prenantes sont :
- Le groupe de travail
- Mme Kloul

### Client
La question du client n'est pas pertinante

## Utilisateurs finaux du produit
Les utilisateurs finaux du produit diffèrent en fonction de la partie du projet. En effet pour la **bibliothèque** le client final est un développeur tierce qui utilise notre travail dans le sien.
Dans le cas de l'**application** l'utilisateur final est une personne lambda (sans compétence informatique particulière) qui souhaite modéliser un problème de graphe orienté.

---
## Modules (Alexandre)

### Interface graphique et Drag & Drop
Cette interface permet à l'utilisateur de choisir parmis les fonctionnalités de l'application et d'avoir un aperçu des graphes.

### Sauvegarde de fichiers
Une sauvegarde de la matrice d'adjacence dans un fichier externe pourra être effectué si voulu. Chacun des résultats des modules pourra égalemment être enregistré dans un fichier.

***EXEMPLE***

0 1 1 1 0 1
1 0 0 1 0 1
0 0 0 1 1 0
1 0 1 0 1 0
0 1 1 1 0 1
1 0 0 1 0 0

### Création de graphes
L'utilisateur a la possibilité de créer un graphe en ajoutant directement les sommets et les arcs, en important une matrice d'adjacence (de taille *N x N*) déjà remplie ou en créant directement une matrice d'adjacence sur l'interface graphique.

### Création de sous-graphes
Ce module permet à l'utilisateur de sélectionner des sommets pour créer un nouveau graphe qui sera le sous-graphe contenant ces sommets et les arcs reliants ces sommets.

### Modification de graphes (Amandine)
Il sera possible de modifier les graphes en supprimant et ajoutant un sommet, le déplaçant ou en ajoutant et supprimant des arcs. Les noms, valeurs et coordonées pourront aussi être affichés, effacés et modifiés.

### Graphes aléatoires
Des matrices de tailles et valeurs aléatoires pourront être créés et affichées sous forme de graphe. Les coordonnées de chacun des sommets seront calculées à l'aide d'un algorithme.

---
## Algorithmes et fonctionnalités

### Algorithme de position
Cet algorithme qui est notamment utilisé dans la création de graphes aléatoires permet de faire en sorte que les sommets d'un graphe ne se superposent pas et aient donc des coordonnées différentes.

### Matrice d'adjacence
La matrice d'adjacence du graphe ouvert sera affichable à l'écran.

### Matrice d'incidence
La matrice d'incidence du graphe ouvert sera calculée par un algorithme et pourra être affichée.

### Degrés entrant et sortant (Guillaume)
Suivant le choix de l'utilisateur,un algorithme calculera les successeurs et prédécesseurs d'un sommet spécifique, ou de tout les sommets du graphe.

### Liste de voisins
En fonction de la sélection de l'utilisateur, une liste des voisins (prédecesseurs et successeurs) du sommet selectionné pourra être affiché ou dans un autre cas une liste globale des voisins de chaque sommet.

### Plus court chemin
L'utilisateur aura la possibilité soit de sélectionner deux sommets puis de trouver le chemin le plus court entre ces derniers, soit de calculer le plus court chemin entre tout les sommets. Il est égalemment possible de calculer les chemins les plus courts entre un sommet et tout les autres.

### Arbres couvrants de poids minimum
Cette fonctionnalité donne à l'utilisateur un arbre couvrant de poids minimal du graphe.
*Un arbre couvrant est un arbre qui passe par tout les sommets d'un graphe, possède une racine et ne contient pas de cycle.*

### Coloration de graphes et nombre chromatique (Vincent)
Il sera possible pour l'utilisateur d'afficher à l'écran la coloration du graphe, chaque noeud sera affiché dans sa couleur et le nombre chromatique sera renseigné.

*Un Nombre Chromatique est le nombre minimum de couleurs différentes nécessaires pour colorier tous les sommets d’un graphe de façon à ce que deux sommets adjacents aient des couleurs différentes.*

### Chaine Eulérienne
Cette fonctionalité vérifie si une chaine Eulérienne existe dans le graphe et si oui l'affiche.

*Une chaine Eulérienne passe par tout les arcs d'un graphe, un graphe possède une chaine eulérienne si les degrés entrant et sortant de ses sommets sont égaux.*

### Chaine Hamiltonienne (Camille)
Un algorithme vérifie si un chaine Hamiltonienne existe bien et l'affichera à l'écran si c'est le cas.

*Une chaine Hamiltonienne passe par tout les sommets d'un graphe.*

### Cliques
L'utilisateur pourra extraire une ou plusieurs Clique(s) du graphe.

*Une clique d'un graphe est un sous ensemble de sommets dont le sous graphe induit est complet.*

### Stables
L'utilisateur pourra extraire un ou plusieurs Stable(s) du graphe.

*Un stable est en ensemble de sommets deux à deux indépendants.(aucun liens entre eux)*

### Optimisation des tâches

L'utilisateur pourra aussi utiliser le diagramme PERT qui propose de calculer l'enchaînement optimal des tâches. Il calculera et affichera pour chacune de ces tâches une date "au plus tôt" et une date "au plus tard". Il sera aussi indiqué les tâches critiques.

*Le diagramme PERT propose de calculer, à l'aide d'un graphe, l'enchaînement optimal des tâches. Chaque tâche est identifiée par sa durée moyenne et sa précédence. Le graphe propose ainsi pour chaque tâche une date "au plus tôt" et une date "au plus tard". Tant que la tâche démarre à une date comprise entre ces deux limites, elle ne pénalisera pas les tâches avales.
Lorsqu'il n'existe pas de marge et que la date de début est équivalente à la date de fin, la tâche est dite "critique". Tout retard pris sur une tâche du chemin critique pénalise la durée du projet.*

### Problème du postier chinois (Hugo)
Cette fonctionalité permet de parcourir tout les arcs du graphe une fois au minimum (meilleur temps/poids minimal).

### Algorithme de Little (problème du voyageur de commerce)
Repose sur le principe du Branch and Bound. Il faut selectionner un chemin seulement si les autres ont un regret plus élevé, c'est à dire qu'ils augmentent le poids total du chemin.
Chemin optimal entre plusieurs sommets sélectionnés par l'utilisateur.

### Gestion des flots
Il sera possible de calculer le flot maximum d'un graphe entre deux sommets qui sera directement visible par l'utilisateur. D'autre part, le flot passant par chaque arc sera lui aussi renseigné ainsi que sa capacité.

*flot maximum: graphe dans lequel chaque arc peut recevoir une capacité et peut recevoir un flux. le cumul des flux ne peut excéder la capacité.*

## Première version de l'organigramme (Alexandre & Sébastien)


### Description
1: Entrees/Sorties <- Inteface Graphique
2: Entrees/Sorties -> Interface Graphique
3: Interface Graphique -> Interface logicielle
4: Interface Graphique <- Interface logicielle
5: Interface Graphique -> Système de gestion de fichiers
6: Interface Graphique <- Système de gestion de fichiers
7: Système de gestion de graphe -> Interface logicielle
8: Interface logicielle -> Système de gestion de graphe

### Légende

1: clics et touches du clavier
2:
3: sommets selectionnés, arcs selecttiones, graphe, choix interaction
4:
5:
6: nom du fichier
7:
8:
9:
10:
11: liste de sommets,
12:

### Entrées/Sorties

### Systeme de Gestion de Graphe

#### Manipulation de base
- Création d'une matrice d'adjacence(simple, complet, biparti, cycle…)
Prend en entrée la taille de ma matrice NxM
- 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 collone N x N, on renvoie l'adresse de l'objet sommet.
- Suppression de matrice
- Duplication de matrice
Instancie une nouvelle matrice M2 à partir de la matrice M1 passée en argument.

#### Conversion
- Transformation du graphe en matrice d’adjacence et inversement
- Conversion d'une matrice d'adjacence en mastrice d'incidence
- Conversion d’un arbre en codage de Prüfer et inversement

#### Entrées et sorties du module
##### Entrées
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

### Opérations sur les graphes

### Interface graphique
- Affichage des données globales :
-> graphes à afficher ( numéro, poids )
-> type de graphes ( couvrant, complet, ..)
-> nb d'arcs, de sommets
- Aficher des données par sommet :
-> degré entrant/sortant
- modifier arc, somme, sous-graphe
- déplacer arc, sommet, sous-graphes(sélection)
- selection arc, sommet, sous-graphes ( 2 sommets & 1 arc minimum)
- Alg de positionnement (dans l'espace )

### Interface logiciel

Soit fonction d'enrobage (wrapper), soit inutile dans l'organigramme

### Systeme de Gestion de fichiers

- Sauvegarde:
Entree -> Nom de fichier, graphe
Sortie -> Message de validation
- Suppression:
Entree -> Nom du fichier
Sortie -> Message de validation
- Chargement: verification du format
Entree -> Nom du fichier
Sortie -> Informations contenue dans le fichier (graphe, position des sommets et arcs, informations sur les arcs, information des sommets)

Contraintes pour les fichiers:
- Nombre de sommets négatifs
- Taille du fichier
- Format du fichier (nombre de colonne / ligne )

Type de fichiers : TxT, autre chose ??

### Sous parties

Bibliothèque : Interface logiciel, Gestion de graphe

Application : Interface graphique, Gestion de fichiers

commentaire:
- on mesure quoi? metrique, definition de metrique, pour calculer de quoi dépndent cela. elles seront def en foncftion des objectifs de l'app.
1) d'abord rentrer en detail des fonctionnalité pour savoirs tout cela.
2) chacunes des fonctionnalités doit spécifié quels algo est employé + compléxité. entré et sortie aussi.