Home Original page

Algorithm for sequencing a collection of dependent equations

Tim Golden mail at timgolden.me.uk
Fri Jul 22 12:35:34 EDT 2016 
On 22/07/2016 17:01, Malcolm Greene wrote:
> We're working on a DSL (domain specific language) that we translate into
> a list of tokenized expressions. My challenge is to figure out how to
> sequence evaluation of these expressions so that we evaluate these
> expressions in the proper order given that expressions have dependencies
> on other expressions.
>
> We've done the work to determine the full list of tokens associated with
> each expression (after referencing other expressions) and we've detected
> expressions that result in loops.

[... snip ...]

> 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?

I think that what you're looking for is a topological sort

TJG
More information about the Python-list mailing list