convert event an activity node graph to an event node graph

Question

Does anyone know where I can find an implementation of an algorithm to convert an activity node graph (aka activity-on-node graph) to an event node graph (aka activiy-on-arrow graph)?

If you don't know what I am talking about, take a look here: http://www.brpreiss.com/books/opus7/html/page581.html

Please provide a working algo in your answer.

Thanks in advance.

Answer 1

That link states how you do it:

The activity-node graph is a vertex-weighted graph. However, the algorithms presented in the preceding sections all require edge-weighted graphs. Therefore, we must convert the vertex-weighted graph into its edge-weighted dual. In the dual graph the edges represent the activities, and the vertices represent the commencement and termination of activities. For this reason, the dual graph is called an event-node graph.

Although I suppose it leaves out some important details. The way they suggest to convert from an activity node to event node graph is to convert every activity node into an event node edge and to add a dummy edge for activities that take multiple inputs.

Another way to construct the event node graph is to replace every activity node with an edge and two nodes, e.g., A->B->C becomes A->A'->B->B'->C-C'. Then, remove every node that has only one input and zero or one output and replace them with an edge of zero cost, as those event nodes don't actually do anything.

Answer 2

The easiest thing to do is replace every node v in your original graph with two nodes, v_in and v_out, connected by a single edge with weight equal to the original vertex weight. Then replace all the original edges (u, v) with edges from u_out to v_in of zero weight.

Answer 3

foreach node in graph
      if count of incoming_arrows != 1
      {
         Create new node
         Assign incoming arrows from old node to new node
         Create arrow from new node to old node
         Assign cost 0 to new node             
      }
      endif
end foreach

foreach arrow in graph
         Assign cost of destination node to cost of arrow
         /* if you want ...preceded by "node name:" to get F:5 */
end foreach

Rename the nodes

The data structures needed are something like

 struct node
     node_name string
     node_cost int
 struct arrow
      arrow_form_node node
      arrow_to_node node
      arrow_cost int