`hascycles`

Tests whether a graph or digraph contains a cycle.

Category: Mathematics > Graph and Network Algorithms

Syntax

tf = hascycles(G)

Returns true if G has at least one cycle.

Description

In an undirected graph a cycle exists exactly when some connected component has at least as many edges as nodes, that is, when the graph is not a forest. In a digraph the edges must be followed in their direction, so a digraph without cycles is a DAG and isdag is the opposite test.

Input arguments

G: A graph or digraph.

Output arguments

tf: Logical scalar.

Example

Path versus triangle

hascycles(graph([1 2], [2 3]))
hascycles(graph([1 2 3], [2 3 1]))
hascycles(digraph([1 2], [2 3]))

Output

ans = logical
   0
ans = logical
   1
ans = logical
   0

See also

isdag allcycles cyclebasis conncomp