ASD/graphe.py

import sys
import random
import numpy as np

import triangulation
import tas
import stack


class Graphe:
    """Implémente un graphe non orienté."""

    class Cout:
        CARBURANT = 0
        TEMPS = 1

    def __init__(self, nom):
        """Initialise un graphe vide.

        :param nom: Nom du graphe
        """
        self.nom = nom
        self.sommets = []
        self.aretes = []
        self.cout = None
        self.arrivee = None

    def renomme(self, nom):
        """Renome le graphe

        :param nom: Nouveau nom du graphe.
        """
        self.nom = nom

    def ajouteSommet(self, x, y):
        """Ajoute le sommet s au graphe.

        :param x: abcisse du sommet.
        :param y: ordonnée du sommet.

        :return: Le sommet créé.
        """
        s = Sommet((x, y), len(self.sommets), graphe=self)
        self.sommets.append(s)
        return s

    def connecte(self, s1, s2, longueur, v_moyenne):
        """Connecte les sommets s1 et s2.

        :param s1: premier sommet.
        :param s2: deuxième sommet.
        :param longueur: longueur de l'arrête.
        :param v_moyenne: vitesse moyenne sur l'arrête.

        :return: L'arête créée.
        """
        a = Arete(s1, s2, longueur, v_moyenne, self)
        self.aretes.append(a)
        s1.aretes.add(a)
        s2.aretes.add(a)
        return a

    def n(self):
        """Retourne le nombre de sommets du graphe."""
        return len(self.sommets)

    def m(self):
        """Retourne le nombre d'arrêtes du graphe."""
        return len(self.aretes)

    def __str__(self):
        return "V({nom})=[\n{noeuds}\n]\nE({nom})=[\n{aretes}\n]\n".format(
            nom=self.nom,
            aretes='\n'.join([str(v) for v in self.aretes]),
            noeuds='\n'.join([str(n) for n in self.sommets])
        )

    def trace(self, dest):
        """Affiche le graphe sur la destination.

        :param dest: instance de Afficheur.
        """
        dest.renomme(self.nom)
        for s in self.sommets:
            dest.changeCouleur(s.couleur)
            dest.tracePoint((s.x(), s.y()))
            if hasattr(s, 'nom'):
                dest.traceTexte((s.x(), s.y()), s.nom)
            else:
                dest.traceTexte((s.x(), s.y()), 'v' + str(s.num))

        for a in self.aretes:
            dest.changeCouleur(a.couleur)
            dest.traceLigne((a.s1.x(), a.s1.y()), (a.s2.x(), a.s2.y()))

    def ajouteRoute(self, v1, v2, vmax):
        """Ajoute une route de distance euclidienne entre v1 et v2.

        :param v1: Premier sommet.
        :param v2: Deuxième sommet.
        :param vmax: vitesse maximale sur la route.

        :return: Route créée.
        """
        return self.connecte(v1, v2, v1.distance(v2), vmax)

    def ajouteNationale(self, v1, v2):
        """Ajoute une nationale au graphe. (rouge et vmax = 90km/h).

        :param v1: Premier sommet.
        :param v2: Deuxième sommet.

        :return: route créée.
        """
        a = self.ajouteRoute(v1, v2, 90)
        a.couleur = (1., 0., 0.)
        return a

    def ajouteDepartementale(self, v1, v2):
        """Ajoute une départementale au graphe. (jaune et vmax = 60km/h).

        :param v1: Premier sommet.
        :param v2: Deuxième sommet.

        :return: route créée.
        """
        a = self.ajouteRoute(v1, v2, 60)
        a.couleur = (1., 1., 0.)
        return a

    def dijkstra(self, depart=None):
        """Calcule les plus courts chemins depuis le sommet `depart` (attention,
        effets de bord).

        :param depart: Sommet de départ.
        """
        for s in self.sommets:
            s.cumul = None
            s.precedent = None
        sommets = [depart or self.sommets[0]]
        sommets[0].cumul = 0
        while sommets:
            i, s = min(enumerate(sommets), key=lambda x: x[1].cumul)
            sommets.pop(i)
            for arete in s.aretes:
                voisin = arete.voisin(s)
                if voisin.cumul is None:  # cumul infini
                    sommets.append(voisin)
                if voisin.cumul is None or s.cumul + arete.cout < voisin.cumul:
                    voisin.cumul = s.cumul + arete.cout
                    voisin.precedent = arete

    def dijkstraAvecTas(self, depart=None):
        """Calcule les plus courts chemins depuis le sommet `depart` (attention,
        effets de bord).

        :param depart: Sommet de départ.
        """
        for s in self.sommets:
            s.cumul = None
            s.precedent = None
        sommets = tas.Tas(lambda x: -x.cumul)
        depart = depart or self.sommets[0]
        depart.cumul = 0
        depart.cle = sommets.ajoute(depart)
        while not sommets.empty():
            s = sommets.pop()
            for arete in s.aretes:
                voisin = arete.voisin(s)
                inf = voisin.cumul is None
                if inf or s.cumul + arete.cout < voisin.cumul:
                    voisin.cumul = s.cumul + arete.cout
                    if inf:  # cumul infini
                        voisin.cle = sommets.ajoute(voisin)
                    else:
                        sommets.actualise(voisin.cle)
                    voisin.precedent = arete

    def dijkstraPartiel(self, depart=None, arrivee=None):
        """Calcule les plus courts chemins depuis le sommet `depart` vers
        `arrivee` (attention, effets de bord).

        :param depart: Sommet de départ.
        """
        for s in self.sommets:
            s.cumul = None
            s.precedent = None
        sommets = tas.Tas(lambda x: -x.cumul)
        depart = depart or self.sommets[0]
        arrivee = arrivee or self.sommets[-1]
        depart.cumul = 0
        depart.cle = sommets.ajoute(depart)
        n_visite = 0
        quit = False
        while not (sommets.empty() or quit):
            s = sommets.pop()
            for arete in s.aretes:
                voisin = arete.voisin(s)
                inf = voisin.cumul is None
                if inf or s.cumul + arete.cout < voisin.cumul:
                    voisin.cumul = s.cumul + arete.cout
                    voisin.precedent = arete
                    if inf:  # cumul infini
                        n_visite += 1
                        voisin.couleur = (0.5, 0.9, 0.1)
                        if voisin == arrivee:
                            quit = True
                        voisin.cle = sommets.ajoute(voisin)
                    else:
                        sommets.actualise(voisin.cle)
        return self.cheminOptimal(arrivee), n_visite

    def astar(self, depart=None, arrivee=None):
        """Calcule les plus courts chemins depuis le sommet `depart` vers
        `arrivee` (attention, effets de bord).

        :param depart: Sommet de départ.
        """
        for s in self.sommets:
            s.cumul = None
            s.precedent = None
        self.arrivee = arrivee or self.sommets[-1]
        arrivee = self.arrivee
        sommets = tas.Tas(lambda x: -(x.cumul + x.minCumulRestant))
        depart = depart or self.sommets[0]
        depart.cumul = 0
        depart.cle = sommets.ajoute(depart)
        n_visite = 0
        quit = False
        while not (sommets.empty() or quit):
            s = sommets.pop()
            for arete in s.aretes:
                voisin = arete.voisin(s)
                inf = voisin.cumul is None
                if inf or s.cumul + arete.cout < voisin.cumul:
                    voisin.cumul = s.cumul + arete.cout
                    voisin.precedent = arete
                    if inf:  # cumul infini
                        n_visite += 1
                        voisin.couleur = (0.5, 0.9, 0.1)
                        if voisin == arrivee:
                            quit = True
                        voisin.cle = sommets.ajoute(voisin)
                    else:
                        sommets.actualise(voisin.cle)
        return self.cheminOptimal(arrivee), n_visite

    def traceArbreDesChemins(self):
        """Change la couleur des chemins optimaux en violet-rose
        (252, 17, 189) et le départ en bleu (10, 98, 252).
        """
        for s in self.sommets:
            if s.precedent:
                s.precedent.couleur = (252 / 255, 17 / 255, 189 / 255)
            if not s.cumul:  # sommet de départ
                s.couleur = (10 / 255, 98 / 255, 252 / 255)

    def fixeCarburantCommeCout(self):
        """Fixe le carburant pour cout lors du calcul de plus court chemin."""
        self.cout = Graphe.Cout.CARBURANT

    def fixeTempsCommeCout(self):
        """Fixe le temps pour cout lors du calcul de plus court chemin."""
        self.cout = Graphe.Cout.TEMPS

    def cheminOptimal(self, arrivee):
        """Donne le chemin optimal pour aller à `arrivee` depuis le point
        de départ donné à `dijkstra`.

        :param arrivee: Sommet d'arrivee

        :return: le chemin (liste des arêtes)
        """
        chemin = []
        suivant = arrivee
        while suivant.cumul:
            chemin.append(suivant.precedent)
            suivant = suivant.precedent.voisin(suivant)
        chemin.reverse()
        return chemin

    def colorieChemin(self, chemin, c):
        """Colorie le chemin.

        :param chemin: une liste d'arrêtes
        :param c: une couleur
        """
        for a in chemin:
            a.couleur = c

    def matriceCout(self, tournee):
        """Calcule la matrice de cout d'une tournée.

        :param tournee:La liste des étapes avec en première position le départ.
        :return: la matrice des couts.
        """
        n = len(tournee)
        matrice = np.zeros((n, n))
        for x, sx in enumerate(tournee):
            self.dijkstra(sx)
            for y, sy in enumerate(tournee):
                matrice[x, y] = matrice[y, x] = sy.cumul
        return matrice

    def voyageurDeCommerceNaif(self, tournee):
        """Résout le problème du voyageur de commerce par backtracking.

        :param tournee: La liste des sommets à visiter.
        :return: le cout minimal et l'itinéraire associé.
        """
        meilleurItineraire = []
        minCout = sys.float_info.max
        matrice = self.matriceCout(tournee)
        cout = 0
        visite = [False] * len(tournee)
        visite[0] = True
        itineraire = [0]

        def backtrack():
            nonlocal meilleurItineraire, minCout, matrice, cout, visite, itineraire
            if cout < minCout:
                if len(itineraire) == len(tournee):
                    if cout + matrice[0, itineraire[-1]] < minCout:
                        minCout = cout + matrice[0, itineraire[-1]]
                        meilleurItineraire = [tournee[x] for x in itineraire]
                else:
                    for i, sommet_visite in enumerate(visite):
                        if not sommet_visite:
                            visite[i] = True
                            indicePrec = itineraire[-1]
                            itineraire.append(i)
                            if cout + matrice[i, indicePrec] < minCout:
                                cout += matrice[i, indicePrec]
                                backtrack()
                                cout -= matrice[i, indicePrec]
                            visite[i] = False
                            itineraire.pop()
        backtrack()
        return minCout, meilleurItineraire

    def traceItineraire(self, itineraire):
        """Colorie les arêtes d'un itinéraire.

        :param itineraire: les points de la tournée ordonnés.
        """
        for i, x in enumerate(itineraire):
            x.nom = "s" + str(i)
            suivant = itineraire[(i + 1) % len(itineraire)]
            c, _ = self.astar(x, suivant)
            self.colorieChemin(c, (0.8, 0.1, 0.8))

    def Prim(self):
        """Applique l'algorithme de Prim sur le graphe.
        Les sommets et arêtes sont ajoutés à l'arbre en passant leur flag
        selection à True.

        :return: le poids de l'arbre minimal
        """
        for s in self.sommets:
            s.selection = False
        for a in self.aretes:
            a.selection = False
        aretes = tas.Tas(lambda x: -x.cout)
        for a in self.sommets[0].aretes:
            aretes.ajoute(a)
        self.sommets[0].selection = True
        ptot = 0
        while not aretes.empty():
            a = aretes.pop()
            s1, s2 = a.s1, a.s2
            if not s1.selection or not s2.selection:
                a.selection = True
                ptot += a.cout
                if not s1.selection:
                    s1.selection = True
                    for a_1 in s1.aretes:
                        aretes.ajoute(a_1)
                if not s2.selection:
                    s2.selection = True
                    for a_2 in s2.aretes:
                        aretes.ajoute(a_2)
        return ptot

    def colorieSelection(self, couleur=(0.1, 0.6, 0.2)):
        """Colorie les sommets et arêtes avec le drapeau `selection` à True."""
        for s in self.sommets:
            if s.selection:
                s.couleur = couleur
        for s in self.aretes:
            if s.selection:
                s.couleur = couleur

    def grapheDeCout(self, tournee):
        """Génère le graphe de coût pour la tournée.

        :param tournee: la tournée.
        :return: le graphe de coûts.
        """
        g = Graphe("Graphe de cout de " + self.nom)
        for s in tournee:
            s_a = g.ajouteSommet(s.x(), s.y())
            s_a.image = s
            s.image = s_a

        for i, s in enumerate(g.sommets):
            self.dijkstraAvecTas(s.image)
            for s_v in g.sommets[i:]:
                d = sum((a.cout for a in self.cheminOptimal(s_v.image)))
                g.connecte(s, s_v, d, 1)
        return g

    def tourneeApproximative(self, tournee):
        """Résout le problème du voyageur de commerce de manière approximative.

        :param tournee: les sommets à visiter
        :return: Le chemin optimal approché
        """
        g_cout = self.grapheDeCout(tournee)
        g_cout.Prim()
        pile = stack.Stack()
        pile.add(tournee[0].image)
        tournee[0].image.selection = False
        chemin = [tournee[0]]
        while not pile.empty():
            actuel = pile.pop()
            fils = list(filter(lambda x: x.selection, actuel.aretes))
            if fils:
                a = fils.pop()
                a.selection = False
                nouveau = a.voisin(actuel)
                nouveau.selection = False
                chemin.append(nouveau.image)
                pile.add(actuel)
                pile.add(nouveau)
        return chemin


