[Haskell-cafe] Functional specification of DFS

[Vimal]

Hello Haskellers,
Yesterday, my professor had asked this question in a quiz:
"Give a functional description of Depth First Search on a graph G. Use lisp."

The first thing I wrote was:

Let DFS(G, root) return the list of edges in the dfs spanning tree of
G, rooted at root.

Let n = |V| in: :)
The naive algorithm of keeping a visited 'array' and recursive
solution is what came to my mind. But, if we look at DFS as a mapping
from G -> List of Spanning trees of G rooted at root,
then we have an exponential (n**(n-2) ?) number of them, so, finding
the one that satistifies the properties of a DFS spanning tree, might
not be tractable.

So, if we modify the specification of DFS(G, root) as DFS(G, root,
intermediate_path), we get:

DFS(G, root, path)
= Union (
         {(root, v)} U DFS(G, v, path U {root}))
        )
for all v not in path, and (root, v) exists in G.

DFS is invoked as:
 DFS(G, root, {root})

The problem with this is that changes to "path" must be persistant across calls.

i.e., {(root, v)} U DFS(G, v, {v, root} + recursive calls}
                  U
      {(root, w)} U DFS(G, v, {v, root}, + nodes added in recursive calls}) etc.

So, the question is:
Is it possible to have a purely functional and tractable description of DFS?

I did a Google on "Haskell DFS", and landed up with a paper [1], that
also says that Graph Algorithms have been difficult to implement in a
purely functional style. They use mutable arrays to achieve the same.

I am getting a small idea using foldls and Monads to achieve this.
Since, we have to take the return value of the previous instance of
the function call, and then pass it on to the next.

dfs initial_visited_list >>=
\spanning_tree -> dfs (merge spanning_tree initial_visited) >>=
\spanning_tree -> etc...

I will try to write it down on paper and see if it works out.

References:
[1]: www.cse.ogi.edu/~jl/Papers/dfs.ps


Do you have any thoughts on this?
Thanks,
-- 
~Vimal
RLE :)
encode = map (length &&& head) . group
decode = concatMap (uncurry replicate)