SSL operations.gi   Sprache: unbekannt

################################################################################
##
##  simpcomp / operations.gi
##
##  Operations on simplicial complexes.
##
##  $Id$
##
################################################################################


SCIntFunc.RelabelSimplexList:=
function(simplices,maptable)
 local facets;
 if(simplices=fail or maptable=fail) then
  return fail;
 else
  if IsSortedList(maptable) then
   return List(simplices,s->List(s,x->maptable[x]));
  else
   facets:= List(simplices,s->List(s,x->maptable[x]));
   Perform(facets,Sort);
   Sort(facets);
   return facets;
  fi;
 fi;
end;

SCIntFunc.RelabelSimplexListInv:=
function(simplices,maptable)
 local facets;
 if(simplices=fail or maptable=fail) then
  return fail;
 else
  if IsSortedList(maptable) then
   return List(simplices,s->List(s,x->Position(maptable,x)));
  else
   facets:=List(simplices,s->List(s,x->Position(maptable,x)));
   Perform(facets,Sort);
   Sort(facets);
   return facets;
  fi;
 fi;
end;

SCIntFunc.RelabelPermutation:=
function(perm,maptable)
 local l1,l2,i;
 if(perm=fail or maptable=fail) then
  return fail;
 else
  l1:=ListPerm(perm);
  l1:=List(l1,x->[Position(l1,x),x]);
  l1:=Filtered(l1,x->x[1]<>x[2]); #kill fixed points
  l1:=Filtered(l1,x->IsSubset(maptable,x)); # kill points that are not part of the complex
  l1:=SCIntFunc.RelabelSimplexListInv(l1,maptable); #relabel
  l2:=[];
  for i in [1..Size(l1)] do # build relabeled permutation in list representation
   l2[l1[i][1]]:=l1[i][2];
  od;
  for i in [1..Size(l2)] do # fill up fixed points
   if not IsBound(l2[i]) then
    l2[i]:=i;
   fi;
  od;
  l2:=PermList(l2); # transform to cycle representation
  
  return l2;
 fi;
end;


SCIntFunc.SCCompactify:=
function(facets)
  return Filtered(DuplicateFreeList(facets), f1->Number(facets,f2->IsSubset(f2,f1))=1);
end;

################################################################################
##<#GAPDoc Label="SCJoin">
## <ManSection>
## <Meth Name="SCJoin" Arg="complex1, complex2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Calculates the simplicial join of the simplicial complexes <Arg>complex1</Arg> and <Arg>complex2</Arg>. If facet lists instead of <C>SCSimplicialComplex</C> objects are passed as arguments, the function internally falls back to the homology package <Cite Key="Dumas04Homology" />, if available. Note that the vertex labelings of the complexes passed as arguments are not propagated to the new complex.
## <Example><![CDATA[
## gap> sphere:=SCJoin(SCBdSimplex(2),SCBdSimplex(2));
## gap> SCHasBoundary(sphere);
## false
## gap> sphere.Facets;
## [ [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 2 ] ],
##   [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 3 ] ],
##   [ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ], [ 2, 3 ] ],
##   [ [ 1, 1 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ] ],
##   [ [ 1, 1 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ] ],
##   [ [ 1, 1 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ] ],
##   [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ] ],
##   [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ] ],
##   [ [ 1, 2 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ] ] ]
## gap> sphere.Homology;
## [ [ 0, [  ] ], [ 0, [  ] ], [ 0, [  ] ], [ 1, [  ] ] ]
## ]]></Example>
## <Example><![CDATA[
## gap> ball:=SCJoin(SC([[1]]),SCBdSimplex(2));
## gap> ball.Homology;
## [ [ 0, [  ] ], [ 0, [  ] ], [ 0, [  ] ] ]
## gap> ball.Facets;
## [ [ [ 1, 1 ], [ 2, 1 ], [ 2, 2 ] ], [ [ 1, 1 ], [ 2, 1 ], [ 2, 3 ] ],
##   [ [ 1, 1 ], [ 2, 2 ], [ 2, 3 ] ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCJoin,
"for List and List",
[IsList,IsList],
function(complex1,complex2)
 local join;
 if(IsBound(SCIntFunc.SCJoinOld)) then
   return SCIntFunc.SCJoinOld(complex1,complex2);
 fi;
   
 Info (InfoSimpcomp, 1, "SCJoin: invalid argument list, expecting a simplicial complex. Fallback to homology package failed.");
 return fail;
end);

InstallMethod(SCJoin,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1,complex2)
 
 local join;
 
 join:=SCFromFacets(Concatenation (List (SCFacetsEx(complex1), s1 -> List (SCFacetsEx(complex2),
 s2 -> Concatenation(List (s1, i -> [1, i]), List (s2, i -> [2, i]))))));
 
 if(join=fail) then
  return fail;
 fi;
 
 if(SCName(complex1)<>fail and SCName(complex2)<>fail) then
  SCRename(join,Concatenation(SCName(complex1)," join ",SCName(complex2)));
 fi;
 return join;
end);


################################################################################
##<#GAPDoc Label="SCSuspension">
## <ManSection>
## <Meth Name="SCSuspension" Arg="complex"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Calculates the simplicial suspension of the simplicial complex <Arg>complex</Arg>. Internally falls back to the homology package <Cite Key="Dumas04Homology" /> (if available) if a facet list is passed as argument. Note that the vertex labelings of the complexes passed as arguments are not propagated to the new complex.
## <Example><![CDATA[
## gap> SCLib.SearchByName("Poincare");
## gap> phs:=SCLib.Load(last[1][1]);
## gap> susp:=SCSuspension(phs);;
## gap> edwardsSphere:=SCSuspension(susp);
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCSuspension,
"for List",
[IsList],
function(complex)
 if(IsBound(SCIntFunc.SCSuspensionOld)) then
  return SCIntFunc.SCSuspensionOld(complex);
 fi;

 Info (InfoSimpcomp, 1, "SCSuspension: invalid argument list, expecting a simplicial complex. Fallback to homology package failed.");
 return fail;
end);

InstallMethod(SCSuspension,
"for SCSimplicialComplex",
[SCIsSimplicialComplex],
function(complex)
 
 local susp;
 
 if SCIsEmpty(complex) then
  return SCFromFacets([[1],[2]]);
 fi;
 
 susp:=SCJoin(complex, SCFromFacets([[1], [2]]));
 
 if(susp=fail) then
  return fail;
 fi;
 
 if(SCName(complex)<>fail) then
  SCRename(susp,Concatenation("susp of ",SCName(complex)));
 fi;
 
 return susp;
end);


################################################################################
##<#GAPDoc Label="SCDeletedJoin">
## <ManSection>
## <Meth Name="SCDeletedJoin" Arg="complex1, complex2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Calculates the simplicial deleted join of the simplicial complexes <Arg>complex1</Arg> and <Arg>complex2</Arg>. If called with a facet list instead of a <C>SCSimplicialComplex</C> object, the function internally falls back to the <Package>homology</Package> package <Cite Key="Dumas04Homology" />, if available.
## <Example><![CDATA[
## gap> deljoin:=SCDeletedJoin(SCBdSimplex(3),SCBdSimplex(3));
## gap> bddeljoin:=SCBoundary(deljoin);;
## gap> bddeljoin.Homology;
## [ [ 1, [  ] ], [ 0, [  ] ], [ 2, [  ] ] ]
## gap> deljoin.Facets;
## [ [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 4, 2 ] ],
##   [ [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 1 ] ],
##   [ [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 2 ] ],
##   [ [ 1, 1 ], [ 2, 2 ], [ 3, 1 ], [ 4, 1 ] ],
##   [ [ 1, 1 ], [ 2, 2 ], [ 3, 1 ], [ 4, 2 ] ],
##   [ [ 1, 1 ], [ 2, 2 ], [ 3, 2 ], [ 4, 1 ] ],
##   [ [ 1, 1 ], [ 2, 2 ], [ 3, 2 ], [ 4, 2 ] ],
##   [ [ 1, 2 ], [ 2, 1 ], [ 3, 1 ], [ 4, 1 ] ],
##   [ [ 1, 2 ], [ 2, 1 ], [ 3, 1 ], [ 4, 2 ] ],
##   [ [ 1, 2 ], [ 2, 1 ], [ 3, 2 ], [ 4, 1 ] ],
##   [ [ 1, 2 ], [ 2, 1 ], [ 3, 2 ], [ 4, 2 ] ],
##   [ [ 1, 2 ], [ 2, 2 ], [ 3, 1 ], [ 4, 1 ] ],
##   [ [ 1, 2 ], [ 2, 2 ], [ 3, 1 ], [ 4, 2 ] ],
##   [ [ 1, 2 ], [ 2, 2 ], [ 3, 2 ], [ 4, 1 ] ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCDeletedJoin,
"for List and List",
[IsList,IsList],
function(complex1,complex2)
 if(IsBound(SCIntFunc.SCDeletedJoinOld)) then
  return SCIntFunc.SCDeletedJoinOld(complex1,complex2);
 fi;
 
 Info(InfoSimpcomp, 1, "SCDeletedJoin: invalid argument list, expecting two simplicial complexes. Fallback to homology package failed.");
 return fail;
end);

