Something based on transitive closure does sound like the way to go.
And this might be the essay Henry Rich was thinking of:
http://code.jsoftware.com/wiki/User:Roger_Hui/t
But I am having trouble following along here.
The text says "task C can only start after tasks A and B finish" and
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.
So, I am expecting
nodes=: 'ABCD'
And when I look at which nodes C depends on in that graph, I do not
see a dependency on B:
((nodes i.'C'){graph)#nodes
A
So I am already lost.
But, wait, maybe I should be looking at the transitive closure of the graph?
((nodes i.'C'){(+. +./ .*~)^:_ graph)#nodes
A
D depends on A and B and C, but B and C only depend on A.
There might be another subtlety to this problem, but need to get the
problem statement correct before addressing any such thing.
That said, I think there's going to be another issue, though, with
transitive closure. You don't strictly want the transitive closure
here. It's not just that D depends on A, B and C - the A and B
dependencies are in parallel, while the C dependency is in series.
Parallel is handled by >. and series is handled by + - I suspect you
need a third operation to determine relevance at any given step. But
can't reason about that until we get the example right for the
numbers.
Thanks,
--
Raul
On Tue, Nov 28, 2017 at 6:41 PM, Henry Rich <[email protected]> wrote:
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
