graph.py

'''
module graph: définition d'une classe Graph
'''

class Maillon:
    '''
    maillon pour File
    '''
    def __init__(self, value):
        self.value = value
        self.next = None

class File:
    '''
    version réduite de la classe File
    utilisée pour les parcours en largeur
    '''
    def __init__(self):
        self.__root = None
        self.__last = None
    def isEmpty(self):
        return self.__root == None
    def push(self, value):
        # insertion en bout de file
        if self.__root == None:
            self.__root = Maillon(value)
            self.__last = self.__root
            return
        newM = Maillon(value)
        self.__last.next = newM
        self.__last = newM
    def pop(self):
        assert not self.isEmpty(), "La file est vide"
        headingMaillon = self.__root
        self.__root = headingMaillon.next
        if self.__root == None:
            self.__last = None
        headingMaillon.next = None
        return headingMaillon.value

class Graph:
    def __init__(self, oriented = False):
        '''
        __vertex: dictionnaire donc chaque paire est :
          clé : étiquette d'un sommet
          valeur: tableau des sommets pouvant être atteints
        oriented: True pour un graphe orienté
        '''
        self.__vertex = {}
        self.__oriented = oriented

    def ordre(self):
        '''
        renvoie l'ordre du graphe = nombre de vertex
        '''
        return len(self.__vertex)

    def add_vertex(self, label):
        '''
        ajoute un sommet
        label : étiquette du sommet. label de n'importe quel type.
          pas d'effet si le sommet existe déjà
        '''
        if not self.has_vertex(label):
            self.__vertex[label] = []

    def add_edge(self, label1, label2):
        '''
        ajoute une arête entre les sommets étiquetés par label1 et label2
          si l'arête existe déjà, pas d'effet
        préconditions :
          les sommets existent dans le graphe
          label1 != label2 pour un graphe non orienté
        '''
        if self.__oriented:
            # cas graphe orienté
            if self.is_successor(label1, label2):
                return
            self.__vertex[label1].append(label2)
            return
        # non orienté
        assert label1 != label2, "Les deux sommets doivent être distincts"
        if self.are_neighbours(label1, label2):
            return
        self.__vertex[label1].append(label2)
        self.__vertex[label2].append(label1)

    def remove_edge(self, label1, label2):
        '''
        supprime une arête entre les sommets étiquetés par label1 et label2
          aucun effet si l'arête est absente du graphe
        préconditions :
          les sommets existent dans le graphe
          il y a une arête entre ces sommets
        '''
        if not self.__oriented:
            if not self.are_neighbours(label1, label2):
                return
            self.__vertex[label1].remove(label2)
            self.__vertex[label2].remove(label1)
            return
        if not self.is_successor(label1, label2):
            return
        self.__vertex[label1].remove(label2)

    def are_neighbours(self, label1, label2):
        '''
        renvoie True si les labels existent dans le graphe
        et qu'ils sont voisins. False sinon.
        '''
        assert self.has_vertex(label1)
        assert self.has_vertex(label2)
        return label1 in self.__vertex[label2] and label2 in self.__vertex[label1]

    def has_vertex(self, label):
        '''
        prédicat: True s'il y a un sommet étiqueté label dans le graphe
        '''
        return label in self.__vertex

    def degre(self, label, sortant = True):
        '''
        renvoie le degré du sommet étiqueté par label dans le graphe
        sortant : True si on demande le degré sortant
          sans effet pour un graphe non orienté
        précondition : le sommet existe
        '''
        if not self.__oriented or sortant:
            return len(self.successors(label))
        # cas orienté et entrant
        return len(self.antecedents(label))

    def is_successor(self, label1, label2):
        '''
        renvoie True si label1 -> label2
        précondition: label1 dans le graph
        '''
        return label2 in self.successors(label1)


    def successors(self, label):
        '''
        renvoie une copie du tableau des successeurs de label
        précondtion: label est dans le graphe
        '''
        assert self.has_vertex(label), "Le sommet {} n'est pas dans le graphe".format(label)
        return self.__vertex[label].copy()

    def antecedents(self, label):
        '''
        renvoie le tableau des antecedents de label
        précondtion: label est dans le graphe
        '''
        assert self.has_vertex(label), "Le sommet {} n'est pas dans le graphe".format(label)
        return [label2 for label2 in self.__vertex if self.is_successor(label2, label)]

    def adjacence(self):
        '''
        renvoie les étiquettes des sommets et la matrice d'ajacence
        '''
        labels = list(self.__vertex.keys())
        matrice = []
        for labelSource in labels:
            line = []
            for labelDest in labels:
                if self.is_successor(labelSource, labelDest):
                    line.append(1)
                else:
                    line.append(0)
            matrice.append(line)
        return labels, matrice

    def __str__(self):
        '''
        transtypage => str
        '''
        output = []
        for label in self.__vertex:
            voisins = [str(it) for it in self.successors(label)]
            line = "{} -> {}".format(label, ', '.join(voisins) )
            output.append(line)
        return "\n".join(output)

    def __repr__(self):
        '''
        représentation console
        '''
        return "<Graph: {}>".format(str(self))

    def has_cycle(self):
        '''
        result: True si le graphe contient un cycle
        précondition : graphe non-orienté
        '''
        assert not self.__oriented, "La méthode has_cycle ne fonctionne que pour le cas non-orienté"
        marques = {}
        for v in self.__vertex:
            marques[v] = None
        f = File()

        notVisited = [vertex for vertex in self.__vertex]
        while notVisited != []:
            firstVertex = notVisited.pop()
            marques[firstVertex] = 0
            f.push(firstVertex)
            while not f.isEmpty():
                s = f.pop()
                for v in self.successors(s):
                    if marques[v] == None:
                        marques[v] = marques[s] + 1
                        f.push(v)
                        notVisited.remove(v)
                    elif marques[v] >= marques[s]:
                        print(v)
                        print(s)
                        return True
        return False

    def coloration(self):
        '''
        result: dict dont les sommets sont les clés, les valeurs un numéro représentant une couleur
        '''
        assert not self.__oriented, "La coloration recquiert un graphe non orienté."
        couleurs = {} # couleurs attribuées
        #sommets par ordre décroissant de degré
        vertexList = list(self.__vertex.keys())
        N = len(vertexList)
        vertexList.sort(key=self.degre, reverse=True)
        col = 0
        for index in range(N):
            sommet = vertexList[index]
            if sommet in couleurs:
                # déjà coloré, on passe au suivant
                continue
            couleurs[sommet] = col
            # recherche des sommets suivants
            for sommet in vertexList[index+1:]:
                if sommet not in couleurs and not self.__hasAdjacentCol(sommet, col, couleurs):
                    couleurs[sommet] = col
            col += 1
        return couleurs

    def __hasAdjacentCol(self, sommet, col, couleurs):
        '''
        méthode accessoire : vérifie si le sommet a déjà un
        voisin de la couleur col
        '''
        for voisin in self.successors(sommet):
            if couleurs.get(voisin) == col:
                return True
        return False