InstallMethod(SCDeletedJoin,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1,complex2)
 local c1,c2,dj,i,j,k,e,l,l1,l2,f1,f2;

 l1:=SCVertices(complex1);
 l2:=SCVertices(complex2);
 
 if(l1=fail or l2=fail or not ForAll(l1,IsInt) or not ForAll(l2,IsInt)) then
  Info(InfoSimpcomp,1,"SCDeletedJoin: complexes must be labeled with integer numbers.");
  return fail;
 fi;
 
 f1:=Union(SCFaceLattice(complex1));
 f2:=Union(SCFaceLattice(complex2));

 if(f1=fail or f2=fail) then
  return fail;
 fi;
 
 dj:=[];
 
 for i in [1..Length(f1)] do
  for j in [1..Length(f2)] do
   if(Intersection(f1[i],f2[j])<>[]) then
    continue;
   fi;
   
   e:=Union(List(f1[i],x->[x,1]),List(f2[j],x->[x,2]));
   l:=Length(e);
   if(not IsBound(dj[l])) then dj[l]:=[]; fi;
   Add(dj[l],e);
  od;
 od;


 for i in [1..Length(dj)] do
  if not IsBound(dj[i]) then
   dj[i]:=[];
  fi;
 od;

 dj:=SCFromFacets(Union(SCIntFunc.reduceFaceLattice(dj)));
 if(dj=fail) then
  return fail;
 fi;
 
 if(SCName(complex1)<>fail and SCName(complex2)<>fail) then
  SCRename(dj,Concatenation(SCName(complex1)," deljoin ",SCName(complex2)));
 fi;
 return dj; 
end);

################################################################################
##<#GAPDoc Label="SCWedge">
## <ManSection>
## <Meth Name="SCWedge" Arg="complex1, complex2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Calculates the wedge product of the complexes supplied as arguments. Note that the vertex labelings of the complexes passed as arguments are not propagated to the new complex.
## <Example><![CDATA[
## gap> wedge:=SCWedge(SCBdSimplex(2),SCBdSimplex(2));
## gap> wedge.Facets;
## [ [ [ 1, 2 ], [ 1, 3 ] ], [ [ 2, 2 ], [ 2, 3 ] ], [ [ 1, 2 ], "a" ], 
##   [ [ 1, 3 ], "a" ], [ [ 2, 2 ], "a" ], [ [ 2, 3 ], "a" ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCWedge,
"for List and List",
[IsList,IsList],
function(complex1,complex2)
 if(IsBound(SCIntFunc.SCWedgeOld)) then
  #fallback to homology package
  return SCIntFunc.SCWedgeOld(complex1,complex2);
 fi;
 Info (InfoSimpcomp, 1, "SCWedge: the arguments should be two simplicial complexes, each of at least dimension 1. Fallback to homology package failed.");
 return fail;
end);

InstallMethod(SCWedge,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1,complex2)
 local points,complexes,names,n,wedge,scwedge;

 if SCDim(complex1) < 1 or SCDim(complex2) < 1 then
   Info (InfoSimpcomp, 1, "SCWedge: the argument should be a list of simplicial complexes, each of at least dimension 1.");
  return fail;
 fi;

 complexes:=[SCFacetsEx(complex1),SCFacetsEx(complex2)]; 
 points:=List(complexes,c->Union(c));
  
 #code taken from homology package
 wedge:=Concatenation(List (Filtered ([1 .. Length (complexes)], i -> points [i] <> []),
 i -> List (complexes [i], s -> List (s,
 function (n)
  if n = points [i] [1] then
   return 1;
  else
   return [i, n];
  fi;
 end))));

 if HasSCName(complex1) and HasSCName(complex2) then
  names:=[SCName(complex1),SCName(complex2)];
 fi;
 
 scwedge:=SCFromFacets(wedge);
 if(scwedge=fail) then
  return fail;
 fi;
 
 if HasSCName(complex1) and HasName(complex2) then
   SCRename(scwedge,Concatenation(names[1]," wedge ",names[2]));
  fi;
 return scwedge;
end);

# check which faces already exist (by dimension)
SCIntFunc.FacesExist:=
function(complex,dim)
 local faces;

 faces:=SCFaceLattice(complex);
 if faces<>fail then
  if dim+1<=Size(faces) and IsBound(faces[dim+1]) and faces[dim+1]<>[] then
   if(not IsList(faces[dim+1]) or not IsDuplicateFreeList(faces[dim+1]) or not ForAll(faces[dim+1],x->IsList(x) and IsDuplicateFree(x))) then
    Info(InfoSimpcomp,1,"SCIntFunc.FacesExist: invalid face lattice.");
    return fail;
   else
    return true;
   fi;
  else
   return false;
  fi;
 else
  return false;
 fi;
end;

#performs an operation on the face lattice of a complex
SCIntFunc.OperationOnFL:=
function(fl1,fl2,op)
 local fl,i;
 
 if(fl1=fail or fl2=fail) then
  return fail;
 fi;
 
 fl:=[];
 for i in [1..MaximumList([Length(fl1),Length(fl2)])] do
  if(IsBound(fl1[i]) and IsBound(fl2[i])) then
   fl[i]:=CallFuncList(op,[fl1[i],fl2[i]]);
  elif(IsBound(fl1[i])) then
   fl[i]:=CallFuncList(op,[fl1[i],[]]);
  elif(IsBound(fl2[i])) then
   fl[i]:=CallFuncList(op,[[],fl2[i]]);
  fi;
 od;
 return fl;
end;


################################################################################
##<#GAPDoc Label="SCDifference">
## <ManSection>
## <Meth Name="SCDifference" Arg="complex1, complex2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Forms the ``difference'' of two simplicial complexes <Arg>complex1</Arg> and <Arg>complex2</Arg> as the simplicial complex formed by the difference of the face lattices of <Arg>complex1</Arg> minus <Arg>complex2</Arg>. The two arguments are not altered. Note: for the difference process the vertex labelings of the complexes are taken into account, see also <Ref Meth="Operation Difference (SCSimplicialComplex, SCSimplicialComplex)"/>.
## <Example><![CDATA[
## gap> c:=SCBdSimplex(3);;
## gap> d:=SC([[1,2,3]]);;
## gap> disc:=SCDifference(c,d);;
## gap> disc.Facets;
## [ [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]
## gap> empty:=SCDifference(d,c);;
## gap> empty.Dim;
## -1
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCDifference,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1, complex2)

 local fl1,fl2,fl,i,s,diff;

 fl1:=SCFaceLattice(complex1);
 fl2:=SCFaceLattice(complex2);
 if(fl1=fail or fl2=fail) then
  return fail;
 fi;
 
 fl:=SCIntFunc.OperationOnFL(fl1,fl2,Difference);
 diff:=SCFromFacets(Union(SCIntFunc.reduceFaceLattice(fl)));
 if diff = fail then
  return fail;
 fi;
 
 if(SCName(complex1)<>fail and SCName(complex2)<>fail) then
  SCRename(diff,Concatenation(SCName(complex1)," \\ ",SCName(complex2)));
 fi;
 
 return diff;
 
end);


################################################################################
##<#GAPDoc Label="SCNeighborsEx">
## <ManSection>
## <Meth Name="SCNeighborsEx" Arg="complex, face"/>
## <Returns>a list of faces upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## In a simplicial complex <Arg>complex</Arg> all neighbors of the <C>k</C>-face  <Arg>face</Arg>, i. e. all <C>k</C>-faces distinct from <Arg>face</Arg> intersecting with <Arg>face</Arg> in a common <M>(k-1)</M>-face, are returned in the standard labeling.
## <Example><![CDATA[
## gap> c:=SCFromFacets(Combinations(["a","b","c"],2));
## gap> SCLabels(c);
## [ "a", "b", "c" ]
## gap> SCNeighborsEx(c,[1,2]);
## [ [ 1, 3 ], [ 2, 3 ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
InstallMethod(SCNeighborsEx,
"for SCSimplicialComplex and List",
[SCIsSimplicialComplex,IsList],
function(complex, face)
 local d,f,skel,l,neigh;
 
 if(not IsDuplicateFreeList(face)) then
  Info(InfoSimpcomp,1,"SCNeighborsEx: second argument must be a proper face, i. e. a duplicate free list.");
  return fail;
 fi;
 
 d:=SCDim(complex);
 if(d=fail) then
  return fail;
 fi;
 
 
 if(Length(face)<2 or Length(face)>d+1) then
  return [];
 fi;
 
 l:=Length(face)-1;
 skel:=SCSkelEx(complex,l);
 
 if(skel=fail) then
  return fail;
 fi;
 
 neigh:=[];
 for f in skel do
  if(face<>f and Length(Intersection(face,f))=l) then
   Add(neigh,f);
  fi;
 od;
 
 return neigh;
end);



