Databases
StackOverflow2013
Postsdbo
PODFS and BFS for Graph in a **pure** functional way in OCaml
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODFS and BFS for Graph in a **pure** functional way in OCaml
    primarykey
    data
    text
    <p>I am using <code>Map</code> to implement <code>pure functional</code> <code>DFS</code> and <code>BFS</code> for graph.</p> <p>here is my code:</p> <pre><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 i acc = if i &lt; v then fill (i+1) (IntMap.add i [] 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 &amp;&amp; IntMap.mem v g then let add u v g = let l = IntMap.find u g in if List.mem v l then 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) then 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) then 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 = [] then p else bfs n v p [] in bfs [u] (IntSet.singleton u) IntMap.empty [];; </code></pre> <hr> <p>I know the code is quite long, but I really do wish for some suggestions:</p> <ol> <li>Is it worthy to really implement a pure functional set of graph algorithm? I do this because I am getting used to <code>functional</code> and hate <code>imperative</code> now.</li> <li>Is my implementation too complicated in some parts or all?</li> <li>Although I like <code>functional</code>, personally I think the implementation I make seems more complicated than the <code>imperative</code> array-everywhere version. Is my feeling correct?</li> </ol> <hr> <p><strong>Edit</strong></p> <p>Added <code>Bipartite</code> code</p> <pre><code>(* basically, we have two sets, one for red node and the other for black node*) (* we keep marking color to nodes via DFS and different level of nodes go to coresponding color set*) (* unless a node is meant to be one color but already in the set of the other color*) type colorType = Red | Black;; let dfs_bipartite u g = let rec dfs current color red black block = if block then (red, black, block) else let dfs_child current color (red, black, block) c = if block then (red, black, block) else let c_red = IntSet.mem c red and c_black = IntSet.mem c black in if (not c_red) &amp;&amp; (not c_black) then if color = Red then dfs c Black (IntSet.add c red) black false else dfs c Red red (IntSet.add c black) false else if (c_red &amp;&amp; color = Black) || (c_black &amp;&amp; color = Red) then (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;; </code></pre> <hr> <p><strong>Edit 2</strong></p> <p>DFS with list based path</p> <pre><code>let dfs_path u g = let rec dfs current visited path = let dfs_child (visited, path) c = if not (IntSet.mem c visited) then 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;; </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJackson Tale
    1. USJackson Tale
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PODFS and BFS for Graph in a **pure** functional way in OCaml
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PODFS and BFS for Graph in a **pure** functional way in OCaml
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload