Find cycles in a graph that don't contain smaller cycle within it

Question

Given the edges of a graph, I wish to create an algorithm in python to find all cycles where there are no other cycles within it, I have tried various ideas for several days with no 100% reliability.

For example,

This graph has the edges as follow:

[[0,1],[2,1],[0,2],[0,3],[3,1],[3,2]]

And there are 7 possible distinct cycles/loops:

[[0, 2, 1, 0], [0, 3, 2, 1, 0], [0, 3, 1, 0], [0, 2, 3, 1, 0], [0, 3, 1, 2, 0], [0, 3, 2, 0], [1, 3, 2, 1]]

But the cycle [0,3,2,1,0] has the cycle [0,2,1,0] and [0,3,2,0] embedded within it. Similarly [0,2,3,1,0] has the cycles [0,3,2,0] and [0,3,1,0] embedded within it. Same goes for [0,3,1,2,0] and [1,3,2,1].

Therefore, my python program should filter all that out and give

[[0,2,1,0],[0,3,1,0],[0,3,2,0]]

which are cycles with no other cycles within it.

I've tried that but if I do that [0,3,2,0] also gets filtered out because all nodes have been visited in the cycles [0,2,1,0],[0,3,1,0] — 5Volts, Jul 17 '20 at 04:14
See also: [Algorithm for finding minimal cycles in a graph](https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph). — Mateen Ulhaq, Jul 17 '20 at 05:10

Prune · Answer 1 · 2020-07-17T04:26:38.557

You've identified all cycles. For determining minimal cycles, the node order is immaterial: a minimal cycle is uniquely identified by its set of nodes.

Convert each list of nodes to a set. Make a new list of sets that have no subsets in the list.

cycle_list = [
    [0, 2, 1, 0],
    [0, 3, 2, 1, 0],
    [0, 3, 1, 0],
    [0, 2, 3, 1, 0],
    [0, 3, 1, 2, 0],
    [0, 3, 2, 0],
    [1, 3, 2, 1]
]

set_list = [set(c) for c in cycle_list]
min_cycle = [c for c in set_list if c!= super
             and not any(super < c for super in set_list)
             ]
print(min_cycle)

Output:

[{0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}]

If you want the cycles in node order, I trust that you can map the four solutions (1, 2, 3, 1 is also a solution) back to the original list.

@MateenUlhaq those nodes are connected in that order. Where are you confused? It's even listed in the original question. — Prune, Jul 17 '20 at 04:48

Mateen Ulhaq · Answer 2 · 2020-07-17T04:56:04.350

EDIT: This method solves a slightly different problem, but perhaps you can adapt it to your particular case. I'll fix the answer at some point in the future.

This method runs dfs() to list all candidate cycles from a particular start node. was_traversed() is used to check if a particular path was already traversed in the current path. Then, the "duplicate" cycles are trimmed away in the cycles() method.

def cycles(graph, start):
    paths = {tuple(sorted(xs)): xs for xs in dfs(graph, [start])}
    return paths.values()

def dfs(graph, path):
    for node in graph[path[-1]]:
        if was_traversed(path, path[-1], node):
            continue
        if node == path[0]:
            yield path + [node]
            continue
        yield from dfs(graph, path + [node])

def was_traversed(path, a, b):
    query = sorted([a, b])
    return any(
        sorted([x, y]) == query
        for x, y in zip(path[:-1], path[1:])
    )

Test:

>>> graph = {
...     0: [1, 2, 3],
...     1: [0, 2, 3],
...     2: [0, 1, 3],
...     3: [0, 1, 2],
... }

>>> for cycle in dfs(graph, [0]):
...     print(cycle)
[0, 1, 2, 0]
[0, 1, 2, 3, 0]
[0, 1, 3, 0]
[0, 1, 3, 2, 0]
[0, 2, 1, 0]
[0, 2, 1, 3, 0]
[0, 2, 3, 0]
[0, 2, 3, 1, 0]
[0, 3, 1, 0]
[0, 3, 1, 2, 0]
[0, 3, 2, 0]
[0, 3, 2, 1, 0]

>>> for cycle in cycles(graph, 0):
...     print(cycle)
[0, 2, 1, 0]
[0, 3, 2, 1, 0]
[0, 3, 1, 0]
[0, 3, 2, 0]

You omitted the edge (2, 1); check the original post. – Prune Jul 17 '20 at 04:49 — Prune, Jul 17 '20 at 04:49

Find cycles in a graph that don't contain smaller cycle within it

2 Answers2