Problems with a simple dependency algorithm

Question

In my webapp, we have many fields that sum up other fields, and those fields sum up more fields. I know that this is a directed acyclic graph.

When the page loads, I calculate values for all of the fields. What I'm really trying to do is to convert my DAG into a one-dimensional list which would contain an efficient order to calculate the fields in.

For example: A = B + D, D = B + C, B = C + E Efficient calculation order: E -> C -> B -> D -> A

Right now my algorithm just does simple inserts into a List iteratively, but I've run into some situations where that starts to break. I'm thinking what would be needed instead would be to work out all the dependencies into a tree structure, and from there convert that into the one dimensional form? Is there a simple algorithm for converting such a tree into an efficient ordering?

Answer 1

Are you looking for topological sort? This imposes an ordering (a sequence or list) on a DAG. It's used by, for example, spreadsheets, to figure out dependencies between cells for calculations.

Answer 2

What you want is a depth-first search.

function ExamineField(Field F)
{
    if (F.already_in_list)
        return

    foreach C child of F
    {
        call ExamineField(C)
    }

    AddToList(F)
}

Then just call ExamineField() on each field in turn, and the list will be populated in an optimal ordering according to your spec.

Note that if the fields are cyclic (that is, you have something like A = B + C, B = A + D) then the algorithm must be modified so that it doesn't go into an endless loop.

For your example, the calls would go:

ExamineField(A)
  ExamineField(B)
    ExamineField(C)
      AddToList(C)
    ExamineField(E)
      AddToList(E)
    AddToList(B)
  ExamineField(D)
    ExamineField(B)
      (already in list, nothing happens)
    ExamineField(C)
      (already in list, nothing happens)
    AddToList(D)
  AddToList(A)
ExamineField(B)
  (already in list, nothing happens)
ExamineField(C)
  (already in list, nothing happens)
ExamineField(D)
  (already in list, nothing happens)
ExamineField(E)
  (already in list, nothing happens)

And the list would end up C, E, B, D, A.