################################################################################
##<#GAPDoc Label="SCNeighbors">
## <ManSection>
## <Meth Name="SCNeighbors" Arg="complex, face"/>
## <Returns>a list of faces upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## In a simplicial complex <Arg>complex</Arg> all neighbors of the <C>k</C>-face  <Arg>face</Arg>, i. e. all <C>k</C>-faces distinct from <Arg>face</Arg> intersecting with <Arg>face</Arg> in a common <M>(k-1)</M>-face, are returned in the original labeling.
## <Example><![CDATA[
## gap> c:=SCFromFacets(Combinations(["a","b","c"],2));
## gap> SCNeighbors(c,["a","d"]);
## [ [ "a", "b" ], [ "a", "c" ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
InstallMethod(SCNeighbors,
"for SCSimplicialComplex and List",
[SCIsSimplicialComplex,IsList],
function(complex, face)
 local d,f,skel,l,neigh;
 
 if(not IsDuplicateFreeList(face)) then
  Info(InfoSimpcomp,1,"SCNeighbors: second argument must be a proper face, i. e. a duplicate free list.");
  return fail;
 fi;
 
 d:=SCDim(complex);
 
 if(d=fail) then
  return fail;
 fi;
 
 
 if(Length(face)<2 or Length(face)>d+1) then
  return [];
 fi;
 
 l:=Length(face)-1;
 skel:=SCSkel(complex,l);
 
 if(skel=fail) then
  return fail;
 fi;
 
 neigh:=[];
 for f in skel do
  if(face<>f and Length(Intersection(face,f))=l) then
   Add(neigh,f);
  fi;
 od;
 
 return neigh;
end);



################################################################################
##<#GAPDoc Label="SCIntersection">
## <ManSection>
## <Meth Name="SCIntersection" Arg="complex1, complex2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Forms the ``intersection'' of two simplicial complexes <Arg>complex1</Arg> and <Arg>complex2</Arg> as the simplicial complex formed by the intersection of the face lattices of <Arg>complex1</Arg> and <Arg>complex2</Arg>. The two arguments are not altered. Note: for the intersection process the vertex labelings of the complexes are taken into account. See also <Ref Meth="Operation Intersection (SCSimplicialComplex, SCSimplicialComplex)"/>.
## <Example><![CDATA[
## gap> c:=SCBdSimplex(3);;        
## gap> d:=SCBdSimplex(3)+1;;      
## gap> d.Facets;
## [ [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ]
## gap> c:=SCBdSimplex(3);;  
## gap> d:=SCBdSimplex(3);;  
## gap> d:=SCMove(d,[[1,2,3],[]])+1;;
## gap> s1:=SCIntersection(c,d);;
## gap> s1.Facets;               
## [ [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
InstallMethod(SCIntersection,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1, complex2)
 local sec,fl1,fl2;
 
 fl1:=SCFaceLattice(complex1);
 fl2:=SCFaceLattice(complex2);
 if fl1 = fail or fl2 = fail then
  return fail;
 fi;
 
 sec:=SCFromFacets(Union(SCIntFunc.reduceFaceLattice(SCIntFunc.OperationOnFL(fl1,fl2,Intersection))));
 if sec = fail then
  return fail;
 fi;
 
 if(SCName(complex1)<>fail and SCName(complex2)<>fail) then
  SCRename(sec,Concatenation(SCName(complex1)," cap ",SCName(complex2)));
 fi;
 
 return sec;
end);






################################################################################
##<#GAPDoc Label="SCUnion">
## <ManSection>
## <Meth Name="SCUnion" Arg="complex1, complex2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Forms the union of two simplicial complexes <Arg>complex1</Arg> and <Arg>complex2</Arg> as the simplicial complex formed by the union of their facets sets. The two arguments are not altered. Note: for the union process the vertex labelings of the complexes are taken into account, see also <Ref Meth="Operation Union (SCSimplicialComplex, SCSimplicialComplex)" />. Facets occurring in both arguments are treated as one facet in the new complex.
## <Example><![CDATA[
## gap> c:=SCUnion(SCBdSimplex(3),SCBdSimplex(3)+3); #a wedge of two 2-spheres
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCUnion,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1,complex2)
 local facets,un,f1,f2;
 
 f1:=SCIntFunc.DeepCopy(SCFacets(complex1));
 f2:=SCIntFunc.DeepCopy(SCFacets(complex2));
 if f1 = fail or f2 = fail then
  return fail;
 fi;
 SCIntFunc.DeepSortList(f1);
 SCIntFunc.DeepSortList(f2);
 
 facets:=Union(f1,f2);
 if(fail in facets) then
  return fail;
 fi;

 un:=SCFromFacets(facets);

 if un = fail then
  Info(InfoSimpcomp,1,"SCUnion: can not unite complexes.");
  return fail;
 fi;
 
 if(SCName(complex1)<>fail and SCName(complex2)<>fail) then
  SCRename(un,Concatenation(SCName(complex1)," cup ",SCName(complex2)));
 fi;
 
 return un;
end);



################################################################################
##<#GAPDoc Label="SCIsSubcomplex">
## <ManSection>
## <Meth Name="SCIsSubcomplex" Arg="sc1,sc2"/>
## <Returns><K>true</K> or <K>false</K> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Returns <K>true</K> if the simplicial complex <Arg>sc2</Arg> is a sub-complex of simplicial complex <Arg>sc1</Arg>, <K>false</K> otherwise. If dim(<Arg>sc2</Arg>) <M>\leq</M> dim(<Arg>sc1</Arg>) the facets of <Arg>sc2</Arg> are compared with the dim(<Arg>sc2</Arg>)-skeleton of <Arg>sc1</Arg>. Only works for pure simplicial complexes. Note: for the intersection process the vertex labelings of the complexes are taken into account. 
## <Example><![CDATA[
## gap> SCLib.SearchByAttribute("F[1]=10"){[1..10]};
## [ [ 17, "T^2 (VT)" ], [ 18, "K^2 (VT)" ], 
##   [ 19, "S^3 (VT)" ], [ 20, "(T^2)#2" ], [ 21, "S^3 (VT)" ],
##   [ 22, "S^3 (VT)" ], [ 23, "S^2xS^1 (VT)" ], 
##   [ 24, "(T^2)#3" ], [ 25, "(P^2)#7 (VT)" ], 
##   [ 26, "S^2~S^1 (VT)" ] ]
## gap> k:=SCLib.Load(last[1][1]);;
## gap> c:=SCBdSimplex(9);;
## gap> k.F;
## [10, 30, 20]
## gap> c.F;
## [10, 45, 120, 210, 252, 210, 120, 45, 10]
## gap> SCIsSubcomplex(c,k);
## true
## gap> SCIsSubcomplex(k,c);
## false
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCIsSubcomplex,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(sc1,sc2)
 local d,facets,skel;
 
 d:=[SCDim(sc1),SCDim(sc2)];
 facets:=[SCFacets(sc1),SCFacets(sc2)];
 
 if(fail in d or fail in facets) then
  return fail;
 fi;
 
 if(d[2]>d[1]) then
  return false;
 elif(d[2]=d[1]) then
  return IsSubset(facets[1],facets[2]);
 else
  #here d[2]<d[1]
  skel:=SCSkel(sc1,d[2]);
  if(skel=fail) then
   return fail;
  fi;
  return IsSubset(skel,facets[2]); 
 fi;
end);

################################################################################
##<#GAPDoc Label="SCAlexanderDual">
## <ManSection>
## <Meth Name="SCAlexanderDual" Arg="complex"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## The Alexander dual of a simplicial complex <Arg>complex</Arg> with set of vertices <M>V</M> is the simplicial complex where any subset of <M>V</M> spans a face if and only if its complement in <M>V</M> is a non-face of <Arg>complex</Arg>.
## <Example><![CDATA[
## # a square
## gap> c:=SC([[1,2],[2,3],[3,4],[4,1]]);;
## gap> dual:=SCAlexanderDual(c);;
## gap> dual.F;
## [4, 2]
## gap> dual.IsConnected;
## false
## gap> dual.Facets;
## [[1, 3], [2, 4]]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCAlexanderDual,
"for List",
[IsList],
function(complex)
 if(IsBound(SCIntFunc.SCAlexanderDualOld)) then
  return SCIntFunc.SCAlexanderDualOld(complex);
 fi;

 Info(InfoSimpcomp,1,"SCAlexanderDual: first argument must be of type SCSimplicialComplex. Fallback to homology package failed.");
 return fail;
end);

InstallMethod(SCAlexanderDual,
"for SCSimplicialComplex",
[SCIsSimplicialComplex],
#code taken from homology package
function(complex)
 local facets,verts,dual,dim,i,missing;

 facets:=SCFacets(complex);
 if facets=fail then
  return fail;
 fi;
 
 dim:=SCDim(complex);
 if dim=fail then
  return fail;
 fi;
 
 if(dim=-1) then
  return SCEmpty();
 fi;
 
 verts:=SCVertices(complex);
 dual:=[];
 missing:=SCIntFunc.MissingFacesComplex(complex,true);
 if missing=fail then
  return fail;
 fi;
 for i in [1..dim] do
   dual[i+1]:=List(missing[i+1],x->Difference(verts,x));
 od;
  
 dual:=SCFromFacets(Union(dual));
 
 if(SCName(complex)<>fail) then
  SCRename(dual,Concatenation("Alexander dual of ",SCName(complex)));
 fi;
 
 return dual; 
end);

SCIntFunc.SCVertexIdentificationEx:=
function(facets,verts,v1,v2)

 local maptable,i,facetsnew,f,fnew,v;

 maptable:=ShallowCopy(verts);
 
 if(not IsSubset(verts,v1) or not IsSubset(verts,v2) or Length(v1)<>Length(v2)) then
  Info(InfoSimpcomp,1,"SCVertexIdentificationEx: must provide valid vertex subsets of same cardinality.");
  return fail;
 fi;
 
 
 for i in [1..Length(v2)] do
  maptable[Position(maptable,v2[i])]:=v1[i];
 od;
 
 facetsnew:=[];
 
 for f in facets do
  fnew:=[];
  for v in f do
   AddSet(fnew,maptable[Position(verts,v)]);
  od;
  
  Add(facetsnew,fnew);
 od;
 
 return Set(facetsnew);
