Closed GoogleCodeExporter closed 9 years ago
Original comment by tomaz.ko...@gmail.com
on 10 Apr 2010 at 8:43
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
Attachments:
Original issue reported on code.google.com by
jbo...@gmail.com
on 9 Apr 2010 at 3:00