class Sommet:
    """Implémente un sommet de graphe."""

    def __init__(self, pos, num, couleur=(0., 0., 0.), graphe=None):
        """Initialise un sommet.

        :param pos: couple donnant la position du point.
        :param num: numéro du sommet.
        :param couleur: couleur du sommet.
        """
        self.pos = pos
        self.num = num
        self.couleur = couleur
        self.aretes = set()
        self.cumul = None
        self.precedent = None
        self.graphe = graphe
        self.selection = False
        self.image = None

    @property
    def minCumulRestant(self):
        """Minore le cumul restant pour le sommet considéré.
        """
        x, y = self.graphe.arrivee.pos
        d = ((self.pos[0] - x)**2 + (self.pos[1] - y)**2)**(1 / 2)
        if self.graphe.cout is Graphe.Cout.TEMPS:
            return d / 90  # On minore le temps en divisant par la vitesse max
        elif self.graphe.cout is Graphe.Cout.CARBURANT:
            return d
        else:
            return 0

    def __str__(self):
        return "v{} (x = {} km y = {} km)".format(
            str(self.num),
            str(self.x()),
            str(self.y())
        )

    def distance(self, v):
        """Calcule la distance entre deux points.

        :param v: Point de calcul de la distance.
        """
        return ((self.x() - v.x())**2 + (self.y() - v.y())**2)**(1 / 2)

    def x(self):
        """Retourne l'abcisse de x."""
        return self.pos[0]

    def y(self):
        """Retourne l'ordonnée de y."""
        return self.pos[1]


