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

Synopsis

Function: isCyclic
Usage:

isCyclic(G)
Inputs:
- G, an instance of the type MixedGraph,
Outputs:
- a Boolean value,

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

Ways to use this method: