# isCyclic(MixedGraph) -- check whether a mixed graph contains a directed cycle

## Synopsis

• Function: isCyclic
• Usage:
isCyclic(G)
• Inputs:
• Outputs:

## Description

This method checks whether a MixedGraph is cyclic, i.e. contains a directed cycle or a cycle on directed edges.

A directed cycle is a cycle in the Digraph constructed from a mixed graph G by identifying all connected components on bidirected and undirected edges. Such a connected component contains either bidirected edges only or undirected edges only.

In the following example, there are no directed cycles.

 i1 : U = graph{{1,2},{2,3},{3,4},{1,4},{1,5}} o1 = Graph{1 => {2, 4, 5}} 2 => {1, 3} 3 => {2, 4} 4 => {1, 3} 5 => {1} o1 : Graph i2 : D = digraph{{2,1},{3,1},{7,8}} o2 = Digraph{1 => {} } 2 => {1} 3 => {1} 7 => {8} 8 => {} o2 : Digraph i3 : B = bigraph{{1,5}} o3 = Bigraph{1 => {5}} 5 => {1} o3 : Bigraph i4 : G = mixedGraph(U,D,B) o4 = MixedGraph{Bigraph => Bigraph{1 => {5}} } 5 => {1} Digraph => Digraph{1 => {} } 2 => {1} 3 => {1} 7 => {8} 8 => {} Graph => Graph{1 => {2, 4, 5}} 2 => {1, 3} 3 => {2, 4} 4 => {1, 3} 5 => {1} o4 : MixedGraph i5 : isCyclic G o5 = false

In the next example, there are no cycles inside the digraph of the mixed graph, but there is a directed cycle after you identify the vertices {1,2} and {3,4}.

 i6 : U = graph{{1,2},{3,4}} o6 = Graph{1 => {2}} 2 => {1} 3 => {4} 4 => {3} o6 : Graph i7 : D = digraph{{1,3},{4,2}} o7 = Digraph{1 => {3}} 2 => {} 3 => {} 4 => {2} o7 : Digraph i8 : G = mixedGraph(U,D) o8 = MixedGraph{Bigraph => Bigraph{} } Digraph => Digraph{1 => {3}} 2 => {} 3 => {} 4 => {2} Graph => Graph{1 => {2}} 2 => {1} 3 => {4} 4 => {3} o8 : MixedGraph i9 : isCyclic G o9 = true

This is a similar example as before, but now the vertices {1,2} are connected by an undirected edge and {3,4} by a bidirected edge.

 i10 : U = graph{{1,2}} o10 = Graph{1 => {2}} 2 => {1} o10 : Graph i11 : B = bigraph{{3,4}} o11 = Bigraph{3 => {4}} 4 => {3} o11 : Bigraph i12 : D = digraph{{1,3},{4,2}} o12 = Digraph{1 => {3}} 2 => {} 3 => {} 4 => {2} o12 : Digraph i13 : G = mixedGraph(U,D,B) o13 = MixedGraph{Bigraph => Bigraph{3 => {4}}} 4 => {3} Digraph => Digraph{1 => {3}} 2 => {} 3 => {} 4 => {2} Graph => Graph{1 => {2}} 2 => {1} o13 : MixedGraph i14 : isCyclic G o14 = true

In the following example, there is a cycle on the directed edges that is inside a connected undirected component.

 i15 : G = mixedGraph(graph{{1,2}},digraph {{1,2},{2,1}}) o15 = MixedGraph{Bigraph => Bigraph{} } Digraph => Digraph{1 => {2}} 2 => {1} Graph => Graph{1 => {2}} 2 => {1} o15 : MixedGraph i16 : isCyclic G o16 = true