write documentation and tests for these functions

[harshitmotwani2015]

Workshop-2020-Warwick/AlgebraicStatistics/GraphicalModelsMultiTrek.m2

Lines 1055 to 1156 in 9b7256e

	Input: graph g, integer k
	Output: list of separation statements: in format {Slist,Alist}, where Slist={S1..Sk}, Alist={A1..Ak}
	Strategy: Loop over all A_1..A_k and all S_1..S_(k-1), find the maximal S_k such that it is separated:
	a vertex w can not be in S_k if and only if it is a descendant of a t in tops(g,k-1,{A_1..A_(k-1)},{S_1..S_(k-1)})
	*-
	multiTrekSeparation = method()
	multiTrekSeparation (MixedGraph,ZZ) := List => (g,k) ->
	(
	G := graph collateVertices g; --outputs the hash table after collating vertices
	statements := {};
	v := sort vertices g;
	DG := graph G#Digraph; --outputs Directed graph as a hash table
	DGhash := new MutableHashTable from apply(v,i->{i,DG#i}); -- creating a mutable hash table from DG
	--DGhash#(v#1) --returns children of the vertex v#1
	for Alist in toList(((set subsets v)^**k)/deepSplice) do --making k-cartesian product of subsets of v
	( -- Alist is one of the k-cartesian product of subsets of v
	SS := apply(k-1,i->delete({},subsetsBetween(Alist#i,v))); --assume A_i \subset S_i
	--subsetsBetween returns all subsets of v containing Alist#i
	-- #SS = k-1, indexed from 0 to k-2
	-- SS_i is all possible subsets of v which contains Alist_i
	--Want: Slist' is the collection of all possible Slists, where Slist=(S_1..S_(k-1)), with S_i \in SS_i
	--remember Alist_0 is actually A_1 and Alist_(k-1) is A_k.
	Slist' := set(apply(SS#0,j->toSequence({j})));
	--Want to loop over all Slist = {S1..}
	for i from 1 to k-2 do --making k-1 cartesian product of SS_0xSS_1..XSS_(k-2)
	(
	Slist' = (Slist' ** (set (SS#i)))/splice;
	);
	for Slist in toList(Slist') do
	(
	toplist := tops(G#Digraph,k-1,toList Slist,toList (drop(Alist,-1))); --find tops of all the treks which ends in S_1,..,S_(k-1) not passing through A_1,..A_(k-1)
	--Find all descendants of all tops in the graph G \ A_k, remove them from v. That is our S_k
	G':=deleteVertices(G#Digraph,Alist_(k-1)); --G'is the induced digraph after removing vertices from A_k
	Sk:=v;
	for w in Alist_(k-1) do
	(
	toplist=delete(w,toplist); -- removing A_k from toplist
	);
	for w in reachable(G',toplist) do
	(
	Sk = delete(w,Sk); --if w is reachable in G' from any one of the vertices of toplist then it cannot be in S_k
	);
	-- we are not removing A_k from S_k. Hence A_k \subset S_k.
	newStatement:={append(Slist,Sk),Alist};
	redundant:=false;
	i:=0;
	while not redundant and i < length(statements) do(
	if impliesSeparationStatement(k,statements#i,newStatement) then (redundant=true;);
	if impliesSeparationStatement(k,newStatement,statements#i) then (
	statements=remove(statements,i);
	i=i-1;
	);
	i=i+1;
	);
	if not redundant then(statements=append(statements,newStatement););
	);
	);
	return sortedout(statements);
	)
	impliesSeparationStatement = method()
	--Return true if statement1 implies statement2
	--For every S1 in statement1 and corresponding S2 in statement2: S2 subset of S1
	--For every A1 in statement1 and corresponding A2 in statement2: A1 subset of A2
	impliesSeparationStatement (ZZ,List,List) := Boolean => (k,statement1,statement2) ->
	(for i from 0 to k-1 do(
	if not isSubset(statement2#0#i,statement1#0#i) then(return false;);
	if not isSubset(statement1#1#i,statement2#1#i) then(return false;);
	);
	return true;
	)
	sortedout = method()
	-- method to sort separration statements
	sortedout (List) := List => (L) ->
	(
	l := #L;
	s := {};
	for i from 0 to l-1 do
	(
	ss := apply(L#i#0,l->sort(l));
	sa := apply(L#i#1,l->sort(l));
	s = s|{{(ss),(sa)}};
	);
	return s;
	)