Алгоритм преобразования ориентированного графа в ациклический

Совместно с экспертами в разных областях знаний авторами статьи за последние пять лет был решен ряд актуальных задач. Используя элементы теории графов, были построены оригинальные экономичные алгоритмы для исследования рассматриваемых моделей и протестированы на реальных данных. Работа является продолжением исследований в этом направлении и задача, решаемая в ней, поставлена специалистами в области биоинженерии. На первом этапе в орграфе была проведена факторизация по отношению циклической эквивалентности, и в каждом кластере были выделены входные и выходные вершины (ребер извне и вовне), применяя ранее построенный авторами работы экономичный алгоритм. На втором шаге, используя алгоритм фронта волны, каждый кластер был заменен на его ациклический подграф, соединяющий входные вершины с выходными путями минимальной длины. Далее исходный орграф был заменен на ациклический орграф, в котором нет обратных связей, связывающий входные и выходные вершины кластеров.