Как обнаружить цикл в ориентированном графе с Python?

Question

У меня есть некоторые данные, такие как: [('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]. Я хочу посмотреть, существует ли существование цикла в ориентированном графе, представленном этим edgeList.

Я прочитал обсуждение: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/, однако в случае :

g = Graph(3)
g.addEdge('A', 'B')
g.addEdge('B', 'C')
g.addEdge('C', 'A')

Его результат «График не имеет цикла». Это явно неправильно. Можете ли вы помочь мне решить эту проблему?

Answer 1

Используя библиотеку networkx , мы можем использовать функцию simple_cycles, чтобы найти все простые циклы ориентированного графа.

Пример кода:

import networkx as nx

edges = [('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]

G = nx.DiGraph(edges)

for cycle in nx.simple_cycles(G):
    print(cycle)

G = nx.DiGraph()

G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('C', 'A')

for cycle in nx.simple_cycles(G):
    print(cycle)

Выход:

['D', 'C']
['B', 'C', 'A']

Answer 2

Проблема в примере, приведенном в [1]: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ работает только для целых чисел, поскольку они используют функцию range() для создания списка узлов, см. Строку

for node in range(self.V):

Это предполагает, что не только все узлы будут целыми числами, но и что они будут смежным множеством, т.е. [0,1,2,3] в порядке, но [0,3,10] - нет.

Вы можете исправить пример если вам нравится работать с любыми узлами, поменяв приведенную выше строку на

for node in self.graph.keys():

, которая пропустит l oop через все узлы вместо диапазона чисел:)

Answer 3

Моя собственная реализация (не рекурсивная, поэтому без ограничения длины цикла):

from collections import defaultdict


def has_cycle(graph):
    try:
        next(_iter_cycles(graph))
    except StopIteration:
        return False
    return True


def _iter_cycles(edges):
    """Iterate over simple cycles in the directed graph."""
    if isinstance(edges, dict):
        graph = edges
    else:
        graph = defaultdict(set)
        for x, y in edges:
            graph[x].add(y)
    SEP = object()
    checked_nodes = set()  # already checked nodes
    for start_node in graph:
        if start_node in checked_nodes:
            continue
        nodes_left = [start_node]
        path = []         # current path from start_node
        node_idx = {}     # {node: path.index(node)}
        while nodes_left:
            node = nodes_left.pop()
            if node is SEP:
                checked_node = path.pop()
                del node_idx[checked_node]
                checked_nodes.add(checked_node)
                continue
            if node in checked_nodes:
                continue
            if node in node_idx:
                cycle_path = path[node_idx[node]:]
                cycle_path.append(node)
                yield cycle_path
                continue
            next_nodes = graph.get(node)
            if not next_nodes:
                checked_nodes.add(node)
                continue
            node_idx[node] = len(path)
            path.append(node)
            nodes_left.append(SEP)
            nodes_left.extend(next_nodes)


assert not has_cycle({0: [1, 2], 1: [3, 4], 5: [6, 7]})
assert has_cycle([(0, 1), (1, 0), (1, 2), (2, 1)])


def assert_cycles(graph, expected):
    detected = sorted(_iter_cycles(graph))
    if detected != expected:
        raise Exception('expected cycles:\n{}\ndetected cycles:\n{}'.format(expected, detected))


assert_cycles([('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')], [['C', 'D', 'C']])
assert_cycles([('A', 'B'),('B', 'A'),('B', 'C'),('C', 'B')], [['A', 'B', 'A'], ['B', 'C', 'B']])

assert_cycles({1: [2, 3], 2: [3, 4]}, [])
assert_cycles([(1, 2), (1, 3), (2, 3), (2, 4)], [])

assert_cycles({1: [2, 4], 2: [3, 4], 3: [1]}, [[1, 2, 3, 1]])
assert_cycles([(1, 2), (1, 4), (2, 3), (2, 4), (3, 1)], [[1, 2, 3, 1]])

assert_cycles({0: [1, 2], 2: [3], 3: [4], 4: [2]}, [[2, 3, 4, 2]])
assert_cycles([(0, 1), (0, 2), (2, 3), (3, 4), (4, 2)], [[2, 3, 4, 2]])

assert_cycles({1: [2], 3: [4], 4: [5], 5: [3]}, [[3, 4, 5, 3]])
assert_cycles([(1, 2), (3, 4), (4, 5), (5, 3)], [[3, 4, 5, 3]])

assert_cycles({0: [], 1: []}, [])
assert_cycles([], [])

assert_cycles({0: [1, 2], 1: [3, 4], 5: [6, 7]}, [])
assert_cycles([(0, 1), (0, 2), (1, 3), (1, 4), (5, 6), (5, 7)], [])

assert_cycles({0: [1], 1: [0, 2], 2: [1]}, [[0, 1, 0], [1, 2, 1]])
assert_cycles([(0, 1), (1, 0), (1, 2), (2, 1)], [[0, 1, 0], [1, 2, 1]])

РЕДАКТИРОВАТЬ:

Я обнаружил, что хотя has_cycle кажется правильным, _iter_cycles не повторяется по всем циклам!

Пример, в котором _iter_cycles не находит все циклы:

assert_cycles([
        (0, 1), (1, 2), (2, 0),  # Cycle 0-1-2
        (0, 2), (2, 0),          # Cycle 0-2
        (0, 1), (1, 4), (4, 0),  # Cycle 0-1-4
    ],
    [
        [0, 1, 2, 0],  # Not found (in Python 3.7)!
        [0, 1, 4, 0],
        [0, 2, 0],
    ]
)