DFS.hs

-- (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',
    xdfsWith,xdfWith,xdffWith,
    -- * 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)