2

我Map用来实现pure functional DFS和BFS用于图形。

这是我的代码：

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 < 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 && 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 [];;

我知道代码很长，但我真的希望得到一些建议：

  1. 是否值得真正实现一组纯函数式的图算法？我这样做是因为我现在已经习惯functional和讨厌imperative了。
  2. 我的实现是否在某些部分或全部方面过于复杂？
  3. 虽然我喜欢functional，但我个人认为我所做的实现似乎比imperativearray-everywhere 版本更复杂。我的感觉对吗？

编辑

添加Bipartite代码

(* 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) && (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 && color = Black) || (c_black && 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;;

编辑 2

具有基于列表的路径的 DFS

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;;
4

2 回答 2

3

我不确定你所说的有价值是什么意思。将这项任务设置为学习练习是值得的。使用不可变数据来解决实际的现实世界图问题也是值得的。在我看来，图形处理并不是一个纯函数式代码成本高于通常愿意为收益付费的应用领域。

您将路径表示为从每个节点到下一个节点的地图。这很好，因为您可以在中间启动路径。但是对于许多应用程序来说，列表是一种更简单、更自然的路径表示。无论如何，您的代码是一个相当重量级的表示，因此它使您的代码比我预期的要重一些。（顺便说一句，这很难弄清楚——一些评论会有所帮助。）

我个人认为这段代码并不比命令式更复杂。我还认为，当被视为链接结构时，数组无法很好地表示图形。所以我不相信“到处都是数组”的解决方案是你想要比较的。我个人会与基于 malloc()/struct 的（a la C）或基于对象的解决方案进行比较。

当将图表示为邻接矩阵时，我会说数组表示更具竞争力。如果您的图表大小变化很大，或者您想通过整数以外的键访问节点，地图仍然有很多优势。

于 2013-04-05T15:15:41.097 回答
0

  1. 如果您在开源社区中找不到好的代码，那么这样做是值得的。不要重新发明轮子。

  2. 还有一篇文章对 OCaml 的 DFS 算法进行了广泛的解释，OCaml 中的拓扑排序 我建议尝试将 bfs、bfs_current 和 bfs_child 写入单个函数。

于 2013-04-05T14:03:54.337 回答