/usr/lib/hugs/packages/fgl/Data/Graph/Inductive/Query/DFS.hs is in libhugs-fgl-bundled 98.200609.21-5.3ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 | -- (c) 2000 - 2005 by Martin Erwig [see file COPYRIGHT]
-- | Depth-First Search
module Data.Graph.Inductive.Query.DFS(
CFun,
dfs,dfs',dff,dff',
dfsWith, dfsWith',dffWith,dffWith',
-- * Undirected DFS
udfs,udfs',udff,udff',
-- * Reverse DFS
rdff,rdff',rdfs,rdfs',
-- * Applications of DFS\/DFF
topsort,topsort',scc,reachable,
-- * Applications of UDFS\/UDFF
components,noComponents,isConnected
) where
import Data.Tree
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Basic
----------------------------------------------------------------------
-- DFS AND FRIENDS
----------------------------------------------------------------------
{-
Classification of all 32 dfs functions:
dfs-function ::= [direction]"df"structure["With"]["'"]
direction --> "x" | "u" | "r"
structure --> "s" | "f"
| structure
direction | "s" "f"
------------------------ + optional With + optional '
"x" | xdfs xdff
" " | dfs dff
"u" | udfs udff
"r" | rdfs rdff
------------------------
Direction Parameter
-------------------
x : parameterized by a function that specifies which nodes
to be visited next
" ": the "normal case: just follow successors
u : undirected, ie, follow predecesors and successors
r : reverse, ie, follow predecesors
Structure Parameter
-------------------
s : result is a list of
(a) objects computed from visited contexts ("With"-version)
(b) nodes (normal version)
f : result is a tree/forest of
(a) objects computed from visited contexts ("With"-version)
(b) nodes (normal version)
Optional Suffixes
-----------------
With : objects to be put into list/tree are given by a function
on contexts, default for non-"With" versions: nodes
' : parameter node list is given implicitly by the nodes of the
graph to be traversed, default for non-"'" versions: nodes
must be provided explicitly
Defined are only the following 18 most important function versions:
xdfsWith
dfsWith,dfsWith',dfs,dfs'
udfs,udfs'
rdfs,rdfs'
xdffWith
dffWith,dffWith',dff,dff'
udff,udff'
rdff,rdff'
Others can be added quite easily if needed.
-}
-- fixNodes fixes the nodes of the graph as a parameter
--
fixNodes :: Graph gr => ([Node] -> gr a b -> c) -> gr a b -> c
fixNodes f g = f (nodes g) g
-- generalized depth-first search
-- (could also be simply defined as applying preorderF to the
-- result of xdffWith)
--
type CFun a b c = Context a b -> c
xdfsWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [c]
xdfsWith _ _ [] _ = []
xdfsWith _ _ _ g | isEmpty g = []
xdfsWith d f (v:vs) g = case match v g of
(Just c,g') -> f c:xdfsWith d f (d c++vs) g'
(Nothing,g') -> xdfsWith d f vs g'
-- dfs
--
dfsWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [c]
dfsWith = xdfsWith suc'
dfsWith' :: Graph gr => CFun a b c -> gr a b -> [c]
dfsWith' f = fixNodes (dfsWith f)
dfs :: Graph gr => [Node] -> gr a b -> [Node]
dfs = dfsWith node'
dfs' :: Graph gr => gr a b -> [Node]
dfs' = dfsWith' node'
-- undirected dfs, ie, ignore edge directions
--
udfs :: Graph gr => [Node] -> gr a b -> [Node]
udfs = xdfsWith neighbors' node'
udfs' :: Graph gr => gr a b -> [Node]
udfs' = fixNodes udfs
-- reverse dfs, ie, follow predecessors
--
rdfs :: Graph gr => [Node] -> gr a b -> [Node]
rdfs = xdfsWith pre' node'
rdfs' :: Graph gr => gr a b -> [Node]
rdfs' = fixNodes rdfs
-- generalized depth-first forest
--
xdfWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> ([Tree c],gr a b)
xdfWith _ _ [] g = ([],g)
xdfWith _ _ _ g | isEmpty g = ([],g)
xdfWith d f (v:vs) g = case match v g of
(Nothing,g1) -> xdfWith d f vs g1
(Just c,g1) -> (Node (f c) ts:ts',g3)
where (ts,g2) = xdfWith d f (d c) g1
(ts',g3) = xdfWith d f vs g2
xdffWith :: Graph gr => CFun a b [Node] -> CFun a b c -> [Node] -> gr a b -> [Tree c]
xdffWith d f vs g = fst (xdfWith d f vs g)
-- dff
--
dffWith :: Graph gr => CFun a b c -> [Node] -> gr a b -> [Tree c]
dffWith = xdffWith suc'
dffWith' :: Graph gr => CFun a b c -> gr a b -> [Tree c]
dffWith' f = fixNodes (dffWith f)
dff :: Graph gr => [Node] -> gr a b -> [Tree Node]
dff = dffWith node'
dff' :: Graph gr => gr a b -> [Tree Node]
dff' = dffWith' node'
-- undirected dff
--
udff :: Graph gr => [Node] -> gr a b -> [Tree Node]
udff = xdffWith neighbors' node'
udff' :: Graph gr => gr a b -> [Tree Node]
udff' = fixNodes udff
-- reverse dff, ie, following predecessors
--
rdff :: Graph gr => [Node] -> gr a b -> [Tree Node]
rdff = xdffWith pre' node'
rdff' :: Graph gr => gr a b -> [Tree Node]
rdff' = fixNodes rdff
----------------------------------------------------------------------
-- ALGORITHMS BASED ON DFS
----------------------------------------------------------------------
components :: Graph gr => gr a b -> [[Node]]
components = (map preorder) . udff'
noComponents :: Graph gr => gr a b -> Int
noComponents = length . components
isConnected :: Graph gr => gr a b -> Bool
isConnected = (==1) . noComponents
postflatten :: Tree a -> [a]
postflatten (Node v ts) = postflattenF ts ++ [v]
postflattenF :: [Tree a] -> [a]
postflattenF = concatMap postflatten
topsort :: Graph gr => gr a b -> [Node]
topsort = reverse . postflattenF . dff'
topsort' :: Graph gr => gr a b -> [a]
topsort' = reverse . postorderF . (dffWith' lab')
scc :: Graph gr => gr a b -> [[Node]]
scc g = map preorder (rdff (topsort g) g) -- optimized, using rdff
-- sccOrig g = map preorder (dff (topsort g) (grev g)) -- original by Sharir
reachable :: Graph gr => Node -> gr a b -> [Node]
reachable v g = preorderF (dff [v] g)
|