# 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 :
## 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:

# 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:

* Code donné :

import visugraphe

# Insérer ici les définitions des classes Graphe et Noeud

if __name__ == "__main__":
    g = Graphe()
    nA = g.ajout_noeud("A")
    nB = g.ajout_noeud("B")
    nC = g.ajout_noeud("C")
    nD = g.ajout_noeud("D")
    nE = g.ajout_noeud("E")
    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)

### Classe Noeud :

class Noeud:
    def __init__(self, ...):
        ...
        

* Solution : :

class Noeud:
    def __init__(self, nom):
        self.nom = nom
        self.couleur = 0
        self.voisins = []

### Classe Graphe :

class Graphe:
    def __init__(self):
        ...

* Solution :

class Graphe:
    def __init__(self):
        self.noeuds = []

    def ajout_noeud(self, nom):
        """ nom est de type str
            renvoie le noeud créé
        """
        n = Noeud(nom)
        self.noeuds.append(n)
        return n

    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:

import visugraphe

class Graphe:
    def __init__(self):
        self.noeuds = []

    def ajout_noeud(self, nom):
        """ nom est de type str
            renvoie le noeud créé
        """
        n = Noeud(nom)
        self.noeuds.append(n)
        return n

    def ajout_arete(self, n1, n2):
        if n2 not in n1.voisins:
            n1.voisins.append(n2)
            n2.voisins.append(n1)

    def welsh_powell_1(self):
        li = []
        for n in self.noeuds:
            n.couleur = -1
            li.append((len(n.voisins), n.nom, n))
        li.sort()
        li.reverse()
        c = 0
        while len(li)!=0:
            for deg, nom, n in li:
                ok = True
                for v in n.voisins:
                    if v.couleur == c:
                        ok = False
                        break
                if ok:
                    n.couleur = c
            for i in range(len(li)-1, -1, -1):
                if li[i][2].couleur == c:
                    li.pop(i)
            c += 1

    def welsh_powell_2(self):
        li = []
        for n in self.noeuds:
            n.couleur = -1
            li.append((-len(n.voisins), n.nom, n))
        li.sort()
        c = 0
        nbcol = 0
        while nbcol<len(li):
            for deg, nom, n in li:
                ok = True
                if n.couleur == -1:
                    for v in n.voisins:
                        if v.couleur == c:
                            ok = False
                            break
                    if ok:
                        n.couleur = c
                        nbcol += 1
            c += 1
            
class Noeud:
    def __init__(self, nom):
        self.nom = nom
        self.couleur = 0
        self.voisins = []

if __name__ == "__main__":
    g = Graphe()
    nA = g.ajout_noeud("A")
    nB = g.ajout_noeud("B")
    nC = g.ajout_noeud("C")
    nD = g.ajout_noeud("D")
    nE = g.ajout_noeud("E")
    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)
    g.welsh_powell_1()
    # g.welsh_powell_2()
    visugraphe.visu_graphe_couleur(g)

# Exercice 3 : Graphes usuels et pathologiques :
Utilisez une fonction clear avant de créer un nouveau graphe !

class Graphe:
    ...
    def clear(self):
        self.noeuds = []

-----------------
------------------

* **Clique (paramètre n) :**

Graphe à n noeuds, tous connectés par une arête.

* **Biparti (paramètres n,p) :**

Graphe à n+p nœuds, chacun de n premiers nœuds étant relié à chacun des p derniers.


* **Cycle (paramètre n) :**

Graphe à n nœuds, chacun étant relié à son successeur et son prédécesseur.

* **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.

* **Nombre chromatique et validation :**
1. Nombre chromatique (nombre de couleurs du graphe)
2. Validation couleur (vérification que chaque noeud a bien une couleur différente de ses voisins)

# solution :

import visugraphe
import sys

