I'm trying to code the "program evaluation and review technique" algorithm as an exercise in learning J.
https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique#Next_step.2C_creating_network_diagram_by_hand_or_by_using_diagram_software <https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique#Next_step.2C_creating_network_diagram_by_hand_or_by_using_diagram_software> You make something like a gantt chart, say "task C can only start after tasks A and B finish" etc, and then task C's earliest finish becomes the maximum of A and B's early finish plus C's duration. The maximum of A and B's earliest finish is called task C's earliest start. This is usually described as a loop, so you start at the nodes with no dependencies and work your way to their children until you run out of nodes. It's this iterative process that I'm not sure A) is there a more direct way to implement this in J? or B) what is the right way to approach doing it iteratively with J? Back in school I heard about the adjacency matrix representation so my thought is to try that here, since J is notably good at matrices. ] graph =: 4 4 $ 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 NB. col 0 = depends-on A, col 1 = depends-on B, etc. 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 Let's set up some durations: ] durations =: >: i.4 1 2 3 4 I see how to apply the durations to the adjacency matrix to get the base early starts: graph *"1 durations 0 0 0 0 1 0 0 0 1 0 0 0 0 2 3 0 Then I can get the early starts: >./"1 graph *"1 durations 0 1 1 3 Around here I start thinking I should transpose my matrix up above, but anyway. And this looks great, because I can just add the durations and get the early finishes: ] early_finish =. durations + >./"1 graph *"1 durations 1 3 4 7 Now the problem is, what if I extend the graph a little bit with one more node, say E depends on C and D: ] graph =: 5 5 $ 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 ] early_finish =. durations + >./"1 graph *"1 durations 1 3 4 7 9 Hang on, the last value is 9, but it should actually be 7 + 5 = 12. It's acquired 9 instead because here where I thought I calculated the greatest early finish: >./"1 graph *"1 durations 0 1 1 3 4 the rightmost value is actually maximum _duration_ of the predecessors, not the maximum _early finish_ of the predecessors. I kind of feel like I need to feed this calculation into itself somehow to make it work. I see there are a few ways to do something like that, with ^:_ and $: but am not seeing "the trick" here. I found this page about representing digraphs in an incidence matrix, but I don't see how that would help me here. http://www.jsoftware.com/help/dictionary/samp20.htm <http://www.jsoftware.com/help/dictionary/samp20.htm> Is it possible to restate the PERT algorithm in terms of the closure or something? -- Daniel Lyons ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
