Re: [Caml-list] Dynamic graph algorithms
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 -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Dynamic graph algorithms
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 -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
[Caml-list] Dynamic graph algorithms
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 -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs