[Caml-list] Dynamic graph algorithms

[Caml-list] Dynamic graph algorithms

[Jon Harrop]

I just stumbled upon the interesting subject of dynamic graph algorithms,
those that can incrementally alter their output given small changes to the
graph (i.e. adding and removing edges and/or vertices). Topology trees and
sparsification are related subjects. I'm wondering if anyone has done any
work on this kind of stuff using OCaml? For some reason, there seems to be
surprisingly little research on these topics...

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com

Re: [Caml-list] Dynamic graph algorithms

[Diego Olivier Fernandez Pons]

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

Re: [Caml-list] Dynamic graph algorithms

[Diego Olivier Fernandez Pons]

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

    Jon,

I was told my explanations weren't very clear so here it goes with more
details, a much simpler example and explicit links

A dynamic graph algorithm is a classical graph algorithm (say all-pairs
shortest path) that is able to update the result when there is a small
modification of the input without computing everything from
scratch. Typical usage are large networks, for instance adding a fiber
optic cable in a suburb of Paris won't change the shortest path between New
York and San Francisco, therefore computing everything from scratch again
is unnecessary.

There are 2 ways of achieving that result
- recomputation : pretty much like backtracking debuggers in functional
languages, they "save" a previous state and re-execute the computation
tree/DAG from there
- dedicated algorithm that "fix" the result in place : STOC / FOCS like
algorithms


Lets take a very simple example fun f a b c -> f a + f b + f c

The computation tree is something like
evaluate f a
evaluate f b
evaluate f c
evaluate f a + f b + f c

if now there is a small change in a, say a -> 'a the backtracking
algorithms will do the following

evaluate f 'a
read f b from memory
read f c from memory
evaluate f 'a + f b + f c

the typical problems to solve are similar to backtracking debuggers in
functional languages : efficiently save intermediate states, optimise fully
reversible transformations, etc.
Umut Acar with his self-adjusting ML is a typical representative of that
kind of work as well as backtracking debuggers (Caml, SML)
http://umut.mpi-sws.org/self-adjusting-computation


A dedicated algorithm instead will use the mathematical properties of the
object being built to "fix in place" the result

evaluate f a
evaluate f 'a
evaluate delta = f 'a - f a
read f a + f b + f c from the result
evaluate f a + f b + f c + delta

Notice this algorithm doesn't require the first algorithm to memoize any
intermediate computation
David Eppstein and other American algorithmicians are typical
representatives of this line of work
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8372


        Diego Olivier

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