преобразовать событие граф узла активности в граф узла события

Question

Кто-нибудь знает, где я могу найти реализацию алгоритма для преобразования графа узла активности (также называемого графом активности на узле) в граф узла событий (он же активируемый на стрелке график)?* Если вы не знаете, о чем я говорю, посмотрите здесь: http://www.brpreiss.com/books/opus7/html/page581.html

Пожалуйста, укажите рабочий ответ в вашем ответе.

Заранее спасибо.

Answer 1

Самое простое, что нужно сделать, это заменить каждый узел v в исходном графе двумя узлами v_in и v_out, соединенными одним ребром с весом, равным исходному весу вершины. Затем замените все исходные ребра (u, v) ребрами от u_out до v_in нулевого веса.

Answer 2

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

Answer 3

Эта ссылка указывает, как вы это делаете:

График узла активности взвешенный по вершинам граф. Тем не менее алгоритмы, представленные в предыдущем все сечения требуют граничного взвешивания графики. Поэтому мы должны преобразовать взвешенный по вершинам граф в его взвешенный по фронту двойной . В двойственном графе края представляют деятельность, и вершины представляют начало и прекращение деятельность. По этой причине двойной граф называется графом узла-события .

Хотя я предполагаю, что это пропускает некоторые важные детали. Они предлагают преобразовать узел активности в граф узла событий, чтобы преобразовать каждый узел активности в ребро узла события и добавить фиктивный край для действий, которые принимают несколько входных данных.

Другим способом построения графа узла события является замена каждого узла активности ребром и двумя узлами, например, A->B->C становится A->A'->B->B'->C-C'. Затем удалите каждый узел, который имеет только один вход и ноль или один выход, и замените их ребром нулевой стоимости, так как эти узлы событий фактически ничего не делают.