CS200 lab 12
Dependence graphs and topological sort
Given the following equations:
- a = true
- b = false
- c = a or b and not b
- d = true and b
- e = true
- f = false or e
- g = f and not f
- h = a or b or c or g
In the dependence graph we represent an equation by its left hand side
identifier.
- Draw the dependence graph for the above equations, as a graph
with nodes and edges, describing which identifiers are needed
in the evaluation of which identifiers.
- Now draw the dependence graph as an array-list of adjacency
lists, where an adjacency list has a source, an inDegree, and
an array list of destinations.
- Perform a topological sort of the dependence graph on paper,
showing the stages of the algorithm. Write on following lines
all identifiers that can be evaluated first, next, etc.