Преобразование циклического DiGraph в ациклический DiGraph (DAG)

(Дискуссия, которая привела нас сюда, была ожесточенной. Я оставляю только хорошие моменты для всех, кому этот ответ понадобится в будущем.)

Здесь другой подход. Я пытаюсь имитировать топологическую сортировку, ЗА ИСКЛЮЧЕНИЕМ того, что я использую подход, заключающийся в том, чтобы всегда находить следующий лучший вариант.

from sortedcontainers import SortedSet

def topological_remove_cycles (g):
    # Dictionary of sets of incoming edges. We want to pick nodes with few of them.
    incoming = {}
    for node in g.nodes:
        incoming[node] = set()
    for node in g.nodes():
        for next_node in g.neighbors(node):
            incoming[next_node].add(node)

    # Sorted set of (count_incoming, -count_outgoing, node) triplets.
    # The first item in the set will have as few incoming nodes as it can, and as many outgoing.
    # In other words, it is a greedy choice for a good node to get rid of cycles.
    todo = SortedSet()
    for node, to_node in incoming.items():
        todo.add((len(to_node), -len(g.adj[node]), node))

    # And now let's start removing cycles.
    while 0 < len(todo):
        # Get the best node.
        _, _, node = todo.pop(0)
        to_node = incoming[node]
        for prev_node in to_node:
            # Each of these edges is in, or comes from, a cycle.
            if prev_node != node:
                # Do bookkeeping in todo.
                len_in = len(incoming[prev_node])
                len_out = len(g.adj[prev_node])
                todo.remove((len_in, -len_out, prev_node))
                todo.add((len_in, -len_out + 1, prev_node))
            g.remove_edge(prev_node, node)

        for next_node in g.neighbors(node):
            # Do bookkeeping in todo for forgetting about node.
            len_in = len(incoming[next_node])
            len_out = len(g.adj[next_node])
            todo.remove((len_in, -len_out, next_node))
            todo.add((len_in - 1, -len_out, next_node))
            incoming[next_node].remove(node)
        # And now we've guaranteed that node is cycle free and gone from our bookkeeping.

И, конечно же, давайте проведем небольшой тест, в котором предыдущий код дал сбой.

data = {0: [1, 2, 11], 1: [3, 4, 10], 2: [5, 6], 3: [7, 8, 6, 9], 4: [9, 10], 5: [11, 12, 3], 6: [13, 14, 10, 5, 7], 7: [1], 8: [7, 14], 9: [10], 10: [14], 11: [10], 12: [], 13: [], 14: [1, 2]}
g = nx.from_dict_of_lists(data, create_using=nx.DiGraph())

print(nx.to_dict_of_lists(g))
print(g)
print("Before removing, there are " + str(len(list(nx.simple_cycles(g)))) + " cycles")
topological_remove_cycles(g)
print(g)
print("After removing, there are " + str(len(list(nx.simple_cycles(g)))) + " cycles")
print(nx.to_dict_of_lists(g))

И более масштабный тест. Обратите внимание, что он настолько хорош в распутывании вещей, что обычно находит способ удалить меньше ребер, чем было добавлено при создании циклов!

g = nx.balanced_tree(3, 6, create_using=nx.DiGraph())
induce_cycles(g, 100)
print(g)
topological_remove_cycles(g)
print(g)
print("After removing, there are " + str(len(list(nx.simple_cycles(g)))) + " cycles")