end;



################################################################################
##<#GAPDoc Label="SCHandleAddition">
## <ManSection>
## <Meth Name="SCHandleAddition" Arg="complex,f1,f2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C>, <K>fail</K> otherwise.</Returns>
## <Description>
## Returns a simplicial complex obtained by identifying the vertices of facet <Arg>f1</Arg> with the ones from facet <Arg>f2</Arg> in <Arg>complex</Arg>. A combinatorial handle addition is possible, whenever we have d<M>(v,w) \geq 3</M> for any two vertices <M>v \in </M><Arg>f1</Arg> and <M>w \in </M><Arg>f2</Arg>, where d<M>(\cdot,\cdot)</M> is the length of the shortest path from <M>v</M> to <M>w</M>. This condition is not checked by this algorithm. See <Cite Key="Bagchi08OnWalkupKd"/> for further information.
## <Example><![CDATA[
## gap> c:=SC([[1,2,4],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);;
## gap> c:=SCUnion(c,SCUnion(SCCopy(c)+3,SCCopy(c)+6));;
## gap> c:=SCUnion(c,SC([[1,2,3],[10,11,12]]));;
## gap> c.Facets;
## [[1, 2, 3], [1, 2, 4], [1, 3, 6], [1, 4, 6], [2, 3, 5],
##   [2, 4, 5], [3, 5, 6], [4, 5, 7], [4, 6, 9], [4, 7, 9],
##   [5, 6, 8], [5, 7, 8], [6, 8, 9], [7, 8, 10], [7, 9, 12],
##   [7, 10, 12], [8, 9, 11], [8, 10, 11], [9, 11, 12], [10, 11, 12]]
## gap> c.Homology;
## [[0, []], [0, []], [1, []]]
## gap> torus:=SCHandleAddition(c,[1,2,3],[10,11,12]);;
## gap> torus.Homology;
## [[0, []], [2, []], [1, []]]
## gap> ism:=SCIsManifold(torus);;
## gap> ism;
## true
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCHandleAddition,
"for SCSimplicialComplex and List and List",
[SCIsSimplicialComplex,IsList,IsList],
function(complex,f1,f2)

 local facets,hb;

 facets:=SCFacets(complex);
 if facets=fail or facets=[] then
  return fail;
 fi;
 
 if(not Set(f1) in facets or not Set(f2) in facets) then
  Info(InfoSimpcomp,1,"SCHandleAddition: invalid facets specified.");
  return fail;
 fi;
  
 facets:=Difference(facets,[Set(f1),Set(f2)]);
 facets:=SCIntFunc.SCVertexIdentificationEx(facets,SCVertices(complex),f1,f2);
 
 if(facets=fail) then
  return fail;
 fi;
 
 hb:=SCFromFacets(facets);
 if(SCName(complex)<>fail) then
  SCRename(hb,Concatenation(SCName(complex)," handle (",String(f1),"=",String(f2),")"));
 fi;
 
 return hb;
end);


################################################################################
##<#GAPDoc Label="SCVertexIdentification">
## <ManSection>
## <Meth Name="SCVertexIdentification" Arg="complex,v1,v2"/>
## <Returns>simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Identifies vertex <Arg>v1</Arg> with vertex <Arg>v2</Arg> in a simplicial complex <Arg>complex</Arg> and returns the result as a new object. A vertex identification of <Arg>v1</Arg> and <Arg>v2</Arg> is possible whenever d(<Arg>v1</Arg>,<Arg>v2</Arg>) <M>\geq 3</M>. This is not checked by this algorithm. 
## <Example><![CDATA[
## gap> c:=SC([[1,2],[2,3],[3,4]]);;
## gap> circle:=SCVertexIdentification(c,[1],[4]);;
## gap> circle.Facets;
## [[1, 2], [1, 3], [2, 3]]
## gap> circle.Homology;
## [[0, []], [1, []]]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCVertexIdentification,
"for SCSimplicialComplex and Object and Object",
[SCIsSimplicialComplex,IsObject,IsObject],
function(complex,v1,v2)

 local facets,id;

 facets:=SCFacets(complex);
 if facets=fail or facets=[] then
  return fail;
 fi;
 
 facets:=SCIntFunc.SCVertexIdentificationEx(facets,SCVertices(complex),v1,v2);
 
 if(facets=fail) then
  return fail;
 fi;
 
 id:=SCFromFacets(facets);
 if(SCName(complex)<>fail) then
  SCRename(id,Concatenation(SCName(complex)," vertex identified (",String(v1),"=",String(v2),")"));
 fi;
 
 return id;
end);




################################################################################
##<#GAPDoc Label="SCLinks">
## <ManSection>
## <Meth Name="SCLinks" Arg="complex,k"/>
## <Returns> a list of simplicial complexes of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Computes the link of all <Arg>k</Arg>-faces of the polyhedral complex <Arg>complex</Arg> and returns them as a list of simplicial complexes. Internally calls <Ref Meth="SCLink"/> for every <Arg>k</Arg>-face of <Arg>complex</Arg>.
## <Example><![CDATA[
## gap> c:=SCBdSimplex(4);;
## # all vertex links -> 2 spheres
## gap> SCLinks(c,0);
## # all edge links -> circles
## gap> SCLinks(c,1);
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCLinks,
"for SCPolyhedralComplex and Int",
[SCIsPolyhedralComplex,IsInt],
function(complex, k)

 local i, j, links, facets, vertices, max, tmp, labels, simplices;

 if(SCDim(complex)<k or k<0) then
  Info(InfoSimpcomp,1,"SCLinks: second argument must be >=0 and less or equal to dimension of complex.");
  return fail;
 fi;

 simplices:=SCSkel(complex,k);
 if simplices=fail then
  Info(InfoSimpcomp,1,"SCLinks: complex lacks ",k,"-faces.");
  return fail;
 fi;

 links:=[];
 for i in [1..Size(simplices)] do
  links[i]:=SCLink(complex,simplices[i]);
 od;

 return links;
end);


################################################################################
##<#GAPDoc Label="SCStars">
## <ManSection>
## <Meth Name="SCStars" Arg="complex,k"/>
## <Returns> a list of simplicial complexes of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Computes the star of all <Arg>k</Arg>-faces of the polyhedral complex <Arg>complex</Arg> and returns them as a list of simplicial complexes. Internally calls <Ref Meth="SCStar"/> for every <Arg>k</Arg>-face of <Arg>complex</Arg>.
## <Example><![CDATA[
## gap> SCLib.SearchByName("T^2"){[1..6]};
## [ [ 4, "T^2 (VT)" ], [ 5, "T^2 (VT)" ], [ 9, "T^2 (VT)" ], 
##   [ 10, "T^2 (VT)" ], [ 17, "T^2 (VT)" ], [ 20, "(T^2)#2" ] ]
## gap> torus:=SCLib.Load(last[1][1]);; # the minimal 7-vertex torus
## gap> SCStars(torus,0); # 7 2-discs as vertex stars
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCStars,
"for SCPolyhedralComplex and Int",
[SCIsPolyhedralComplex,IsInt],
function(complex, k)

 local i, j, stars, faces, max, labels;

 if(SCDim(complex)<k or k<0) then
  Info(InfoSimpcomp,1,"SCLinks: second argument must be >=0 and less or equal to dimension of complex.");
  return fail;
 fi;

 faces:=SCFaces(complex,k);
 if faces=fail then
  Info(InfoSimpcomp,1,"SCStars: complex lacks ",k,"-faces.");
  return fail;
 fi;
 
 stars:=[];
 for i in [1..Size(faces)] do
  stars[i]:=SCStar(complex,faces[i]);
 od;
 
 return stars;
end);


################################################################################
##<#GAPDoc Label="SCLink">
## <ManSection>
## <Meth Name="SCLink" Arg="complex,face"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Computes the link of <Arg>face</Arg> (a face given as a list of vertices or a scalar interpreted as vertex) in a polyhedral complex <Arg>complex</Arg>, i. e. all facets containing <Arg>face</Arg>, reduced by <Arg>face</Arg>. if <Arg>complex</Arg> is pure, the resulting complex is of dimension dim(<Arg>complex</Arg>) - dim(<Arg>face</Arg>) <M>-1</M>. If <Arg>face</Arg> is not a face of <Arg>complex</Arg> the empty complex is returned.
## <Example><![CDATA[
## gap> SCLib.SearchByName("RP^2");     
## [ [ 3, "RP^2 (VT)" ], [ 262, "RP^2xS^1" ] ]
## gap> rp2:=SCLib.Load(last[1][1]);;
## gap> SCVertices(rp2);
## [1, 2, 3, 4, 5, 6]
## gap> SCLink(rp2,[1]);
## gap> last.Facets;
## [[2, 3], [2, 6], [3, 5], [4, 5], [4, 6]]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCLink,
"for List and Object",
[IsList,IsObject],
function(complex,face)

 local tmp;

 if(IsBound(SCIntFunc.SCLinkOld)) then
  #fallback to homology package
  tmp:=face;
  if(not IsList(tmp)) then
   tmp:=[tmp];
  fi;
  return SCIntFunc.SCLinkOld(complex,tmp);
 fi;
 
 Info(InfoSimpcomp,1,"SCLink: first argument must be of type SCPolyhedralComplex.");
 return fail;
