how to design CPM algorithm ?

Question

Hi

how to represent a graph with list data structure i have three class (Graph, Node, Edge) and would like to find the critical path in graph.

how to calculate

• ES : Earliest Start
• EC : Earliest Complete
• LS : Latest Start
• LC : Latest Complete

thanks

Answer 1

The excellent quickgraph library has classes for describing graphs, and a large number of graph algorithms, including shortest path. You may be able to do something like that.

What you seem to want, though, is actually more complex than a standard graph algorithm; it seems like you want the core of Microsoft Project available in a simple algorithm, and unfortunately it's not. You might consider buying a copy of project, and using it's COM API to do create your plan -- that may be the easy way, depending on your environment. I suspect you're going to have a whole bunch of work ahead of you, though.

Answer 2

Another alternative for storing the graph is the Boost Graph Library (BGL). From what I see at wikipedia, the critical path is the longest path between two vertices. Furthermore it seems like finding the longest path is NP Complete for the general case but for a directed acyclic graph (DAG), which I think is your case, there are more efficient algorithms.

The longest path algorithm isn't in BGL but the DAG algorithm on wikipedia looks reasonably easy to implement.