be-graphes/be-graphes-algos/src/test/java/org/insa/graphs/algorithm/utils/PccAlgorithmTest.java

package org.insa.graphs.algorithm.utils;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.List;

import org.insa.graphs.algorithm.shortestpath.ShortestPathAlgorithm;
import org.insa.graphs.algorithm.shortestpath.ShortestPathData;
import org.insa.graphs.algorithm.shortestpath.ShortestPathSolution;

import org.insa.graphs.algorithm.ArcInspector;
import org.insa.graphs.algorithm.ArcInspectorFactory;
import org.insa.graphs.algorithm.AbstractInputData.Mode;
import org.insa.graphs.algorithm.AbstractSolution.*;

import org.insa.graphs.model.Graph;
import org.insa.graphs.model.Arc;
import org.insa.graphs.model.Node;
import org.insa.graphs.model.Path;

import org.insa.graphs.model.io.BinaryGraphReader;
import org.insa.graphs.model.io.BinaryPathReader;
import org.insa.graphs.model.io.GraphReader;
import org.insa.graphs.model.io.PathReader;


public abstract class PccAlgorithmTest {

    // Oracle (généré à partir du Bellman Ford)
    String hauteGaronneFileName = "./Maps/haute-garonne.mapgr";
    String lfboInsaPathName = "./Paths/LFBO_INSA_correct.path";
    Graph hauteGaronne;
    Path LfboInsa;

    // Outils
    PathReader pathReader;
    ArcInspector inspector;

    // Solution trouvée par l'algorithme donné pour le chemin LFBO - INSA
    ShortestPathSolution solutionTrouveeLfboInsa;

    class Scenario {
        Graph graph;
        Mode nc;
        Node origine;
        Node destination;

        public Scenario(Graph graph, Mode nc, Node origine, Node destination) {
            this.graph = graph;
            this.origine = origine;
            this.destination = destination;
            this.nc = nc;
        }
    }


    protected abstract ShortestPathAlgorithm createAlgorithm(ShortestPathData data);

    /**
     * Fonction utilitaire, test un scenario donné
     * @param scenario
     * @return
     */
    public ShortestPathSolution testScenario(Scenario scenario) {
        // Préparation des données
        ShortestPathData data = new ShortestPathData(scenario.graph, scenario.origine, scenario.destination, inspector);
        // Préparation de l'algorithme
        ShortestPathAlgorithm algo = createAlgorithm(data);
        // Lancement de l'algorithme
        return algo.run();
    }

    /**
     * Fonction utilitaire, fait calculer le chemin LFBO - INSA à l'algorithme donné
     * @return
     */
    public ShortestPathSolution doLFBO_INSA() {
        // Récupération du chemin
        Path correctPath = LfboInsa;
        
        // Création du scénario
        Scenario ScnLfboInsa = new Scenario(hauteGaronne, Mode.LENGTH, correctPath.getOrigin(), correctPath.getDestination());

        return testScenario(ScnLfboInsa);
    }

    /**
     * Constructeur, lit les fichiers liés à l'oracle et calcul LFBO - INSA
     * @throws IOException
     */
    public PccAlgorithmTest() throws IOException {
        inspector = ArcInspectorFactory.getAllFilters().get(0);

        GraphReader reader = new BinaryGraphReader(new DataInputStream(new BufferedInputStream(new FileInputStream(hauteGaronneFileName))));
        hauteGaronne = reader.read();

        pathReader = new BinaryPathReader(new DataInputStream(new BufferedInputStream(new FileInputStream(lfboInsaPathName))));
        LfboInsa = pathReader.readPath(hauteGaronne);

        solutionTrouveeLfboInsa = doLFBO_INSA();
    }

    @Test
    public void testLFBO_INSA() {
        Path pathTrouve = solutionTrouveeLfboInsa.getPath();

        // Test de la solution trouvée
        assertTrue(solutionTrouveeLfboInsa.isFeasible());
        assertEquals(solutionTrouveeLfboInsa.getStatus(), Status.OPTIMAL);

        assertEquals(pathTrouve.getOrigin(), LfboInsa.getOrigin());
        assertEquals(pathTrouve.getDestination(), LfboInsa.getDestination());
    
        assertEquals(pathTrouve.getLength(), LfboInsa.getLength(), 0.01);
    }

    @Test
    public void testOneNodePath()  {
        Node onlyOne = LfboInsa.getOrigin();

        // Création du scénario
        Scenario ScnOneNode = new Scenario(hauteGaronne, Mode.LENGTH, onlyOne, onlyOne);

        // Test du scénario
        ShortestPathSolution solutionTrouvee = testScenario(ScnOneNode);

        // Test de la solution trouvée
        assertTrue(solutionTrouvee.isFeasible());
        assertEquals(solutionTrouvee.getStatus(), Status.OPTIMAL);
    
        assertEquals(solutionTrouvee.getPath().getLength(), 0.0, 0.01);
    }

    /**
     * Il n'y a pas beaucoup de solution pour vérifier l'optimalité d'un chemin sans oracle.
     * On peut cependant vérifier que les sous-chemin sont également optimaux.
     * Note : La meilleure solution reste de démontrer l'optimalité du A* et de prendre 
     * une heurestique admissible.
     */
    @Test
    public void testSousChemin() {
        Path pathTrouve = solutionTrouveeLfboInsa.getPath();
        
        Node n = pathTrouve.getOrigin();
        Node m = pathTrouve.getArcs().get(30).getDestination();
        Scenario ScnSousChemin = new Scenario(pathTrouve.getGraph(), Mode.LENGTH, n, m);
        ShortestPathSolution sol = testScenario(ScnSousChemin);

        List<Arc> arcsCheminOriginal = pathTrouve.getArcs();
        List<Arc> arcsSousChemin = sol.getPath().getArcs();
        for (int i = 0; i < 30; ++i) {
            assertTrue(arcsCheminOriginal.get(i) == arcsSousChemin.get(i));
        }
    }

    /**
     * Ce test permet de vérifier que la distance à vol d'oiseau est toujours plus faible
     * que la longueur du chemin retourné par l'algorithme
     */
    @Test
    public void testVolDOiseau() {
        Path pathTrouve = solutionTrouveeLfboInsa.getPath();

        double dx = LfboInsa.getOrigin().getPoint().getLongitude() - LfboInsa.getDestination().getPoint().getLongitude();
        double dy = LfboInsa.getOrigin().getPoint().getLatitude() - LfboInsa.getDestination().getPoint().getLatitude();


        assertTrue(pathTrouve.getLength() >= Math.sqrt(dx * dx + dy * dy));
    }

    @Test
    public void testInegaliteTriangulaire() {
        // Récupération d'un point légèrement dé-axé
        Node pointDePassage = LfboInsa.getOrigin().getSuccessors().get(0).getDestination().getSuccessors().get(0).getDestination().getSuccessors().get(0).getDestination();
        
        // Récupération de la solution directe
        Path pathTrouve = solutionTrouveeLfboInsa.getPath();

        Scenario Scn1 = new Scenario(LfboInsa.getGraph(), Mode.LENGTH, pathTrouve.getOrigin(), pointDePassage);
        Scenario Scn2 = new Scenario(LfboInsa.getGraph(), Mode.LENGTH, pointDePassage, pathTrouve.getDestination());
        ShortestPathSolution sol1 = testScenario(Scn1);
        ShortestPathSolution sol2 = testScenario(Scn2);

        // Vérification de l'inégalité triangulaire
        assertTrue(sol1.getPath().getLength() + sol2.getPath().getLength() >= pathTrouve.getLength());
    }


}