daily pastebin goal
19%
SHARE
TWEET

Untitled

a guest Jan 21st, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Estructuras de Datos
  3.  * Práctica 9 - Orden topológico en digrafos (sin clonar el grafo)
  4.  *
  5.  * APELLIDOS :                         NOMBRE:
  6.  */
  7.  
  8. package topoSort;
  9.  
  10. import dataStructures.dictionary.Dictionary;
  11. import dataStructures.dictionary.HashDictionary;
  12. import dataStructures.graph.DiGraph;
  13. import dataStructures.list.ArrayList;
  14. import dataStructures.list.List;
  15. import dataStructures.set.HashSet;
  16. import dataStructures.set.Set;
  17. import dataStructures.tuple.Tuple2;
  18.  
  19. public class TopologicalSortingDicPar<V> {
  20.  
  21.     private List<Set<V>> topSort;
  22.     private boolean hasCycle;
  23.  
  24.     /*
  25.      * Agrega los predecesores de cada vértice.
  26.      */
  27.     private Dictionary<V, Integer> PendingPredecessors(DiGraph<V> graph) {
  28.         Dictionary<V, Integer> pendingPredecessors = new HashDictionary<>();
  29.         for(V v : graph.vertices()) {
  30.             pendingPredecessors.insert(v, graph.inDegree(v));
  31.         }
  32.         return pendingPredecessors;
  33.     }
  34.    
  35.     /**
  36.      * Para los que tiene como predecesor a V, los decremente en 1 el grado de entrada.
  37.      * @param graph Digrafo.
  38.      * @param pendingPredecessors Predecesorse pendientes.
  39.      */
  40.     private void DecrementInDegree(DiGraph<V> graph, Dictionary<V, Integer> pendingPredecessors, V vertex) {
  41.         for(V v : graph.vertices()) {
  42.             if(pendingPredecessors.isDefinedAt(v) && graph.predecessors(v).isElem(vertex)) {
  43.                 pendingPredecessors.insert(
  44.                         v,
  45.                         pendingPredecessors.valueOf(v) - 1);
  46.             }
  47.         }
  48.     }
  49.    
  50.     public TopologicalSortingDicPar(DiGraph<V> graph) {
  51.         topSort = new ArrayList<>();
  52.         // dictionary: vertex -> # of pending predecessors
  53.         Dictionary<V, Integer> pendingPredecessors;
  54.         Set<V> sources = new HashSet<>();
  55.         // Añadir predecesores.
  56.         pendingPredecessors = PendingPredecessors(graph);
  57.         // Flags de estados.
  58.         boolean finished = false;
  59.         while(!finished && !hasCycle) {
  60.             // Actualizar las fuentes.
  61.             for(Tuple2<V, Integer> t : pendingPredecessors.keysValues()) {
  62.                 if(t._2() == 0) {
  63.                     sources.insert(t._1());
  64.                     // Eliminar del diccionario.
  65.                     pendingPredecessors.delete(t._1());
  66.                 }
  67.             }
  68.             // Una vez eliminado los predecesores de la lista, si no hay más, esta es la última iteración.
  69.             if(pendingPredecessors.isEmpty()) {
  70.                 finished = true;
  71.             }
  72.             // Si no hay fuentes pero aún no hemos terminado, es porque hay ciclo.
  73.             if(sources.isEmpty()) {
  74.                 hasCycle = true;
  75.             } else {
  76.                 // Añadir todas las fuentes al conjunto.
  77.                 topSort.append(sources);
  78.                 // Decrementar el grado de los vértices que tienen como predecesor a alguna fuente añadida.
  79.                 for(V v : sources)
  80.                     DecrementInDegree(graph, pendingPredecessors, v);
  81.                 // Limpiar las fuentes.
  82.                 sources = new HashSet<>();
  83.             }
  84.         }
  85.     }
  86.  
  87.     public boolean hasCycle() {
  88.         return hasCycle;
  89.     }
  90.  
  91.     public List<Set<V>> order() {
  92.         return hasCycle ? null : topSort;
  93.     }
  94.  
  95. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top