Algorithm for sequencing a collection of dependent equations

[Robin Becker]

On 22/07/2016 17:01, Malcolm Greene wrote:
..........
> Here's an example of expressions and their full list of dependencies:
>
> a = b + b + b + c + c   > b, c, d, e, s, t, x
> b = c + d + e > c, d, e, s, t, x
> c = s + 3 > s, x
> d = t + 1 > t
> e = t + 2 > t
> s = x + 100 > x
> t = 10 > None
> x = 1 > None
> y = 2 > None
>
> I'm looking for an algorithm/data structure that will me to start with
> the least dependent expression (t, x, y) and move through the list of
> expressions in dependency order ending with the expression with the most
> dependencies.
>
> I imagine that spreadsheets have to perform a similar type of analysis
> to figure out how to recalculate their cells.
>
> Suggestions on algorithms and/or data structures (some form of graph?)
> to support the above goals?
>
> Thank you,
> Malcolm
>
assuming you have no loops then the topological sort is what you need. If you 
have mutual dependencies then you need to find a set of variables that cuts all 
the loops and solve for those simultaneously. Unfortunately for a directed graph 
structure I think the minimal cutset problem is NP complete so good luck with that.
-- 
Robin Becker