Я ищу способ сделать ациклический ориентированный граф. Я прочитал о [Minimum Feedback Arc Set] и [этот пост] , но я не понимаю решений, достаточных для их реализации.
Моя цель - acyclic-ize нескольких графов, каждый из которых имеет очень мало узлов (обычно меньше 50), с низкой связностью, но иногда достаточно для того, чтобы граф был циклическим.
У меня действительно есть вес на краях, но я бы предпочел минимизировать потерю связи, а не минимизировать потерю веса. Я не могу редактировать значения веса, но могу изменить направление ребер.
Я знаю, что это не простая задача, поэтому любое подробное объяснение (и / или код, или псевдокод) очень помогло бы.
Примечание: для моего текущего проекта я использую Python 3.7 и пакет networkx