DFS and BFS for Graph in a **pure** functional way in OCaml -

i using map implement pure functional dfs , bfs graph.

here code:

module intmap = map.make(struct type t = int let compare = compare end);; module intset = set.make(struct type t = int let compare = compare end);;  type digraph = int list intmap.t;;  exception cantaddedge;;  let create v =    let rec fill acc =     if < v       fill (i+1) (intmap.add [] acc)     else        acc   in    fill 0 intmap.empty;;  let num_vertices g = intmap.cardinal g;;  let add_edge u v g =    if intmap.mem u g && intmap.mem v g      let add u v g =       let l = intmap.find u g in        if list.mem v l g       else intmap.add u (v::l) g     in      add u v (add v u g)   else      raise cantaddedge;;  let dfs_path u g =   let rec dfs current visited path =     let dfs_child current (visited, path) c =       if not (intset.mem c visited)          dfs c (intset.add c visited) (intmap.add c current path)       else           (visited, path)     in      list.fold_left (dfs_child current) (visited, path) (intmap.find current g)   in    let (v, p) = dfs u (intset.singleton u) intmap.empty   in    p;;  let bfs_path u g =   let rec bfs current_list v p n =     let bfs_current (v,p,n) current  =       let bfs_child current (v, p, n) c =           if not (intset.mem c v) begin            print_int c;            ((intset.add c v), (intmap.add c current p), (c::n))          end           else             (v, p, n)       in        list.fold_left (bfs_child current) (v, p, n) (intmap.find current g)     in      let (v,p,n) = list.fold_left bfs_current (v,p,n) current_list     in      if n = [] p     else bfs n v p []   in     bfs [u] (intset.singleton u) intmap.empty [];; 

---

i know code quite long, wish suggestions:

1. is worthy implement pure functional set of graph algorithm? because getting used functional , hate imperative now.
2. is implementation complicated in parts or all?
3. although functional, think implementation make seems more complicated imperative array-everywhere version. feeling correct?

---

edit

added bipartite code

(* basically, have 2 sets, 1 red node , other black node*) (* keep marking color nodes via dfs , different level of nodes go coresponding color set*) (* unless node meant 1 color in set of other color*) type colortype = red | black;; let dfs_bipartite u g =   let rec dfs current color red black block  =     if block (red, black, block)     else        let dfs_child current color (red, black, block) c =     if block (red, black, block)     else        let c_red = intset.mem c red , c_black = intset.mem c black in       if (not c_red) && (not c_black)         if color = red           dfs c black (intset.add c red) black false         else           dfs c red red (intset.add c black) false       else if (c_red && color = black) || (c_black && color = red) (red, black, true)       else (red, black, block)       in        list.fold_left (dfs_child current color) (red, black, block) (intmap.find current g)   in    let (r, b, block) = dfs u black (intset.singleton u) intset.empty false   in    not block;; 

---

edit 2

dfs list based path

let dfs_path u g =   let rec dfs current visited path =     let dfs_child (visited, path) c =       if not (intset.mem c visited) begin     print_int c;     dfs c (intset.add c visited) (c::path)       end        else (visited, path)     in      list.fold_left dfs_child (visited, path) (intmap.find current g)   in    let (v, p) = dfs u (intset.singleton u) [u]   in    p;; 

i'm not sure mean worthy. it's worthy set task learning exercise. it's worthy use immutable data solve actual real world graph problems. doesn't seem me graph processing area of application pure functional code costs more 1 willing pay benefits.

you're representing path map each node next. nice because can start path in middle. list simpler , more natural representation of path lot of applications. @ rate, yours pretty heavyweight representation , makes code little heavier have expected. (btw hard figure out--some comments help.)

i don't think code more complicated imperative be. think arrays make poor representation graphs when viewed linked structures. don't believe "arrays everywhere" solution want compare against. i'd compare against malloc()/struct based (a la c) or against object-based solution, personally.

when representing graphs adjacency matrices, i'd array representation more competitive. if graph changes size lot, or if want access nodes keys other integers, maps still have many advantages.