Precedence Graph

A precedence graph is a directed acyclic graph whose nodes corresponds to individual statements.

Precedence Graph
Figure 1 – Precedence Graph

An edge from S_i& to S_j, implies that statement S_j can only be executed after statement S_i has completed execution.

In the above diagram following precedence relation is shown:

  • S2 and S3 can be executed only after S1 has finished execution.
  • S4 can be executed only after S2 has completed execution.
  • S5 can be executed only after S2, S3, and S4 have finished execution.

The precedence graph is also a dependency graph.

Rate this post