1votos

Clausura transitiva en grafos no dirigidos en Haskell

por josejuan hace 5 años

Podemos plegar (fold) directamente todo el grado en una única pasada.

Dado un grafo no dirigido, obtener la clausura transitiva, es decir, el conjunto de conjuntos de nodos conectados.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
{-  En lugar de aplicar iterativamente la clausura, tomamos un vértice cualquiera 
    del grafo y nos vamos por las ramas "comiéndonos" todos los nodos por el camino. 
    Así, hemos obtenido un grupo (todos están conectados con todos) y en el grafo, 
    pueden o no quedar más nodos (no conectados con ninguno previo), por lo que 
    simplemente repetimos. 
-} 
closure' :: Ord a => M.Map a (S.Set a) -> [[a]] 
closure' g = foldGroups $ M.keysSet g 
 
  where foldGroups ks 
          | S.null ks = []                                   -- No quedan vértices por plegar. 
          | otherwise = 
              rs : foldGroups ks'                            -- El resultado es éste grupo, seguido de los que queden. 
              where (rs, ks') = feed ([], ks) $ S.findMin ks -- El grupo resulta de rastrear desde uno pendiente cualquiera. 
 
        feed (xs, ks) x = 
          if S.notMember x ks                                -- Si ese nodo no está pendiente... 
            then (xs, ks)                                    -- ...el grupo no crece por ahí. 
            else S.foldl feed (x:xs, S.delete x ks) (g!x)    -- Si sí, lo añadimos, quitamos de pendiente y plegamos 
                                                             --    para sus adyacentes. 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.