(*
(* mis.nb *)
*)
(*
enumerate

enumerate the triangulations (TRI) and maximal independent
sets (MIS)

*** defined outside ***
NumberOfSimplices = total number of maximal dimensional
                    simplices
IntersectProperQ[i,j] = True, False
						whether simplex[i] and simplex[j]
						intersect properly or not
OutputFile = file to append output
simplexVolume[i] = volume of the i-th simplex
wholeVolume = volume of the whole convex hull

*** variables ***
current = the current set
level = 0, 1, ..., NumberOfSimplices
trace = array of the trace of search
		index: 1, ..., NumberOfSimplices
		contents: 0 = not visited
				  1 = Union[currentset,level] was
				      independent. visiting that unique
				      child
				  2 = Union[currentset,level] was
				  	  dependent. visiting the first
				  	  child "currentset"
				  3 = Union[currentset,level] was
				  	  dependent. visiting the second
				  	  child, which is the maximal subset
				  	  of Union[currentset,level]
				  	  including "level"
candidate = candidate of the second child
*)
ClearAll[enumerate];
enumerate:=
Module[
	{current={}, level = 1,
	 trace,
	 candidate},
	Do[trace[i]=0, {i, NumberOfSimplices}];
	While[
		level > 0,
		If[	level <= NumberOfSimplices,
			(* internal node *)
			Switch[	((***
					 Print["trace[",level,"] is ",
					 	trace[level]];
					 ***)
					 trace[level]),
				(* 0 = visiting the unvisited child *)
				0,
				If[	(* Union[current,level] independent ? *)						\
SetIntersectProperQ[current,level],
					(AppendTo[current,level];
					 trace[level] = 1; level++),
					((* no change to current *)
					 trace[level] = 2; level++)]
				(***
				; Print["node 0, level ",level,", current ",
					current]
				***)
				,
				(* 1 = ascending from the unique child *)
				1,
				(current = Complement[current,{level}];
				 trace[level] = 0; level--)
				(***
				; Print["node 1, level ",level,", current ",
					current]
				***)
				,
				(* 2 = ascending from the first child *)
				2,
				If[ (* the second child exist ? *)
					And[((* making candidate *)
						 candidate = {};
						 Scan[
							(If[IntersectProperQ[#,level],
								AppendTo[candidate,#]])&,
							current];
						 AppendTo[candidate,level]
						 (***
						 ; Print["candidate ",candidate]
						 ***)
						 );
						(* checking the maximality of
							candidate in {1,...,level} *)
						MaximalQ[candidate,level],
						(* is parent the lexicographically
							smallest parent of candidate ? *)
						LexMinParentQ[current,
							candidate,
							level]],
					(* the second child exists *)
					(current = candidate;
					 trace[level] = 3; level++),
					(* the second child does not exist *)
					((* no change to current *)
					 trace[level] = 0; level--)]
				(***
				; Print["node 2, level ",level,", current ",
					current]
				***)
				,
				(* 3 = ascending from the second child *)
				3,
				(current = Complement[current,{level}];
				 Do[
				 	If[ And[
				 			Not[MemberQ[current,i]],
				 			SetIntersectProperQ[current,i]],
					current=Union[current,{i}]],
					{i,level-1}];
				 trace[level] = 0; level--)
				 (***
				 ; Print["node 3, level ",level,", current ",
				 	current]
				 ***)
				],
			(* bottom *)
			(If[
				Apply[
					Plus,
					Abs[
						Map[
							simplexVolume,
							current]]]
				==wholeVolume,
				((*Print["TRI ",current];*)
				 PutAppend[{TRI,current},OutputFile]),
				((*Print["MIS ",current];*)
				 PutAppend[{MIS,current},OutputFile])];
			 level--)]]]
(*
SetIntersectProperQ[list,j] = True, False
	whether all simplex[i] for some element i of list
	intersects properly with simplex[j] or not
*)
ClearAll[SetIntersectProperQ];
SetIntersectProperQ[list_,j_] :=
	If[	list=={},
		True,
		If[	IntersectProperQ[Part[list,1],j],
			SetIntersectProperQ[Rest[list],j],
			False]]
(*
MaximalQ[set,level] = True, False
	whether set is a maximal independent set in {1,...,level}
	or not
*)
ClearAll[MaximalQ];
MaximalQ[set_,level_] :=
	Module[{i=1,j,l=Length[set]},
		While[
			And[i<=level,
				Or[	MemberQ[set,i],
					(j=1;
					 While[
					 	And[j<=l,														IntersectProperQ[i,set[[j]]]],
						j++];
					 j<=l)]],
			i++];
		(***
		If[	i>level,
			Print[set," is maximal in {1,...,",level,"}"],
			Print[set," is not maximal in {1,...",level,"}"]];
		***)
		i>level]
(*
LexMinParentQ[parent,child,level] = True, False
	whether parent is the lexicographically smallest parent of
	candidate or not
*)
ClearAll[LexMinParentQ];
LexMinParentQ[parent_,child_,level_] :=
	Module[{temporaryset,i=1,m},
		m =	If[	parent=={},
				level-1,
				Last[parent]];
		temporaryset = Complement[child,{level}];
		While[MemberQ[parent,i],
			(AppendTo[temporaryset,i];
			 i++)];
		While[
			And[i < m,
				Not[SetIntersectProperQ[temporaryset,i]]],
			(i++;
			 While[MemberQ[parent,i],
				(AppendTo[temporaryset,i];
				 i++)])];
		(***
		If[	i >= m,
			Print["parent is lex min parent"],
			Print["parent is not lex min parent"]];
		***)
		i >= m]
