43b4c41fbb07705c9df321221ab9cb9832460407Christian Maeder{-|

c63ebf815c8a874525cf18670ad74847f7fc7b26Christian Maeder

456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder > HetCATS/GraphUtils.hs

5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder > $Id$

456238178f89e5a3de2988ee6c8af924297d52d9Christian Maeder > Authors: Klaus L�ttich

5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder > Year: 2002

5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder

5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder Useful functions missing in the graph library fgl.

43b4c41fbb07705c9df321221ab9cb9832460407Christian Maeder

5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder Todo:

f4a2a20e49f41b2afa657e5e64d9e349c7faa091Christian Maeder

f2f9df2e17e70674f0bf426ed1763c973ee4cde0Christian Maeder-}

c9a7e6af169a2adfb92f42331cd578065ed83a2bChristian Maeder

c9a7e6af169a2adfb92f42331cd578065ed83a2bChristian Maedermodule Common.GraphUtils where

e7757995211bd395dc79d26fe017d99375f7d2a6Christian Maeder

e7757995211bd395dc79d26fe017d99375f7d2a6Christian Maederimport Common.Lib.Graph

63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder

63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maederimport Data.List (nub)

a1ed34933c266ce85066acb0d7b20c90cb8eb213Christian Maeder-- import IOExts

c0c2380bced8159ff0297ece14eba948bd236471Christian Maeder

404166b9366552e9ec5abb87a37c76ec8a815fb7Klaus Luettich-- |

b1f59a4ea7c96f4c03a4d7cfcb9c5e66871cfbbbChristian Maeder-- transitive closure on Graphs

ad270004874ce1d0697fb30d7309f180553bb315Christian MaedertransitiveClosure :: b -> Graph a b -> Graph a b

4d56f2fa72e4aec20eb827c11ed49c8cbb7014bdChristian MaedertransitiveClosure el g = insEdges (concatMap mkEdges $ nodes g) g

4cb215739e9ab13447fa21162482ebe485b47455Christian Maeder where mkEdges n = zip3 (repeat n)

8ef75f1cc0437656bf622cec5ac9e8ea221da8f2Christian Maeder (filter (notSuc n) $ reachableNodes g n)

404166b9366552e9ec5abb87a37c76ec8a815fb7Klaus Luettich (repeat el)

63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder notSuc n x = not $ x `elem` suc g n

74eed04be26f549d2f7ca35c370e1c03879b28b1Christian Maeder

d23b0cc79c0d204e6ec758dff8d0ba71c9f693f7Christian MaedertransitiveClosureU :: Graph a () -> Graph a ()

3e8b136f23ed57d40ee617f49bcac37830b58cabChristian MaedertransitiveClosureU = transitiveClosure ()

ef9e8535c168d3f774d9e74368a2317a9eda5826Christian Maeder

3e8b136f23ed57d40ee617f49bcac37830b58cabChristian MaederreachableNodes :: Graph a b -> Node -> [Node]

ef9e8535c168d3f774d9e74368a2317a9eda5826Christian MaederreachableNodes g sn = nub $ collectReachableNodes [sn] []

63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder where collectReachableNodes [] _ = []

e593b89bfd4952698dc37feced21cefe869d87a2Christian Maeder collectReachableNodes (v:vs) seen =

63f0e65a37b95621334db9ee4ba0cd9d826f5c0fChristian Maeder sucs ++ (collectReachableNodes (vs ++ sucs) seen')

5191fa24c532d1f67e7a642e9aece65efb8a0975Christian Maeder where sucs = filter (\x -> not $ x `elem` seen') $ nub $ suc g v

7cc09dd93962a2155c34d209d1d4cd7d7b838264Christian Maeder -- self = if sn `elem` sucgv then [sn] else []

1aee4aaddde105264c1faf394d88e302c05094ffChristian Maeder seen' = v:seen

1aee4aaddde105264c1faf394d88e302c05094ffChristian Maeder

51d769d55d88dfa88bdf54bee78d8fa85a2deba8Christian MaederreflexiveClosure :: b -> Graph a b -> Graph a b

f041c9a6bda23de33a38490e35b831ae18d96b45Christian MaederreflexiveClosure el g = insEdges (filter notSuc $ map mkEdge $ nodes g) g

7cc09dd93962a2155c34d209d1d4cd7d7b838264Christian Maeder where mkEdge n = (n,n,el)

51d769d55d88dfa88bdf54bee78d8fa85a2deba8Christian Maeder notSuc (n,_,_) = not $ n `elem` suc g n

1aee4aaddde105264c1faf394d88e302c05094ffChristian MaederreflexiveClosureU :: Graph a () -> Graph a ()

1aee4aaddde105264c1faf394d88e302c05094ffChristian MaederreflexiveClosureU = reflexiveClosure ()

c3053d57f642ca507cdf79512e604437c4546cb9Christian Maeder

dcbd32289a7bdf1e6edd06c6ab0698c6a9dbf37aChristian MaederlabelEdges :: (b->b) -> b -> [Edge] -> (b,[LEdge b])

f4a2a20e49f41b2afa657e5e64d9e349c7faa091Christian MaederlabelEdges f ilab ps =

f4a2a20e49f41b2afa657e5e64d9e349c7faa091Christian Maeder (f ilab, map (\(s,t) -> (s,t,ilab)) ps)

dcbd32289a7bdf1e6edd06c6ab0698c6a9dbf37aChristian Maeder