Critical Path algorithm should calculate Early Start and Free Float for each node

[GoogleCodeExporter]

It would be useful if the critical path function could optionally return a
list of tuples: the Early Start and Late Finish (or Free Float) of each node. 

That's very important from scheduling or project management perspective. 

From wikipedia (http://en.wikipedia.org/wiki/Critical_path_method):

"CPM calculates the longest path of planned activities to the end of the
project, and the earliest and latest that each activity can start and
finish without making the project longer."

Original issue reported on code.google.com by jbo...@gmail.com on 9 Apr 2010 at 3:00

[GoogleCodeExporter]

Original comment by tomaz.ko...@gmail.com on 10 Apr 2010 at 8:43

[GoogleCodeExporter]

As you probably noticed, the majority of algorithms included in this library 
are well 
known in the field of graph theory and AI. The critical path algorithm that is 
currently 
implemented in this library has a mathematical background. 

It solves the critical or longest path problem in a acyclic weighted directed 
graph, 
with a dynamic programming approach.  

It does so by computing a list of triples for every node. Each triple is 
represented by: (predecessor, longest path to the predecessor, no. of unchecked 
edges). The algorithm 
then backtracks the computed triples and finds the critical path.

Example:
(see the attachment below)
a: (-, 0, 0)
b: (-, 0, 1), (a, 2, 0)
c: (-, 0, 2), (a, 10, 1), (b, 3, 0)
d: (-, 0, 3), (a, 5, 2), (b, 10, 1), (c, 12, 0)
e: (-, 0, 3), (a, 10, 2), (c, 14, 1), (d, 19, 0)

Result: a,c,d,e - 19 

To summarize my point: the algorithm above has very little to do with activity 
networks 
used in project management. That's why I'm marking this issue as invalid. 

Irony: I became a contributor to python-graph when I was working on activity 
and event 
networks using this library. I actually implemented a standard scheduling 
algorithm that 
computes all the properties you have mentioned above, including: earliest 
start/finish, 
latest start/finish, floating properties and time reserves. We can get in touch 
and I 
would gladly send you my code, if I find it in my archives. (email me: tomaz 
dot kovacic 
at gmail dot com)

Regards, Tomaž

Original comment by tomaz.ko...@gmail.com on 10 Apr 2010 at 9:58

• Changed state: Invalid

Attachments:

• graph-example.png