Noeud extends ElementCarteTopo { public Groupe plusCourtChemin(Noeud arrivee, double maxLongueur) { List<Noeud> noeudsFinaux = new ArrayList<Noeud>(0); List<Arc> arcsFinaux = new ArrayList<Arc>(0); List<Noeud> noeudsVoisins = new ArrayList<Noeud>(0); List<Arc> arcsVoisins = new ArrayList<Arc>(0); List<Double> distancesVoisins = new ArrayList<Double>(0); List<Noeud> traites = new ArrayList<Noeud>(0); List<Noeud> aTraiter = new ArrayList<Noeud>(0); int i; Arc arcVoisin; Noeud noeudVoisin, plusProche, suivant; double dist; try { if (this.getCarteTopo() == null) { Noeud.logger.error("ATTENTION : le noeud " + this + " ne fait pas partie d'une carte topo"); Noeud.logger.error(" Impossible de calculer un plus court chemin"); return null; } if (this.getCarteTopo().getPopGroupes() == null) { Noeud.logger.error("ATTENTION : le noeud " + this + " fait partie d'une carte topo sans population de groupes"); Noeud.logger.error(" Impossible de calculer un plus court chemin"); return null; } Groupe plusCourtChemin = this.getCarteTopo().getPopGroupes().nouvelElement(); plusCourtChemin.setSchema(this.getSchema()); if (this == arrivee) { Noeud.logger.debug("node is arrival"); plusCourtChemin.addNoeud(this); this.addGroupe(plusCourtChemin); return plusCourtChemin; } this.distance = 0; this.chercheArcsNoeudsVoisins(noeudsVoisins, distancesVoisins, arcsVoisins); for (i = 0; i < noeudsVoisins.size(); i++) { noeudVoisin = noeudsVoisins.get(i); arcVoisin = arcsVoisins.get(i); dist = distancesVoisins.get(i).doubleValue(); noeudVoisin.distance = dist; noeudVoisin.arcPrecedent = arcVoisin; noeudVoisin.noeudPrecedent = this; } aTraiter.addAll(noeudsVoisins); while (!aTraiter.isEmpty()) { plusProche = aTraiter.get(0); for (i = 1; i < aTraiter.size(); i++) { if (aTraiter.get(i).distance < plusProche.distance) { plusProche = aTraiter.get(i); } } traites.add(plusProche); aTraiter.remove(plusProche); if (plusProche == arrivee) { break; } if (maxLongueur != 0) { if (plusProche.distance > maxLongueur) { return null; } } plusProche.chercheArcsNoeudsVoisins(noeudsVoisins, distancesVoisins, arcsVoisins); for (i = 0; i < noeudsVoisins.size(); i++) { noeudVoisin = noeudsVoisins.get(i); arcVoisin = arcsVoisins.get(i); dist = distancesVoisins.get(i).doubleValue(); if (traites.contains(noeudVoisin)) { continue; } if (aTraiter.contains(noeudVoisin)) { if (noeudVoisin.distance > (plusProche.distance + dist)) { noeudVoisin.distance = plusProche.distance + dist; noeudVoisin.arcPrecedent = arcVoisin; noeudVoisin.noeudPrecedent = plusProche; } continue; } noeudVoisin.distance = plusProche.distance + dist; noeudVoisin.arcPrecedent = arcVoisin; noeudVoisin.noeudPrecedent = plusProche; aTraiter.add(noeudVoisin); } } if (!traites.contains(arrivee)) { Noeud.logger.debug("couldn't reach it"); return null; } suivant = arrivee; while (true) { arcsFinaux.add(0, suivant.arcPrecedent); suivant.arcPrecedent.addGroupe(plusCourtChemin); suivant = suivant.noeudPrecedent; if (suivant == this) { break; } noeudsFinaux.add(0, suivant); suivant.addGroupe(plusCourtChemin); } noeudsFinaux.add(0, this); this.addGroupe(plusCourtChemin); noeudsFinaux.add(arrivee); arrivee.addGroupe(plusCourtChemin); plusCourtChemin.setListeArcs(arcsFinaux); plusCourtChemin.setListeNoeuds(noeudsFinaux); plusCourtChemin.setLength(arrivee.distance); return plusCourtChemin; } catch (Exception e) { Noeud.logger.error("----- ERREUR dans calcul de plus court chemin."); e.printStackTrace(); return null; } } Noeud();  Noeud(IPoint point);  Noeud(IDirectPosition p); IPoint getGeometrie(); void setGeometrie(IPoint geometrie); IDirectPosition getCoord(); void setCoord(IDirectPosition dp); List<Arc> getEntrants(); void addEntrant(Arc arc); void enleveEntrant(Arc arc); List<Arc> getSortants(); void addSortant(Arc arc); void enleveSortant(Arc arc); List<Arc> arcs(); List<Noeud> voisins(); List<Face> faces(); List<Arc> entrantsOrientes(); List<Arc> sortantsOrientes(); Map<Noeud, Arc> noeudsSortantsOrientes(); List<Object> arcsClasses(); List<Groupe> getListeGroupes(); void setListeGroupes(List<Groupe> liste); void addGroupe(Groupe groupe); List<Noeud> voisins(Groupe groupe); double distance(Noeud noeud); double distance2D(Noeud noeud); double distance(Arc arc); Groupe plusCourtChemin(Noeud arrivee, double maxLongueur); Groupe plusCourtChemin(Noeud arrivee, Groupe groupe, double maxLongueur); Angle directionArc(Arc arc, double longueurEspaceTravail,
      double pasEchantillonage); @Override String toString(); double getDistance(); void setDistance(double distance); void enleveArc(Arc arc); Noeud copy();  }