end);

InstallMethod(SCLink,
"for SCPolyhedralComplex and Object",
[SCIsPolyhedralComplex,IsObject],
function(complex,face)
 return SCLink(complex,[face]);
end);

InstallMethod(SCLink,
"for SCPolyhedralComplex and List",
[SCIsPolyhedralComplex,IsList],
function(complex,face)

 local i, j, tmp, flag, link, ctr, facets, labels, lsubset;

 if SCIsEmpty(complex) then
  return SCEmpty();
 fi;
 
 labels:=SCLabels(complex);
  
 if(labels=fail) then
  Info(InfoSimpcomp,1,"SCLink: complex lacks vertex labels.");
  return fail;
 fi;

 if(not IsList(face)) then
  lsubset:=[face];
 else
  lsubset:=face;
 fi;
 
 if not IsSubset(labels,lsubset) then
  Info(InfoSimpcomp,1,"SCLink: face must be a face / non-face of complex.");
  return SCEmpty();
 fi;

 lsubset:=List(lsubset,x->Position(labels,x));
 
 facets:=SCFacetsEx(complex);
 if facets=fail then
  return fail;
 fi;

 link:=[];
 ctr:=0;
 for i in facets do
  if IsSubset(i,lsubset) then
   ctr:=ctr+1;
   tmp:=Difference(i,lsubset);
   flag:=0;
   link[ctr]:=tmp;
  fi;
 od;
 if link=[] then
  link:=SCEmpty();
 else
  link:=SCFromFacets(SCIntFunc.RelabelSimplexList(link,labels));
 fi;
 
 if(SCName(complex)<>fail) then
  SCRename(link,Concatenation("lk(",String(face),") in ",SCName(complex)));
 else
  SCRename(link,Concatenation("lk(",String(face),")"));
 fi;
 
 return link;
end);


################################################################################
##<#GAPDoc Label="SCStar">
## <ManSection>
## <Meth Name="SCStar" Arg="complex,face"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise .</Returns>
## <Description>
## Computes the star of <Arg>face</Arg> (a face given as a list of vertices or a scalar interpreted as vertex) in a polyhedral complex <Arg>complex</Arg>, i. e. the set of facets of <Arg>complex</Arg> that contain <Arg>face</Arg>.
## <Example><![CDATA[
## gap> SCLib.SearchByName("RP^2");     
## [ [ 3, "RP^2 (VT)" ], [ 262, "RP^2xS^1" ] ]
## gap> rp2:=SCLib.Load(last[1][1]);;
## gap> SCVertices(rp2);
## [1, 2, 3, 4, 5, 6]
## gap> SCStar(rp2,1);
## gap> last.Facets;
## [ [1, 2, 3], [1, 2, 6], [1, 3, 5], [1, 4, 5], [1, 4, 6] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCStar,
"for List and Object",
[IsList,IsObject],
function(complex,face)

 local tmp;

 if(IsBound(SCIntFunc.SCStarOld)) then
  #fallback to homology package
  tmp:=face;
  if(not IsList(tmp)) then
   tmp:=[tmp];
  fi;
  return SCIntFunc.SCStarOld(complex,tmp);
 fi;

 Info(InfoSimpcomp,1,"SCStar: first argument must be of type SCPolyhedralComplexx. Fallback to homology package failed");
 return fail;
end);

InstallMethod(SCStar,
"for SCPolyhedralComplex and Object",
[SCIsPolyhedralComplex,IsObject],
function(complex,face)
 return SCStar(complex,[face]);
end);

InstallMethod(SCStar,
"for SCPolyhedralComplex and Object",
[SCIsPolyhedralComplex,IsList],
function(complex,face)

 local tmp, elements, facets, labels, lface;
 
 labels:=SCVertices(complex);
 if(labels=fail) then
  Info(InfoSimpcomp,1,"SCStar: complex lacks vertex labels.");
  return fail;
 fi;
 
 if not IsSubset(labels,face) then
  Info(InfoSimpcomp,1,"SCStar: face must be a face / non-face of complex.");
  return SCEmpty();
 fi;
 
 lface:=List(face,x->Position(labels,x));
 facets:=SCFacetsEx(complex);
 if facets=fail then
  return fail;
 fi;

 tmp:=[];
 for elements in facets do
   if IsSubset(elements,lface) then
    AddSet(tmp,elements);
   fi;
 od;

 if tmp=[] then
  tmp:=SCEmpty();
 else
  tmp:=SCFromFacets(SCIntFunc.RelabelSimplexList(tmp,labels));
 fi;
 
 if(SCName(complex)<>fail) then
  SCRename(tmp,Concatenation("star(",String(face),") in ",SCName(complex)));
 else
  SCRename(tmp,Concatenation("star(",String(face),")"));
 fi;
 
 return tmp;
end);


################################################################################
##<#GAPDoc Label="SCAntiStar">
## <ManSection>
## <Meth Name="SCAntiStar" Arg="complex,face"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise .</Returns>
## <Description>
## Computes the anti star of <Arg>face</Arg> (a face given as a list of vertices or a scalar interpreted as vertex) in <Arg>complex</Arg>, i. e. the complement of <Arg>face</Arg> in <Arg>complex</Arg>.
## <Example><![CDATA[
## gap> SCLib.SearchByName("RP^2");     
## [ [ 3, "RP^2 (VT)" ], [ 262, "RP^2xS^1" ] ]
## gap> rp2:=SCLib.Load(last[1][1]);;
## gap> SCVertices(rp2);
## [1, 2, 3, 4, 5, 6]
## gap> SCAntiStar(rp2,1);
## gap> last.Facets;
## [ [ 2, 3, 4 ], [ 2, 4, 5 ], [ 2, 5, 6 ], [ 3, 4, 6 ], [ 3, 5, 6 ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCAntiStar,
"for SCPolyhedralComplex and List",
[SCIsPolyhedralComplex,IsObject],
function(complex,face)
 return SCAntiStar(complex,[face]);
end);

InstallMethod(SCAntiStar,
"for SCPolyhedralComplex and List",
[SCIsPolyhedralComplex,IsList],
function(complex,face)

 local tmp, elements, facets, labels, lface;
 
 labels:=SCVertices(complex);
 if(labels=fail) then
  Info(InfoSimpcomp,1,"SCAntiStar: complex lacks vertex labels.");
  return fail;
 fi;
 
 if not IsSubset(labels,face) then
  Info(InfoSimpcomp,1,"SCAntiStar: face must be a face of complex.");
  return SCEmpty();
 fi;
 
 lface:=List(face,x->Position(labels,x));
 
 facets:=SCFacetsEx(complex);
 if facets=fail then
  return fail;
 fi;

 tmp:=[];
 for elements in facets do
   if Intersection(elements,lface)=[] then
    AddSet(tmp,elements);
   fi;
 od;

 if tmp=[] then
  tmp:=SCEmpty();
 else
  tmp:=SCFromFacets(SCIntFunc.RelabelSimplexList(tmp,labels));
 fi;
 
 if(SCName(complex)<>fail) then
  SCRename(tmp,Concatenation("ast(",String(face),") in ",SCName(complex)));
 else
  SCRename(tmp,Concatenation("ast(",String(face),")"));
 fi;
 
 return tmp;
end);



################################################################################
##<#GAPDoc Label="SCFillSphere">
## <ManSection>
## <Func Name="SCFillSphere" Arg="complex[, vertex]"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise .</Returns>
## <Description>
## Fills the given simplicial sphere <Arg>complex</Arg> by forming the suspension of the anti star of <Arg>vertex</Arg> over <Arg>vertex</Arg>. This is a triangulated <M>(d+1)</M>-ball with the boundary <Arg>complex</Arg>, see <Cite Key="Bagchi08LBTNormPseudoMnf" />. If the optional argument <Arg>vertex</Arg> is not supplied, the first vertex of <Arg>complex</Arg> is chosen.<P/>
## Note that it is not checked whether <Arg>complex</Arg> really is a simplicial sphere -- this has to be done by the user!
## <Example><![CDATA[
## gap> SCLib.SearchByName("S^4");
## gap> s:=SCLib.Load(last[1][1]);;
## gap> filled:=SCFillSphere(s);
## gap> SCHomology(filled);
## gap> SCCollapseGreedy(filled);
## gap> bd:=SCBoundary(filled);;
## gap> bd=s;
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallGlobalFunction(SCFillSphere,
function(arg)

 local complex, vertex, tmp, elements, facets, labels, lvertex;

 if(Length(arg)<1 or Length(arg)>2) then
  Info(InfoSimpcomp,1,"SCFillSphere: first argument must be of type SCSimplicialComplex, optional second argument a vertex of that complex.");
  return fail;
 fi;
 
 complex:=arg[1];
 
 if(not SCIsSimplicialComplex(complex) and not SCIsNormalSurface(complex)) then
  Info(InfoSimpcomp,1,"SCFillSphere: first argument must be of type SCSimplicialComplex.");
  return fail;
 fi;
 
 labels:=SCVertices(complex);
 if(labels=fail or Length(labels)<2) then
  Info(InfoSimpcomp,1,"SCFillSphere: complex lacks vertex labels or is too small (<2 vertices).");
  return fail;
 fi;
 
 if(Length(arg)=2) then
  vertex:=arg[2];
 else
  vertex:=[labels[1]];
 fi;

 if(not IsList(vertex)) then
  lvertex:=[vertex];
 else
  lvertex:=vertex;
 fi;
 
 if not IsSubset(labels,lvertex) then
  Info(InfoSimpcomp,1,"SCFillSphere: vertex must be a vertex of the complex.");
  return SCEmpty();
 fi;
 
 lvertex:=List(lvertex,x->Position(labels,x));
 
 facets:=SCFacetsEx(complex);
 if facets=fail then
  return fail;
 fi;

 #form ast(lvertex)*lvertex 
 tmp:=[];
 for elements in facets do
   if Intersection(elements,lvertex)=[] then
    AddSet(tmp,Union(elements,lvertex));
   fi;
 od;

 if tmp=[] then
  tmp:=SCEmpty();
 else
  tmp:=SCFromFacets(SCIntFunc.RelabelSimplexList(tmp,labels));
 fi;
 
 if(SCName(complex)<>fail) then
  SCRename(tmp,Concatenation("FilledSphere(",SCName(complex),") at vertex ", String(lvertex)));
 else
  SCRename(tmp,Concatenation("FilledSphere at vertex ",String(lvertex)));
 fi;
 
 return tmp;
end);


