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

## Synopsis

• Usage:
partitionLMG(G)
• Inputs:
• Outputs:
• , (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 .