@Test public void testPlusCourtChemin() { logger.info("Début du test plus court chemin"); initCarteTopo1(); Noeud n1 = ct1.getListeNoeuds().get(0); Noeud n2 = ct1.getListeNoeuds().get(1); Noeud n3 = ct1.getListeNoeuds().get(2); Noeud n4 = ct1.getListeNoeuds().get(3); Arc a2 = ct1.getListeArcs().get(1); Arc a3 = ct1.getListeArcs().get(2); Arc a4 = ct1.getListeArcs().get(3); Arc a5 = ct1.getListeArcs().get(4); Groupe gpFinal = null; Groupe gpResult = null; logger.info("Cas n°1 : chemin n1-n2"); gpResult = n1.plusCourtChemin(n2, 10); gpFinal = new Groupe(); gpFinal.addNoeud(n1); gpFinal.addNoeud(n4); gpFinal.addNoeud(n2); gpFinal.addArc(a5); gpFinal.addArc(a4); Assert.assertEquals("Comparaison de la liste des noeuds cas 1 : ", gpFinal.getListeNoeuds(), gpResult.getListeNoeuds()); Assert.assertEquals("Comparaison de la liste des arcs cas 1 : ", gpFinal.getListeArcs(), gpResult.getListeArcs()); logger.info("Cas n°2 : chemin n2-n1"); gpResult.vide(); gpFinal.vide(); gpResult = n2.plusCourtChemin(n1, 10); gpFinal = new Groupe(); gpFinal.addNoeud(n2); gpFinal.addNoeud(n3); gpFinal.addNoeud(n1); gpFinal.addArc(a3); gpFinal.addArc(a2); Assert.assertEquals("Comparaison de la liste des noeuds cas 2 : ", gpFinal.getListeNoeuds(), gpResult.getListeNoeuds()); Assert.assertEquals("Comparaison de la liste des arcs cas 2 : ", gpFinal.getListeArcs(), gpResult.getListeArcs()); logger.info("Cas n°3 : chemin n1-n1"); gpResult.vide(); gpFinal.vide(); gpResult = n1.plusCourtChemin(n1, 10); gpFinal = new Groupe(); gpFinal.addNoeud(n1); Assert.assertEquals("Comparaison de la liste des noeuds cas 3 : ", gpFinal.getListeNoeuds(), gpResult.getListeNoeuds()); Assert.assertEquals("Comparaison de la liste des arcs cas 3 : ", gpFinal.getListeArcs(), gpResult.getListeArcs()); logger.info("Cas n°4.1 : chemin n4-n1 (bonne comparaison)"); gpResult.vide(); gpFinal.vide(); gpResult = n4.plusCourtChemin(n1, 10); gpFinal = new Groupe(); gpFinal.addNoeud(n4); gpFinal.addNoeud(n1); gpFinal.addArc(a5); Assert.assertEquals("Comparaison de la liste des noeuds cas 4.1 : ", gpFinal.getListeNoeuds(), gpResult.getListeNoeuds()); Assert.assertEquals("Comparaison de la liste des arcs cas 4.1 : ", gpFinal.getListeArcs(), gpResult.getListeArcs()); Assert.assertTrue("", gpFinal.getListeNoeuds().equals(gpResult.getListeNoeuds())); Assert.assertTrue("", gpFinal.getListeArcs().equals(gpResult.getListeArcs())); logger.info("Cas n°4.1 : chemin n4-n1 (mauvaise comparaison : inversion des noeuds)"); gpFinal.vide(); gpFinal = new Groupe(); gpFinal.addNoeud(n1); gpFinal.addNoeud(n4); Assert.assertFalse( "Comparaison de la liste des noeuds en sens inverse cas 4.2 : ", gpFinal.getListeNoeuds().equals(gpResult.getListeNoeuds())); }