class Arete:
    """Implémente une arête de graphe."""

    def __init__(self, **kwargs):
        """Initialise une arête.

        :param s1: sommet 1.
        :param s2: sommet 2.
        :param longueur: longueur de l'arête.
        :param v_moyenne: vitesse moyenne sur l'arête.
        :param couleur: couleur de l'arête.
        :param graph: le graphe de l'arête.
        """
        self.s1 = kwargs.get('s1')
        self.s2 = kwargs.get('s2')
        self.s1.aretes.add(self)
        self.s2.aretes.add(self)
        self.longueur = kwargs.get('longueur')
        self.v_moyenne = kwargs.get('v_moyenne')
        self.couleur = kwargs.get('couleur', (0., 0., 0.))
        self.graph = kwargs.get('graph')
        self.selection = False

    def voisin(self, s):
        """Retourne le sommet voisin de s dans l'arête.

        :param s: Un sommet de l'arête.
        """
        if s == self.s1:
            return self.s2
        else:
            return self.s1

    @property
    def cout(self):
        """Retourne le cout de l'arête."""
        if self.graph.cout is Graphe.Cout.TEMPS:
            return self.longueur / self.v_moyenne
        elif self.graph.cout is Graphe.Cout.CARBURANT:
            return self.longueur
        else:
            return 1

    def __str__(self):
        return " v{v1}, v{v2} (long. = {lon} km vlim. = {v} km/h)".format(
            v1=str(self.s1.num),
            v2=str(self.s2.num),
            lon=str(self.longueur),
            v=str(self.v_moyenne)
        )


