Sorting Algorithm
|
 |
Let us consider the equation system in the box below. First, we build two dependencies graphs: a "Can" dependencies set will be useful to compute variables CanDate while a "Must" dependencies set will be used to compute variables MustDate. To build Can dependencies graph we start from the input variables and the arrow -> means "depends". At the opposite, to build Must dependencies graph we start from the output variables and the arrow -> means "needs". If there is a dependency cycle in a graph, there is a causality cycle and the program cannot be compiled.
| Levels | CanDate | MustDate |
|---|---|---|
| 0 | x y t | x y |
| 1 | a b | a |
| 2 | c e | c t |
| 3 | d | b d e |
x, y and t can be evaluated first. Then b can be evaluated. Then , c and e can be evaluated in any order and finally d can be evaluated.
Second, we compute the dates. At the initialization phase, each variable has 0 for CanDate and the maximum of levels (3 in the presented example) for MustDate. Then, relying on the Can graph, each time there is a dependency towards a variable, we increase its CanDate by 1. Similarly, relying in the Must graph, each time there is a dependency towards a variable, we decrease by 1 its MustDate. Finally, we compute a CanDate and a MustDate for each variable. The Candate is the level from which the variable can be evaluated while the MustDate is the level at which the variable must be evaluated. Indeed, the the evaluation of a variable is possible in any level between its two dates.
