OCAML Depth-First Search

Question

I've been doing a tutorial in OCaml (don't ask me why, I just decided to expand my knowledge of languages, I guess) and I've gotten to the point where I'm working with graphs. The tutorial taught me how to do a breadth-first search on a graph, which I can implement fine. However, I've been struggling with an algorithm for a depth-first search, which is one of those things where the tutorial goes, "We suggest you try this on a depth-first method, but we won't tell you how to do it."

I'm trying to implement it like so: let rec dfs graph start end. Which is to say, I've been trying to do it where I take in a list of edges (graph), a starting node (start), and an ending node (end).

I've created my graph using a list of edges...

let edges = [
  ("a", "b"); ("a", "c");
  ("a", "d"); ("b", "e");
  ("c", "f"); ("d", "e");
  ("e", "f"); ("e", "g")
];;

However, I'm totally lost about where to go from here. Any advice on how to get me going? Thanks.

Answer 1

So, I did it but I find it strange that you represent a graph as a list if you have to search in it. A map would be much better. Anyway, here's how it's done :

let edges = [
  ("a", "b"); ("a", "c");
  ("a", "d"); ("b", "e");
  ("c", "f"); ("d", "e");
  ("e", "f"); ("e", "g")
];;

let successors n e = 
  List.map (fun (_, v) -> v) (List.filter (fun (u, _) -> n = u) e)

let dfs graph start f =
  let rec rdfs visited node =
    if not (List.mem node visited) then
      begin
        f node;
        let s = successors node graph in
        List.fold_left rdfs (node::visited) s
      end
    else visited
  in rdfs [] start

 let () = let _ = dfs edges "a" print_string in ()

First thing, define a successors functions which will give you every direct successor of a node (the List.filter part gets you the edges, the List.map part split the resulting edges in two parts and keep only the second one (the first one is naturally the node for which you are searching the successors).

The dfs function defines an internal function that do two things, checking if the node we are working on was already visited or not.

• If yes, nothing changes, we just return the same list of visited nodes (and maybe some other things depending on what you want to do with your search).

• If no, then

• We apply the function we gave to dfs to the current node,

• We add this node to the visited nodes,

• We take his successors,

• We apply the function to each one, (here, there's a small trick, since we have

  List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

  and

  rdfs : string list -> string -> string list

  instead of writing

  List.fold_left (fun visited node -> rdfs visited node) ...

  we can write

  List.fold_left rdfs ...

  (something to do with this strange thing called Lambda Calculus and some rule called eta conversion which states that :

  λ x · ux η u (x ∉ fv(u)) (fv(u) being the free variables of u) :-p) (what it means is that in OCaml, if you write fun x -> f x you could have written f instead, it is strictly equivalent.)

• We return the visited nodes list in which all the visited nodes have been added

Hope I helped.