def pointsAleatoires(n, L):
    """Crée un graphe de n points aléatoires non reliés dans le carré centré en
    0 de largeure L.

    :param n: nombre de points.
    :param L: Côté du carré.
    """
    g = Graphe("Graphe aléatoire")
    for _ in range(n):
        x, y = random.uniform(-L / 2, L / 2), random.uniform(-L / 2, L / 2)
        g.ajouteSommet(x, y)
    return g


def test_gabriel(g, v1, v2):
    """Teste si on peut connecter deux sommets selon le critère de Gabriel.

    :param g: Le graphe.
    :param v1: Premier sommet.
    :param v2: Deuxième sommet.
    """
    milieu = Sommet(((v1.x() + v2.x()) / 2, (v1.y() + v2.y()) / 2), -1)
    rayon = v1.distance(v2) / 2
    ajoute = True
    for v3 in g.sommets:
        if v3 in [v1, v2]:
            continue
        elif v3.distance(milieu) < rayon:
            ajoute = False
            break
    return ajoute


def gabriel(g, ignore_gvr=False):
    """Crée le graphe de Gabriel associé à g avec des routes démartementales.

    :param g: Un graphe sans arrêtes.
    :param ignore_gvr: booléen indiquant si on ne doit pas ajouter une arrête
    quand gvr en ajoute une.
    """
    for v1 in g.sommets:
        for v2 in g.sommets:
            if v2 == v1:
                continue
            if test_gabriel(g, v1, v2):
                if (ignore_gvr and not test_gvr(g, v1, v2)) or not ignore_gvr:
                    g.ajouteDepartementale(v1, v2)


