Re: [Caml-list] Dynamic graph algorithms

[Diego Olivier Fernandez Pons <dofp.ocaml@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2164 bytes --]

    Jon,

In ML there has been work on self adjusting computations (check the work of
Amut Acar and unfold recursively).
Dynamic graphs are in a sense an optimization of self-adjusting
computations in the same way logical persistence is an optimization of
physical persistence

Lets say I have an backtracking algorithm that uses a set data structure. I
have two implementation possibilities
- physical persistence : restore the data structure to its (physical)
previous states
- logical persistence : store changes and restore them when I am
backtracking (the sets will be represented by a different physical tree)

(* Physical persistence *)
let rec subsetsum = fun target candidates ->
  match target with
    | 0 -> Some []
    | n when n > 0 ->
      if IntSet.is_empty candidates then None
      else
(
  let value = IntSet.choose candidates in
  let remaining_candidates = IntSet.remove value candidates in
  match subsetsum (target - value) (IntSet.filter (fun x -> x <= target -
value) remaining_candidates)
  with
    | None -> subsetsum target remaining_candidates
    | Some list -> Some (value :: list)
 )
    | _ -> failwith "incorrect argument : negative target"

(* Logical persistence *)

let add_list = List.fold_left (fun s v -> IntSet.add v s)

let rec subsetsum = fun target candidates ->
  match target with
    | 0 -> Some []
    | n when n < 0 || IntSet.is_empty candidates -> None
    | _ ->
      let value = IntSet.choose candidates in
      let removed = IntSet.elements (IntSet.filter (fun x -> x > target -
value) candidates) in
      let candidates = IntSet.remove value (IntSet.filter (fun x -> x <=
target - value) candidates) in
      match subsetsum (target - value) candidates
      with
| None -> subsetsum target (add_list (IntSet.add value candidates) removed)
 | Some list -> Some (value :: list)

In self-adjusting systems, whenever a data changes, the sequence of
computations is replayed from the last common node (like the inner match in
the loop of a backtracking algorithm). In dynamic algorithms for problem
XXX there is an algorithm that restores an equivalent state (typically an
invariant).

        Diego Olivier

[-- Attachment #2: Type: text/html, Size: 3231 bytes --]