DFS Algorithm(s)

[WalternativE]

Background

I'm currently looking into possible implementations for the DFS. I'm basing my research on the FGL paper, the original FGL DFS implementation (https://github.com/haskell/fgl/blob/master/Data/Graph/Inductive/Query/DFS.hs) as well as this blog post (http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/). The Haskell implementation looks interesting as it makes heavy usage of composability and higher order functions to go from very general implementations to very granular ones (dfs, dff, etc). It's a bit complex though.

Question

Should we go in the direction of the Haskell implementation? They are well described in the paper (and well commented in the source code). Do you have other plans? Where would you place the functions - a lot of them work on general graphs - others are rather specific to undirected/directed graphs (pretty much everything with the u or r prefix). What module/submodule/namespace order would you suggest?

First attempt

I played around with the examples in the aformentioned blog post and translated the given DFS example to F# (still - I think a better way would be to stick to the FGL implementation). What do you think?

let dfs (nodes : 'Vertex list) (graph : Graph<'Vertex, 'Label, 'Edge>) : 'Vertex list =
    let rec dfs (nodes : 'Vertex list) (graph : Graph<'Vertex, 'Label, 'Edge>) : 'Vertex list =
        match nodes, graph with
        | ([], _) -> []
        | (_, g) when Graph.isEmpty g -> []
        | (n::ns, g) ->
            match Graph.tryDecompose n g with
            | (Some c, g') ->
                let neighbours = Undirected.Vertices.neighbours c
                n::(dfs (neighbours @ ns) g')
                // n::(dfs (Undirected.Vertices.neighbours c)::ns g')
            | None, _ -> dfs ns g

    dfs nodes graph