LINUX.ORG.RU

OCaml DFS algorithm implementation


0

0

Учу Ocaml. Есть некоторые проблемы в том, что часто хочется написать какой-то
алгоритм в привычном императивном стиле. Долго с непривычки мучаюсь, чтобы
написать в функциональном стиле, а то что получается не всегда нравится.

Может кто поможет, никак не могу придумать нормальную реализацию DFS (depth
first search) в функциональном стиле. Пока лучшее, что придумал весьма
громоздко и использует модуль Set для хранения состояния:

module IntSet = Set.Make (
  struct
    type t = int
    let compare x y = if x < y then (-1) else if x > y then 1 else 0
  end) ;;

let dfs gm v =
  let n = Array.length gm in

  let rec dfs_aux v l results =
    let rec iter i (l, results) =
      if i = n
      then (l, results)
      else
	if gm.(v).(i) && not (IntSet.mem i l)
	then iter (i + 1) (dfs_aux i (IntSet.add i l) (i :: results))
	else iter (i + 1) (l, results)
    in
    iter 0 (l, results)
  in

  List.rev (snd (dfs_aux v (IntSet.singleton v) [v])) ;;

let dfs gm v =
  let n = Array.length gm in

  let l = Array.make n false in
  let verticies = ref [] in

  let rec dfs_aux v =
    l.(v) <- true ;
    verticies := v :: !verticies ;

    for i = 0 to n - 1 do
      if gm.(v).(i) && not l.(i)
      then dfs_aux i
    done
  in
  dfs_aux v ;
  List.rev !verticies ;;


let gm = Array.make_matrix 8 8 false ;;
gm.(0).(1) <- true ;;
gm.(0).(2) <- true ;;
gm.(0).(4) <- true ;;
gm.(1).(0) <- true ;;
gm.(1).(3) <- true ;;
gm.(2).(0) <- true ;;
gm.(2).(3) <- true ;;
gm.(2).(5) <- true ;;
gm.(3).(1) <- true ;;
gm.(3).(2) <- true ;;
gm.(4).(0) <- true ;;
gm.(4).(6) <- true ;;
gm.(4).(7) <- true ;;
gm.(5).(2) <- true ;;
gm.(6).(4) <- true ;;
gm.(7).(4) <- true ;;

Printf.printf "[" ;;
List.iter (function v -> Printf.printf "%d; " v) (dfs gm 0) ;;
Printf.printf "]\n" ;;


Расскажите пожалуйста, как это сделать красиво?

Спасибо.

P. S. Может кто знает какую-нить свободную книгу или сайт какой, где можно
почерпнуть знания о реализации стандартных алгоритмов/структур данных в
функциональном стиле ?
anonymous

Извините, просто скопировал реализацию из файла. Вторую реализацию можно не смотреть - она императивная.

Спасибо.

anonymous
()
Ответ на: комментарий от Zulu

Обычный алгоритм обхода графа в глубину (это я же в первом посте указал). Граф как видно задан в виде матрицы смежности (это не принципиально).

Вот императивный аналог на C (в первом посте есть такой же аналог на OCaml):

int n;
int a[][];
int l[];

int verticies[];
int number;

memset ((void *) l, 0, sizeof (l));
number = 0;

void DFS (int v)
{
  int i;

  l[v] = 1;
  verticies[number++] = v;

  for (i = 0; i < n; ++i)
    if (a[v][i] && !l[i])
      DFS (i);
}

n - кол-во вершин;
a - матрица смежностей;
l - массив пометок (были/не были);
verticies - выход алгоритма (вершины в порядке обхода).

Спасибо.

anonymous
()

На мой взгяд задачки на графах, где требуется помечать пройденные узлы лучше ложатся на императивные структуры данных. Функциональщина здесь не сильна имхо. С удовольствием посмотрю на простой изящный код, опровергающий мое предположение

Bob1
()

http://www.lri.fr/~filliatr/ftp/ocaml/misc/search.ml

(* Depth-first search *)
module FunctionalDFS(P : FunctionalProblem) = struct

  let search s0 = 
    let visited = Hashtbl.create 65537 in
    let already s = match P.mark s with
      | None -> false
      | Some h -> (Hashtbl.mem visited h) || (Hashtbl.add visited h (); false)
    in
    let rec dfs path s =
      if already s then raise Not_found;
      if P.success s then s, List.rev path else first path (P.moves s)
    and first path = function
      | [] -> raise Not_found
      | (m,s) :: r -> try dfs (m :: path) s with Not_found -> first path r
    in
    dfs [] s0

end

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.