There used to be an essay of Roger's called "Transitive closure" that
discussed this in detail. I can't find it now, but there seems to be a
version of it hanging around at
http://code.jsoftware.com/wiki/User:Roger_Hui/t . Look for "Successor
lists". There are two versions, tcm and tcs, each one line long.
Henry Rich
On 11/28/2017 6:14 PM, Daniel Lyons wrote:
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?
---
This email has been checked for viruses by AVG.
http://www.avg.com
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
