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
--
https://mail.python.org/mailman/listinfo/python-list
