File: TransClos.hs

package info (click to toggle)
haskell-fgl 5.3-3
  • links: PTS
  • area: main
  • in suites: etch, etch-m68k
  • size: 236 kB
  • ctags: 3
  • sloc: haskell: 1,760; makefile: 60; sh: 22
file content (21 lines) | stat: -rw-r--r-- 675 bytes parent folder | download | duplicates (13) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
module Data.Graph.Inductive.Query.TransClos(
    trc
) where

import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Query.DFS (reachable)


getNewEdges :: DynGraph gr => [LNode a] -> gr a b -> [LEdge ()]
getNewEdges vs g = concatMap (\(u,_)->r u g) vs
                   where r = \u g' -> map (\v->(u,v,())) (reachable u g')

{-|
Finds the transitive closure of a directed graph.
Given a graph G=(V,E), its transitive closure is the graph:
G* = (V,E*) where E*={(i,j): i,j in V and there is a path from i to j in G}
-}
trc :: DynGraph gr => gr a b -> gr a ()
trc g = insEdges (getNewEdges ln g) (insNodes ln empty)
        where ln = labNodes g