def test_gvr(g, v1, v2):
    """Teste si on peut connecter deux sommets selon le critère GVR.

    :param g: Le graphe.
    :param v1: Premier sommet.
    :param v2: Deuxième sommet.
    """
    rayon = v1.distance(v2)
    ajoute = True
    for v3 in g.sommets:
        if v3 in [v1, v2]:
            continue
        elif v3.distance(v1) < rayon and v3.distance(v2) < rayon:
            ajoute = False
            break
    return ajoute


def gvr(g):
    """Crée le graphe GVR associé à g avec des routes nationales.

    :param g: Un graphe sans arrêtes.
    """
    for v1 in g.sommets:
        for v2 in g.sommets:
            if v2 == v1:
                continue
            if test_gvr(g, v1, v2):
                g.ajouteNationale(v1, v2)


def reseau(g):
    """Construit une carte routière avec comme nationales les routes obtenues
    par la méthode GVR et départementales celles de Gabriel.

    :param g: Un raphe sans arêtes.
    """
    gabriel(g, ignore_gvr=True)
    gvr(g)


def delaunay(g):
    """Crée une triangulation de Delaunay à partir d ' un nuage de point"""
    t = triangulation.Triangulation(g)
    # Définit une fonction destinée à être appelée
    # pour toute paire (s1,s2) de sommets
    # qui forme une arête dans la triangulation de Delaunay.
    # v3 et v4 sont les troisièmes sommets des deux triangles
    # ayant (s1,s2) comme côté.

    def selectionneAretes(graphe, v1, v2, v3, v4):
        # Fait de chaque arête de la triangulation
        # une nationale
        graphe.ajouteNationale(v1, v2)
    # Construit le graphe de retour, égal à la triangulation de Delaunay
    g = t.construitGrapheDeSortie(selectionneAretes)
    g.renomme("Delaunay(" + str(g.n()) + ")")
    return g


def reseauRapide(g):
    """Crée une triangulation de Delaunay à partir d ' un nuage de point"""
    t = triangulation.Triangulation(g)
    # Définit une fonction destinée à être appelée
    # pour toute paire (s1,s2) de sommets
    # qui forme une arête dans la triangulation de Delaunay.
    # v3 et v4 sont les troisièmes sommets des deux triangles
    # ayant (s1,s2) comme côté.

    def selectionneAretes(graphe, v1, v2, v3, v4):
        if test_gabriel(graphe, v1, v2):
            if test_gvr(graphe, v1, v2):
                graphe.ajouteNationale(v1, v2)
            else:
                graphe.ajouteDepartementale(v1, v2)
    # Construit le graphe de retour, égal à la triangulation de Delaunay
    g = t.construitGrapheDeSortie(selectionneAretes)
    g.renomme("Delaunay(" + str(g.n()) + ")")
    return g