Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Find the Relative Neighbourhood
- * Graph
- * @param g
- * @param <V>
- * @param <E>
- * @return
- */
- public static<V,E> Graph<V,E> RNG(Graph<V,E> g) {
- //Criar grafo resultante
- Graph<V,E> result = g.clone();
- //Mapa com todos os vertices adjacentes:
- Iterable<V> vertices = g.vertices();
- //Para cada vértice origem
- for(V vertexA : vertices) {
- //Para cada vértice destino
- for(V vertexB : vertices) {
- //Obter distância minima entre A e B
- double d = GraphAlgorithms.shortestPath(g, vertexA, vertexB, new LinkedList<>());
- //Para outro qualquer vértice Z:
- for(V vertexZ : vertices) {
- //Calcular distâncias:
- double dAZ = GraphAlgorithms.shortestPath(g, vertexA, vertexZ, new LinkedList<>());
- double dBZ = GraphAlgorithms.shortestPath(g, vertexB, vertexZ, new LinkedList<>());
- //Se a condição se verificar, então remover a edge, e fazer break do for:
- if(d <= Math.max(dAZ, dBZ)) {
- //Remove a edge, se existente
- result.removeEdge(vertexA, vertexB);
- //Saimos do for, para continuar para o próximo vértice
- break;
- }
- }
- }
- }
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement