Re: [Caml-list] Dynamic graph algorithms

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

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