0

I have the precedence table

Activity | depends on    
A        | -
B        | - 
C        | -
D        | A,B
E        | B,C    
F        | A,C

And I want to write it as an activity on arc network

So far I have:

    1--D--4
   /|
  A ^
 /  |
0-B-2
 \  |
  C v 
   \|
    3--E--5

Where the events are numbered, and the vertical arcs represent dummy activities, directed by the arrows.

I can't see how I can now attach activity F to this network. I can't attach F directly or indirectly to any of the existing events. Is this possible? And in general is there an algorithmic approach to forming the activity on arc network from the precedence table?

James K
  • 1,255
  • i don't understand what you need dummy activities for. Why not let $V = {A, \ldots, G}$ and have $(x,y) \in E$ if $y$ depends on $x$? – gt6989b Jul 01 '16 at 14:17
  • Because that would be a "activity on node" network, and this question is explicitly about "activity on arc" – James K Jul 01 '16 at 16:03
  • I don't understand. Can you please post the entire question? – gt6989b Jul 01 '16 at 17:07
  • There isn't a "question". I'm trying to implement the algorithms in the A-level D1 syllabus in code, including the algorithm to produce an activity network from a precedence table. This is a test case for the algorithm, but I failed to find a "activity on arc" network for this case (I trust you are happy with the terms "activity on arc" and "activity on node" used here) I would like to know if one exists, and if there is an algorithm for finding it. I am aware that a network could be drawn with each activity represented by an node, and with no dummies, but that doesn't answer the question. – James K Jul 01 '16 at 20:28
  • tl;dr Its not my homework! – James K Jul 01 '16 at 20:30
  • i am sorry, i don;t understand what is activity by node. Perhaps you can try to create what you call activity on arc and take its line graph? – gt6989b Jul 01 '16 at 22:06
  • Let us continue this discussion in chat. – James K Jul 01 '16 at 23:19

1 Answers1

0

I found a possible solution, with 6 dummies, I'm not certain it is the most efficient solution, but I believe it points to an answer to my questions. Activity network

Based on this it seems likely that any precedence tree can be represented in an activity-on-arc network, if you allow for lots of dummies, simply join each new activity to the tree by dummies, one for each dependency.

It also suggests a possible algorithm for producing such a network could be to build it with lots of dummies, and then manipulate the tree to reduce the number of dummies. It has also given me some insight into what an "Event" is: Each of the unique lists of dependencies in the precedence table is an Event.

James K
  • 1,255