1

I have a list of properties, that are bound to some string expression:

property z, expression '[x] + [y]'
property x, expression '[y] + 1'
property y, expression '1'

So to solve z, I need first to solve x and y. My current approximation is this:

var solved = new List<string>();
while (properties.Count() > 0) 
{
   var property = properties.Dequeue();
   var dependencies = FindDependencies(property)
         .Where(x => !solved.Contains(x))
         .ToList();

   // no unsolved dependencies, solve it
   if (dependencies.Count == 0) 
   {
       property.Solve();
       solved.Add(property.Name);
   } 
   // it can't be solved now, add to the end of queue
   else 
   {  
        properties.Enqueue();
   }
}

This approximation has two problems:

a) I think it is not optimal, because not solved property is added to the end, may be it could be solved sooner and in that case on it dependant properties would not postponed also.
b) Could not get any good exit condition, when it is unsolvable (meaning, that there's circular reference).

Does anybody recognize here existing well known algorithm, or has ideas how to optimize it?

4

Your properties are nodes in a directed acyclic graph (DAG), with the dependencies being edges. Finding a topological sort will give you the order you need to evaluate the properties. There are other algorithms to detect cycles to enforce the acyclic property when you add a node.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.