ASD/test.py

"""Test des fonctions du TL.

Pour tester la question x_y : `python3 test.py x_y`.

Donc pour la question 3_4 : `python3 test.py 3_4`.
"""

import sys
import random

import graphe
import graphique
import copy
import numpy as np
import matplotlib.pyplot as pl
import time


def creerGrapheFigure1():
    """ Crée le graphe de la figure 1 """
    g = graphe.Graphe("Graphe de la figure 1")
    s1 = g.ajouteSommet(1.0, 1.0)
    s2 = g.ajouteSommet(2.0, 3.5)
    s3 = g.ajouteSommet(2.5, 2.5)
    s4 = g.ajouteSommet(5.0, 2.0)
    s1.couleur = (1., 1., 0.)
    s2.couleur = (0., 0., 1.)
    s3.couleur = (1., 0., 0.)
    s4.couleur = (1., 1., 0.)
    a = g.connecte(s1, s2, 4.0, 90.)
    a.couleur = (1., 1., 0.)
    g.connecte(s1, s4, 5.2, 124.)
    g.connecte(s2, s3, 2.0, 54.)
    g.connecte(s2, s4, 5.0, 90.)
    return g


def testQuestion1_2():
    """' Teste que la création d ' un graphe ne plante pas
    print ”Question 1.2 :"""
    creerGrapheFigure1()
    print("Ok. Pas de plantage")


def testQuestion1_3():
    """ Teste l ' affichage d ' un graphe dans la console"""
    print("Question 1.3 :")
    g = creerGrapheFigure1()
    print(g)


def testQuestion1_4():
    """ Teste du dessin d'un graphe."""
    print("Question 1.4:")
    graphique.affiche(creerGrapheFigure1(), (3., 2.), 100.)


def testQuestion2_2():
    """Teste de génération aléatoire de graphe."""
    print("Question 2.2:")
    graphique.affiche(graphe.pointsAleatoires(5, 30), (0, 0), 10.)


def testQuestion2_4():
    """Teste de gabriel et gvr."""
    print("Question 2.4")
    g = graphe.pointsAleatoires(30, 30)
    g.renomme("Gabriel")
    g1 = copy.deepcopy(g)
    g1.renomme("GVR")
    graphe.gabriel(g)
    graphe.gvr(g1)
    graphique.affiche(g, (0, 0), 10., blocage=False)
    graphique.affiche(g1, (0, 0), 10.)


def testQuestion2_5():
    """Teste de la création de réseau."""
    g = graphe.pointsAleatoires(30, 30)
    graphe.reseau(g)
    graphique.affiche(g, (0, 0), 10.)


def chronometre(fonctionTest, fonctionPreparation, parametres):
    ''' Mesure le temps d ' exécution fonctionTest pour différentes valeurs d '
    un paramètres '''
    temps = []
    # Pour chaque valeur de paramètre
    for p in parametres:
        # Lance le test pour ces entrées
        print("t({}) = ".format(p), end="", flush=True)
        t = []
        for i in range(10):
            entrees = fonctionPreparation(p)
            debut = time.time()
            fonctionTest(entrees)
            fin = time.time()
            # Mesure le temps d ' exécution
            t.append(fin - debut)
        t = sum(t)/10
        print("{:.2f} s".format(t))
        temps.append(t)
    return temps


def testQuestion2_6():
    """Mesure la performance de graphe.reseau"""
    def prepare(p): return graphe.pointsAleatoires(p, 10)
    valeurs_n = list(map(int, np.logspace(1, 2.7, 100)))
    temps = chronometre(graphe.reseau, prepare, valeurs_n)
    pl.close('all')
    pl.title("Mesure du temps d'exécution de `reseau`.")
    pl.plot(valeurs_n, temps)
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()
    pl.title("Mesure du temps d'exécution de `reseau`.")
    pl.loglog(valeurs_n, temps, label='temps de calcul')
    pl.loglog(valeurs_n, (lambda x: x**3)(valeurs_n), label='$x\mapsto x^3$')
    pl.legend(loc='best')
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()


