Prev: Slimming down a tclkit
Next: Help removing remote files with Expect
From: Alexandre Ferrieux on 21 Jan 2010 10:24
Ping ?

From: Will Duquette on 21 Jan 2010 11:10
On Jan 21, 7:22 am, Andrew Mangogna <amango...(a)mindspring.com> wrote:
> Will Duquette wrote:
> > I'm writing a model that bears some resemblance to a spreadsheet
> > model: cells with formulas that depend on the values of other cells.
> > I'm trying to determine a natural order for evaluating the cells so as
> > to minimize the number of iterations required to recompute the model.
>
> > You can think of the model as a directed graph, where the nodes are
> > the cells and the arcs are the dependencies of a cell's formulas on
> > other cells: a node points at the nodes it depends on.
>
> > There are two problems: when the model contains no cyclic
> > dependencies, and when it does.
>
> > 1. Given an acyclic directed graph, produce a list of the nodes such
> > that each node depends only on nodes prior to it in the list.  If
> > there are no cycles, this order should recompute the model in one
> > pass.
>
> > 2. Given an acyclic directed graph *with* cycles, produce a similar
> > list of the nodes such that to the extent possible the cycles are
> > pushed to the end and th enumber of iterations is minimized.
>
> My first impulse here would be to perform a depth first search of the graph to
> compute a spanning tree and then sort the tree. Some advanced compiler books
> might be a good resource since flow graphs have many of these properties and
> compiler optimizations do a lot of graph manipulations.
>
>
>
> > I've come up with an algorithm for #1 and a heuristic for #2, but they
> > are both kind of brute force; and this is clearly a solved problem.
> > Can anyone point me in the right direction?
>
> --
> Andrew Mangogna

That's a thought. My initial idea was to use a topological sorting
algorithm that detects cycles; and when it has gone as far as it can,
remove dependencies arbitrarily until it can make more progress. If I
mark where the initial topo sort stops, then I know that those nodes,
at least, can be computed once; I only need to iterate on the
subsequent ones.

As with everything else, I suppose the answer is to give it a try and
measure the results.
From: Will Duquette on 21 Jan 2010 11:10
On Jan 21, 7:24 am, Alexandre Ferrieux <alexandre.ferri...(a)gmail.com>
wrote:
> Ping ?

Pong?
From: Alexandre Ferrieux on 21 Jan 2010 11:35
On Jan 21, 5:10 pm, Will Duquette <w...(a)wjduquette.com> wrote:
> On Jan 21, 7:24 am, Alexandre Ferrieux <alexandre.ferri...(a)gmail.com>
> wrote:
>
> > Ping ?
>
> Pong?

You didn't say whether the methods I proposed were suited or not...

-Alex
From: tomk on 21 Jan 2010 12:21
On Jan 21, 9:10 am, Will Duquette <w...(a)wjduquette.com> wrote:
> On Jan 21, 7:22 am, Andrew Mangogna <amango...(a)mindspring.com> wrote:
>
>
>
> > Will Duquette wrote:
> > > I'm writing a model that bears some resemblance to a spreadsheet
> > > model: cells with formulas that depend on the values of other cells.
> > > I'm trying to determine a natural order for evaluating the cells so as
> > > to minimize the number of iterations required to recompute the model.
>
> > > You can think of the model as a directed graph, where the nodes are
> > > the cells and the arcs are the dependencies of a cell's formulas on
> > > other cells: a node points at the nodes it depends on.
>
> > > There are two problems: when the model contains no cyclic
> > > dependencies, and when it does.
>
> > > 1. Given an acyclic directed graph, produce a list of the nodes such
> > > that each node depends only on nodes prior to it in the list.  If
> > > there are no cycles, this order should recompute the model in one
> > > pass.
>
> > > 2. Given an acyclic directed graph *with* cycles, produce a similar
> > > list of the nodes such that to the extent possible the cycles are
> > > pushed to the end and th enumber of iterations is minimized.
>
> > My first impulse here would be to perform a depth first search of the graph to
> > compute a spanning tree and then sort the tree. Some advanced compiler books
> > might be a good resource since flow graphs have many of these properties and
> > compiler optimizations do a lot of graph manipulations.
>
> > > I've come up with an algorithm for #1 and a heuristic for #2, but they
> > > are both kind of brute force; and this is clearly a solved problem.
> > > Can anyone point me in the right direction?
>
> > --
> > Andrew Mangogna
>
> That's a thought.  My initial idea was to use a topological sorting
> algorithm that detects cycles; and when it has gone as far as it can,
> remove dependencies arbitrarily until it can make more progress.  If I
> mark where the initial topo sort stops, then I know that those nodes,
> at least, can be computed once; I only need to iterate on the
> subsequent ones.
>
> As with everything else, I suppose the answer is to give it a try and
> measure the results.

FYI - if you're doing this in tcl then you can use struct::graph
(Create and manipulate directed graph objects) from tcllib to test out
ideas.
tomk
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Slimming down a tclkit
Next: Help removing remote files with Expect