A trek between vertices $i$ and $j$ in a mixed graph $G$ with directed and bidirected edges is a triple $(P_L,P_R)$ where $P_L$ is a directed path of directed edges with sink $i$ and source $k$, $P_R$ is a directed path of directed edges with sink $j$ and source $l$, and either $k=l$ or there is a bidirected edge between $k$ and $l$. Let $A,B,CA,CB$ be subsets of vertices of $G$.
We say that $(CA,CB)$ trek-separates $A$ from $B$ in $G$ if for every trek $(P_L,P_R)$ from a vertex in $A$ to a vertex in $B$, either $P_L$ contains a vertex in $CA$ or $P_R$ contains a vertex in $CB$.
The function trekSeparation returns a list of trek separation statements $\{A,B,CA,CB\}$\,where $#CA + #CB < min(#A, #B)$. Each statement is maximal in the ordering where $\{A1,B1,CA,CB\}\,<\,\{A2,B2,CA,CB\}$\,if $A1$ is a subset of $A2$ and $B1$ is a subset of $B2$. Each statement is also unique up to symmetry, since $\{B,A,CB,CA\}$\,is a trek separation statement if and only if $\{A,B,CA,CB\}$.
i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})
o1 = MixedGraph{Bigraph => Bigraph{a => {d}} }
d => {a}
Digraph => Digraph{b => {c, d}}
c => {d}
d => {}
Graph => Graph{}
o1 : MixedGraph
|
i2 : S = trekSeparation G
o2 = {{{a}, {b, c}, {}, {}}, {{a, b}, {b, c}, {}, {b}}, {{b, c}, {a, b}, {},
------------------------------------------------------------------------
{b}}, {{b, c}, {a, c}, {}, {c}}, {{b, c}, {d, a}, {}, {d}}}
o2 : List
|
trekSeparation $G$ is only implemented for mixedGraphs with directed and bidirected edges.
The object trekSeparation is a method function.