def testQuestion2_7():
    """Compare la création de graphe de gabriel et ed delaunay."""
    def prepare(p): return graphe.pointsAleatoires(p, 10)
    valeurs_n = np.arange(1, 200)
    temps1 = chronometre(graphe.gabriel, prepare, valeurs_n)
    temps2 = chronometre(graphe.delaunay, prepare, valeurs_n)
    pl.close('all')
    pl.title("Comparaison du temps pour `delaunay` et `gabriel`")
    pl.plot(valeurs_n, temps1, label='gabriel')
    pl.plot(valeurs_n, temps2, label='delaunay')
    pl.legend(loc='best')
    pl.xlabel('n')
    pl.ylabel('temps')
    pl.show()


def testQuestion2_8():
    """Compare le reseau naif et non naif."""
    g = graphe.pointsAleatoires(30, 30)
    g1 = copy.deepcopy(g)
    g.renomme("Naïf")
    g1.renomme("Non naïf")

    graphe.reseau(g)
    graphe.reseauRapide(g1)
    graphique.affiche(g, (0, 0), 10.)
    graphique.affiche(g1, (0, 0), 10.)


def testQuestion2_9():
    """Compare le temps de création des deux méthodes de création de réseau"""
    def prepare(p): return graphe.pointsAleatoires(p, 10)
    valeurs_n = list(map(lambda x: int(x), np.logspace(1, 3, 30)))
    temps1 = chronometre(graphe.reseau, prepare, valeurs_n)
    temps2 = chronometre(graphe.reseauRapide, prepare, valeurs_n)
    pl.close('all')
    pl.title("Comparaison du temps d'exécution de `reseau` et `reseauRapide`.")
    pl.plot(valeurs_n, temps1, label='reseau')
    pl.plot(valeurs_n, temps2, label='reseauRapide')
    pl.legend(loc='best')
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()
    pl.title("Comparaison du temps d'exécution de `reseau` et `reseauRapide`.")
    pl.loglog(valeurs_n, temps1, label='reseau')
    pl.loglog(valeurs_n, temps2, label='reseauRapide')
    pl.legend(loc='best')
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()


def testQuestion3_1():
    """Trace le plus court chemin avec dijkstra."""
    g = graphe.pointsAleatoires(30, 30)
    g.renomme("Dijkstra")

    graphe.reseauRapide(g)
    g.dijkstra(g.sommets[0])
    g.traceArbreDesChemins()
    graphique.affiche(g, (0, 0), 10.)


def testQuestion3_2():
    """Trace le plus court chemin avec dijkstra."""
    g = graphe.pointsAleatoires(30, 30)
    g.renomme("Dijkstra")

    graphe.reseauRapide(g)
    g.fixeTempsCommeCout()
    g.dijkstra(g.sommets[0])
    g.traceArbreDesChemins()
    g.renomme("Temps")
    graphique.affiche(g, (0, 0), 10., blocage=False)
    g.fixeCarburantCommeCout()
    g.dijkstra(g.sommets[0])
    g.traceArbreDesChemins()
    g.renomme("Carburant")
    graphique.affiche(g, (0, 0), 10.)


def testQuestion3_3():
    """Mesure le temps d'exécution de Dijkstra."""
    def prepare(p): return graphe.reseauRapide(graphe.pointsAleatoires(p, 100))
    valeurs_n = list(map(lambda x: int(x), np.logspace(1, 3, 100)))
    temps = chronometre(graphe.Graphe.dijkstra, prepare, valeurs_n)

    def f(x): return x*np.log(x)
    theorie = [f(x) for x in valeurs_n]
    pl.close('all')
    pl.title("Temps d'exécution en fonction de la taille du graphe.")
    pl.plot(valeurs_n, temps, label="Dijkstra")
    pl.plot(valeurs_n, theorie, label="$x \mapsto x\log x$")
    pl.legend(loc="best")
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()
    pl.title("Temps d'exécution en fonction de la taille du graphe.")
    pl.loglog(valeurs_n, temps)
    pl.loglog(valeurs_n, theorie, label="$x \mapsto x\log x$")
    pl.legend(loc="best")
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()


def testQuestion3_4():
    """Trace le plus court chemin avec dijkstra."""
    g = graphe.pointsAleatoires(30, 30)
    g.renomme("Plus court chemin")

    graphe.reseauRapide(g)
    g.fixeTempsCommeCout()
    g.dijkstra(g.sommets[0])
    c = g.cheminOptimal(g.sommets[-1])
    g.colorieChemin(c, (0., 1., 0.))
    g.renomme("Temps")
    graphique.affiche(g, (0, 0), 10.)


