Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Estructuras de Datos
- * Práctica 9 - Orden topológico en digrafos (sin clonar el grafo)
- *
- * APELLIDOS : NOMBRE:
- */
- package topoSort;
- import dataStructures.dictionary.Dictionary;
- import dataStructures.dictionary.HashDictionary;
- import dataStructures.graph.DiGraph;
- import dataStructures.list.ArrayList;
- import dataStructures.list.List;
- import dataStructures.queue.LinkedQueue;
- import dataStructures.queue.Queue;
- import dataStructures.tuple.Tuple2;
- public class TopologicalSortingDic<V> {
- private List<V> topSort;
- private boolean hasCycle;
- /*
- * Agrega los predecesores de cada vértice.
- */
- private Dictionary<V, Integer> PendingPredecessors(DiGraph<V> graph) {
- Dictionary<V, Integer> pendingPredecessors = new HashDictionary<>();
- for(V v : graph.vertices()) {
- pendingPredecessors.insert(v, graph.inDegree(v));
- }
- return pendingPredecessors;
- }
- /**
- * Para los que tiene como predecesor a V, los decremente en 1 el grado de entrada.
- * @param graph Digrafo.
- * @param pendingPredecessors Predecesorse pendientes.
- */
- private void DecrementInDegree(DiGraph<V> graph, Dictionary<V, Integer> pendingPredecessors, V vertex) {
- for(V v : graph.vertices()) {
- if(pendingPredecessors.isDefinedAt(v) && graph.predecessors(v).isElem(vertex)) {
- pendingPredecessors.insert(
- v,
- pendingPredecessors.valueOf(v) - 1);
- }
- }
- }
- public TopologicalSortingDic(DiGraph<V> graph) {
- topSort = new ArrayList<>();
- // dictionary: vertex -> # of pending predecessors
- Dictionary<V, Integer> pendingPredecessors;
- Queue<V> sources = new LinkedQueue<>();
- // Añadir predecesores.
- pendingPredecessors = PendingPredecessors(graph);
- // Flags de estados.
- boolean finished = false;
- while(!finished && !hasCycle) {
- // Actualizar las fuentes.
- for(Tuple2<V, Integer> t : pendingPredecessors.keysValues()) {
- if(t._2() == 0) {
- sources.enqueue(t._1());
- // Eliminar del diccionario.
- pendingPredecessors.delete(t._1());
- }
- }
- // Si no hay fuentes pero aún no hemos terminado, es porque hay ciclo.
- if(pendingPredecessors.isEmpty()) {
- finished = true;
- } else if(sources.isEmpty()) {
- hasCycle = true;
- } else {
- // Coger una fuente e insertarla en el orden topológico.
- V source = sources.first();
- // Añadir al orden topológico.
- topSort.append(source);
- sources.dequeue();
- // Actualizar el diccionario.
- DecrementInDegree(graph, pendingPredecessors, source);
- }
- }
- }
- public boolean hasCycle() {
- return hasCycle;
- }
- public List<V> order() {
- return hasCycle ? null : topSort;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement