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)
So add another argument containing all nodes seen in any path, and maintain that properly. You're going to need to make your DFS > routine tail-recursive.
The problem is efficiency. I don't know if it can be done in linear time without state (and something like arrays with O(1) access). Quadratic time (in the number of nodes) is fairly straightforward. But your professor did not ask for an efficient algorithm. --PR
This was what I had in mind. But, strictly speaking, when you have three vertices like this: G(V = {1, 2, 3}, E = {(1, 2), (2, 3)}) And you call DFS(G, 2), and say you have visited 1 first (from 2), when you call DFS(G, 3), the visited list should contain {1, 2}, which is not possible. However, I had this idea: At each level, you have atmost degree (root) choices. So, if we have choices = [v1, v2, ..., vk], you do something similar to a foldr, and return the spanning tree. This return value will contain a list of visited vertices, and so, merge it with the current list of visited vertices. The code link is: http://j.vimal.googlepages.com/dfs.hs Now, I face some problem which i think is due to Lazy evaluation. I tried adding strictness in as many meaningful places as possible, but it doesnt work :( I have sat with the code for a long time, and yet I am not able to come up with a convincing reason as to why it doesnt work. For somegraphs, it even hangs and gives a stack overflow exception! Any help appreciated. Thanks, Vimal
Vimal writes: ...
Now, I face some problem which i think is due to Lazy evaluation. I tried adding strictness in as many meaningful places as possible, but it doesnt work :(
I have sat with the code for a long time, and yet I am not able to come up with a convincing reason as to why it doesnt work. For somegraphs, it even hangs and gives a stack overflow exception!
First, the suspicion that lazy evaluation may lead to a non-termination of such algorithm is almost surely wrong, and in any case it is against my religious beliefs [some twisted smiley here]. Then, please, would you mind stating again what do you *ultimately* want? A depth-first SEARCH of a goal node, if reachable, or the construction of the spanning tree (through backtracking). You probably said that, but I have probably missed that posting. Jerzy Karczmarczuk
First, the suspicion that lazy evaluation may lead to a non-termination of such algorithm is almost surely wrong, and in any case it is against my religious beliefs [some twisted smiley here].
Sorry to have clubbed both lazy evaluation and non-termination. I meant that Lazy eval could have given me a wrong answer. Recursive procedures can give a wrong answer, if one recursive procedure's answer is dependent on the one invoked after it.
Then, please, would you mind stating again what do you *ultimately* want? A depth-first SEARCH of a goal node, if reachable, or the construction of the spanning tree (through backtracking). You probably said that, but I have probably missed that posting.
Okay, I want a DFS Spanning tree. Vimal
participants (2)
-
jerzy.karczmarczuk＠info.unicaen.fr -
Vimal