CSc 352: An Algorithm for the mymake Problem
This is a high-level outline of an algorithm for the
mymake problem in Assignment 10. It does not
address many details, such as how to determine whether
a file exists or when it was last modified, or what
to do if an error occurs.
Given a (directed) graph G
expressing the dependences between different
files, and a target vertex X in
G, we proceed as follows:
-
Process each vertex Y that X
depends on (i.e., there is an edge from X
to Y).
-
If the file named by vertex X does not
exist, execute the action
associated with vertex X.
(Note that the program spec requires that each action being
executed be printed to stdout before it is executed.)
Otherwise (X exists):
-
obtain the time stamp TX
for when X was last modified.
-
For each vertex Y that X
depends on:
-
Obtain the time stamp TY
for when Y was last modified.
(Y must exist. Why?)
-
If TY is more recent than
TX, execute the action
associated with vertex X.