Advertisement
Guest User

Untitled

a guest
Jan 20th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.49 KB | None | 0 0
  1. /**
  2.      * Find the Relative    Neighbourhood
  3.      * Graph
  4.      * @param g
  5.      * @param <V>
  6.      * @param <E>
  7.      * @return
  8.      */
  9.     public static<V,E> Graph<V,E> RNG(Graph<V,E> g) {
  10.  
  11.         //Criar grafo resultante
  12.         Graph<V,E> result = g.clone();
  13.  
  14.         //Mapa com todos os vertices adjacentes:
  15.         Iterable<V> vertices = g.vertices();
  16.  
  17.         //Para cada vértice origem
  18.         for(V vertexA : vertices) {
  19.  
  20.             //Para cada vértice destino
  21.             for(V vertexB : vertices) {
  22.  
  23.                 //Obter distância minima entre A e B
  24.                 double d = GraphAlgorithms.shortestPath(g, vertexA, vertexB, new LinkedList<>());
  25.  
  26.                 //Para outro qualquer vértice Z:
  27.                 for(V vertexZ : vertices) {
  28.  
  29.                     //Calcular distâncias:
  30.                     double dAZ = GraphAlgorithms.shortestPath(g, vertexA, vertexZ, new LinkedList<>());
  31.                     double dBZ = GraphAlgorithms.shortestPath(g, vertexB, vertexZ, new LinkedList<>());
  32.  
  33.                     //Se a condição se verificar, então remover a edge, e fazer break do for:
  34.                     if(d <= Math.max(dAZ, dBZ)) {
  35.  
  36.                         //Remove a edge, se existente
  37.                         result.removeEdge(vertexA, vertexB);
  38.  
  39.                         //Saimos do for, para continuar para o próximo vértice
  40.                         break;
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.  
  46.  
  47.         return result;
  48.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement