next | previous | forward | backward | up | top | index | toc | Macaulay2 website
StatGraphs :: partitionLMG

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

Synopsis

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 :

For the programmer

The object partitionLMG is a method function.