import graphviz 

class Graphe():
    """Implémentation d'un graphe avec une liste de successeur
       (dictionnaire d'adjacence)."""
    def __init__(self, dic = {}, oriente=True):
        """Création de l'objet graphe. le graphe est initialisé vide ou avec
           le dictionnaire d'ajdacence optionnel fourni.
           L'argument optionnel oriente permet d'indiquer si le graphe est
           orienté ou non. Cela change l'ajout d'arc (dans le cas d'un graphe
           non-orienté une arête est équivalente à deux arcs réciproques)."""
        self.succ = dic
        self._attributs_sommets = {}
        for s in dic.keys():
            self._attributs_sommets[s] = {}
        self.oriente = oriente

    def ajouter_sommet(self, s):
        """Ajoute le sommet s au graphe s'il n'existe pas"""
        if s not in self.succ:
            self.succ[s] = set()

    def ajouter_arc(self, s1, s2):
        """Ajoute un arc entre les sommets s1 et s2. Les sommets sont crées
           s'ils n'existent pas encore."""
        self.ajouter_sommet(s1)
        self.ajouter_sommet(s2)
        self.succ[s1].add(s2)
        if not self.oriente:        # Si le graphe n'est pas orienté
            self.succ[s2].add(s1)   # On ajoute l'arc réciproque pour créer l'arête

    def voisins(self, s) -> set:
        """Renvoie la liste de tous les voisins du sommet s."""
        if s in self.succ:
            return self.succ[s]
        else:
            return set()
    
    def ordre(self) -> int:
        """Renvoie l'ordre du graphe"""
        return len(self.succ)
    
    def degre(self, s) -> int:
        """Renvie le degré du sommet s."""
        return len(self.succ[s])
    
    def sommets(self) -> list:
        """Renvoie la liste de tous les sommets du graphe."""
        return list(self.succ.keys())
    
    def attributs_sommets(self) -> dict:
        """Renvoie le dictionnaire des attributs des sommets du graphe."""
        return self._attributs_sommets

    def __str__(self):
        """Renvoie une chaîne représentant le graphe sous la forme d’une ligne
           par sommet avec pour chaque sommet, la liste de ses successeurs."""
        chaine = ""
        for s in self.succ:
            chaine += str(s) +  " -> " + str(self.succ[s])
        return chaine

    def dico(self):
        """Renvoie le dictionnaire d'adjacence du graphe"""
        return self.succ

    def afficher(self):
        """Affiche une représentation graphique du graphe en utilisant la
           bibliothèque graphviz. Un graphe graphviz est crée avec les données
           du graphe puis on appelle la méthode view de grahviz pour
           l'afficher."""
        g = graphviz.Graph()
        # Création des sommets
        for s in self.succ.keys():   # Les sommets sont les clés du dictionnaire d'adjacence
            g.node(str(s))
        if self.oriente:
            # Création des arcs
            for s1 in self.succ.keys():
                for s2 in self.succ[s1]:
                    g.edge(str(s1), str(s2))
        else:
            # Création des arêtes
            aretes = set()   # Ensemble des arêtes déjà crées (pour éviter les doublons)
            for s1 in self.succ.keys():
                for s2 in self.succ[s1]:
                    if (str(s1),str(s2)) not in aretes and (str(s2),str(s1)) not in aretes:
                        g.edge(str(s1), str(s2))
                        aretes.add((str(s1),str(s2)))
        g.view()