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:

  1. Process each vertex Y that X depends on (i.e., there is an edge from X to Y).

  2. 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):