#reduce given face lattice
SCIntFunc.reduceFaceLattice:=function(faces)
 local i,reduced,maxf;
 
 if(faces=[]) then
  return [];
 fi;
 
 reduced:=[];
 reduced[Length(faces)]:=ShallowCopy(faces[Length(faces)]);
 
 for i in Reversed([1..Length(faces)-1]) do
  reduced[i]:=[];
  maxf:=Union(List(faces[i+1],x->Combinations(x,i)));
  reduced[i]:=ShallowCopy(Difference(faces[i],maxf));
 od;

 return reduced;
end;



################################################################################
##<#GAPDoc Label="SCSpan">
## <ManSection>
## <Meth Name="SCSpan" Arg="complex,subset"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Computes the reduced face lattice of all faces of a simplicial complex <Arg>complex</Arg> that are spanned by <Arg>subset</Arg>, a subset of the set of vertices of <Arg>complex</Arg>. 
## <Example><![CDATA[
## gap> c:=SCBdCrossPolytope(4);;
## gap> SCVertices(c);
## [1, 2, 3, 4, 5, 6, 7, 8]
## gap> span:=SCSpan(c,[1,2,3,4]);
## gap> span.Facets;
## [[1, 3], [1, 4], [2, 3], [2, 4]]
## ]]></Example>
## <Example><![CDATA[
## gap> c:=SC([[1,2],[1,4,5],[2,3,4]]);;
## gap> span:=SCSpan(c,[2,3,5]);
## gap> SCFacets(span);
## [[2, 3], [5]]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCSpan,
"for SCSimplicialComplex and List",
[SCIsSimplicialComplex,IsList],
function(complex,subset)

 local faces,span,k,labels;

 labels:=SCVertices(complex);
 if(labels=fail) then
  Info(InfoSimpcomp,1,"SCSpan: complex lacks vertex labels.");
  return fail;
 fi; 
 
 faces:=SCFaceLattice(complex);
 if faces=fail then
  return fail;
 fi;

 span:=SCFromFacets(
  Union(
   SCIntFunc.reduceFaceLattice(
    List([1..Length(faces)],k->SCIntFunc.DeepCopy(
     Filtered(faces[k],x->IsSubset(subset,x))
    ))
   )
  ));
 
 if(SCName(complex)<>fail) then
  SCRename(span,Concatenation("span(",String(subset),") in ",SCName(complex)));
 else
  SCRename(span,Concatenation("span(",String(subset),")"));
 fi;
 
 return span; 
end);


################################################################################
##<#GAPDoc Label="SCIsomorphismEx">
## <ManSection>
## <Meth Name="SCIsomorphismEx" Arg="complex1,complex2"/>
## <Returns> a list of pairs of vertex labels or <K>false</K> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Returns an isomorphism of simplicial complex <Arg>complex1</Arg> to simplicial complex <Arg>complex2</Arg> in the standard labeling if they are combinatorially isomorphic, <K>false</K> otherwise. If the <M>f</M>-vector and the Altshuler-Steinberg determinant of <Arg>complex1</Arg> and <Arg>complex2</Arg> are equal, the internal function <C>SCIntFunc.SCComputeIsomorphismsEx(complex1,complex2,true)</C> is called.
## <Example><![CDATA[
## gap> c1:=SC([[11,12,13],[11,12,14],[11,13,14],[12,13,14]]);;
## gap> c2:=SCBdSimplex(3);;
## gap> SCIsomorphism(c1,c2);
## [ [ 11, 1 ], [ 12, 2 ], [ 13, 3 ], [ 14, 4 ] ]
## gap> SCIsomorphismEx(c1,c2);
## [ [ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ] ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCIsomorphismEx,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1, complex2)

 local FA,FB,DA,DB,iso,i,facets1,facets2,sc1,sc2;

 sc1:=SCIsStronglyConnected(complex1);
 sc2:=SCIsStronglyConnected(complex2);
 if sc1 = fail or sc2 = fail then
  return fail;
 fi;
 
 if not sc1 or not sc2 then
  Info(InfoSimpcomp,1,"SCIsomoprhismEx: complexes must be strongly connected.");
  return fail;
 fi;
 
 #f vector test
 FA:=SCFVector(complex1);
 FB:=SCFVector(complex2);

 if(FA=fail or FB=fail) then
  Info(InfoSimpcomp,1,"SCIsomorphismEx: can't compute f-vector.");
  return fail;
 fi;

 if FA = [] then
  Info(InfoSimpcomp,1,"SCIsomoprhismEx: complex is empty.");
  return [];
 fi;
 
 if Size(FA) = 1 and FA[1] = FB[1] then
  iso:=[];
  facets1:=SCLabels(complex1);
  facets2:=SCLabels(complex2);
  if facets1 = fail or facets2 = fail then
   return fail;
  fi;
  
  for i in [1..FA[1]] do 
   Add(iso,[facets1[i],facets2[i]]);
  od;
  return [iso];
 fi;
 
 if(not FA=FB) then
  return false;
 fi;

 #as-det test
 DA:=SCAltshulerSteinberg(complex1);
 DB:=SCAltshulerSteinberg(complex2);

 if(DA=fail or DB=fail) then
  Info(InfoSimpcomp,1,"SCIsomorphismEx: can't compute AS-determinant.");
  return fail;
 fi;

 if(not DA=DB) then
  return false;
 fi; 
 
 #equality check
 facets1:=SCFacetsEx(complex1);
 facets2:=SCFacetsEx(complex2);
 if facets1 = fail or facets2 = fail then
  return fail;
 fi;
 
 if(facets1=facets2) then
  iso:=[];
  
  for i in [1..FA[1]] do
   Add(iso,[i,i]);
  od;
  
  return [iso];
 fi;
 
 if(not SCIsPseudoManifold(complex1) or not SCIsPseudoManifold(complex2)) then
  Info(InfoSimpcomp,1,"SCIsomorphismEx: both arguments must have the weak pseudomanifold property.");
  return fail;
 fi;

 iso:=SCIntFunc.SCComputeIsomorphismsEx(complex1,complex2,true);
 
 if iso=[] then
  return false;
 else
  return iso;
 fi;
 
end);



################################################################################
##<#GAPDoc Label="SCIsomorphism">
## <ManSection>
## <Meth Name="SCIsomorphism" Arg="complex1,complex2"/>
## <Returns> a list of pairs of vertex labels or <K>false</K> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Returns an isomorphism of simplicial complex <Arg>complex1</Arg> to simplicial complex <Arg>complex2</Arg> in the standard labeling if they are combinatorially isomorphic, <K>false</K> otherwise. Internally calls <Ref Meth="SCIsomorphismEx"/>.
## <Example><![CDATA[
## gap> c1:=SC([[11,12,13],[11,12,14],[11,13,14],[12,13,14]]);;
## gap> c2:=SCBdSimplex(3);;
## gap> SCIsomorphism(c1,c2);
## [ [ 11, 1 ], [ 12, 2 ], [ 13, 3 ], [ 14, 4 ] ]
## gap> SCIsomorphismEx(c1,c2);
## [ [ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ] ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCIsomorphism,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1, complex2)

 local isos,empty1,empty2,sc1,sc2;
 
 empty1:=SCIsEmpty(complex1);
 empty2:=SCIsEmpty(complex2);
 if empty1 = fail or empty2 = fail then
  return fail;
 fi;
 
 if empty1 or empty2 then
  Info(InfoSimpcomp,1,"SCIsomoprhism: complex is empty.");
  return [];
 fi;
 
 sc1:=SCIsStronglyConnected(complex1);
 sc2:=SCIsStronglyConnected(complex2);
 if sc1 = fail or sc2 = fail then
  return fail;
 fi;
 
 if not sc1 or not sc2 then
  Info(InfoSimpcomp,1,"SCIsomoprhism: complexes must be strongly connected.");
  return fail;
 fi;
 
 isos:=SCIsomorphismEx(complex1,complex2);
 
 if(isos=fail) then
  return fail;
 elif(isos=false or isos=[]) then
  return [];
 else
  isos:=List(isos[1],x->[SCIntFunc.RelabelSimplexList([[x[1]]],SCVertices(complex1))[1][1],SCIntFunc.RelabelSimplexList([[x[2]]],SCVertices(complex2))[1][1]]);
  return isos;
 fi;
