将事件活动节点图转换为事件节点图

Question

谁知道在哪里可以找到将活动节点图(又称节点上活动图)转换为事件节点图(也称为箭头上活动图)的算法实现？

如果你不知道我在说什么，看看这里：http://www.brpreiss.com/books/opus7/html/page581.html

请在您的答案中提供一个有效的算法。

提前谢谢。

Answer 1

最简单的做法是将原始图中的每个节点v替换为两个节点v_in和v_out，这两个节点由一条权重等于原始顶点权重的边连接。然后用从u_out到v_in的零权重的边替换所有原始边(u, v)。

Answer 2

该链接说明了您如何做到这一点：

活动节点图是一个顶点加权图。然而，前面几节中提出的算法都需要边加权图。因此，我们必须将顶点加权图转换为它的边加权对偶。在对偶图中，边表示活动，顶点表示活动的开始和结束。因此，对偶图被称为事件节点图。

虽然我想它遗漏了一些重要的细节。他们建议从活动节点转换为事件节点图的方法是将每个活动节点转换为事件节点边，并为接受多个输入的活动添加一条虚拟边。

构建事件节点图的另一种方法是将每个活动节点替换为一条边和两个节点，例如，A->B->C变为A->A'->B->B'->C-C'。然后，删除每个只有一个输入和零个或一个输出的节点，并将它们替换为零成本的边，因为这些事件节点实际上不做任何事情。

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

所需的数据结构类似于

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