`cyclebasis`

A set of independent cycles from which all cycles of a graph can be built.

Category: Mathematics > Graph and Network Algorithms

Syntax

cycles = cyclebasis(G)

Returns a fundamental cycle basis as a cell array of node lists.

Description

The number of independent cycles of a graph is numedges(G) - numnodes(G) + c, where c is the number of connected components. cyclebasis returns that many cycles, each one formed by a non-tree edge together with the tree path between its ends. Any other cycle is a combination of these, with shared edges cancelling.

A graph with no cycles returns an empty cell array.

Input arguments

G: An undirected graph.

Output arguments

cycles: Cell array with one cell per basis cycle. Each cell lists the nodes of the cycle in order.

Example

Two triangles sharing an edge

G = graph([1 1 2 2 3], [2 3 3 4 4]);
c = cyclebasis(G);
fprintf('%d independent cycles\n', numel(c))

Output

2 independent cycles

cyclebasis