Networkx, используя кратчайшие пути, чтобы сделать кратчайшие циклы

Question

этот вопрос специфичен для NetworkX. Я мог бы создавать свои собственные функции для выполнения всего, что мне нужно, но это заняло бы гораздо больше времени, поэтому я хочу избежать этого.

Ситуация:

У меня есть невзвешенный граф, представленный неориентированным графом NetworkX. Из этого графа я ищу «кратчайшие циклы» - то есть для данного узла k я нахожу кратчайший простой путь (проходит только через узел один раз), который покидает k и затем возвращается к k.

Для этого я хотел бы использовать любой алгоритм кратчайших путей NetworkX и выполнять поиск от узла k к узлу k. Проблема, кажется, что каждый алгоритм кратчайшего пути просто возвращает узел k в качестве пути. Таким образом, это никогда не уходит. И я не знаю, как это изменить.

Возможное решение было бы для меня сделать:

for each edge from k
    disconnect that edge
    do shortest path from the other side of that edge to k
    reconnect that edge

Однако огромное количество раз, когда я планирую использовать эту технику "кратчайшего цикла", чрезвычайно велико, и я бы предпочел не делать этого. Итак, есть ли более простой способ сделать то, что я хочу с NetworkX?

Спасибо.

Answer 1

Вы можете попробовать cycle_basis, который пытается найти набор циклов, которые составляют основу, и выбрать минимальный цикл:

import networkx as nx

g = nx.Graph()
g.add_nodes_from([1,2,3,4,5,6,7])
g.add_edges_from([(1,2), (1,3), (2,4), (2,7), (3,5), (6,7), (5,6), (1,5), (3,4)])

min(nx.cycle_basis(g, 1), key=lambda cycle: len(cycle))