graph algorithms ( ( ( start ( ( ( finish ( ( ( figure activity-node graph time past units on the other handactivity is less critical and can be delayed up to two time units without affecting the final completion time to perform these calculationswe convert the activity-node graph to an event-node graph each event corresponds to the completion of an activity and all its dependent activities events reachable from node in the event-node graph may not commence until after the event is completed this graph can be constructed automatically or by hand dummy edges and nodes may need to be inserted in the case where an activity depends on several others this is necessary in order to avoid introducing false dependencies (or false lack of dependenciesthe event-node graph corresponding to the graph in figure is shown in figure to find the earliest completion time of the projectwe merely need to find the length of the longest path from the first event to the last event for general graphsthe longest-path problem generally does not make sensebecause of the possibility of positive-cost cycles these are the equivalent of negative-cost cycles in shortest-path problems if positive-cost cycles are presentwe could ask for the longest simple pathbut no satisfactory solution is known for this problem since the event-node graph is acyclicwe need not worry about cycles in this caseit is easy to adapt the shortest-path algorithm to compute the earliest / / / / / figure event-node graph / / / /