# TD 7 : Coloration de graphes
## Notes préliminaires
### Programmation orientée Objet
#### Vocabulaire :
- **Classe** : Objet contenant la définition des méthodes et propriétés communs à un ensemble d'objets. *"Moule à **instance**"*.
- **Instance** : Objet avec un comportement d'état défini par une **classe**. *"Résultat en sortie du moule"*.
- **Variable d'instance** : Variable définie par une **classe** que chaque **instance** va copier pour son propre usage.
- **Méthode** : Une méthode définie dans une classe sera comprise par toutes les instances qui en proviennent.
#### Application à Python :
- **Classe** :
```python
# Définition d'une classe
class Voiture:
# Constructeur: méthode appelée à la création de l'objet
def __init__(self, marque, modele, vmax, acceleration=20):
# Déclaration des variables d'instance
# On utilise ici les arguments du constructeur
self.marque = marque
self.modele = modele
self.vmax = vmax
# Ou pas
self. vitesse = 0
self.acceleration = 20
# Méthode que chaque instance de la classe pourra utiliser
def accelerer(self):
self.vitesse = min(self.vmax, self.vitesse + self.acceleration)
```
- **Instance et variables d'instance** :
```python
# Instanciation de deux voitures
c3 = Voiture("Citroen", "C3", 130)
p307 = Voiture("Peugeot", "307", 130, 30)
# Elles comprennent les memes methodes
c3.accelerer()
p307.accelerer()
# Ces deux instances ont les memes variables d'instance
c3.vitesse
>>> 20
p307.vitesse
>>> 30
```
#### Explication de `if __name__ == "__main__":`
Cette expression se traduit en :
> Si le fichier donné est en train d'être exécuté, exécuter ce qui suit cette expression, sinon, si le fichier est importé, ne rien faire.
Elle permet de compartimenter proprement son code et ses classes en différents fichiers et de leur associer des variables/fonctions de test particulières.
Exemples d'utilisation :
- Deux variables avec le même nom définies dans deux fichiers différents
- Une fonction de test longue à exécuter (lecture de fichier par exemple)
## Exercice 1 : Définition des classes`Graphe` et `Noeud`
- **Code donné :**
```python
import visugraphe
# Définition de la classe Graphe
# Définition de la classe Noeud
if __name__ == "__main__":
g = Graphe()
nA = Noeud("A")
nB = Noeud("B")
nC = Noeud("C")
nD = Noeud("D")
nE = Noeud("E")
g.ajout_noeud(nA)
g.ajout_noeud(nB)
g.ajout_noeud(nC)
g.ajout_noeud(nD)
g.ajout_noeud(nE)
g.ajout_arete(nA, nB)
g.ajout_arete(nA, nE)
g.ajout_arete(nB, nC)
g.ajout_arete(nB, nD)
g.ajout_arete(nB, nE)
g.ajout_arete(nC, nD)
g.ajout_arete(nC, nE)
g.ajout_arete(nD, nE)
visugraphe.visu_graphe_simple(g)
```
#### Quelques questions à se poser :
- Quels sont les **arguments passés au constructeur** de chaque classe ?
- Quelles **variables d'instance** sont données à chaque classe ?
- Quelle **méthode** définir dans quelle classe ?
- **Classe `Noeud` :**
```python
class Noeud:
def __init__(self, ...):
...
```
**Solution :**
```python
class Noeud:
def __init__(self, nom):
self.nom = nom
self.couleur = 0
self.voisins = []
```
- **Classe `Graphe` :**
```python
class Graphe:
def __init__(self):
...
```
**Solution :**
```python
class Graphe:
def __init__(self):
self.noeuds = []
def ajout_noeud(self, noeud):
self.noeuds.append(noeud)
def ajout_arete(self, n1, n2):
if n2 not in n1.voisins:
n1.voisins.append(n2)
n2.voisins.append(n1)
```
---
## Exercice 2 : Implémentation de Welsh-Powell
<!--
#### ATTENTION ARNAQUE
**A ne pas faire :** *Recommandation du TD :* Faire une liste de tuples (degré, nom du noeud, noeud) pour comparer avec la méthode `sort()`. Dans le cas d'une égalité du degré, le nom va être comparé.
**A faire :** Ajouter des méthodes propres à Python à vos objets pour la comparaison :
```python
class Noeud():
...
def degre(self):
return len(self.voisins)
# Infériorité (lesser than = lt)
def __lt__(self, other):
return self.degre() < other.degre()
```
La méthode `sort()` compare les éléments mais ne sait pas comment comparer des objets par défaut. Une fois la relation d'ordre définie, votre liste de noeuds pourra se trier simplement.
On peut aussi définir d'autre fonction interne de Python. Par exemple, afficher un noeud nous donne son adresse en mémoire pour l'instant. Pour un retoru plus utile, on peut redéfinir (***surcharger***) `__str__` :
```python
class Noeud():
...
def __str__(self):
return "(Noeud " + self.nom + " - couleur: " + str(self.couleur) + ")"
```
-->
#### Pseudo-code :
1. ~~Trier les nœuds par nombre de voisins décroissant (le *degré* du nœud).~~
2. Tant qu'il existe des noeuds non coloriés :
3. 1. Sélectionner une nouvelle couleur (successeur de la couleur précédente ou 0 au premier passage).
2. Parcourir la liste des sommets non-coloriés :
3. 1. Si aucun de ses voisins n'a la couleur courante, lui affecter la couleur courante.
- **Fonction Welsh-Powell :**
```python
class Graphe:
...
def welsh_powell(self):
# Attribution de la couleur -1
for noeud in self.noeuds:
noeud.couleur = -1
couleur = 0
nb_noeuds_colores = 0
# Tant que tous les noeuds ne sont pas colores
while nb_noeuds_colores < len(self.noeuds):
for noeud in self.noeuds:
couleur_non_attribuee = True
# Si le noeud n'a pas de couleur
if noeud.couleur == -1:
# Verification des voisins
for voisin in noeud.voisins:
# Le voisin a deja la couleur
if voisin.couleur == couleur:
couleur_non_attribuee = False
break
# La couleur n'est pas attribuee
if couleur_non_attribuee:
noeud.couleur = couleur
nb_noeuds_colores += 1
couleur += 1
```
---
## Exercice 3 : Cas pathologiques
Utilisez une fonction clear avant de créer un nouveau graphe !
```python
class Graphe:
...
def clear(self):
self.noeuds = []
```
##### Différents cas pathologiques à implémenter :
- **Clique (paramètre `n`) :**
> Graphe à n noeuds, tous connectés par une arête
<!--
```python
class Graphe:
...
def clique(self, n):
self.clear()
for i in range(n):
self.ajout_noeud(Noeud(str(i)))
for i in range(n):
for j in range(i):
self.ajout_arete(self.noeuds[i], self.noeuds[j])
```
-->
- **Biparti (paramètres `n,p`) :**
> Graphe à n+p nœuds, chacun de n premiers nœuds étant relié à chacun des p derniers
<!--
```python
class Graphe:
...
def biparti(self, n, p):
self.clear()
for i in range(n):
self.ajout_noeud("A"+str(i))
for i in range(p):
self.ajout_noeud("B"+str(i))
for i in range(n):
for j in range(p):
self.ajout_arete(self.noeuds[i], self.noeuds[n+j])
```
-->
- **Cycle (paramètre `n`) :**
> Graphe à n nœuds, chacun étant relié à son successeur et son prédécesseur
<!--
```python
class Graphe:
...
def cycle(self, n):
self.clear()
for i in range(n):
self.ajout_noeud(str(i))
for i in range(n-1):
self.ajout_arete(self.noeuds[i], self.noeuds[i+1])
self.ajout_arete(self.noeuds[0], self.noeuds[-1])
```
-->
- **Pathos :**
> Graphe à 8 nœuds, A, B, ... H. Les noeuds A,C,D,E,G,H forment un cycle, auquel on ajoute les arêtes AB et EF.
<!--
```python
class Graphe:
...
def pathos(self):
self.clear()
nA = self.ajout_noeud("A")
nB = self.ajout_noeud("B")
nC = self.ajout_noeud("C")
nD = self.ajout_noeud("D")
nE = self.ajout_noeud("E")
nF = self.ajout_noeud("F")
nG = self.ajout_noeud("G")
nH = self.ajout_noeud("H")
for n, nn in zip([nA, nC, nD, nE, nG, nH], [nC, nD, nE, nG, nH, nA]):
self.ajout_arete(n, nn)
self.ajout_arete(nA, nB)
self.ajout_arete(nE, nF)
```
-->
#### Nombre chromatique et validation :
- **Nombre chromatique** (nombre de couleurs du graphe) :
<!--
```python
class Graphe:
...
def nombre_chromatique(self):
s = set()
for n in self.noeuds:
s.add(n.couleur)
return len(s)
```
-->
- **Validation couleur** (vérification que chaque noeud a bien une couleur différente de ses voisins) :
<!--
```python
class Graphe:
...
def validation_couleur(self):
for n in self.noeuds:
for v in n.voisins:
if n.couleur == v.couleur:
return False
return True
```
-->
---
## Exercice 4 : Lecture depuis un fichier
On rajoute la position de chaque noeud et on veut pouvoir lire un graphe sauvegardé dans un fichier puis l'afficher !
---
1. Modification du code existant :
- **Ajout :** Variables d'instance `x` et `y` pour la classe `Noeud`.
- **Ajout :** Paramètres `x` et `y` au constructeur de `Noeud`.
- **Ajout :** Paramètres `x` et `y` à la méthode `ajout_noeud` de `Graphe`.
---
2. **Fonction `trouve_noeud(nom)`** qui renvoie le noeud qui a le nom qui correspond dans un graphe ou `None` sinon.
<!--
```python
class Graphe:
...
def trouve_noeud(self, nom):
for n in self.noeuds:
if n.nom == nom:
return n
return None
```
-->
---
3. Fonction de lecture de fichier `lire_fichier()` :
- Présentation du fichier :
```txt
5 <-- Nombre de noeuds
29 -5 0 <-- Définition des noeuds
22 0 3 |
56 2 -4 |
35 5 2 |
44 6 -6 |
29 22 56 <-- Définition des arêtes
22 35 56 29 |
56 29 22 35 44 |
35 22 44 56 |
44 35 56 |
```
- Fonction à écrire :
```python
class Graphe:
...
def lire_fichier(self, nom_de_fichier):
# Ouverture du fichier
# Extraction du nombre de noeuds
# Premiere boucle
# Definition des noeuds
# Deuxieme boucle
# Definition des aretes
```
<!--
```python
class Graphe:
...
def lire_fichier(self, nom_de_fichier):
f = open(nom_de_fichier)
n = int(f.readline().strip())
for i in range(n):
lig = f.readline()
nom, sx, sy = lig.split()
self.ajout_noeud(nom, float(sx), float(sy))
for i in range(n):
lig = f.readline()
tab = lig.split()
n = self.trouve_noeud(tab[0])
for nom in tab[1:]:
v = self.trouve_noeud(nom)
self.ajout_arete(n, v)
```
-->
---
4. Graphe de Petersen :
---
5. Graphe Départements :
###### tags: `python`
Sign in with Wallet
Connect another wallet