From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id pAIBDCmJ027580 for ; Fri, 18 Nov 2011 12:13:12 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsMBAE09xk5KfVIqkGdsb2JhbABCmlSHUwGHdQgiAQEBAQkJDRsEIYFyAQEBBBICExkBGx0BAwwGBQQHOyIBEQEFARwGNYdpmToKi2GCZoUaPYhxAgUKig0ElDmNUj2Dcw X-IronPort-AV: E=Sophos;i="4.69,532,1315173600"; d="scan'208";a="119686449" Received: from mail-ww0-f42.google.com ([74.125.82.42]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 18 Nov 2011 12:13:07 +0100 Received: by wwe3 with SMTP id 3so859593wwe.3 for ; Fri, 18 Nov 2011 03:13:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=IooSGNZinkGdaxSU+q90oM15OfroQRcI0sQv/9uaEug=; b=FEhqduPiMX2gJq/1Eg8e90UroJsf6cnhXZsH0qqPHspKKuXtONnlSFPcFXcXF3F3rP 3wMhrjj2aNJuw1S56SB1y3xk/GStJn5da2STpAw/htSc6mvVhRVuMzvk0xxFZC+DV+bo c7zcdlvzX2ndQle+7g6t38hH+cpggh+/QfcK0= MIME-Version: 1.0 Received: by 10.227.205.79 with SMTP id fp15mr1703321wbb.20.1321614786501; Fri, 18 Nov 2011 03:13:06 -0800 (PST) Received: by 10.216.17.137 with HTTP; Fri, 18 Nov 2011 03:13:06 -0800 (PST) In-Reply-To: References: <006501cc9e61$ac282470$04786d50$@ffconsultancy.com> Date: Fri, 18 Nov 2011 12:13:06 +0100 Message-ID: From: Diego Olivier Fernandez Pons To: Jon Harrop Cc: Caml List Content-Type: multipart/alternative; boundary=000e0cdf99b6e11da404b2006bfb Subject: Re: [Caml-list] Dynamic graph algorithms --000e0cdf99b6e11da404b2006bfb Content-Type: text/plain; charset=ISO-8859-1 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 --000e0cdf99b6e11da404b2006bfb Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable =A0 =A0 Jon,

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

A dynamic graph algorithm is a classical = graph algorithm (say all-pairs shortest path) that is able to update the re= sult when there is a small modification of the input without computing ever= ything from scratch.=A0Typical usage are large networks, for instance addin= g a fiber optic cable in a suburb of Paris won't change the shortest pa= th 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 l= anguages, they "save" a previous state and re-execute the computa= tion 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 -> = 9;a the backtracking algorithms will do the following

evaluate f 'a
read f b from memory
<= div>read f c from memory
evaluate f 'a + f b + f c
=
the typical problems to solve are similar to backtracking de= buggers in functional languages : efficiently save intermediate states, opt= imise fully reversible transformations, etc.
Umut Acar with his self-adjusting ML is a typical representative of th= at kind of work as well as backtracking debuggers (Caml, SML)


A dedicated algorithm instead will use t= he mathematical properties of the object being built to "fix in place&= quot; the result

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

<= div>Notice this algorithm doesn't require the first algorithm to memoiz= e any intermediate computation
David Eppstein and other American algorithmicians are typical represen= tatives of this line of work


=A0 =A0 =A0 =A0 Diego = Olivier
--000e0cdf99b6e11da404b2006bfb--