partitionLMG -- partition the vertices of a loopless mixed graph into adjacent to undirected edges and adjacent to bidirected edges

Synopsis

Usage:

partitionLMG(G)
Inputs:
- G, an instance of the type MixedGraph,
Outputs:
- a sequence, (U,W) where U are vertices adjacent to undirected edges and W are vertices adjacent to bidirected edges

Description

This function makes a partition $U\cup W$ of the vertices V of a loopless mixed graph such that:

- if $i-j$ in $G$ then $i,j\in U$,

- if $i\leftarrow \rightarrow j$ in $G$ then $i,j\in W$

- there is no directed edge $i\to j$ in $G$ such that $i\in W$ and $j\in U$.

These conditions are equivalent to those introduced in Seth Sullivant, Kelli Talaska, and Jan Draisma, Trek separation for Gaussian graphical models, The Annals of Statistics 38.3 (2010): 1665-1685.

For technical purposes we assume, without loss of generality, that vertices in the LMG are ordered such that:

1. all vertices in U come before vertices in W,

2. if there is a directed edge from $i$ to $j$, then $i<j$.

This method checks that the input contains no loops and it requires the graph to be directed acyclic, i.e., there should not be any directed cycles after the identification of the connected undirected and bidirected components.

i1 : U = graph{{1,2},{2,3},{1,3}}

o1 = Graph{1 => {2, 3}}
           2 => {1, 3}
           3 => {1, 2}

o1 : Graph

i2 : D = digraph{{1,4},{3,7}}

o2 = Digraph{1 => {4}}
             3 => {7}
             4 => {}
             7 => {}

o2 : Digraph

i3 : B = bigraph{{4,5},{5,6},{7,8}}

o3 = Bigraph{4 => {5}   }
             5 => {4, 6}
             6 => {5}
             7 => {8}
             8 => {7}

o3 : Bigraph

i4 : G = mixedGraph(U,D,B)

o4 = MixedGraph{Bigraph => Bigraph{4 => {5}   }}
                                   5 => {4, 6}
                                   6 => {5}
                                   7 => {8}
                                   8 => {7}
                Digraph => Digraph{1 => {4}}
                                   3 => {7}
                                   4 => {}
                                   7 => {}
                Graph => Graph{1 => {2, 3}}
                               2 => {1, 3}
                               3 => {1, 2}

o4 : MixedGraph

i5 : partitionLMG G

o5 = ({1, 2, 3}, {4, 5, 6, 7, 8})

o5 : Sequence

The vertices that are adjacent only to directed edges are sorted depending on their order. If v is such a vertex and v < max U, then v is added to U. Otherwise, it is added to W.

i6 : U = graph{{2,3},{3,4},{4,2}}

o6 = Graph{2 => {3, 4}}
           3 => {2, 4}
           4 => {2, 3}

o6 : Graph

i7 : D = digraph{{1,2},{2,5},{4,9}}

o7 = Digraph{1 => {2}}
             2 => {5}
             4 => {9}
             5 => {}
             9 => {}

o7 : Digraph

i8 : B = bigraph{{5,6},{6,7},{8,9}}

o8 = Bigraph{5 => {6}   }
             6 => {5, 7}
             7 => {6}
             8 => {9}
             9 => {8}

o8 : Bigraph

i9 : G = mixedGraph(U,D,B)

o9 = MixedGraph{Bigraph => Bigraph{5 => {6}   }}
                                   6 => {5, 7}
                                   7 => {6}
                                   8 => {9}
                                   9 => {8}
                Digraph => Digraph{1 => {2}}
                                   2 => {5}
                                   4 => {9}
                                   5 => {}
                                   9 => {}
                Graph => Graph{2 => {3, 4}}
                               3 => {2, 4}
                               4 => {2, 3}

o9 : MixedGraph

i10 : partitionLMG G

o10 = ({1, 2, 3, 4}, {5, 6, 7, 8, 9})

o10 : Sequence

i11 : U = graph{{1,2},{2,3},{1,3}}

o11 = Graph{1 => {2, 3}}
            2 => {1, 3}
            3 => {1, 2}

o11 : Graph

i12 : D = digraph{{1,4},{3,7},{8,9}}

o12 = Digraph{1 => {4}}
              3 => {7}
              4 => {}
              7 => {}
              8 => {9}
              9 => {}

o12 : Digraph

i13 : B = bigraph{{4,5},{5,6},{7,9}}

o13 = Bigraph{4 => {5}   }
              5 => {4, 6}
              6 => {5}
              7 => {9}
              9 => {7}

o13 : Bigraph

i14 : G = mixedGraph(U,D,B)

o14 = MixedGraph{Bigraph => Bigraph{4 => {5}   }}
                                    5 => {4, 6}
                                    6 => {5}
                                    7 => {9}
                                    9 => {7}
                 Digraph => Digraph{1 => {4}}
                                    3 => {7}
                                    4 => {}
                                    7 => {}
                                    8 => {9}
                                    9 => {}
                 Graph => Graph{1 => {2, 3}}
                                2 => {1, 3}
                                3 => {1, 2}

o14 : MixedGraph

i15 : partitionLMG G

o15 = ({1, 2, 3}, {4, 5, 6, 7, 8, 9})

o15 : Sequence

Ways to use partitionLMG :

partitionLMG(MixedGraph)

For the programmer

The object partitionLMG is a method function.