end);


################################################################################
##<#GAPDoc Label="SCIsIsomorphic">
## <ManSection>
## <Meth Name="SCIsIsomorphic" Arg="complex1,complex2"/>
## <Returns><K>true</K> or <K>false</K> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## The function returns <K>true</K>, if the simplicial complexes <Arg>complex1</Arg> and <Arg>complex2</Arg> are combinatorially isomorphic, <K>false</K> if not.
## <Example><![CDATA[
## gap> c1:=SC([[11,12,13],[11,12,14],[11,13,14],[12,13,14]]);;
## gap> c2:=SCBdSimplex(3);;
## gap> SCIsIsomorphic(c1,c2);
## true
## gap> c3:=SCBdCrossPolytope(3);;
## gap> SCIsIsomorphic(c1,c3);
## false
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCIsIsomorphic,
"for SCSimplicialComplex and SCSimplicialComplex",
[SCIsSimplicialComplex,SCIsSimplicialComplex],
function(complex1, complex2)

 local isomorphism,sc1,sc2;
 
 if SCIsEmpty(complex1) and SCIsEmpty(complex2) then
  return true;
 elif SCIsEmpty(complex1) or SCIsEmpty(complex2) then
  return false;
 fi;

 if HasSCExportIsoSig(complex1) and HasSCExportIsoSig(complex2) then
  return SCExportIsoSig(complex1) = SCExportIsoSig(complex2); 
 fi;
 
 sc1:=SCIsStronglyConnected(complex1);
 sc2:=SCIsStronglyConnected(complex2);
 if sc1 = fail or sc2 = fail then
  return fail;
 fi;
 
 if not sc1 or not sc2 then
  Info(InfoSimpcomp,1,"SCIsIsomoprhic: complexes must be strongly connected.");
  return fail;
 fi;
 
 isomorphism:=SCIsomorphismEx(complex1,complex2);
 
 if(isomorphism=fail) then
  return fail;
 else
  if isomorphism=false or isomorphism=[] then
   return false;
  else
   return true;
  fi;
 fi;
end);


################################################################################
##<#GAPDoc Label="SCCone">
## <ManSection>
## <Func Name="SCCone" Arg="complex, apex"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## If the second argument is passed every facet of the simplicial complex <Arg>complex</Arg> is united with <Arg>apex</Arg>. If not, an arbitrary vertex label <M>v</M> is used (which is not a vertex of <Arg>complex</Arg>). In the first case the vertex labeling remains unchanged. In the second case the function returns the new complex in the standard vertex labeling from <M>1</M> to <M>n+1</M> and the apex of the cone is <M>n+1</M>.<P/>
## If called with a facet list instead of a <C>SCSimplicialComplex</C> object and <Arg>apex</Arg> is not specified, internally falls back to the homology package <Cite Key="Dumas04Homology" />, if available. 
## <Example><![CDATA[
## gap> SCLib.SearchByName("RP^3");
## [ [ 45, "RP^3" ], [ 114, "RP^3=L(2,1) (VT)" ], 
##   [ 237, "(S^2xS^1)#RP^3" ], [ 238, "(S^2~S^1)#RP^3" ], 
##   [ 263, "(S^2xS^1)#2#RP^3" ], [ 264, "(S^2~S^1)#2#RP^3" ], 
##   [ 366, "RP^3#RP^3" ], [ 382, "RP^3=L(2,1) (VT)" ], 
##   [ 399, "(S^2~S^1)#3#RP^3" ], [ 402, "(S^2xS^1)#3#RP^3" ], 
##   [ 417, "RP^3=L(2,1) (VT)" ], [ 502, "(S^2~S^1)#4#RP^3" ], 
##   [ 503, "(S^2xS^1)#4#RP^3" ], [ 531, "(S^2xS^1)#5#RP^3" ], 
##   [ 532, "(S^2~S^1)#5#RP^3" ] ]
## gap> rp3:=SCLib.Load(last[1][1]);;
## gap> rp3.F;
## [11, 51, 80, 40]
## gap> cone:=SCCone(rp3);;
## gap> cone.F;
## [12, 62, 131, 120, 40]
## ]]></Example>
## <Example><![CDATA[
## gap> s:=SCBdSimplex(4)+12;;
## gap> s.Facets;             
## [ [ 13, 14, 15, 16 ], [ 13, 14, 15, 17 ], [ 13, 14, 16, 17 ], 
##   [ 13, 15, 16, 17 ], [ 14, 15, 16, 17 ] ]
## gap> cc:=SCCone(s,13);;    
## #I  SCCone: second argument must not be a vertex label of first argument.
## gap> cc:=SCCone(s,12);;
## gap> cc.Facets;
## [ [ 12, 13, 14, 15, 16 ], [ 12, 13, 14, 15, 17 ], [ 12, 13, 14, 16, 17 ], 
##   [ 12, 13, 15, 16, 17 ], [ 12, 14, 15, 16, 17 ] ]
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallGlobalFunction(SCCone,
function(arg)
 local maxv,facets,verts,cone,f,cc,complex,apex,labels;

 if Size(arg) = 1 then
  complex:=arg[1];
 elif Size(arg) = 2 then
  complex:=arg[1];
  apex:=arg[2];
 else
  Info(InfoSimpcomp,1,"SCCone: number of arguments must be one or two.");
  return fail;
 fi;
 
 if(not SCIsSimplicialComplex(complex)) then
  #fallback to homology package
  if(IsBound(SCIntFunc.SCConeOld)) then
   return SCIntFunc.SCConeOld(complex);
  fi;
  
  Info(InfoSimpcomp,1,"SCCone: first argument must be of type SCSimplicialComplex.");
  return fail;
 fi;
 
 labels:=SCVertices(complex);
 if labels = fail then
  return fail;
 fi;
 if IsBound(apex) and apex in labels then
  Info(InfoSimpcomp,1,"SCCone: second argument must not be a vertex label of first argument.");
  return fail;
 fi;
 
 if SCIsEmpty(complex) then
  if IsBound(apex) then
   cc:=SC([[apex]]);
  else
   cc:=SC([[1]]);
  fi;  
  SCRename(cc,"cone over empty complex");
  return cc;
 fi;
 
 if IsBound(apex) then
  facets:=SCFacets(complex);
  if facets = fail then
   return fail;
  fi;
  
  cone:=List(facets,x->Union(x,[apex]));
  cc:=SCFromFacets(cone);
  
  if(SCName(complex)<>fail) then
   SCRename(cc,Concatenation("cone over ",SCName(complex)," with apex ",String(apex)));
  fi; 
  
 else

  facets:=SCFacetsEx(complex);
  verts:=SCSkelEx(complex,0);
  if(facets=fail or verts=fail) then
   return fail;
  fi;
  
  maxv:=Length(verts);
  
  cone:=[];
  for f in facets do
   Add(cone,Union(f,[maxv+1]));
  od;
  
  cc:=SCFromFacets(cone);
  
  if(SCName(complex)<>fail) then
   SCRename(cc,Concatenation("cone over ",SCName(complex)));
  fi; 

 fi;
 return cc;
end);

################################################################################
##<#GAPDoc Label="SCClose">
## <ManSection>
## <Func Name="SCClose" Arg="complex [, apex]"/>
## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon success, <K>fail</K> otherwise.</Returns>
## <Description>
## Closes a simplicial complex <Arg>complex</Arg> by building a cone over its boundary. If <Arg>apex</Arg> is specified it is assigned to the apex of the cone and the original vertex labeling of <Arg>complex</Arg> is preserved, otherwise an arbitrary vertex label is chosen and <Arg>complex</Arg> is returned in the standard labeling. 
## <Example><![CDATA[
## gap> s:=SCSimplex(5);;                                       
## gap> b:=SCSimplex(5);;
## gap> s:=SCClose(b,13);;
## gap> SCIsIsomorphic(s,SCBdSimplex(6));                       
## true
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallGlobalFunction(SCClose,
function(arg)
 local facets,cone,c,apex,labels,bd,complex,relabel;

 if Size(arg) = 1 then
  complex:=arg[1];
 elif Size(arg) = 2 then
  complex:=arg[1];
  apex:=arg[2];
 else
  Info(InfoSimpcomp,1,"SCCone: number of arguments must be one or two.");
  return fail;
 fi;
 
 labels:=SCLabels(complex);
 if labels = fail then
  return fail;
 fi;
 
 if IsBound(apex) then
  if apex in labels then
   Info(InfoSimpcomp,1,"SCCone: second argument must not be a vertex label of first argument.");
   return fail;
  fi;
  bd:=SCBoundary(complex);
  if bd = fail then
   return fail;
  fi;
  if SCIsEmpty(bd) then
   return complex;
  fi;
  cone:=SCCone(bd,apex);
  return Union(cone,complex);  
 else
  c:=SCCopy(complex);
  relabel:=SCRelabelStandard(c);
  if relabel <> true then
   Info(InfoSimpcomp,1,"SCCone: relabeling vertices failed.");
   return fail;
  fi;
  bd:=SCBoundary(complex);
  if bd = fail then
   return fail;
  fi;
  if SCIsEmpty(bd) then
   return complex;
  fi;
  cone:=SCCone(bd,Size(labels)+1);
  return Union(cone,complex);  
 fi; 
end);

