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 |