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 |