hascycles - Determine whether graph contains cycles - MATLAB (original) (raw)
Main Content
Determine whether graph contains cycles
Since R2021a
Syntax
Description
tf = hascycles([G](#mw%5F159f35e8-a36a-4a08-a663-c4f549e76871%5Fsep%5Fshared-G)) returns logical1 (true) if graph G contains one or more cycles, and logical0 (false) otherwise.
Examples
Create and plot an undirected graph.
G = graph([1 1 1 1],[2 3 4 5]); plot(G)
Determine whether the graph has cycles.
Now add an edge to the graph between node 2 and node 3. Replot the graph.
G = addedge(G,2,3); plot(G)
Determine whether the new graph has cycles.
Examine the difference between the hascycles and isdag functions operating on a directed graph.
Create and plot a directed graph.
s = [1 1 1 2 3 3 3 4 6]; t = [2 4 5 5 6 7 4 1 4]; G = digraph(s,t); plot(G)
Determine whether the graph contains any cycles.
hascycles returns true when a directed graph contains a cycle.
Now, use isdag to determine whether the graph is directed and acyclic.
isdag returns false because the graph contains a cycle. In general, the hascycles and isdag functions return opposite results for directed graphs.
Input Arguments
More About
A cycle exists in a graph when there is a nonempty path in which only the first and last nodes are repeated. An example of a cycle is: (Node1 - Node2 - Node3 - Node1).
A cycle cannot traverse the same edge twice. For example, the cycle (Node1 - Node2 - Node1) in an undirected graph only exists if there is more than one edge connecting Node1 and Node2. By this definition, self-loops count as cycles, though they cannot be part of any larger cycles.
Version History
Introduced in R2021a