################################################################################
##<#GAPDoc Label="SCShellingExt">
## <ManSection>
## <Meth Name="SCShellingExt" Arg="complex, all,checkvector"/>
## <Returns> a list of facet lists (if <Arg>checkvector = []</Arg>) or <K>true</K> or <K>false</K> (if <Arg>checkvector</Arg> is not empty), <K>fail</K> otherwise.</Returns>
## <Description>
## The simplicial complex <Arg>complex</Arg> must be pure of dimension <M>d</M>, strongly connected and must fulfill the weak pseudomanifold property with non-empty boundary (cf. <Ref Meth="SCBoundary"/>).<P/>
## An ordering <M>(F_1, F_2, \ldots , F_r)</M> on the facet list of a simplicial complex is a shelling if and only if <M>F_i \cap (F_1 \cup \ldots \cup F_{i-1})</M> is a pure simplicial complex of dimension <M>d-1</M> for all <M>i = 1, \ldots , r</M>.<P/>
## If <Arg>all</Arg> is set to <K>true</K> all possible shellings of <Arg>complex</Arg> are computed. If <Arg>all</Arg> is set to <K>false</K>, at most one shelling is computed.<P/>
## Every shelling is represented as a permuted version of the facet list of <Arg>complex</Arg>. The list <Arg>checkvector</Arg> encodes a shelling in a shorter form. It only contains the indices of the facets. If an order of indices is assigned to <Arg>checkvector</Arg> the function tests whether it is a valid shelling or not.<P/>
## See <Cite Key="Ziegler95LectPolytopes"/>, <Cite Key="Pachner87KonstrMethKombHomeo" /> to learn more about shellings.
## <Example><![CDATA[
## gap> c:=SCBdSimplex(4);;
## gap> c:=SCDifference(c,SC([c.Facets[1]]));; # bounded version
## gap> all:=SCShellingExt(c,true,[]);;
## gap> Size(all);                                  
## gap> all[1];
## gap> all:=SCShellingExt(c,false,[]);
## gap> all:=SCShellingExt(c,true,[1..4]);
## ]]></Example>
## </Description>
## </ManSection>
##<#/GAPDoc>
################################################################################
InstallMethod(SCShellingExt,
"for SCSimplicialComplex and Bool and List",
[SCIsSimplicialComplex,IsBool,IsList],
function(complex,all,checkvector)
 local getFacetNeighborsIdx,complexStronglyConnectedShelling,
  computeBoundaryShelling,markBoundaryFactesShelling,isValidNextShellingFacet,
  computeShellingBt,shellings,killed,killedn,i,idx,sc,sconn,
  shellingVectorToFacetList,checkShellingValid,bd,pure;

 shellingVectorToFacetList:=function(sc,sv)
  local flist,idxlist,i;

  flist:=[];
  idxlist:=Permuted([1..Length(sv)],SortingPerm(sv));
  for i in [1..Length(idxlist)] do
   flist[i]:=sc[idxlist[i]];
  od;

  return flist;
 end;

 checkShellingValid:=function(sc,shellingvec)
  return SCShellingExt(sc,false,shellingvec);
 end;

 getFacetNeighborsIdx:=function(sc,sidx)
  local side,sides,t,neighbors,s;

  s:=sc[sidx];

  sides:=Combinations(s,Length(s)-1);
  neighbors:=[];

  for t in sc do
   if(t=s) then continue; fi;
   for side in sides do
    if(IsSubset(t,side)) then
     AddSet(neighbors,Position(sc,t));
    fi;
   od;
  od;

  return neighbors;
 end;

 complexStronglyConnectedShelling:=function(sc,killed)
  local seen,curfacet,stack,neighbors,n,i;

  seen:=ShallowCopy(killed);

  if(Position(seen,0)=fail) then
   return false;
  fi;

  curfacet:=Position(seen,0);
  seen[curfacet]:=1;
  stack:=[];

  repeat
   neighbors:=Filtered(getFacetNeighborsIdx(sc,curfacet),x->killed[x]=0);
   for n in neighbors do
    if(seen[n]=0) then
     seen[n]:=1;
     UniteSet(stack,Filtered(getFacetNeighborsIdx(sc,n),x->seen[x]=0 and killed[x]=0));
    fi;
   od;
   if(stack<>[]) then
    curfacet:=stack[1];
    RemoveSet(stack,stack[1]);
    seen[curfacet]:=1;
   else
    curfacet:=0;
   fi;
  until(curfacet=0);

  return not 0 in seen;
 end;


 computeBoundaryShelling:=function(sc,killed)
  local dim,faces,s,sf,countf,p,bd,i,sidx;

  if(Length(sc)=0) then
   return [];
  fi;

  dim:=Length(sc[1]);

  faces:=[];
  for s in [1..Length(sc)] do
   if(killed[s]<>0) then continue; fi;
   UniteSet(faces,Combinations(sc[s],dim-1));
  od;

  countf:=ListWithIdenticalEntries(Length(faces),0);
  for sidx in [1..Length(sc)] do
   if(killed[sidx]<>0) then continue; fi;
   s:=sc[sidx];
   for sf in Combinations(s,dim-1) do
    p:=Position(faces,sf);
    countf[p]:=countf[p]+1;
   od;
  od;

  bd:=[];
  for i in [1..Length(countf)] do
   if(countf[i]=1) then
    AddSet(bd,faces[i]);
   fi;
  od;

  return bd;
 end;

 markBoundaryFactesShelling:=function(sc,killed)
  local bd,bdfacets,s,t;

  bdfacets:=ListWithIdenticalEntries(Length(sc),0);
  bd:=computeBoundaryShelling(sc,killed);

  for s in bd do
   for t in [1..Length(sc)] do
    if(killed[t]<>0) then continue; fi;
    if(IsSubset(sc[t],s)) then
     bdfacets[t]:=1;
    fi;
   od;
  od;

  return bdfacets;
 end;

 isValidNextShellingFacet:=function(sc,killed,cur)
  local i,j,intersection,alllen,prev,span,failed,dim,done;

  failed:=0;
  intersection:=[];
  for i in [1..Length(killed)] do
   if(killed[i]=0) then continue; fi;
   if(Intersection(sc[i],sc[cur])<>[]) then
    AddSet(intersection,Intersection(sc[cur],sc[i]));
   fi;
  od;

  #consolidate simplices
  done:=0;
  while(done=0) do
   done:=1;
   for i in [1..Length(intersection)] do
    for j in [1..Length(intersection)] do
     if(j=i) then continue; fi;
     if(IsSubset(intersection[i], intersection[j])) then
      RemoveSet(intersection,intersection[j]);
      done:=0;
      break;
     fi;
    od;

    if(done=0) then break; fi;
   od;
  od;

  dim:=List(intersection,Length)-1;
  
  if(Size(Set(dim))<>1) then
   #intersection not pure
   return false;
  else
   dim:=dim[1];
  fi;
  
  if(dim=Length(sc[1])-2) then
   #always valid here since any ordering of facets of simplex is a shelling
   return true;
  else
   return false;
  fi;
 end;

 computeShellingBt:=function(sc,killedn,killed,shellings,all)
  local i,bd,lkilled;

  if(not 0 in killed) then
   AddSet(shellings,ShallowCopy(killed));
   return true;
  fi;

  if(not complexStronglyConnectedShelling(sc,killed)) then

   return false;
  fi;

  bd:=markBoundaryFactesShelling(sc,killed);

  lkilled:=ShallowCopy(killed);
  for i in [1..Length(bd)] do
   if(bd[i]=1) then
    if(killedn=1 or isValidNextShellingFacet(sc,killed,i)) then
     #backtrack
     lkilled[i]:=killedn;
     if(computeShellingBt(sc,killedn+1,lkilled,shellings,all) and not all) then
      return true;
     fi;
     lkilled[i]:=0;
    fi;
   fi;
  od;

  return false;
 end;

 sc:=SCFacetsEx(complex);
 sconn:=SCIsStronglyConnected(complex);
 pure:=SCIsPure(complex);
 bd:=SCHasBoundary(complex);
 if sc = fail or sconn = fail or pure = fail or bd = fail then
  Info(InfoSimpcomp,1,"SCShellingExt: invalid arguments. complex must be a pure strongly connected simplicial complex with boundary.");
  return fail;
 fi;

 if(bd=false or sconn=false or pure=false) then
  Info(InfoSimpcomp,1,"SCShellingExt: invalid arguments. complex must be a pure strongly connected simplicial complex with boundary.");
  return fail;
 fi;

 if(checkvector=[]) then
  #compute shelling(s)
  shellings:=[];
  computeShellingBt(sc,1,ListWithIdenticalEntries(Length(sc),0),shellings,all);

  if(shellings<>[] and not ForAll(shellings,x->checkShellingValid(complex,x)=true)) then
   Info(InfoSimpcomp,1,"SCShellingExt: internal error, invalid shelling.");
   return fail;
  fi;

  return List(shellings,x->shellingVectorToFacetList(sc,x));
 else
  #check shelling vector for validity
  killed:=ListWithIdenticalEntries(Length(sc),0);
  killedn:=1;

  if(not complexStronglyConnectedShelling(sc,killed)) then
   return false;
  fi;

  for idx in [1..Length(checkvector)] do
--> --------------------

--> maximum size reached

--> --------------------

[ Verzeichnis aufwärts0.61unsichere Verbindung  Übersetzung europäischer Sprachen durch Browser  ]