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