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 |
The object partitionLMG is a method function.