`allcycles`

Finds every simple cycle of a graph or digraph.

Category: Mathematics > Graph and Network Algorithms

Syntax

cycles = allcycles(G)

Returns a cell array with one node list per cycle.

Description

A simple cycle is a closed walk that never visits a node twice. In an undirected graph each cycle is reported once, not once per direction or starting point. In a digraph the edge directions must be followed.

The number of cycles can grow very fast with the size of the graph, so use it on small graphs. cyclebasis gives a compact set of cycles that generates all the others.

Input arguments

G: A graph or digraph.

Output arguments

cycles: Cell array. Each cell holds the nodes of one cycle, in the order they are visited. It is empty when G has no cycle.

Example

A triangle with a tail

G = graph([1 2 3 3], [2 3 1 4]);
c = allcycles(G);
numel(c)
c{1}

Output

ans = 1
ans = 1×3

     1     2     3

allcycles