class Graphe:
    def __init__(self):
        self.noeuds = []

    def clear(self):
        self.noeuds=[]

    def ajout_noeud(self, nom):
        """ nom est de type str
            renvoie le noeud créé
        """
        n = Noeud(nom)
        self.noeuds.append(n)
        return n

    def ajout_arete(self, n1, n2):
        if n2 not in n1.voisins:
            n1.voisins.append(n2)
            n2.voisins.append(n1)

    def clique(self, n):
        self.clear()
        for i in range(n):
            self.ajout_noeud(str(i))
        for i in range(n):
            for j in range(i):
                self.ajout_arete(self.noeuds[i], self.noeuds[j])
            
    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])

    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])

    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)

    def validation_couleur(self):
        for n in self.noeuds:
            for v in n.voisins:
                if n.couleur == v.couleur:
                    return False
        return True
    
    def nombre_chromatique(self):
        s = set()
        for n in self.noeuds:
            s.add(n.couleur)
        return len(s)
        
    def welsh_powell_1(self):
        li = []
        for n in self.noeuds:
            n.couleur = -1
            li.append((len(n.voisins), n.nom, n))
        li.sort()
        li.reverse()
        c = 0
        while len(li)!=0:
            for deg, nom, n in li:
                ok = True
                for v in n.voisins:
                    if v.couleur == c:
                        ok = False
                        break
                if ok:
                    n.couleur = c
            for i in range(len(li)-1, -1, -1):
                if li[i][2].couleur == c:
                    li.pop(i)
            c += 1

    def welsh_powell_2(self):
        li = []
        for n in self.noeuds:
            n.couleur = -1
            li.append((-len(n.voisins), n.nom, n))
        li.sort()
        c = 0
        nbcol = 0
        while nbcol<len(li):
            for deg, nom, n in li:
                ok = True
                if n.couleur == -1:
                    for v in n.voisins:
                        if v.couleur == c:
                            ok = False
                            break
                    if ok:
                        n.couleur = c
                        nbcol += 1
            c += 1
            
class Noeud:
    def __init__(self, nom):
        self.nom = nom
        self.couleur = 0
        self.voisins = []

if __name__ == "__main__":
    g = Graphe()
    if sys.argv[1] == "clique":
        g.clique(int(sys.argv[2]))
    elif sys.argv[1] == "biparti":
        g.biparti(int(sys.argv[2]), int(sys.argv[3]))
    elif sys.argv[1] == "cycle":
        g.cycle(int(sys.argv[2]))
    elif sys.argv[1] == "pathos":
        g.pathos()
    g.welsh_powell_1()
    # g.welsh_powell_2()
    if sys.argv[1] == "pathos" and len(sys.argv)>2 and sys.argv[2]=="manuel":
        for i in [0,3,5,6]:
            g.noeuds[i].couleur = 0
        for i in [1, 2, 4, 7]:
            g.noeuds[i].couleur = 1
    if g.validation_couleur():
        print("Nombre chromatique estimé :", g.nombre_chromatique())
    else:
        print("Coloration incorrecte")
    visugraphe.visu_graphe_couleur(g)

# Exercice 4 : Lecture de graphe depuis un fichier:

# Solution :

import visugraphe
import sys

class Graphe:
    def __init__(self):
        self.noeuds = []

    def clear(self):
        self.noeuds=[]

    def ajout_noeud(self, nom, x=0, y=0):
        """ nom est de type str
            renvoie le noeud créé
        """
        n = Noeud(nom, x, y)
        self.noeuds.append(n)
        return n

    def ajout_arete(self, n1, n2):
        if n2 not in n1.voisins:
            n1.voisins.append(n2)
            n2.voisins.append(n1)

    def trouve_noeud(self, nom):
        for n in self.noeuds:
            if n.nom == nom:
                return n
        return None

    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)
    
    def validation_couleur(self):
        for n in self.noeuds:
            for v in n.voisins:
                if n.couleur == v.couleur:
                    return False
        return True
    
    def nombre_chromatique(self):
        s = set()
        for n in self.noeuds:
            s.add(n.couleur)
        return len(s)
        
    def welsh_powell_1(self):
        li = []
        for n in self.noeuds:
            n.couleur = -1
            li.append((len(n.voisins), n.nom, n))
        li.sort()
        li.reverse()
        c = 0
        while len(li)!=0:
            for deg, nom, n in li:
                ok = True
                for v in n.voisins:
                    if v.couleur == c:
                        ok = False
                        break
                if ok:
                    n.couleur = c
            for i in range(len(li)-1, -1, -1):
                if li[i][2].couleur == c:
                    li.pop(i)
            c += 1

    def welsh_powell_2(self):
        li = []
        for n in self.noeuds:
            n.couleur = -1
            li.append((-len(n.voisins), n.nom, n))
        li.sort()
        c = 0
        nbcol = 0
        while nbcol<len(li):
            for deg, nom, n in li:
                ok = True
                if n.couleur == -1:
                    for v in n.voisins:
                        if v.couleur == c:
                            ok = False
                            break
                    if ok:
                        n.couleur = c
                        nbcol += 1
            c += 1
            
class Noeud:
    def __init__(self, nom, x=0, y=0):
        self.nom = nom
        self.couleur = 0
        self.x = x
        self.y = y
        self.voisins = []

if __name__ == "__main__":
    g = Graphe()
    g.lire_fichier(sys.argv[1])
    for n in g.noeuds:
        print(n.nom, n.x, n.y)
    g.welsh_powell_1()
    # g.welsh_powell_2()
    if g.validation_couleur():
        print("Nombre chromatique estimé :", g.nombre_chromatique())
    else:
        print("Coloration incorrecte")
    visugraphe.visu_graphe_coord(g)