Взято из библиотеки bytenet3
import collections, itertools
def get_loops(MN):
""" Returns the tuple of closed loops. Loops are represented as ordered lists of nodes """
network = {}
for a,b in MN:
network[a].add(b) if a in network else network.update({a:{b}})
network[b].add(a) if b in network else network.update({b:{a}})
chain = collections.OrderedDict()
def __loop_iterator(node):
if node not in chain:
chain[node] = None
next = network[node]
while next:
n = next.pop()
network[n].remove(node)
yield from __loop_iterator(n)
chain.popitem()
else: yield tuple(itertools.chain(itertools.takewhile(lambda x: x is not node, reversed(chain)), (node,)))
# 'for' is needed for just to run from any first available node as n
for n in network: return tuple(__loop_iterator(n))
ch = [(1,4), (4,3), (3,2), (6,3), (4,6), (5,6), (5,4)]
>>> print( *get_loops(ch), sep = '\n' )
(6, 3, 4)
(5, 6, 3, 4)