RSS
Twitter
Facebook
A
dependency graph characterizes the possible order in which we can evaluate the attributes
at various nodes of a parse tree. If there is an edge from node M to N, then attribute
corresponding to M first be evaluated before evaluating N. Thus the only allowable
orders of evaluation are N1, N2, ..., Nk such that if there is an edge from Ni to
Nj then i < j. Such an ordering embeds a directed graph into a linear order,
and is called a topological sort of
the graph.
If
there is any cycle in the graph, then there are no topological sorts; that is,
there is no way to evaluate the SDD on this parse tree. If there are no cycles,
however, then there is always at least one topological sort.
Example:
Topological sorts for the above the dependency graph is shown in a simplified fashion
with the nodes indicating the nodes of the parse tree and the edges indicating precedence
of evaluation. It is apparent that the last section of the dependence graph denoted
by the nodes { 6 7 8 9 } needs to be evaluated in sequence. The only
flexibility of the order of evaluation is on the two sub-sequences { 1 3 5 }
and { 2 4 } which can with any interleaving provided the relative order of
their nodes is preserved are as below.
Base
sequences are {1 3 5} and {2 4} with the suffix {6 7 8 9} being constant as the
last nodes of the topological sorting need to remain fixed.
1
3 5 2 4 6 7 8 9, 1 3 2 5 4 6 7 8 9, 1 2 3 5 4 6 7 8 9, 1 3 2 4 5 6 7 8 9, 1 2 3
4 5 6 7 8 9, 1 2 4 3 5 6 7 8 9, 2 1 3 5 4 6 7 8 9, 2 1 3 4 5 6 7 8 9, 2 1 4 3 5
6 7 8 9, 2 4 1 3 5 6 7 8 9
0 comments