From: Will Duquette on
On Jan 21, 8:35 am, Alexandre Ferrieux <alexandre.ferri...(a)gmail.com>
wrote:
> 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

I'm sorry; I haven't had a chance to give them a try yet. For #1,
right, it's a topological sort; that's straightforward. The serious
question is what to do when there are cycles.

My gut feeling is that for my particular problem domain, isolating the
cycles as "macro-nodes" probably isn't going to work; most cells are
probably linked into one or more cycles, so I'd end up with a few non-
cyclic cells at the front end, and then a big rat's nest. (I can't
get rid of the cycles, as that's simply the kind of model we're trying
to compute.)

But suppose the model includes a cycle like this:

A => B => C => D => A

that is, B's formula depends on A, and C's formula depends on B, and
so on. I just want to make sure I'm evaluating these in the order A,
B, C, D during each iteration, rather than, say, D, C, B, A. I should
make as much progress in one iteration through the model in the former
case as I do in four iterations in the latter case.

Having detected that there's a cycle, let's say that I break it by
removing one of the dependencies, say, C => D. Then it should give me
the order D, A, B, C, which is fine.
From: Richard Owlett on
Will Duquette wrote:
> [snip]
>
> I'm sorry; I haven't had a chance to give them a try yet. For #1,
> right, it's a topological sort; that's straightforward. The serious
> question is what to do when there are cycles.
>
> My gut feeling is that for my particular problem domain, isolating the
> cycles as "macro-nodes" probably isn't going to work; most cells are
> probably linked into one or more cycles, so I'd end up with a few non-
> cyclic cells at the front end, and then a big rat's nest. (I can't
> get rid of the cycles, as that's simply the kind of model we're trying
> to compute.)
> [snip]

I may be far out in left field, BUT ?
Would reformulating the problem as a set of parametric equations
help?

ie - use a path rather than position as independent variable.
Think hysteresis plot. It's been 40+ yrs since I had to consider
one and didn't do so well then.
From: Will Duquette on
On Jan 21, 2:17 pm, Richard Owlett <rowl...(a)pcnetinc.com> wrote:
> Will Duquette wrote:
> > [snip]
>
> > I'm sorry; I haven't had a chance to give them a try yet.  For #1,
> > right, it's a topological sort; that's straightforward.  The serious
> > question is what to do when there are cycles.
>
> > My gut feeling is that for my particular problem domain, isolating the
> > cycles as "macro-nodes" probably isn't going to work; most cells are
> > probably linked into one or more cycles, so I'd end up with a few non-
> > cyclic cells at the front end, and then a big rat's nest.  (I can't
> > get rid of the cycles, as that's simply the kind of model we're trying
> > to compute.)
> > [snip]
>
> I may be far out in left field, BUT ?
> Would reformulating the problem as a set of parametric equations
> help?
>
> ie - use a path rather than position as independent variable.
> Think hysteresis plot. It's been 40+ yrs since I had to consider
> one and didn't do so well then.

Nope. What I've got is a generalized Leontief input/output model, and
I'm definitely using the appropriate algorithm to solve it. I'd just
like to be able to optimize it a little. :-)
From: Uwe Klein on
Will Duquette wrote:
> (I can't
> get rid of the cycles, as that's simply the kind of model we're trying
> to compute.)

Do cyclicals converge? ( or where do you set the limit? N cycles? )

uwe
From: Will Duquette on
On Jan 22, 1:11 am, Uwe Klein <uwe_klein_habertw...(a)t-online.de>
wrote:
> Will Duquette wrote:
> > (I can't
> > get rid of the cycles, as that's simply the kind of model we're trying
> > to compute.)
>
> Do cyclicals converge? ( or where do you set the limit? N cycles? )
>
> uwe

If the model's correct, then generally it converges after some number
of iterations through the cells. Naturally, you set a limit on the
maximum number of iterations, and you have to take into account that
the model might *not* converge.