Tema 6 - Examples/Ejercicios

PRIM

module Prim where

import WeightedGraph
import List((\\),  minimumBy)
-- estudiar la función minimumBy

prim g = aux [v] vs []
 where
    (v:vs) = vertices g
    aux _ [] st = st -- el tercer argumento es el spanning tree (lista de arcos)
    aux t r  st = aux (y:t) (r\\[y]) (WE x p y : st)
        where
            WE x p y = minimumBy comp [WE v w u | v <- t, (u,w) <- successors g v, u`elem`r]
            comp (WE _ w _) (WE _ w' _)
              | w == w' = EQ
              | w < w' = LT
              | w > w' = GT



g1 :: WeightedGraph Char Int
g1 = mkWeigthedGraphEdges ['a','b','c','d','e']
                            [ WE 'a' 3 'b', WE 'a' 7 'd'
                            , WE 'b' 4 'c', WE 'b' 2 'd'
                            , WE 'c' 5 'd', WE 'c' 6 'e'
                            , WE 'd' 5 'e'
                            ]

gEjer3 :: WeightedGraph Char Int
gEjer3 = mkWeigthedGraphEdges ['a','b','c','d','e','f','g']
                            [ WE 'a' 7 'b', WE 'a' 5 'd'
                            , WE 'b' 9 'd', WE 'b' 8 'c', WE 'b' 7 'e'
                            , WE 'c' 5 'e'
                            , WE 'd' 15 'e', WE 'd' 6 'f'
                            , WE 'e' 8 'f', WE 'e' 9 'g'
                            , WE 'f' 11 'g'
                            ]

Práctica 8 (Java) - Grafos dirigidos

La práctica 8 consistirá en implementar en java el orden topológico para grafos dirigidos basado en un diccionario y una cola. Para resolverla necesitais los paquetes incluidos en este tema

Para ello, os proporcionamos una plantilla de la clase que debe implementar el orden topológico TopologicalSortingDQ.java y una clase de prueba TopSortDemo.java. 
La clase TopologicalSortingDQ.java debe colocarse en el paquete graph. La clase TopSortDemo.java debe incluirse en el paquete por defecto.



public class TopologicalSortingDQ<V> {
private List<V> order; private Queue<V> queueSources; // queue with vertices with 0 sucs private boolean cycle;   //  private Dictionary<V,Integer> inDegreeVertice; // dictionary: Vertices -> Number of pred public TopologicalSortingDQ(DiGraph<V> graph) { inDegreeVertice = new HashDictionary<V, Integer>(); queueSources = new QueueList<V>(); order = new ListArray<V>(); cycle = false; // initialize dictionary Set <V> conjunto = graph.vertices(); for (V vertice : conjunto) { if(graph.inDegree(vertice)==0) { //Meter en cola de nodos fuente queueSources.enqueue(vertice); } else { //Meter en diccionario inDegreeVertice.insert(vertice,graph.inDegree(vertice)); } } cycle= false; // start without cycle (the algorithm progress)    // (While the dictionary is not empty or there are vertices in the queue) ,  // and there is progress (no cycles) //while ...  while(!queueSources.isEmpty() && !inDegreeVertice.isEmpty()) { V vertice = queueSources.first(); order.add(0, vertice); Set <V> sucesores = graph.successors(vertice); queueSources.dequeue(); for(V v :inDegreeVertice.keys()) { if(sucesores.isElem(v)) { if(inDegreeVertice.valueOf(v)==1) { queueSources.enqueue(v); inDegreeVertice.delete(v); } else { inDegreeVertice.insert(v, inDegreeVertice.valueOf(v)-1); } } } } //Meter los restantes: while(!queueSources.isEmpty()) { V vertice = queueSources.first(); queueSources.dequeue(); order.add(0, vertice); } } public boolean hasCycle() { return cycle; } public List<V> order() { return cycle ? null : order; } }