def testQuestion3_5():
    """Trace le plus court chemin avec dijkstra."""
    g = graphe.pointsAleatoires(30, 30)
    g.fixeTempsCommeCout()

    graphe.reseauRapide(g)
    g.dijkstra(g.sommets[0])
    g.traceArbreDesChemins()
    g.renomme("Liste")
    graphique.affiche(g, (0, 0), 10., blocage=False)
    g.dijkstraAvecTas(g.sommets[0])
    g.traceArbreDesChemins()
    g.renomme("Tas")
    graphique.affiche(g, (0, 0), 10.)


def testQuestion3_6():
    """Compare Dijkstra avec et sans tas."""
    def prepare(p): return graphe.reseauRapide(graphe.pointsAleatoires(p, 10))
    valeurs_n = list(map(lambda x: int(x), np.logspace(1, 3, 10)))
    temps1 = chronometre(graphe.Graphe.dijkstra, prepare, valeurs_n)
    temps2 = chronometre(graphe.Graphe.dijkstraAvecTas, prepare, valeurs_n)
    pl.close('all')
    pl.title("Comparaison du temps d'exécution de `dijkstra` et `dijkstraAvecTas`.")
    pl.plot(valeurs_n, temps1, label='Dijkstra')
    pl.plot(valeurs_n, temps2, label='Dijkstra avec tas')
    pl.legend(loc='best')
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()
    pl.title("Comparaison du temps d'exécution de `reseau` et `reseauRapide`.")
    pl.loglog(valeurs_n, temps1, label='Dijkstra')
    pl.loglog(valeurs_n, temps2, label='Dijkstra avec tas')
    pl.legend(loc='best')
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()


def testQuestion3_7():
    """Trace le plus court chemin avec dijkstra."""
    g = graphe.pointsAleatoires(30, 30)
    g.fixeTempsCommeCout()

    graphe.reseauRapide(g)
    g.dijkstraPartiel(g.sommets[0], g.sommets[-1])
    g.traceArbreDesChemins()
    g.renomme("Dijkstra partiel")
    graphique.affiche(g, (0, 0), 10.)


def testQuestion3_8():
    """Trace le plus court chemin avec dijkstra."""
    g = graphe.pointsAleatoires(30, 30)
    g.fixeCarburantCommeCout()

    graphe.reseauRapide(g)
    g.astar(g.sommets[0], g.sommets[-1])
    g.traceArbreDesChemins()
    g.renomme("A*")
    graphique.affiche(g, (0, 0), 10., blocage=False)
    g.dijkstraPartiel(g.sommets[0], g.sommets[-1])
    g.traceArbreDesChemins()
    g.renomme("Dijkstra partiel")
    graphique.affiche(g, (0, 0), 10.)


def testQuestion3_9():
    """Compare Dijkstra avec et sans tas et A*."""
    def prepare(p): return graphe.reseauRapide(graphe.pointsAleatoires(p, 10))
    valeurs_n = list(map(lambda x: int(x), np.logspace(1, 2.5, 30)))
    temps1 = chronometre(graphe.Graphe.dijkstra, prepare, valeurs_n)
    temps2 = chronometre(graphe.Graphe.dijkstraPartiel, prepare, valeurs_n)
    temps3 = chronometre(graphe.Graphe.astar, prepare, valeurs_n)
    pl.close('all')
    pl.title(
        "Comparaison du temps d'exécution de `dijkstra`, `dijkstraPartiel` et `astar`.")
    pl.plot(valeurs_n, temps1, label='Dijkstra')
    pl.plot(valeurs_n, temps2, label='Dijkstra partiel avec tas')
    pl.plot(valeurs_n, temps3, label='A*')
    pl.legend(loc='best')
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()
    pl.title(
        "Comparaison du temps d'exécution de `dijkstra`, `dijkstraPartiel` et `astar`.")
    pl.loglog(valeurs_n, temps1, label='Dijkstra')
    pl.loglog(valeurs_n, temps2, label='Dijkstra partiel avec tas')
    pl.loglog(valeurs_n, temps3, label='A*')
    pl.legend(loc='best')
    pl.xlabel("n")
    pl.ylabel("temps")
    pl.show()


def testQuestion4_1():
    """Trace le plus court chemin avec dijkstra."""
    g = graphe.pointsAleatoires(30, 30)

    graphe.reseauRapide(g)
    g.renomme("graphe")
    print("Points 0,1 et 2")
    tournee = [g.sommets[i] for i in (0, 1, 2)]
    print(g.matriceCout(tournee))
    graphique.affiche(g, (0, 0), 10.)


def testQuestion4_2():
    g = graphe.pointsAleatoires(30, 30)

    graphe.reseauRapide(g)
    g.renomme("graphe")
    print("Points 0,1,2 et 7")
    tournee = [g.sommets[i] for i in (0, 1, 2, 7)]
    cout, iti = g.voyageurDeCommerceNaif(tournee)
    g.traceItineraire(iti)
    graphique.affiche(g, (0, 0), 10.)


def testQuestion4_3():
    """Mesure le temps de calcul."""
    g = graphe.reseauRapide(graphe.pointsAleatoires(1000, 1000))

    def prepare(p): return random.sample(g.sommets, p)
    valeurs_n = list(map(int, np.linspace(1, 11, 10)))
    temps = chronometre(g.voyageurDeCommerceNaif, prepare, valeurs_n)
    pl.close('all')
    pl.title("Temps d'exécution pour le voyageur de commerce.")
    pl.plot(valeurs_n, temps)
    pl.xlabel("n (nombre de points de la tournée)")
    pl.ylabel("temps")
    pl.show()
    pl.title("Temps d'exécution pour le voyageur de commerce.")
    pl.loglog(valeurs_n, temps)
    pl.xlabel("n (nombre de points de la tournée)")
    pl.ylabel("temps")
    pl.show()


def testQuestion4_6():
    g = graphe.pointsAleatoires(30, 30)

    graphe.reseauRapide(g)
    g.fixeTempsCommeCout()
    g.renomme("Algorithme de Prim (cout=temps)")
    p = g.Prim()
    print("Poids de prim:", p)
    g.colorieSelection()
    graphique.affiche(g, (0, 0), 10.)


def testQuestion4_7():
    g = graphe.pointsAleatoires(30, 30)

    graphe.reseauRapide(g)
    g.fixeTempsCommeCout()
    g.renomme("Graphe de test (cout=temps)")
    tournee = [g.sommets[i] for i in (0, 1, 2, 7)]
    g1 = g.grapheDeCout(tournee)
    graphique.affiche(g, (0, 0), 10., blocage=False)
    graphique.affiche(g1, (0, 0), 10.)


def testQuestion4_8():
    g = graphe.pointsAleatoires(30, 30)

    graphe.reseauRapide(g)
    g.fixeTempsCommeCout()
    g.renomme("Graphe de test (cout=temps) tournée approximative")
    g1 = copy.deepcopy(g)
    g1.renomme("Graphe de test (cout=temps) tournée naïve")
    print("Tournée 0, 1, 2, 7")
    tournee = [g.sommets[i] for i in (0, 1, 2, 7)]
    iti = g.tourneeApproximative(tournee)
    g.traceItineraire(iti)
    tournee = [g1.sommets[i] for i in (0, 1, 2, 7)]
    cout, iti = g1.voyageurDeCommerceNaif(tournee)
    g1.traceItineraire(iti)
    graphique.affiche(g, (0, 0), 10., blocage=False)
    graphique.affiche(g1, (0, 0), 10.)


def testQuestion4_9():
    """Mesure le temps de calcul."""
    g = graphe.reseauRapide(graphe.pointsAleatoires(1000, 1000))

    def prepare(p): return random.sample(g.sommets, p)
    valeurs_n = list(map(int, np.logspace(1, 3, 30)))
    temps = chronometre(g.tourneeApproximative, prepare, valeurs_n)
    pl.close('all')
    pl.title("Temps d'exécution pour le voyageur de commerce approximatif.")
    pl.plot(valeurs_n, temps)
    pl.xlabel("n (nombre de points de la tournée)")
    pl.ylabel("temps")
    pl.show()
    pl.title("Temps d'exécution pour le voyageur de commerce approximatif.")
    pl.loglog(valeurs_n, temps)
    pl.xlabel("n (nombre de points de la tournée)")
    pl.ylabel("temps")
    pl.show()


if __name__ == '__main__':
    n = sys.argv[1]
    if n in ('--help', '-h'):
        print(__doc__)
    else:
        print('Question ', n)
        locals()['testQuestion'+n]()