1################################################################################
2##
3##  simpcomp / bistellar.gi
4##
5##  Functions for bistellar moves
6##
7##  $Id$
8##
9################################################################################
10
11################################################################################
12##<#GAPDoc Label="SCBistellarOptions">
13## <ManSection>
14## <Var Name="SCBistellarOptions"/>
15## <Description>
16## Record of global variables to adjust output an behavior of bistellar moves
17## in <Ref Func="SCIntFunc.SCChooseMove"/> and <Ref Func="SCReduceComplexEx"/>
18## respectively.
19## <Enum>
20## <Item><C>BaseRelaxation</C>: determines the length of the relaxation period.
21## Default: <M>3</M></Item>
22## <Item><C>BaseHeating</C>: determines the length of the heating period.
23## Default: <M>4</M></Item>
24## <Item><C>Relaxation</C>: value of the current relaxation period. Default:
25## <M>0</M></Item>
26## <Item><C>Heating</C>: value of the current heating period. Default:
27## <M>0</M></Item>
28## <Item><C>MaxRounds</C>: maximal over all number of bistellar flips that
29## will be performed. Default: <M>500000</M></Item>
30## <Item><C>MaxInterval</C>: maximal number of bistellar flips that will be
31## performed without a change of the <M>f</M>-vector of the moved complex.
32## Default: <M>100000</M></Item>
33## <Item><C>Mode</C>: flip mode, <M>0</M>=reducing, <M>1</M>=comparing,
34## <M>2</M>=reduce as sub-complex, <M>3</M>=randomize. Default: <M>0</M>
35## </Item>
36## <Item><C>WriteLevel</C>: <M>0</M>=no output, <M>1</M>=storing of every
37## vertex minimal complex to user library, <M>2</M>=e-mail notification.
38## Default: <M>1</M> </Item>
39## <Item><C>MailNotifyIntervall</C>: (minimum) number of seconds between
40## two e-mail notifications. Default:
41## <M>24 \cdot 60 \cdot 60</M> (one day)</Item>
42## <Item><C>MaxIntervalIsManifold</C>: maximal number of bistellar flips that
43## will be performed without a change of the <M>f</M>-vector of a vertex link
44## while trying to prove that the complex is a combinatorial manifold. Default:
45## <M>5000</M></Item>
46## <Item><C>MaxIntervalRandomize := 50</C>: number of flips performed to create
47## a randomized sphere. Default: <M>50</M></Item>
48## </Enum>
49## <Example>
50## gap> SCBistellarOptions.BaseRelaxation;
51## 3
52## gap> SCBistellarOptions.BaseHeating;
53## 4
54## gap> SCBistellarOptions.Relaxation;
55## 0
56## gap> SCBistellarOptions.Heating;
57## 0
58## gap> SCBistellarOptions.MaxRounds;
59## 500000
60## gap> SCBistellarOptions.MaxInterval;
61## 100000
62## gap> SCBistellarOptions.Mode;
63## 0
64## gap> SCBistellarOptions.WriteLevel;
65## 1
66## gap> SCBistellarOptions.MailNotifyInterval;
67## 86400
68## gap> SCBistellarOptions.MaxIntervalIsManifold;
69## 5000
70## gap> SCBistellarOptions.MaxIntervalRandomize;
71## 50
72## </Example>
73## </Description>
74## </ManSection>
75##<#/GAPDoc>
76################################################################################
77InstallValue(SCBistellarOptions,
78rec(
79  BaseRelaxation:=3,
80  BaseHeating:=4,
81  Relaxation:=0,
82  Heating:=0,
83  MaxRounds:=500000,
84  MaxInterval:=100000,
85  Mode:=0,
86  WriteLevel:=0,
87  MailNotifyInterval:=24*60*60,
88  MaxIntervalIsManifold:=5000,
89  MaxIntervalRandomize:=50
90));
91MakeReadWriteGlobal("SCBistellarOptions");
92
93################################################################################
94##
95#F SCIntFunc.IRawBistellarRMoves (< r>,<faces>, <max >
96##                    [,<mode>,<complex >])
97##
98##
99##
100## INPUT:      r: codimension of faces that are about to be examined
101##              ("testelement")
102##             sComplex: simplicial Complex by faces
103##             max: Size of maximal Elements of sComplex (max-1) =
104##              Dimension of complex
105##
106## OUTPUT:     rawOptions: vector containing all possible candidates for r-moves
107##
108## DESCRIPTION:
109##
110## Initial options for moves (and reverse moves)
111## (Reverse_k_Move=(max-k-1)-move)
112##
113## Test for all (dim-r)-dimensional faces "testelement" whether there are
114## exactly (r + 1) maximal faces "maxface" containing "testelement".
115## If this is true return all vertices of those maximal faces ("linkface"), and
116## "testelement" in rawOptions[r+1] (#(raw_element[r+1])<=#(faces[max-r]))
117##
118## EXAMPLE:
119## r:=1;
120## faces[max]:=[[1,2,3],[2,3,4], ...];
121## faces[max-r]:=[[1,2],[2,3],[3,1],[2,4],[3,4], ...];
122## raw_options[r+1]:=[[[2,3],[1,4]],[...], ...];
123##
124## r:=2;
125## faces[max]:=[[1,2,3],[1,2,4],[1,3,4],[2,3,5],[2,4,6],[2,5,6], ...];
126## faces[max-r]:=[[1],[2],[3],[4],[5],[6], ...];
127## raw_options[r+1]:=[[[1],[2,3,4]],[...], ...];
128## [[2],[1,3,4,5,6]] not in raw_options[r+1]
129##
130## Elements in raw_options[r+1] -> canditates for r-moves
131## changes of global vars:
132## raw_options[r+1] -> all faces in "faces[max-r]" which are contained in (r+1)
133## maximal faces, including all vertices of those maximal faces.
134##
135SCIntFunc.IRawBistellarRMoves:=function(arg)
136
137  local testelement, linkface, rawOptions, r, faces, max,
138    mode, complex, hd, idx, i, j, base, tmp;
139
140  if Size(arg)<3 or Size(arg)=4 or Size(arg)>5 then
141    Info(InfoSimpcomp,2,"SCIntFunc.IRawBistellarRMoves: number of arguments ",
142      "must be 3 or 5");
143    return fail;
144  fi;
145  r:=arg[1];
146  faces:=arg[2];
147  max:=arg[3];
148  if Size(arg)=5 then
149    mode:=arg[4];
150    complex:=arg[5];
151  fi;
152  rawOptions:=[];
153
154  # build Hasse diagram section
155  hd:=List([1..Size(faces[max-r])],x->[]);
156
157  idx:=Combinations([1..max],max-r);
158
159  for i in [1..Size(faces[max])] do
160    for j in idx do
161      base:=faces[max][i]{j};
162      Add(hd[PositionSorted(faces[max-r],base)],i);
163    od;
164  od;
165
166  for i in [1..Size(hd)] do
167    if Size(hd[i]) <> r+1 then continue; fi;
168    linkface:=Union(faces[max]{hd[i]});
169    testelement:=faces[max-r][i];
170    SubtractSet(linkface,testelement);
171    if Size(arg)=3 or mode<>4 then
172      Add(rawOptions,[testelement,linkface]);
173    else
174      if Size(linkface)>0 and linkface in complex[Size(linkface)] then
175        Add(rawOptions,[testelement,linkface]);
176        fi;
177    fi;
178  od;
179
180  return rawOptions;
181end;
182
183################################################################################
184##
185#F SCIntFunc.IBistellarRMoves (< r>,<max>,<rawOptions>,<faces >)
186##
187## Include options for moves (and reverse moves)
188## Test for all elements in "raw_options[r+1]" whether they are
189## really candidates for a r-move or not.
190##
191## EXAMPLE:
192## r:=0;
193## faces[max]:=[[1,2,3],[2,3,4],[1,3,4],[1,2,4]]; (2-sphere)
194## faces[max-r]:=[[1,2,3],[2,3,4],[1,3,4],[1,2,4]];
195## raw_options[r+1]:=[[[1,2,3],[]],[[2,3,4],[]],[[1,3,4],[]],[[1,2,4],[]]];
196## r:=1;
197## faces[max]:=[[1,2,3],[2,3,4],[1,3,4],[1,2,4]]; (2-sphere)
198## faces[max-r]:=[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]];
199## raw_options[r+1]:=[[[1,2],[3,4]],[[1,3],[2,4]],[[1,4],[2,4]],[[2,3],[1,4]],
200## [[2,4],[1,3]],[[[3,4],[1,2]]];
201## r:=2;
202## faces[max]:=[[1,2,3],[2,3,4],[1,3,4],[1,2,4]]; (2-sphere)
203## faces[max-r]:=[[1],[2],[3],[4]];
204## raw_options[r+1]:=[[[1],[2,3,4]],[[2],[1,3,4]],
205## [[3],[1,2,4]],[[4],[1,2,3]]];
206##
207## but: [1,2] -> [3,4] in faces[2], etc. ...
208##      [1] -> [2,3,4] in faces[3], etc. ...
209## -> options:=[[[1,2,3],[]],[[2,3,4],[]],[[1,3,4],[]],[[1,2,4],[]]];
210##
211SCIntFunc.IBistellarRMoves:=function(r,max,rawOptions,faces)
212
213  local element, options;
214
215  options:=[];
216
217  for element in rawOptions do
218    # case element[1] in faces[max] (-> element[2]=[])
219    if element[2]<>[] then
220      # case "linkface" element[2] of element[1] isn't already
221      # contained in the simplicial complex
222      if not element[2] in faces[Length(element[2])] then
223        Add(options,element);
224      fi;
225    elif element[2]=[] then
226      Add(options,element);
227    fi;
228  od;
229
230  #options :=Set(options);
231  return options;
232
233end;
234
235
236###################################################################
237###                Moves (and reverse moves)                    ###
238###################################################################
239
240################################################################################
241##
242#F SCIntFunc.BallBoundary (< max >,<faces>,<raw_options>,
243##    < ball_boundary_faces>,<mode,complex >)
244##
245## test all elements in "ball_boundary_faces" whether they can be flipped or
246## not (in this case, add them to "raw_options") (this routine is part
247## of every r-move (at the end))
248##
249SCIntFunc.BallBoundary:=function(max,faces,raw_options,ball_boundary_faces,
250    mode,complex)
251
252  local element, j, count, linkface, maxface;
253
254  element:=[];
255  for j in ball_boundary_faces do
256    element:=Union(element,j);
257  od;
258  if Size(element)>(max+1) or Size(element)<(max) then
259    Info(InfoSimpcomp,2,"SCIntFunc.BallBoundary: wrong ball boundary faces - ",
260      "wrong number\nof vertices: ",element,".");
261    return fail;
262  fi;
263
264  for element in ball_boundary_faces do
265
266    count:=0;
267    linkface:=[];
268    for maxface in faces[max] do
269      if IsSubset(maxface,element)=true  then
270        count:=count+1;
271        UniteSet(linkface,maxface);
272      fi;
273    od;
274    # linkface -> all vertices that are not in "element" but in a maximal
275    # face containing "element".
276    SubtractSet(linkface,element);
277
278    # If "element" occurs in "raw_options[max-Length[element]+1]]", remove it.
279    j:=1;
280    while j<=Length(raw_options[max-Length(element)+1]) do
281      if element=raw_options[max-Length(element)+1][j][1] then
282        RemoveSet(raw_options[max-Length(element)+1],
283                  raw_options[max-Length(element)+1][j]);
284        j:=Length(raw_options[max-Length(element)+1]);
285      fi;
286      j:=j+1;
287    od;
288
289    # If "element" is contained in exactly "max - Length(element) + 1" maximal
290    # faces, add it again to "raw_options" (with a
291    # possibly different set "linkface")
292    if count=max - Length(element) + 1 then
293      if (linkface=[] and Size(element)=max) or
294        (linkface<>[] and Size(element)+Size(linkface)=max + 1) then
295        if(mode<>4) then
296          AddSet(raw_options[max-Size(element)+1],[element,linkface]);
297        else
298          if Size(linkface)>0 and linkface in complex[Size(linkface)] then
299            AddSet(raw_options[max-Size(element)+1],[element,linkface]);
300          fi;
301        fi;
302      else
303        Info(InfoSimpcomp,1,"SCIntFunc.BallBoundary: wrong flip added: ",
304          [element,linkface]);
305        return fail;
306      fi;
307    fi;
308  od;
309
310  return raw_options;
311
312end;
313
314################################################################################
315##
316#F SCIntFunc.ZeroMove (< max>,<faces>,<F >,<raw_options>,
317##  <mode>,   < randomelement>,<complex >)
318##
319## realizes a 0-move (i.e. f[1] -> f[1] + 1, ..., f[max] -> f[max] + dim)
320#
321## FURTHER EXPLANATION:
322##
323## A "0-move" subdivides a maximal (dim-)simplex into (dim+1)=max
324## (dim-)simplices, coned over a new vertex in its center (see Paper
325## "Simplicial Manifolds..." by Lutz/Björner for a formal definition of
326## bistellar k-moves)
327##
328SCIntFunc.ZeroMove:=function(max,faces,F,randomelement,raw_options,mode,complex)
329
330  local element, i, j, A, linkface, maxface, maxvertex, ball_boundary_faces;
331
332  if randomelement[2]=[] then
333    maxvertex:=MaximumList(faces[1])+1;
334    maxvertex:=maxvertex[1];
335  elif Size(randomelement[2])=1 then
336    maxvertex:=randomelement[2][1];
337  else
338    Info(InfoSimpcomp,1,"SCIntFunc.ZeroMove: Ivalid type of 0_Move ",
339      "(Size(randomelement[2])>1)");
340    return fail;
341  fi;
342
343  # first part: "M \ (A * Bd(B))" (from the formal definition)...
344  # ...where M=faces[max], A=randomelement[1], B=new vertex "[maxvertex]"
345  # (-> Bd(B) =  [])
346  RemoveSet(faces[max],randomelement[1]);
347  F[max]:=F[max]-1;
348  if raw_options<>[] then
349    RemoveSet(raw_options[1],randomelement);
350  fi;
351
352  # second part: "(Bd(A) * B)"... (see above)
353  for i in [0..(max-1)] do
354    for element in Combinations(randomelement[1],i) do
355      # add new elements to triangulation "faces"
356      A:=[maxvertex];
357      UniteSet(A,element);
358      AddSet(faces[i+1],A);
359      F[i+1]:=F[i+1]+1;
360
361      if raw_options<>[] then
362        # add new possible flip-operations
363        linkface:=[];
364        for maxface in Combinations(randomelement[1],max-1) do
365          if IsSubset(maxface,element)=true  then
366            UniteSet(linkface,maxface);
367          fi;
368        od;
369        SubtractSet(linkface,element);
370
371        if (linkface=[] and Size(A)=max) or (linkface<>[] and
372          Size(A)+Size(linkface)=max + 1) then
373          if mode<>4 then
374            AddSet(raw_options[max+1-Size(A)],[A,linkface]);
375          else
376            if Size(linkface)>0 and linkface in complex[Size(linkface)] then
377              AddSet(raw_options[max+1-Size(A)],[A,linkface]);
378            fi;
379          fi;
380        else
381          Info(InfoSimpcomp,1,"SCIntFunc.ZeroMove: wrong flip added: ",
382            [A,linkface]);
383        fi;
384      fi;
385    od;
386  od;
387
388  if raw_options<>[] then
389    # get all faces of boundary of simplex...
390    ball_boundary_faces:=[];
391    for i in [1..(max-1)] do
392      UniteSet(ball_boundary_faces,Combinations(randomelement[1],i));
393    od;
394
395    # ... and check if they can be added to "raw_options"
396    raw_options :=   SCIntFunc.BallBoundary(max,faces,raw_options,
397      ball_boundary_faces,mode,complex);
398    if raw_options=fail then
399      return fail;
400    fi;
401  fi;
402  return [faces,F,raw_options];
403
404end;
405
406
407################################################################################
408##
409#F SCIntFunc.Move (< r>,<max>,<faces>,<F>,<randomelement>,
410##    < raw_options> ,<mode>,<complex>)
411##
412## realizes a r-move
413##
414SCIntFunc.Move:=function(r,max,faces,F,randomelement,raw_options,mode,complex)
415
416  local element, i, j, A, count, maxface, linkface,
417       new_facets, ball_interior_faces, ball_boundary_faces, tmp;
418
419  if r=0 then
420    tmp:=SCIntFunc.ZeroMove(max,faces,F,randomelement,raw_options,mode,complex);
421    if tmp=fail then
422      return fail;
423    fi;
424    faces:=tmp[1];
425    F:=tmp[2];
426    raw_options:=tmp[3];
427  else
428    for i in [0..r] do
429      # for all (i-1)-dimensional faces of "linkface" of "(random-)element"
430      for element in Combinations(randomelement[2],i) do
431        # first part: "(M \ A * Bd(B))" -> remove (A * Bd(B))
432        A:=[];
433        UniteSet(A,randomelement[1]);
434        UniteSet(A,element);
435        # A -> (max - r + i - 1)-dimensional face of "facets"
436        RemoveSet(faces[max-r+i],A);
437        # update f-vector
438        F[max-r+i]:=F[max-r+i]-1;
439        if F[max-r+i]<>Size(faces[max-r+i]) then
440          Info(InfoSimpcomp,1,"SCIntFunc.Move: invalid flip was performed.\n",
441            A," not in complex.");
442          return fail;
443        fi;
444        if raw_options<>[] then
445          # update "raw_options"
446          # remove flips, which involve the recently removed element "A"
447          # of "faces"
448          for j in [1..Size(raw_options[r-i+1])] do
449            if A=raw_options[r-i+1][j][1] then
450              RemoveSet(raw_options[r-i+1],raw_options[r-i+1][j]);
451              break;
452            fi;
453          od;
454        fi;
455      od;
456    od;
457
458    # second part: add "(Bd(A) * B)" to M
459    new_facets:=[];
460    ball_interior_faces:=[];
461
462    for i in [0..(max-r-1)] do
463      for element in Combinations(randomelement[1],i) do
464        A:=[];
465        UniteSet(A,randomelement[2]);
466        UniteSet(A,element);
467        # i in [0..(max-r-1)] -> (r + 1)<=(r + i + 1)<=max=(dim + 1)
468        AddSet(faces[r+i+1],A);
469        # update f-vector
470        F[r+i+1]:=F[r+i+1]+1;
471        if F[r+i+1]<>Size(faces[r+i+1]) then
472          Info(InfoSimpcomp,1,"SCIntFunc.Move: invalid flip was performed:\n",
473            A," is already in mainComplex.");
474          return fail;
475        fi;
476        # if i is maximal, add A to the array "new_facets", if not, add it to
477        # "ball_interior_faces"
478        if i=max - r - 1 then
479          AddSet(new_facets,A);
480        else
481          AddSet(ball_interior_faces,A);
482        fi;
483      od;
484    od;
485
486    # new_facets: Set of all maximal dimensional facets of the form
487    # A=Union(Combinations(randomelement[1],(max-r-1)),randomelement[2])
488    # second part: "add (Bd(A) * B) to M"
489    for i in [0..(max-r-1)] do
490      for element in Combinations(randomelement[1],i) do
491        A:=[];
492        UniteSet(A,randomelement[2]);
493        UniteSet(A,element);
494
495        # get "linkface" of A -> all maximal facets that contain A minus A
496        linkface:=[];
497        for maxface in new_facets do
498          if IsSubset(maxface,A)=true  then
499            UniteSet(linkface,maxface);
500          fi;
501        od;
502        SubtractSet(linkface,A);
503
504        if raw_options<>[] then
505          # update options vector "raw_options"
506          if (linkface=[] and Size(A)=max) or (linkface<>[] and
507            Size(A)+Size(linkface)=max + 1) then
508            if(mode<>4) then
509              AddSet(raw_options[max-Size(A)+1],[A,linkface]);
510            else
511              if Size(linkface)>0 and linkface in complex[Size(linkface)] then
512                AddSet(raw_options[max-Size(A)+1],[A,linkface]);
513              fi;
514            fi;
515          else
516            Info(InfoSimpcomp,1,"SCIntFunc.Move: wrong flip added: ",
517              [A,linkface]);
518            return fail;
519          fi;
520        fi;
521      od;
522    od;
523
524    if raw_options<>[] then
525      # get all surrounding facets
526      ball_boundary_faces:=[];
527      for element in new_facets do
528        for i in [1..(max-1)] do
529          UniteSet(ball_boundary_faces,Combinations(element,i));
530        od;
531      od;
532      SubtractSet(ball_boundary_faces,ball_interior_faces);
533
534      raw_options:=SCIntFunc.BallBoundary(max,faces,raw_options,
535        ball_boundary_faces,mode,complex);
536      if raw_options=fail then
537        return fail;
538      fi;
539    fi;
540
541  fi;
542
543  return [faces,F,raw_options];
544
545end;
546
547################################################################################
548##<#GAPDoc Label="SCIsMovableComplex">
549## <ManSection>
550## <Meth Name="SCIsMovableComplex" Arg="complex"/>
551## <Returns> <K>true</K> or <K>false</K> upon success, <K>fail</K> otherwise.
552## </Returns>
553## <Description>
554## Checks if a simplicial complex <Arg>complex</Arg> can be modified by
555## bistellar moves, i. e. if it is a pure simplicial complex which fulfills
556## the weak pseudomanifold property with empty boundary.<P/>
557## <Example>
558## gap> c:=SCBdCrossPolytope(3);;
559## gap> SCIsMovableComplex(c);
560## true
561## </Example>
562## Complex with non-empty boundary:
563## <Example>
564## gap> c:=SC([[1,2],[2,3],[3,4],[3,1]]);;
565## gap> SCIsMovableComplex(c);
566## false
567## </Example>
568## </Description>
569## </ManSection>
570##<#/GAPDoc>
571################################################################################
572InstallMethod(SCIsMovableComplex,
573"for SCSimplicialComplex",
574[SCIsSimplicialComplex],
575function(complex)
576
577  local pure, pm, bd, dim;
578
579  dim :=SCDim(complex);
580  if dim = fail then
581    return fail;
582  fi;
583
584  if dim < 1 then
585    Info(InfoSimpcomp,2,"SCIsMovableComplex: complex dimension is smaller ",
586      "than 1, no bistellar moves are possible.");
587    return false;
588  fi;
589
590  pure := SCIsPure(complex);
591  if pure = fail then
592    return fail;
593  fi;
594
595  if pure = false then
596    return false;
597  fi;
598
599  pm := SCIsPseudoManifold(complex);
600  if pm = fail then
601    return fail;
602  fi;
603
604  if pm = false then
605    return false;
606  fi;
607
608  bd := SCHasBoundary(complex);
609  if bd = fail then
610    return fail;
611  fi;
612  if bd = true then
613    return false;
614  fi;
615
616  return true;
617
618end);
619
620################################################################################
621##<#GAPDoc Label="SCRMoves">
622## <ManSection>
623## <Meth Name="SCRMoves" Arg="complex, r"/>
624## <Returns> a list of pairs of the form <C>[ list, list ]</C>, <K>fail</K>
625## otherwise.</Returns>
626## <Description>
627## A bistellar <M>r</M>-move of a <M>d</M>-dimensional combinatorial manifold
628## <Arg>complex</Arg> is a <M>r</M>-face <M>m_1</M> together with a
629## <M>d-r</M>-tuple <M>m_2</M> where <M>m_1</M> is a common face of exactly
630## <M>(d+1-r)</M> facets and <M>m_2</M> is not a face of <Arg>complex</Arg>.<P/>
631## The <M>r</M>-move removes all facets containing <M>m_1</M> and replaces
632## them by the <M>(r+1)</M> faces obtained by uniting <M>m_2</M> with any
633## subset of <M>m_1</M> of order <M>r</M>.<P/>
634## The resulting complex is PL-homeomorphic to <Arg>complex</Arg>.
635## <Example>
636## gap> c:=SCBdCrossPolytope(3);;
637## gap> moves:=SCRMoves(c,1);
638## [ [ [ 1, 3 ], [ 5, 6 ] ], [ [ 1, 4 ], [ 5, 6 ] ], [ [ 1, 5 ], [ 3, 4 ] ],
639##   [ [ 1, 6 ], [ 3, 4 ] ], [ [ 2, 3 ], [ 5, 6 ] ], [ [ 2, 4 ], [ 5, 6 ] ],
640##   [ [ 2, 5 ], [ 3, 4 ] ], [ [ 2, 6 ], [ 3, 4 ] ], [ [ 3, 5 ], [ 1, 2 ] ],
641##   [ [ 3, 6 ], [ 1, 2 ] ], [ [ 4, 5 ], [ 1, 2 ] ], [ [ 4, 6 ], [ 1, 2 ] ] ]
642## </Example>
643## </Description>
644## </ManSection>
645##<#/GAPDoc>
646################################################################################
647InstallMethod(SCRMoves,
648"for SCSimplicialComplex and Int",
649[SCIsSimplicialComplex,IsInt],
650function(complex,r)
651
652  local tmp, options, dim, faces;
653
654  dim:=SCDim(complex);
655    if dim=fail then
656      return fail;
657  fi;
658
659  if dim < 1 then
660    SCPropertyTmpSet(complex,"Moves",[]);
661    return [];
662  fi;
663
664
665  if dim < r then
666    return [];
667  fi;
668
669  options:=SCPropertyTmpByName(complex,"Moves");
670  if options<>fail and IsBound(options[r+1]) then
671    return options[r+1];
672  else
673    if not SCIsMovableComplex(complex) then
674      Info(InfoSimpcomp,2,"SCRMoves: argument should be a closed ",
675        "pseudomanifold");
676      return fail;
677    fi;
678    faces:=SCFaceLatticeEx(complex);
679    if faces=fail then
680      return fail;
681    fi;
682
683    if options=fail then
684      options:=[];
685    fi;
686    tmp:=SCIntFunc.IRawBistellarRMoves(r,faces,dim+1);
687    if tmp=fail then
688      return fail;
689    fi;
690    options[r+1]:=SCIntFunc.IBistellarRMoves(r+1,dim+1,tmp,faces);
691
692    SCPropertyTmpSet(complex,"Moves",options);
693    return options[r+1];
694  fi;
695
696end);
697
698
699################################################################################
700##<#GAPDoc Label="SCMoves">
701## <ManSection>
702## <Meth Name="SCMoves" Arg="complex"/>
703## <Returns> a list of list of pairs of lists upon success, <K>fail</K>
704## otherwise.</Returns>
705## <Description>
706## See <Ref Meth="SCRMoves"/> for further information.
707## <Example>
708## gap> c:=SCBdCrossPolytope(3);;
709## gap> moves:=SCMoves(c);
710## [
711## # 0-moves
712##   [[[1, 3, 5], []], [[1, 3, 6], []], [[1, 4, 5], []],
713##     [[1, 4, 6], []], [[2, 3, 5], []], [[2, 3, 6], []],
714##     [[2, 4, 5], []], [[2, 4, 6], []]],
715## # 1-moves
716##   [[[1, 3], [5, 6]], [[1, 4], [5, 6]], [[1, 5], [3, 4]],
717##     [[1, 6], [3, 4]], [[2, 3], [5, 6]], [[2, 4], [5, 6]],
718##     [[2, 5], [3, 4]], [[2, 6], [3, 4]], [[3, 5], [1, 2]],
719##     [[3, 6], [1, 2]], [[4, 5], [1, 2]], [[4, 6], [1, 2]]],
720## # 2-moves
721##   []
722##]
723## </Example>
724## </Description>
725## </ManSection>
726##<#/GAPDoc>
727################################################################################
728InstallMethod(SCMoves,
729"for SCSimplicialComplex",
730[SCIsSimplicialComplex],
731function(complex)
732
733  local i, dim, options;
734
735  dim:=SCDim(complex);
736
737  if dim=fail then
738    return fail;
739  fi;
740
741  if dim < 1 then
742    SCPropertyTmpSet(complex,"Moves",[]);
743    return [];
744  fi;
745
746  options:=[];
747  for i in [0..dim] do
748    options[i+1]:=SCRMoves(complex,i);
749    if options[i+1]=fail then
750      return fail;
751    fi;
752  od;
753
754  SCPropertyTmpSet(complex,"Moves",options);
755  return options;
756
757end);
758
759
760
761################################################################################
762##<#GAPDoc Label="SCMove">
763## <ManSection>
764## <Meth Name="SCMove" Arg="c, move"/>
765## <Returns> simplicial complex of type <C>SCSimplicialComplex</C> upon
766## success, <K>fail</K> otherwise.</Returns>
767## <Description>
768## Applies the bistellar move <Arg>move</Arg> to a simplicial complex
769## <Arg>c</Arg>. <Arg>move</Arg> is given as a <M>(r+1)</M>-tuple together
770## with a <M>(d+1-r)</M>-tuple if <M>d</M> is the dimension of <Arg>c</Arg>
771## and if <Arg>move</Arg> is a <M>r</M>-move. See <Ref Meth="SCRMoves"/> for
772## detailed information about bistellar <M>r</M>-moves.<P/>
773## Note: <Arg>move</Arg> and <Arg>c</Arg> should be given in standard
774## labeling to ensure a correct result.
775## <Example>
776## gap> obj:=SC([[1,2],[2,3],[3,4],[4,1]]);
777## [SimplicialComplex
778##
779## Properties known: Dim, Facets, Name, SCVertices.
780##
781## Name="unnamed complex m"
782## Dim=1
783##
784## /SimplicialComplex]
785## gap> moves:=SCMoves(obj);
786## [[[[1, 2], []], [[1, 4], []],
787##     [[2, 3], []], [[3, 4], []]],
788##   [[[1], [2, 4]], [[2], [1, 3]],
789##     [[3], [2, 4]], [[4], [1, 3]]]]
790## gap> obj:=SCMove(obj,last[2][1]);
791## [SimplicialComplex
792##
793##  Properties known: Chi, Dim, F, Faces, Facets, SCVertices.
794##
795##  Name="unnamed complex m"
796##  Dim=1
797##  Chi=0
798##  F=[3, 3]
799##
800## /SimplicialComplex]
801## </Example>
802## </Description>
803## </ManSection>
804##<#/GAPDoc>
805################################################################################
806InstallMethod(SCMove,
807"for SCSimplicialComplex and List",
808[SCIsSimplicialComplex,IsList],
809function(c, move)
810
811  local dim, moves, r, i, j, faces, f, tmp, options, labels, invLabels, max,
812    fvec, fl, complex;
813
814  complex:=SCCopy(c);
815  labels:=SCVertices(complex);
816  if labels=fail then
817    return fail;
818  fi;
819  max:=SCLabelMax(complex);
820  if max=fail then
821    return fail;
822  fi;
823  if labels <> [1..max] then
824    Info(InfoSimpcomp,2,"SCMove: complex not in standard labeling, ",
825      "relabeling.");
826    SCRelabelStandard(complex);
827  fi;
828
829  if not SCIsMovableComplex(complex) then
830    Info(InfoSimpcomp,2,"SCMove: complex not closed or no pseudomanifold");
831    return false;
832  fi;
833
834  dim:=SCDim(complex);
835  if dim=fail then
836    return fail;
837  fi;
838  faces:=SCIntFunc.DeepCopy(SCFaceLatticeEx(complex));
839  if faces=fail then
840    return fail;
841  fi;
842  f:=ShallowCopy(SCFVector(complex));
843  if f=fail then
844    return fail;
845  fi;
846  if Size(move)<>2 or not (Size(move[1]) + Size(move[2]) in [dim+1,dim+2]) then
847    Info(InfoSimpcomp,2,"SCMove: 'move' is not a bistellar move");
848    return fail;
849  fi;
850  if move[2]=[] then
851    r:=0;
852  else
853    r:=Size(move[2])-1;
854  fi;
855  moves:=SCMoves(complex);
856  if moves=fail then
857    return fail;
858  fi;
859  if not move in moves[r+1] then
860    Info(InfoSimpcomp,2,"SCMove: 'move' not valid (in standard labeling)");
861    return fail;
862  fi;
863
864  tmp:=SCIntFunc.Move(r,dim+1,faces,f,move,moves,1,[]);
865  if tmp=fail then
866    return fail;
867  fi;
868
869  if r = dim then
870    invLabels:=[];
871    labels:=Union(tmp[1][1]);
872    for i in [1..Size(labels)] do
873      invLabels[labels[i]]:=i;
874    od;
875    for i in [1..Size(tmp[1])] do
876      tmp[1][i]:=SCIntFunc.RelabelSimplexList(tmp[1][i],invLabels);
877    od;
878    for i in [1..Size(tmp[3])] do
879      for j in [1..Size(tmp[3][i])] do
880        tmp[3][i][j]:=SCIntFunc.RelabelSimplexList(tmp[3][i][j],invLabels);
881      od;
882    od;
883  fi;
884
885  complex:=SCFromFacets(tmp[1][dim+1]);
886  if complex=fail then
887    return fail;
888  fi;
889
890  fvec:=[];
891  fl:=[];
892  for i in [1..Size(tmp[2])] do
893    fvec[2*i-1]:=i-1;
894    fl[2*i-1]:=i-1;
895    fvec[2*i]:=tmp[2][i];
896    fl[2*i]:=tmp[1][i];
897  od;
898  SetComputedSCNumFacess(complex,fvec);
899  SetComputedSCSkelExs(complex,fl);
900
901  options:=[];
902  for r in [1..dim+1] do
903    options[r]:=SCIntFunc.IBistellarRMoves(r,dim+1,tmp[3][r],tmp[1]);
904  od;
905  SCPropertyTmpSet(complex,"Moves",options);
906
907  return complex;
908
909end);
910
911################################################################################
912##<#GAPDoc Label="SCIntFunc.SCChooseMove">
913## <ManSection>
914## <Func Name="SCIntFunc.SCChooseMove" Arg="dim, moves"/>
915## <Returns> a bistellar move, i. e. a pair of lists upon success, <K>fail</K>
916## otherwise.</Returns>
917## <Description>
918## Since the problem of finding a bistellar flip sequence that reduces a
919## simplicial complex is undecidable, we have to use an heuristic approach to
920## choose the next move. <P/>
921## The implemented strategy <C>SCIntFunc.SCChooseMove</C> first tries to
922## directly remove vertices, edges, <M>i</M>-faces in increasing dimension etc.
923## If this is not possible it inserts high dimensional faces in decreasing
924## co-dimension. To do this in an efficient way a number of parameters have
925## to be adjusted, namely <C>SCBistellarOptions.BaseHeating</C> and
926## <C>SCBistellarOptions.BaseRelaxation</C>. See
927## <Ref Var="SCBistellarOptions"/> for further options.
928## <P/>
929## If this strategy does not work for you, just implement a customized
930## strategy and pass it to <Ref Func="SCReduceComplexEx"/>.<P/>
931## See <Ref Meth="SCRMoves" /> for further information.
932## </Description>
933## </ManSection>
934##<#/GAPDoc>
935################################################################################
936SCIntFunc.SCChooseMove:=
937  function(dim,moves)
938
939  local i,options;
940
941  options:=[];
942  if dim=1 then
943
944    Append(options,moves[2]);
945
946  elif dim=2 then
947
948    Append(options,moves[3]);
949    if options=[] then
950      Append(options,moves[2]);
951    fi;
952
953  elif dim=3 then
954
955    if SCBistellarOptions.Heating>0 then
956      if IsInt(SCBistellarOptions.Heating/15)=true then
957        Append(options,moves[1]);
958      else
959        Append(options,moves[2]);
960        if options=[] then
961          Append(options,moves[3]);
962          SCBistellarOptions.Heating:=0;
963        fi;
964      fi;
965      SCBistellarOptions.Heating:=SCBistellarOptions.Heating-1;
966    else
967      Append(options,moves[4]);
968      if options=[] then
969        Append(options,moves[3]);
970        if options=[] then
971          Append(options,moves[2]);
972          if SCBistellarOptions.Relaxation=10 then
973            SCBistellarOptions.Heating:=15;
974            SCBistellarOptions.Relaxation:=0;
975          fi;
976          SCBistellarOptions.Relaxation:=SCBistellarOptions.Relaxation+1;
977        fi;
978      fi;
979    fi;
980
981  elif dim=4 then
982
983    if SCBistellarOptions.Heating>0 then
984      if IsInt(SCBistellarOptions.Heating/20)=true then
985        Append(options,moves[1]);
986      else
987        Append(options,moves[2]);
988        Append(options,moves[3]);
989        if options=[] then
990          Append(options,moves[4]);
991        fi;
992      fi;
993      SCBistellarOptions.Heating:=SCBistellarOptions.Heating-1;
994    else
995      Append(options,moves[5]);
996      if options=[] then
997        Append(options,moves[4]);
998        if options=[] then
999          Append(options,moves[3]);
1000          Append(options,moves[2]);
1001          if SCBistellarOptions.Relaxation=15 then
1002            SCBistellarOptions.Heating:=20;
1003            SCBistellarOptions.Relaxation:=0;
1004          fi;
1005          SCBistellarOptions.Relaxation:=SCBistellarOptions.Relaxation+1;
1006        fi;
1007      fi;
1008    fi;
1009
1010  elif dim=5 then
1011
1012    if SCBistellarOptions.Heating>0 then
1013      if IsInt(SCBistellarOptions.Heating/40)=true then
1014        Append(options,moves[1]);
1015      else
1016        Append(options,moves[2]);
1017        Append(options,moves[3]);
1018        Append(options,moves[4]);
1019        if options=[] then
1020          Append(options,moves[5]);
1021        fi;
1022      fi;
1023      SCBistellarOptions.Heating:=SCBistellarOptions.Heating-1;
1024    else
1025      Append(options,moves[6]);
1026      if options=[] then
1027        Append(options,moves[5]);
1028        if options=[] then
1029          Append(options,moves[4]);
1030          if options=[] then
1031            Append(options,moves[2]);
1032            Append(options,moves[3]);
1033            if SCBistellarOptions.Relaxation=20 then
1034              SCBistellarOptions.Heating:=40;
1035              SCBistellarOptions.Relaxation:=0;
1036            fi;
1037            SCBistellarOptions.Relaxation:=SCBistellarOptions.Relaxation+1;
1038          fi;
1039        fi;
1040      fi;
1041    fi;
1042
1043  else
1044
1045    if SCBistellarOptions.Heating>0 then
1046      if IsInt(SCBistellarOptions.Heating/((dim+2)*SCBistellarOptions.BaseHeating))=true
1047        and dim>2 then
1048        Append(options,moves[1]);
1049      else
1050        for i in [1..Int((dim+1)/2)] do
1051          Append(options,moves[i+1]);
1052        od;
1053      fi;
1054      if options=[] then
1055        for i in [1..(dim+1)] do
1056          Append(options,moves[dim+2-i]);
1057          if options<>[] and i>=Int((dim+1)/2)-1 then
1058            break;
1059          fi;
1060        od;
1061      fi;
1062      SCBistellarOptions.Heating:=SCBistellarOptions.Heating-1;
1063    else
1064      if IsInt((dim+1)/2) then
1065        for i in [1..Int((dim+1)/2)] do
1066          Append(options,moves[dim+2-i]);
1067          if options<>[] then
1068            break;
1069          fi;
1070        od;
1071      else
1072        for i in [1..Minimum((Int((dim+1)/2)+1),(dim+1)-1)] do
1073          Append(options,moves[dim+2-i]);
1074          if options<>[] then
1075            break;
1076          fi;
1077        od;
1078      fi;
1079      if options=[] then
1080        for i in [1..Minimum((Int((dim+1)/2)+1),(dim+1)-1)] do
1081          Append(options,moves[i+1]);
1082          if options<>[] then
1083            break;
1084          fi;
1085        od;
1086      fi;
1087      if SCBistellarOptions.Relaxation=(dim+2)*SCBistellarOptions.BaseRelaxation then
1088        SCBistellarOptions.Heating:=(dim+2)*SCBistellarOptions.BaseHeating;
1089        SCBistellarOptions.Relaxation:=0;
1090      fi;
1091      SCBistellarOptions.Relaxation:=SCBistellarOptions.Relaxation+1;
1092    fi;
1093    options:=Set(options);
1094
1095  fi;
1096
1097  # choosing move at random
1098  if options=[] then
1099    return [];
1100  else
1101    return RandomList(options);
1102  fi;
1103
1104end;
1105
1106
1107################################################################################
1108##<#GAPDoc Label="SCExamineComplexBistellar">
1109## <ManSection>
1110## <Meth Name="SCExamineComplexBistellar" Arg="complex"/>
1111## <Returns> simplicial complex passed as argument with additional properties
1112## upon success, <K>fail</K> otherwise.</Returns>
1113## <Description>
1114## Computes the face lattice, the <M>f</M>-vector, the AS-determinant, the
1115## dimension and the maximal vertex label of <Arg>complex</Arg>.
1116## <Example>
1117## gap> obj:=SC([[1,2],[2,3],[3,4],[4,5],[5,6],[6,1]]);
1118## [SimplicialComplex
1119##
1120##  Properties known: Dim, Facets, Name, SCVertices.
1121##
1122##  Name="unnamed complex m"
1123##  Dim=1
1124##
1125## /SimplicialComplex]
1126## gap> SCExamineComplexBistellar(obj);
1127## [SimplicialComplex
1128##
1129##  Properties known: AltshulerSteinberg, Boundary, Chi, Dim, F, Faces, Facets,
1130##                    HasBoundary, IsPM, IsPure, Name, SCVertices.
1131##
1132##  Name="unnamed complex 21"
1133##  Dim=1
1134##  Chi=0
1135##  F=[ 6, 6 ]
1136##  HasBoundary=false
1137##  IsPM=true
1138##  IsPure=true
1139##
1140## /SimplicialComplex]
1141## </Example>
1142## </Description>
1143## </ManSection>
1144##<#/GAPDoc>
1145################################################################################
1146InstallMethod(SCExamineComplexBistellar,
1147"for SCSimplicialComplex",
1148[SCIsSimplicialComplex],
1149function(complex)
1150
1151  local dim, moves, faces, f,
1152        det, matrix, movable;
1153
1154
1155  movable := SCIsMovableComplex(complex);
1156  if movable = fail then
1157    return fail;
1158  fi;
1159  if not movable then
1160    Info(InfoSimpcomp,2,"SCExamineComplexBistellar: 'complex' not closed or ",
1161      "no pseudomanifold");
1162    return fail;
1163  fi;
1164  f:=SCFVector(complex);
1165  if f=fail then
1166    return fail;
1167  fi;
1168  det:=SCAltshulerSteinberg(complex);
1169  if det=fail then
1170    return fail;
1171  fi;
1172  dim:=SCDim(complex);
1173  if dim=fail then
1174    return fail;
1175  fi;
1176  moves:=SCMoves(complex);
1177  if moves=fail then
1178    return fail;
1179  fi;
1180
1181  return complex;
1182
1183end);
1184
1185
1186################################################################################
1187##<#GAPDoc Label="SCReduceComplexEx">
1188## <ManSection>
1189## <Func Name="SCReduceComplexEx" Arg="complex, refComplex,
1190## mode, choosemove"/>
1191## <Returns><C>SCBistellarOptions.WriteLevel=0</C>: a triple of the form
1192## <C>[ boolean, simplicial complex, rounds  ]</C> upon termination of the
1193## algorithm.<P/>
1194## <C>SCBistellarOptions.WriteLevel=1</C>: A library of simplicial complexes
1195## with a number of complexes from the reducing process and (upon termination)
1196## a triple of the form <C>[ boolean, simplicial complex, rounds ]</C>.<P/>
1197## <C>SCBistellarOptions.WriteLevel=2</C>: A mail in case a smaller version
1198## of <Arg>complex1</Arg> was found, a library of simplicial complexes with
1199## a number of complexes from the reducing process and (upon termination) a
1200## triple of the form <C>[ boolean, simplicial complex, rounds ]</C>.<P/>
1201## Returns <K>fail</K> upon an error.</Returns>
1202## <Description>
1203## Reduces a pure simplicial complex <Arg>complex</Arg> satisfying the weak
1204## pseudomanifold property via bistellar moves <Arg>mode = 0</Arg>, compares
1205## it to the simplicial complex <Arg>refComplex</Arg> (<Arg>mode = 1</Arg>) or
1206## reduces it as a sub-complex of <Arg>refComplex</Arg>
1207## (<Arg>mode = 2</Arg>).<P/>
1208## <Arg>choosemove</Arg> is a function containing a flip strategy, see also
1209## <Ref Func="SCIntFunc.SCChooseMove"/>. <P/>
1210## The currently smallest complex is stored to the variable <C>minComplex</C>,
1211## the currently smallest <M>f</M>-vector to <C>minF</C>. Note that in general
1212## the algorithm will not stop until the maximum number of rounds is reached.
1213## You can adjust the maximum number of rounds via the property
1214## <Ref Var="SCBistellarOptions"/>. The number of rounds performed is returned
1215## in the third entry of the triple returned by this function.<P/>
1216## This function is called by
1217## <Enum>
1218## <Item> <Ref Meth="SCReduceComplex" Style="Text"/>,</Item>
1219## <Item> <Ref Meth="SCEquivalent" Style="Text"/>,</Item>
1220## <Item> <Ref Meth="SCReduceAsSubcomplex" Style="Text"/>,</Item>
1221## <Item> <Ref Meth="SCBistellarIsManifold" Style="Text"/>.</Item>
1222## <Item> <Ref Meth="SCRandomize" Style="Text"/>.</Item>
1223## </Enum>
1224## Please see <Ref Func="SCMailIsPending"/> for further information about the
1225## email notification system in case <C>SCBistellarOptions.WriteLevel</C> is
1226## set to <M>2</M>.<P/>
1227## <Example>
1228## gap> c:=SCBdCrossPolytope(4);;
1229## gap> SCBistellarOptions.WriteLevel:=0;; # do not save complexes
1230## gap> SCReduceComplexEx(c,SCEmpty(),0,SCIntFunc.SCChooseMove);
1231## [ true, [SimplicialComplex
1232##
1233##      Properties known: Dim, Facets, Name, SCVertices.
1234##
1235##      Name="unnamed complex 14425"
1236##      Dim=3
1237##
1238##     /SimplicialComplex], 9 ]
1239## gap> SCReduceComplexEx(c,SCEmpty(),0,SCIntFunc.SCChooseMove);
1240## gap> SCMailSetAddress("johndoe@somehost");
1241## true
1242## gap> SCMailIsEnabled();
1243## true
1244## gap> SCReduceComplexEx(c,SCEmpty(),0,SCIntFunc.SCChooseMove);
1245## [ true, [SimplicialComplex
1246##
1247##      Properties known: Boundary, Chi, Date, Dim, F, Faces, Facets, G, H,
1248##                        HasBoundary, Homology, IsConnected, IsManifold, IsPM,
1249##                        Name, SCVertices, Vertices.
1250##
1251##      Name="ReducedComplex_5_vertices_9"
1252##      Dim=3
1253##      Chi=0
1254##      F=[ 5, 10, 10, 5 ]
1255##      G=[ 0, 0 ]
1256##      H=[ 1, 1, 1, 1 ]
1257##      HasBoundary=false
1258##      Homology=[ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ]
1259##      IsConnected=true
1260##      IsPM=true
1261##
1262##     /SimplicialComplex], 9 ]
1263## </Example>
1264## Content of sent mail:
1265## <Example> NOEXECUTE
1266## Greetings master,
1267##
1268## this is simpcomp 2.1.10 running on comp01.maths.fancytown.edu
1269##
1270## I have been working hard for 0 seconds and have a message for you, see below.
1271##
1272## #### START MESSAGE ####
1273##
1274## SCReduceComplex:
1275##
1276## Computed locally minimal complex after 7 rounds:
1277##
1278## [SimplicialComplex
1279##
1280##  Properties known: Boundary, Chi, Date, Dim, F, Faces, Facets, G, H,
1281##  HasBoundary, Homology, IsConnected, IsManifold, IsPM, Name, SCVertices,
1282##  Vertices.
1283##
1284##  Name="ReducedComplex_5_vertices_7"
1285##  Dim=3
1286##  Chi=0
1287##  F=[ 5, 10, 10, 5 ]
1288##  G=[ 0, 0 ]
1289##  H=[ 1, 1, 1, 1 ]
1290##  HasBoundary=false
1291##  Homology=[ [ 0, [ ] ], [ 0, [ ] ], [ 0, [ ] ], [ 1, [ ] ] ]
1292##  IsConnected=true
1293##  IsPM=true
1294##
1295## /SimplicialComplex]
1296##
1297## ##### END MESSAGE #####
1298##
1299## That's all, I hope this is good news! Have a nice day.
1300## </Example>
1301## </Description>
1302## </ManSection>
1303##<#/GAPDoc>
1304################################################################################
1305InstallGlobalFunction(SCReduceComplexEx,
1306  function(complex,refComplex,mode,choosemove)
1307
1308  local move,moves,validMoves,rounds,minF,name,globalRounds,minComplex,
1309    refFaces,msg,elapsed,stime,i,j,equivalent,time,rep,tmpFaces,tmpF,
1310    tmpOptions,dim,tmp,refF;
1311
1312  dim:=SCDim(complex);
1313  if dim = fail then
1314    return fail;
1315  fi;
1316
1317  if dim <= 0 then
1318    return [true,complex,0];
1319  fi;
1320
1321  SCBistellarOptions.Mode:=0;
1322  globalRounds:=0;
1323  rounds:=0;
1324  stime:=SCIntFunc.TimerStart();
1325
1326  if stime=fail then
1327    Info(InfoSimpcomp,1,"SCReduceComplexEx: can not start timer.");
1328    return fail;
1329  fi;
1330
1331  if SCBistellarOptions.WriteLevel>=1 then
1332    time:=SCIntFunc.GetCurrentTimeString();
1333    if(time=fail) then
1334      return fail;
1335    fi;
1336    # TODO: FIX: paths cannot be given like that
1337    rep:=SCLibInit(Concatenation(SCIntFunc.UserHome,"/reducedComplexes/",time));
1338  fi;
1339  equivalent:=false;
1340
1341  complex:=SCExamineComplexBistellar(complex);
1342  if complex=fail then
1343    Info(InfoSimpcomp,1,"SCReduceComplexEx: can not compute complex ",
1344      "properties.");
1345    return fail;
1346  fi;
1347
1348  minF:=SCIntFunc.DeepCopy(SCFVector(complex));
1349  if minF=fail then
1350    Info(InfoSimpcomp,1,"SCReduceComplexEx: error calculating f-vector.");
1351    return fail;
1352  fi;
1353
1354  minComplex:=complex;
1355
1356  #init moves
1357  tmpFaces:=SCIntFunc.DeepCopy(SCFaceLatticeEx(complex));
1358  if tmpFaces = fail then
1359    return fail;
1360  fi;
1361  tmpF:=ShallowCopy(SCFVector(complex));
1362  if tmpF = fail then
1363    return fail;
1364  fi;
1365
1366  tmpOptions:=[];
1367  for i in [1..dim+1] do
1368    tmpOptions[i]:=SCIntFunc.IRawBistellarRMoves(i-1,tmpFaces,dim+1);
1369    if tmpOptions[i]=fail then
1370      Info(InfoSimpcomp,1,"SCReduceComplexEx: no ",i-1,"-moves found.");
1371      return fail;
1372    fi;
1373    tmpOptions[i]:=SCIntFunc.IBistellarRMoves(i,dim+1,tmpOptions[i],tmpFaces);
1374  od;
1375
1376  if mode=2 then
1377    if not SCIsSubcomplex(refComplex,complex) then
1378      Info(InfoSimpcomp,1,"SCReduceComplexEx: complex is not a sub-complex.");
1379      return fail;
1380    fi;
1381
1382    refFaces:=SCFaceLatticeEx(refComplex);
1383    if refFaces=fail then
1384      return fail;
1385    fi;
1386  fi;
1387
1388  if mode = 1 then
1389    refF:=SCFVector(refComplex);
1390
1391    if refF=fail then
1392      return fail;
1393    fi;
1394  fi;
1395
1396
1397
1398  #loop..
1399  while rounds < SCBistellarOptions.MaxInterval and
1400    globalRounds < SCBistellarOptions.MaxRounds do
1401
1402    if mode=1 then
1403      if tmpF = refF then
1404        equivalent:=SCIsIsomorphic(SCFromFacets(tmpFaces[dim+1]),refComplex);
1405      fi;
1406      if equivalent=fail then
1407        Info(InfoSimpcomp,1,"SCReduceComplexEx: can not compute isomorphism ",
1408          "between complexes.");
1409        return fail;
1410      fi;
1411    fi;
1412
1413    if mode<>1 or equivalent=false then
1414      if mode=2 then
1415        # remove bistellar moves that can't be performed in supercomplex
1416        # 'refComplex'
1417        validMoves:=[];
1418        validMoves[1]:=[];
1419        for i in [2..Size(tmpOptions)] do
1420          validMoves[i]:=[];
1421          for move in tmpOptions[i] do
1422            if move[2] in refFaces[Size(move[2])] then
1423              Add(validMoves[i],move);
1424            fi;
1425          od;
1426        od;
1427        tmpOptions:=validMoves;
1428      fi;
1429
1430      #choose a move
1431#      move:=choosemove(dim,tmpOptions,tmpF,globalRounds);
1432      move:=choosemove(dim,tmpOptions);
1433      if move=fail then
1434        Info(InfoSimpcomp,1,"SCReduceComplexEx: error in flip strategy.");
1435        return fail;
1436      fi;
1437
1438      if move<>[] then
1439        #move length
1440        i:=Length(move[2]);
1441        if(i>0) then
1442          i:=i-1;
1443        fi;
1444
1445        #do move
1446        tmp:=SCIntFunc.Move(i,dim+1,tmpFaces,tmpF,move,tmpOptions,1,[]);
1447
1448        tmpFaces:=tmp[1];
1449        tmpF:=tmp[2];
1450
1451        for i in [1..dim+1] do
1452          tmpOptions[i]:=SCIntFunc.IBistellarRMoves(i,dim+1,tmp[3][i],tmpFaces);
1453        od;
1454
1455        Info(InfoSimpcomp,3,"round ",globalRounds,", move: ",move,"\nF: ",tmpF);
1456        rounds:=rounds+1;
1457
1458        if tmpF<minF then
1459          rounds := 0;
1460          minComplex:=SCFromFacets(tmpFaces[dim+1]);
1461
1462          if minComplex=fail then
1463            return fail;
1464          fi;
1465
1466          Info(InfoSimpcomp,2,"round ",globalRounds,"\nReduced complex, F: ",tmpF);
1467
1468          if tmpF[1]<minF[1] or rounds>SCBistellarOptions.MaxInterval then
1469            if SCBistellarOptions.WriteLevel>=1 then
1470              name:=Concatenation(["ReducedComplex_",String(tmpF[1]),
1471                "_vertices_",String(globalRounds)]);
1472              if minComplex<>fail and name<>fail and rep<>fail then
1473                SCRename(minComplex,name);
1474                SCLibAdd(rep,minComplex);
1475              else
1476                Info(InfoSimpcomp,1,"SCReduceComplexEx: illegal complex, ",
1477                  "name or rep.");
1478                return fail;
1479              fi;
1480            fi;
1481            if SCBistellarOptions.WriteLevel=2 then
1482              msg:=Concatenation(["SCReduceComplex:\n\nReduced complex after ",
1483                String(globalRounds)," rounds:\n\n",String(minComplex),"\n"]);
1484              SCMailSend(msg,stime);
1485            fi;
1486          fi;
1487          minF:=ShallowCopy(tmpF);
1488        fi;
1489
1490        globalRounds:=globalRounds+1;
1491
1492        if(globalRounds mod 1000000=0 and SCBistellarOptions.WriteLevel=2) then
1493          elapsed:=SCIntFunc.TimerElapsed();
1494          if elapsed=fail then
1495            return fail;
1496          fi;
1497          if(SCIntFunc.TimerElapsed()>=SCBistellarOptions.MailNotifyInterval) then
1498            SCIntFunc.TimerStart();
1499            msg:=Concatenation(["SCReduceComplex:\n\nStatus report after ",
1500              String(globalRounds)," rounds:\n\n",String(minComplex),
1501              "\n\nMinimal complex so far:\n\n",String(minComplex)]);
1502            SCMailSend(msg,stime);
1503          fi;
1504        fi;
1505
1506      else
1507        # no moves available
1508        if SCBistellarOptions.WriteLevel>=1 then
1509          name:=Concatenation(["ReducedComplex_",String(tmpF[1]),"_vertices_",
1510            String(globalRounds)]);
1511          SCRename(minComplex,name);
1512          SCLibAdd(rep,minComplex);
1513        fi;
1514        if SCBistellarOptions.WriteLevel=2 then
1515          msg:=Concatenation(["SCReduceComplex:\n\nComputed locally minimal ",
1516            "complex after ",String(globalRounds)," rounds:\n\n",
1517            String(minComplex),"\n"]);
1518          SCMailClearPending();
1519          SCMailSend(msg,stime,true);
1520        fi;
1521        if mode=1 then
1522          Info(InfoSimpcomp,1,"SCReduceComplexEx: could not prove bistellar ",
1523            "equivalence between 'complex' and 'refComplex'\n(reached local ",
1524            "minimum after  ",String(globalRounds)," rounds).");
1525        elif mode<>1 then
1526          Info(InfoSimpcomp,2,"SCReduceComplexEx: computed locally minimal ",
1527            "complex after ",String(globalRounds)," rounds.");
1528        fi;
1529
1530        if mode=1 then
1531          return [fail,minComplex,globalRounds];
1532        elif mode=3 then
1533          return [fail,SCFromFacets(tmpFaces[dim+1]),globalRounds];
1534        else
1535          return [true,minComplex,globalRounds];
1536        fi;
1537      fi;
1538    else
1539      # equivalent<>false and mode=1 -> bistellarly equivalent
1540      if SCBistellarOptions.WriteLevel>=1 then
1541        name:=Concatenation(["ReducedComplex_",String(tmpF[1]),"_vertices_",
1542          String(globalRounds)]);
1543        SCRename(minComplex,name);
1544        SCLibAdd(rep,minComplex);
1545      fi;
1546
1547      if SCBistellarOptions.WriteLevel=2 then
1548        msg:=Concatenation(["SCReduceComplexEx:\n\nComplexes are bistellarly ",
1549          "equivalent.\n\n",String(minComplex),"\n"]);
1550        SCMailClearPending();
1551        SCMailSend(msg,stime,true);
1552      fi;
1553      if mode=1 then
1554        Info(InfoSimpcomp,1,"SCReduceComplexEx: complexes are bistellarly ",
1555          "equivalent.");
1556      fi;
1557
1558      if mode <> 3 then
1559        return [true,minComplex,globalRounds];
1560      else
1561        return [true,SCFromFacets(tmpFaces[dim+1]),globalRounds];
1562      fi;
1563    fi;
1564  od;
1565
1566  if SCBistellarOptions.WriteLevel>=1 then
1567    name:=Concatenation(["ReducedComplex_",String(tmpF[1]),"_vertices_",
1568      String(globalRounds)]);
1569    SCRename(minComplex,name);
1570    SCLibAdd(rep,minComplex);
1571  fi;
1572
1573  if SCBistellarOptions.WriteLevel=2 then
1574    msg:=Concatenation(["SCReduceComplexEx:\n\nReached maximal number of ",
1575      "rounds ",String(globalRounds)," rounds. Reduced complex to:\n\n",
1576        String(minComplex),"\n"]);
1577    SCMailClearPending();
1578    SCMailSend(msg,stime,true);
1579  fi;
1580
1581  if mode=1 then
1582    Info(InfoSimpcomp,1,"SCReduceComplexEx: could not prove bistellar ",
1583      "equivalence between 'complex' and 'refComplex'.");
1584  elif mode<>1 and mode <> 3 then
1585    Info(InfoSimpcomp,2,"SCReduceComplexEx: reached maximal number of ",
1586      "rounds. Returning smallest complex found.");
1587  fi;
1588
1589  if mode <> 3 then
1590#    return [fail,minComplex,globalRounds];
1591    return [fail,SC(tmpFaces[dim+1]),globalRounds];
1592  else
1593    return [fail,SCFromFacets(tmpFaces[dim+1]),globalRounds];
1594  fi;
1595
1596end);
1597
1598################################################################################
1599##<#GAPDoc Label="SCReduceComplex">
1600## <ManSection>
1601## <Meth Name="SCReduceComplex" Arg="complex"/>
1602## <Returns> <C>SCBistellarOptions.WriteLevel=0</C>: a triple of the form
1603## <C>[ boolean, simplicial complex, rounds performed ]</C> upon termination
1604## of the algorithm.<P/>
1605## <C>SCBistellarOptions.WriteLevel=1</C>: A library of simplicial complexes
1606## with a number of complexes from the reducing process and (upon termination)
1607## a triple of the form
1608## <C>[ boolean, simplicial complex, rounds performed ]</C>.<P/>
1609## <C>SCBistellarOptions.WriteLevel=2</C>: A mail in case a smaller version
1610## of <Arg>complex1</Arg> was found, a library of simplicial complexes with a
1611## number of complexes from the reducing process and (upon termination) a
1612## triple of the form
1613## <C>[ boolean, simplicial complex, rounds performed ]</C>.<P/>
1614## Returns <K>fail</K> upon an error..</Returns>
1615## <Description>
1616## Reduces a pure simplicial complex <Arg>complex</Arg> satisfying the weak
1617## pseudomanifold property via bistellar moves.
1618## Internally calls <Ref Func="SCReduceComplexEx" Style="Text" />
1619## <C>(complex,SCEmpty(),0,SCIntFunc.SCChooseMove);</C>
1620## <Example>
1621## gap> obj:=SC([[1,2],[2,3],[3,4],[4,5],[5,6],[6,1]]);; # hexagon
1622## gap> SCBistellarOptions.WriteLevel:=0;; # do not save complexes
1623## gap> tmp := SCReduceComplex(obj);
1624## #I  round 0, move: [ [ 6 ], [ 1, 5 ] ]
1625## [ 5, 5 ]
1626## #I  round 1, move: [ [ 4 ], [ 3, 5 ] ]
1627## [ 4, 4 ]
1628## #I  round 2, move: [ [ 3 ], [ 2, 5 ] ]
1629## [ 3, 3 ]
1630## #I  SCReduceComplexEx: computed locally minimal complex after 3 rounds.
1631## [ true, [SimplicialComplex
1632##
1633##      Properties known: Dim, Facets, Name, SCVertices.
1634##
1635##      Name="unnamed complex 6"
1636##      Dim=1
1637##
1638##     /SimplicialComplex], 3 ]
1639## </Example>
1640## </Description>
1641## </ManSection>
1642##<#/GAPDoc>
1643################################################################################
1644InstallMethod(SCReduceComplex,
1645"for SCSimplicialComplex",
1646[SCIsSimplicialComplex],
1647function(complex)
1648  return SCReduceComplexEx(complex,SCEmpty(),0,SCIntFunc.SCChooseMove);
1649end);
1650
1651
1652################################################################################
1653##<#GAPDoc Label="SCEquivalent">
1654## <ManSection>
1655## <Meth Name="SCEquivalent" Arg="complex1, complex2"/>
1656## <Returns> <K>true</K> or <K>false</K> upon success, <K>fail</K> or a list
1657## of type <C>[ fail, SCSimplicialComplex, Integer, facet list]</C>
1658## otherwise.</Returns>
1659## <Description>
1660## Checks if the simplicial complex <Arg>complex1</Arg> (which has to fulfill
1661## the weak pseudomanifold property with empty boundary) can be reduced to the
1662## simplicial complex <Arg>complex2</Arg> via bistellar moves, i. e. if
1663## <Arg>complex1</Arg> and <Arg>complex2</Arg> are <M>PL</M>-homeomorphic.
1664## Note that in general the problem is undecidable. In this case <K>fail</K>
1665## is returned.<P/>
1666## It is recommended to use a minimal triangulation <Arg>complex2</Arg> for
1667## the check if possible.<P/>
1668## Internally calls <Ref Func="SCReduceComplexEx" Style="Text"/>
1669## <C>(complex1,complex2,1,SCIntFunc.SCChooseMove);</C>
1670## <Example>
1671## gap> SCBistellarOptions.WriteLevel:=0;; # do not save complexes to disk
1672## gap> obj:=SC([[1,2],[2,3],[3,4],[4,5],[5,6],[6,1]]);; # hexagon
1673## gap> refObj:=SCBdSimplex(2);; # triangle as a (minimal) reference object
1674## gap> SCEquivalent(obj,refObj);
1675## #I  round 0: [ 5, 5 ]
1676## #I  round 1: [ 4, 4 ]
1677## #I  round 2: [ 3, 3 ]
1678## #I  SCReduceComplexEx: complexes are bistellarly equivalent.
1679## true
1680## </Example>
1681## </Description>
1682## </ManSection>
1683##<#/GAPDoc>
1684################################################################################
1685InstallMethod(SCEquivalent,
1686"for SCSimplicialComplex and SCSimplicialComplex",
1687[SCIsSimplicialComplex,SCIsSimplicialComplex],
1688function(complex1, complex2)
1689
1690  local dim1, dim2, pm1, pm2, hom1, hom2, ret;
1691
1692  dim1:=SCDim(complex1);
1693  if dim1=fail then
1694    return fail;
1695  fi;
1696  dim2:=SCDim(complex2);
1697  if dim2=fail then
1698    return fail;
1699  fi;
1700  if dim1<>dim2 then
1701    return false;
1702  fi;
1703  pm1:=SCIsMovableComplex(complex1);
1704  if pm1=fail then
1705    return fail;
1706  fi;
1707  pm2:=SCIsMovableComplex(complex2);
1708  if pm2=fail then
1709    return fail;
1710  fi;
1711  if pm1<>pm2 then
1712    return false;
1713  fi;
1714  if pm1=false then
1715    Info(InfoSimpcomp,2,"SCEquivalent: complexes should be closed ",
1716      "pseudomanifolds");
1717    return fail;
1718  fi;
1719  hom1:=SCHomology(complex1);
1720  if hom1=fail then
1721    return fail;
1722  fi;
1723  hom2:=SCHomology(complex2);
1724  if hom2=fail then
1725    return fail;
1726  fi;
1727  if hom1<>hom2 then
1728    return false;
1729  fi;
1730
1731  ret:=SCReduceComplexEx(complex1,complex2,1,SCIntFunc.SCChooseMove);
1732
1733  if(ret<>fail) then
1734    return ret[1];
1735  else
1736    return fail;
1737  fi;
1738
1739end);
1740
1741################################################################################
1742##<#GAPDoc Label="SCReduceAsSubcomplex">
1743## <ManSection>
1744## <Meth Name="SCReduceAsSubcomplex" Arg="complex1, complex2"/>
1745## <Returns> <C>SCBistellarOptions.WriteLevel=0</C>: a triple of the form
1746## <C>[ boolean, simplicial complex, rounds performed  ]</C> upon termination
1747## of the algorithm.<P/>
1748## <C>SCBistellarOptions.WriteLevel=1</C>: A library of simplicial complexes
1749## with a number of complexes from the reducing process and (upon termination)
1750## a triple of the form
1751## <C>[ boolean, simplicial complex, rounds performed ]</C>.<P/>
1752## <C>SCBistellarOptions.WriteLevel=2</C>: A mail in case a smaller version of
1753## <Arg>complex1</Arg> was found, a library of simplicial complexes with a
1754## number of complexes from the reducing process and (upon termination) a
1755## triple of the form
1756## <C>[ boolean, simplicial complex, rounds performed ]</C>.<P/>
1757## Returns <K>fail</K> upon an error.</Returns>
1758## <Description>
1759## Reduces a  simplicial complex <Arg>complex1</Arg> (satisfying the weak
1760## pseudomanifold property with empty boundary) as a sub-complex of the
1761## simplicial complex <Arg>complex2</Arg>. <P/>
1762## Main application: Reduce a sub-complex of the cross polytope without
1763## introducing diagonals.
1764## <P/>
1765## Internally calls <Ref Func="SCReduceComplexEx" Style="Text"  />
1766## <C>(complex1,complex2,2,SCIntFunc.SCChooseMove);</C>
1767## <Example>
1768## gap> c:=SCFromFacets([[1,3],[3,5],[4,5],[4,1]]);;
1769## gap> SCBistellarOptions.WriteLevel:=0;; # do not save complexes
1770## gap> SCReduceAsSubcomplex(c,SCBdCrossPolytope(3));
1771## #I  round 0, move: [ [ 2 ], [ 1, 4 ] ]
1772## [ 3, 3 ]
1773## #I  SCReduceComplexEx: computed locally minimal complex after 1 rounds.
1774## [ true, [SimplicialComplex
1775##
1776##      Properties known: Dim, Facets, Name, SCVertices.
1777##
1778##      Name="unnamed complex 9"
1779##      Dim=1
1780##
1781##     /SimplicialComplex], 1 ]
1782##</Example>
1783##</Description>
1784## </ManSection>
1785##<#/GAPDoc>
1786################################################################################
1787InstallMethod(SCReduceAsSubcomplex,
1788"for SCSimplicialComplex and SCSimplicialComplex",
1789[SCIsSimplicialComplex,SCIsSimplicialComplex],
1790function(complex1, complex2)
1791
1792  return SCReduceComplexEx(complex1,complex2,2,SCIntFunc.SCChooseMove);
1793
1794end);
1795
1796################################################################################
1797##<#GAPDoc Label="SCBistellarIsManifold">
1798## <ManSection>
1799## <Meth Name="SCBistellarIsManifold" Arg="complex"/>
1800## <Returns><K>true</K> or <K>false</K> upon success, <K>fail</K>
1801## otherwise.</Returns>
1802## <Description>
1803## Tries to prove that a closed simplicial <M>d</M>-pseudomanifold is a
1804## combinatorial manifold by reducing its vertex links to the boundary of the
1805## d-simplex.<P/>
1806## <K>false</K> is returned if it can be proven that there exists a vertex link
1807## which is not PL-homeomorphic to the standard PL-sphere, <K>true</K> is
1808## returned if all vertex links are bistellarly equivalent to the boundary of
1809## the simplex, <K>fail</K> is returned if the algorithm does not terminate
1810## after the number of rounds indicated by
1811## <C>SCBistellarOptions.MaxIntervallIsManifold</C>.<P/>
1812## Internally calls <Ref Func="SCReduceComplexEx" Style="Text"/>
1813## <C>(link,SCEmpty(),0,SCIntFunc.SCChooseMove);</C> for every link of
1814## <Arg>complex</Arg>. Note that <K>false</K> is returned in case of a bounded
1815## manifold.<P/>
1816##
1817## See <Ref Func="SCIsManifoldEx" /> and <Ref Func="SCIsManifold" /> for
1818## alternative methods for manifold verification.
1819## <Example>
1820## gap> c:=SCBdCrossPolytope(3);;
1821## gap> SCBistellarIsManifold(c);
1822## #I  SCBistellarIsManifold: processing vertex link 1/6
1823## #I  round 0: [ 3, 3 ]
1824## #I  SCReduceComplexEx: computed locally minimal complex after 1 rounds.
1825## #I  SCBistellarIsManifold: link is sphere.
1826## ...
1827## #I  SCBistellarIsManifold: processing vertex link 6/6
1828## #I  round 0: [ 3, 3 ]
1829## #I  SCReduceComplexEx: computed locally minimal complex after 1 rounds.
1830## #I  SCBistellarIsManifold: link is sphere.
1831## true
1832## </Example>
1833## </Description>
1834## </ManSection>
1835##<#/GAPDoc>
1836################################################################################
1837InstallGlobalFunction(SCBistellarIsManifold,
1838function(complex)
1839
1840  local links, result, f, linkidx, verts, writelevel, maxrounds,
1841    type, movable, dim, manifold, im,t;
1842
1843  if HasSCIsManifold(complex) then
1844    return SCIsManifold(complex);
1845  fi;
1846
1847  dim :=SCDim(complex);
1848  if dim = fail then
1849    return fail;
1850  fi;
1851  verts:=SCVertices(complex);
1852  if verts=fail then
1853    Info(InfoSimpcomp,2,"SCBistellarIsManifold: complex has no vertex labels.");
1854    return fail;
1855  fi;
1856
1857  if SCIsEmpty(complex) then
1858    Info(InfoSimpcomp,2,"SCBistellarIsManifold: complex is empty.");
1859      SetSCIsManifold(complex,false);
1860      return false;
1861  fi;
1862  if dim = 0 then
1863    im:=Size(verts)=2;
1864      SetSCIsManifold(complex,im);
1865      return im;
1866  fi;
1867
1868  links:=SCLinks(complex,0);
1869  if fail in links then
1870    return fail;
1871  fi;
1872
1873  maxrounds:=SCBistellarOptions.MaxInterval;
1874  SCBistellarOptions.MaxInterval:=SCBistellarOptions.MaxIntervalIsManifold;
1875  writelevel:=SCBistellarOptions.WriteLevel;
1876  SCBistellarOptions.WriteLevel:=0;
1877
1878  for linkidx in [1..Length(links)] do
1879
1880    SCRelabelStandard(links[linkidx]);
1881    Info(InfoSimpcomp,2,"SCBistellarIsManifold: processing vertex link ",
1882      verts[linkidx],"/",Length(verts));
1883    f:=links[linkidx].F[1];
1884    if f = fail then
1885      return fail;
1886    fi;
1887    if dim = 1 and f = 2 then
1888      continue;
1889    elif dim = 1 and f <> 2 then
1890      Info(InfoSimpcomp,2,"SCBistellarIsManifold: link is no sphere.");
1891      SetSCIsManifold(complex,false);
1892      return false;
1893    fi;
1894
1895    movable:=SCIsMovableComplex(links[linkidx]);
1896    if movable = fail then
1897      Info(InfoSimpcomp,2,"SCBistellarIsManifold: complex check failed. ",
1898        "Invalid link.");
1899      return fail;
1900    fi;
1901
1902    if movable then
1903      result:=SCReduceComplexEx(links[linkidx],SCEmpty(),0,
1904        SCIntFunc.SCChooseMove);
1905    else
1906      Info(InfoSimpcomp,2,"SCBistellarIsManifold: link ",linkidx,
1907        " is not a closed pseudomanifold.");
1908      SetSCIsManifold(complex,false);
1909      return false;
1910    fi;
1911
1912    if result=fail then
1913      Info(InfoSimpcomp,1,"SCBistellarIsManifold: SCReduceComplexEx ",
1914        "returned fail.");
1915      return fail;
1916    fi;
1917
1918    if result[1]=true then
1919      f:=SCFVector(result[2]);
1920      if f = fail then
1921        return fail;
1922      fi;
1923      if f[1]<>f[Size(f)] or f[1]<>(Size(f)+1) then
1924        Info(InfoSimpcomp,2,"SCBistellarIsManifold: link is no sphere.");
1925        type:=SCLibDetermineTopologicalType(SCLib,result[2]);
1926        if type<>fail and type<>[] then
1927          if(Length(type)=1) then
1928            Info(InfoSimpcomp,2,"SCBistellarIsManifold: link is the following ",
1929              "complex:\n",type,".");
1930          else
1931            Info(InfoSimpcomp,2,"SCBistellarIsManifold: link could be PL ",
1932              "equivalnet to one of the following complexes specified by ",
1933              "their global library ids:\n",type,".");
1934          fi;
1935        else
1936          Info(InfoSimpcomp,2,"SCBistellarIsManifold: link is not in global ",
1937            "library.");
1938        fi;
1939        SetSCIsManifold(complex,false);
1940        return false;
1941      else
1942        Info(InfoSimpcomp,2,"SCBistellarIsManifold: link is sphere.");
1943        if HasSCAutomorphismGroupTransitivity(complex) and
1944          SCAutomorphismGroupTransitivity(complex)>0 then
1945          Info(InfoSimpcomp,2,"SCBistellarIsManifold: transitive automorphism ",
1946            "group, checking only one link.");
1947          SetSCIsManifold(complex,true);
1948          return true;
1949        fi;
1950      fi;
1951    else
1952      Info(InfoSimpcomp,2,"SCBistellarIsManifold: maximum rounds reached, ",
1953        "check link ",linkidx,".");
1954      return fail;
1955    fi;
1956  od;
1957
1958  SCBistellarOptions.MaxInterval:=maxrounds;
1959  SCBistellarOptions.WriteLevel:=writelevel;
1960  SetSCIsManifold(complex,true);
1961  return true;
1962
1963end);
1964
1965################################################################################
1966##<#GAPDoc Label="SCIsKStackedSphere">
1967## <ManSection>
1968## <Meth Name="SCIsKStackedSphere" Arg="complex, k"/>
1969## <Returns>a list upon success, <K>fail</K> otherwise.</Returns>
1970## <Description>
1971## Checks, whether the given simplicial complex <Arg>complex</Arg> that must
1972## be a PL <M>d</M>-sphere is a <Arg>k</Arg>-stacked sphere with
1973## <M>1\leq k\leq \lfloor\frac{d+2}{2}\rfloor</M> using a randomized algorithm
1974## based on bistellar moves (see
1975## <Cite Key="Effenberger09StackPolyTightTrigMnf" />,
1976## <Cite Key="Effenberger10Diss" />). Note that it is not checked whether
1977## <Arg>complex</Arg> is a PL sphere -- if not, the algorithm will not succeed.
1978## Returns a list upon success: the first entry is a boolean, where
1979## <K>true</K>  means that the complex is <C>k</C>-stacked and <K>false</K>
1980## means that the complex cannot be <Arg>k</Arg>-stacked. A value of -1 means
1981## that the question could not be decided. The second argument contains a
1982## simplicial complex that, in case of success, contains the trigangulated
1983## <M>(d+1)</M>-ball <M>B</M> with <M>\partial B=S</M> and
1984## <M>\operatorname{skel}_{d-k}(B)=\operatorname{skel}_{d-k}(S)</M>,
1985## where <M>S</M> denotes the simplicial complex passed in
1986## <Arg>complex</Arg>.<P/>
1987## Internally calls <Ref Func="SCReduceComplexEx" Style="Text" />.
1988## <Example>
1989## gap> SCLib.SearchByName("S^4~S^1");
1990## [ [ 204, "S^4~S^1 (VT)" ], [ 339, "S^4~S^1 (VT)" ], [ 341, "S^4~S^1 (VT)" ],
1991##   [ 438, "S^4~S^1 (VT)" ], [ 493, "S^4~S^1 (VT)" ], [ 494, "S^4~S^1 (VT)" ],
1992##   [ 495, "S^4~S^1 (VT)" ], [ 496, "S^4~S^1 (VT)" ], [ 497, "S^4~S^1 (VT)" ],
1993##   [ 500, "S^4~S^1 (VT)" ], [ 501, "S^4~S^1 (VT)" ], [ 502, "S^4~S^1 (VT)" ] ]
1994## gap> c:=SCLib.Load(last[1][1]);;
1995## gap> l:=SCLink(c,1);
1996## [SimplicialComplex
1997##
1998##  Properties known: Dim, Facets, Name, SCVertices.
1999##
2000##  Name="lk(1) in S^4~S^1 (VT)"
2001##  Dim=4
2002##
2003## /SimplicialComplex]
2004## gap> SCIsKStackedSphere(l,1);
2005## #I  SCIsKStackedSphere: try 1/50
2006## #I  round 0: [ 11, 40, 70, 65, 26 ]
2007## #I  round 1: [ 10, 35, 60, 55, 22 ]
2008## #I  round 2: [ 9, 30, 50, 45, 18 ]
2009## #I  round 3: [ 8, 25, 40, 35, 14 ]
2010## #I  round 4: [ 7, 20, 30, 25, 10 ]
2011## #I  round 5: [ 6, 15, 20, 15, 6 ]
2012## #I  SCReduceComplexEx: computed locally minimal complex after 6 rounds.
2013## 1
2014## </Example>
2015## </Description>
2016## </ManSection>
2017##<#/GAPDoc>
2018################################################################################
2019InstallMethod(SCIsKStackedSphereOp,
2020"for SCSimplicialComplex and Int",
2021[SCIsSimplicialComplex,IsPosInt],
2022function(complex,k)
2023
2024  local d, f, h, links, result, linkidx, verts, writelevel, maxrounds,
2025    type, movable, ks, cc, try, maxtries, kStackedStrategy, ball, tmp, l, i;
2026
2027
2028  kStackedStrategy:=function(dim,moves)
2029    local options,i,tmp;
2030
2031    #allow reverse 0..(k-1)-moves
2032    options:=[];
2033    for i in [0..k-1] do
2034      Append(options,moves[dim+1-i]);
2035    od;
2036
2037    #choose move at random
2038    if options=[] then
2039      return [];
2040    else
2041      tmp:=RandomList(options);
2042      #save move to reconstruct filled sphere later
2043      Add(ball,Union(tmp));
2044      return tmp;
2045    fi;
2046  end;
2047
2048  if(k <= 0 or k > Int((SCDim(complex)+2)/2)) then
2049    Info(InfoSimpcomp,1,"SCIsKStackedSphere: second argument must be a ",
2050      "positive integer k with 1 <= k <= \\lfloor ",
2051      "(SCDim(complex)+2)/2 \\rfloor.");
2052    return fail;
2053  fi;
2054
2055  if HasComputedSCIsKStackedSpheres(complex) then
2056    l:=ComputedSCIsKStackedSpheres(complex);
2057  fi;
2058  for i in [1..Size(l)] do
2059    if not IsBound(l[i]) then
2060      continue;
2061    fi;
2062    if IsList(l[i]) and l[i][1] = true then
2063      if IsBound(l[i-1]) and l[i-1] <= k then
2064        Info(InfoSimpcomp,1,"SCIsKStackedSphere: complex is even (at least) a ",
2065          l[i-1],"-stacked sphere.");
2066        return l[i];
2067      fi;
2068      break;
2069    fi;
2070  od;
2071
2072
2073  d:=SCDim(complex);
2074  f:=SCFVector(complex);
2075  h:=SCIsHomologySphere(complex);
2076
2077  if(d=fail or h=fail or f=fail) then
2078    Info(InfoSimpcomp,1,"SCIsKStackedSphere: error computing dimension, f-vector, or homology.");
2079    return fail;
2080  fi;
2081
2082  if(h<>true) then
2083    Info(InfoSimpcomp,1,"SCIsKStackedSphere: first argument must be a PL ",
2084      "manifold -- passed complex is not even a homology sphere.");
2085    return [false,SCEmpty()];
2086  fi;
2087
2088  #set bistellar flip options
2089  maxrounds:=Sum(f)*10;
2090  SCBistellarOptions.MaxInterval:=SCBistellarOptions.MaxIntervalIsManifold;
2091  writelevel:=SCBistellarOptions.WriteLevel;
2092  SCBistellarOptions.WriteLevel:=0;
2093
2094  Info(InfoSimpcomp,1,"SCIsKStackedSphere: checking if complex is a ",
2095    k,"-stacked sphere...");
2096
2097  if k = 1 then
2098    maxtries:=1;
2099  else
2100    maxtries:=50;
2101  fi;
2102  for try in [1..maxtries] do
2103
2104    cc:=SCCopy(complex);
2105    SCRelabelStandard(cc);
2106
2107    Info(InfoSimpcomp,1,Concatenation("SCIsKStackedSphere: try ",
2108      String(try),"/",String(maxtries)));
2109
2110    movable:=SCIsMovableComplex(cc);
2111    if movable = fail then
2112      Info(InfoSimpcomp,1,"SCIsKStackedSphere: invalid complex.");
2113      return fail;
2114    fi;
2115
2116    if movable then
2117      ball:=[]; #construct ball with skel_d-k(ball)=skel_d-k(sphere)
2118      result:=SCReduceComplexEx(cc,SCEmpty(),0,kStackedStrategy);
2119    else
2120      Info(InfoSimpcomp,1,"SCIsKStackedSphere: complex is not a closed ",
2121        "pseudomanifold.");
2122          return [false,SCEmpty()];
2123    fi;
2124
2125    if result=fail then
2126      Info(InfoSimpcomp,1,"SCIsKStackedSphere: SCReduceComplexEx ",
2127        "returned fail.");
2128      return fail;
2129    fi;
2130
2131
2132    if result[1]=true then
2133      f:=SCFVector(result[2]);
2134
2135      if(f=fail) then
2136        return fail;
2137      fi;
2138
2139      if (result[3]=0 and f[1]<>d+2) or (k=1 and f[1]<>d+2) then
2140        #could not reduce to boundary of a simplex. not k-stacked?
2141        Info(InfoSimpcomp,1,"SCIsKStackedSphere: complex is not a ",
2142          k,"-stacked sphere.");
2143          return [false,SCEmpty()];
2144      fi;
2145
2146      if f[1]=d+2 and f[1]=f[Size(f)] then
2147        #reduced to boundary of a simplex. k-stacked.
2148        Info(InfoSimpcomp,1,"SCIsKStackedSphere: complex is a ",
2149          k,"-stacked sphere.");
2150        tmp:=SCFacets(result[2]); #get facets of reduced complex
2151        if(tmp=fail) then
2152          return fail;
2153        fi;
2154
2155        #add last simplex to ball = filled sphere
2156        ball:=Set(ball);
2157        AddSet(ball,Union(tmp));
2158
2159        ball:=SCFromFacets(ball);
2160
2161        if(ball=fail) then
2162          Info(InfoSimpcomp,1,"SCIsKStackedSphere: something is wrong with ",
2163            "the facet list of the constructed ball that should be a filled ",
2164            "version of the sphere passed as complex. Please contact the ",
2165            "authors/maintainers of simpcomp.");
2166          return fail;
2167        fi;
2168
2169        SCRename(ball,Concatenation("Filled ",String(k),"-stacked sphere (",
2170          String(SCName(complex)),")"));
2171        return [true,ball];
2172      fi;
2173    fi;
2174  od;
2175
2176  SCBistellarOptions.MaxInterval:=maxrounds;
2177  SCBistellarOptions.WriteLevel:=writelevel;
2178
2179  Info(InfoSimpcomp,1,"SCIsKStackedSphere: could not determine whether ",
2180    "given complex is a ",k,"-stacked sphere.");
2181  return fail;
2182end);
2183
2184################################################################################
2185##<#GAPDoc Label="SCRandomize">
2186## <ManSection>
2187## <Func Name="SCRandomize" Arg="complex [ [, rounds] [,allowedmoves] ]"/>
2188## <Returns>a simplicial complex upon success, <K>fail</K> otherwise.</Returns>
2189## <Description>
2190## Randomizes the given simplicial complex <Arg>complex</Arg> via bistellar
2191## moves chosen at random. By passing the optional array
2192## <Arg>allowedmoves</Arg>, which has to be a dense array of integer values
2193## of length <C>SCDim(complex)</C>, certain moves can be allowed or forbidden
2194## in the proccess. An entry <C>allowedmoves[i]=1</C> allows <M>(i-1)</M>-moves
2195## and an entry <C>allowedmoves[i]=0</C> forbids <M>(i-1)</M>-moves in the
2196## randomization process.<P />With optional positive integer argument
2197## <Arg>rounds</Arg>, the amount of randomization can be controlled. The
2198## higher the value of <Arg>rounds</Arg>, the more bistellar moves will be
2199## randomly performed on <Arg>complex</Arg>. Note that the argument
2200## <Arg>rounds</Arg> overrides the global setting
2201## <C>SCBistellarOptions.MaxIntervalRandomize</C> (this value is used, if
2202## <Arg>rounds</Arg> is not specified).
2203## Internally calls <Ref Func="SCReduceComplexEx" Style="Text" />.
2204## <Example>
2205## gap> c:=SCRandomize(SCBdSimplex(4));
2206## #I  SCRandomize: randomizing complex S^3_5 with allowed moves [ -1, 1, 1, 1 ]
2207## [SimplicialComplex
2208##
2209##  Properties known: Dim, Facets, Name, SCVertices.
2210##
2211##  Name="Randomized S^3_5"
2212## Dim=3
2213##
2214## /SimplicialComplex]
2215## gap> c.F;
2216## [ 20, 85, 130, 65 ]
2217## </Example>
2218## </Description>
2219## </ManSection>
2220##<#/GAPDoc>
2221################################################################################
2222InstallGlobalFunction(SCRandomize,
2223function(arg)
2224
2225  local p,complex,tcomplex,allowedmoves,writelevel,maxrounds,d,f,i,movable,
2226    rounds,result,randomizeStrategy,arounds;
2227
2228  randomizeStrategy:=function(dim,moves)
2229    local options,i;
2230
2231    options:=[];
2232    for i in [0..d] do
2233      if(allowedmoves[i+1]<>0) then
2234        if((i>0 and i<d) or (i=0 and (rounds mod 2)=0) or
2235          (i=d and (rounds mod 2)=1)) then
2236          Append(options,moves[i+1]);
2237        fi;
2238      fi;
2239    od;
2240
2241    rounds:=rounds+1;
2242
2243    # choosing move at random
2244    if options=[] then
2245      return [];
2246    else
2247      return RandomList(options);
2248    fi;
2249  end;
2250
2251  if(Length(arg)<1 or not SCIsSimplicialComplex(arg[1])) then
2252    Info(InfoSimpcomp,2,"SCRandomize: invalid argument list, first argument ",
2253      "must be of type SCSimplicialComplex.");
2254    return fail;
2255  fi;
2256
2257  complex:=arg[1];
2258  d:=SCDim(complex);
2259  f:=SCFVector(complex);
2260
2261  if(d=fail or f=fail) then
2262    return fail;
2263  fi;
2264
2265  if(Length(arg)>1 and IsInt(arg[2])) then
2266    arounds:=arg[2];
2267  else
2268    arounds:=0;
2269  fi;
2270
2271  if(Length(arg)>1 and IsList(arg[2]) and not IsEmpty(arg[2])
2272    and ForAll(arg[2],x->(x=0 or x=1))) then
2273    p:=2;
2274  elif(Length(arg)>2 and IsList(arg[3]) and not IsEmpty(arg[3])
2275    and ForAll(arg[3],x->(x=0 or x=1))) then
2276    p:=3;
2277  else
2278    p:=0;
2279  fi;
2280
2281  if(p<>0) then
2282    allowedmoves:=arg[p];
2283  else
2284    allowedmoves:=ListWithIdenticalEntries(d+1,1);
2285    allowedmoves[1]:=-1;
2286  fi;
2287
2288  for i in [1..d+1] do
2289    if(not IsBound(allowedmoves[i])) then
2290      allowedmoves[i]:=1;
2291    fi;
2292  od;
2293
2294
2295
2296  movable:=SCIsMovableComplex(complex);
2297  if movable = fail then
2298    Info(InfoSimpcomp,2,"SCRandomize: invalid complex.");
2299    return fail;
2300  fi;
2301
2302  Info(InfoSimpcomp,2,"SCRandomize: randomizing complex ",SCName(complex),
2303    " with allowed moves ",allowedmoves);
2304
2305  maxrounds:=SCBistellarOptions.MaxInterval;
2306
2307  if(arounds<>0) then
2308    SCBistellarOptions.MaxInterval:=arounds;
2309  else
2310    SCBistellarOptions.MaxInterval:=SCBistellarOptions.MaxIntervalRandomize;
2311  fi;
2312
2313
2314
2315  writelevel:=SCBistellarOptions.WriteLevel;
2316  SCBistellarOptions.WriteLevel:=0;
2317
2318  rounds:=0;
2319  result:=SCReduceComplexEx(complex,SCEmpty(),3,randomizeStrategy);
2320
2321  SCBistellarOptions.MaxInterval:=maxrounds;
2322  SCBistellarOptions.WriteLevel:=writelevel;
2323
2324  if result=fail then
2325    Info(InfoSimpcomp,2,"SCRandomize: SCReduceComplexEx returned fail.");
2326    return fail;
2327  fi;
2328
2329  tcomplex:=result[2];
2330  if(tcomplex<>fail) then
2331    SCRename(tcomplex,Concatenation("Randomized ",SCName(complex)));
2332  fi;
2333
2334  return tcomplex;
2335end);
2336
2337
2338
2339
2340
2341SCIntFunc.SCReduceComplexEx2:=
2342  function(complex,refComplex,mode,choosemove)
2343
2344  local move,moves,validMoves,rounds,minF,name,globalRounds,minComplex,
2345    refFaces,msg,elapsed,stime,i,j,equivalent,time,rep,tmpFaces,tmpF,
2346    tmpOptions,dim,tmp,refF;
2347
2348  dim:=SCDim(complex);
2349  if dim = fail then
2350    return fail;
2351  fi;
2352
2353  if dim <= 0 then
2354    return [true,complex,0];
2355  fi;
2356
2357  SCBistellarOptions.Mode:=0;
2358  globalRounds:=0;
2359  rounds:=0;
2360  stime:=SCIntFunc.TimerStart();
2361
2362  if stime=fail then
2363    Info(InfoSimpcomp,1,"SCReduceComplexEx: can not start timer.");
2364    return fail;
2365  fi;
2366
2367  if SCBistellarOptions.WriteLevel>=1 then
2368    time:=SCIntFunc.GetCurrentTimeString();
2369    if(time=fail) then
2370      return fail;
2371    fi;
2372    rep:=SCLibInit(Concatenation(SCIntFunc.UserHome,"/reducedComplexes/",time));
2373  fi;
2374  equivalent:=false;
2375
2376  complex:=SCExamineComplexBistellar(complex);
2377  if complex=fail then
2378    Info(InfoSimpcomp,1,"SCReduceComplexEx: can not compute complex ",
2379      "properties.");
2380    return fail;
2381  fi;
2382
2383  minF:=SCIntFunc.DeepCopy(SCFVector(complex));
2384  if minF=fail then
2385    Info(InfoSimpcomp,1,"SCReduceComplexEx: error calculating f-vector.");
2386    return fail;
2387  fi;
2388
2389  minComplex:=complex;
2390
2391  #init moves
2392  tmpFaces:=SCIntFunc.DeepCopy(SCFaceLatticeEx(complex));
2393  if tmpFaces = fail then
2394    return fail;
2395  fi;
2396  tmpF:=ShallowCopy(SCFVector(complex));
2397  if tmpF = fail then
2398    return fail;
2399  fi;
2400
2401  tmpOptions:=[];
2402  for i in [1..dim+1] do
2403    tmpOptions[i]:=SCIntFunc.IRawBistellarRMoves(i-1,tmpFaces,dim+1);
2404    if tmpOptions[i]=fail then
2405      Info(InfoSimpcomp,1,"SCReduceComplexEx: no ",i-1,"-moves found.");
2406      return fail;
2407    fi;
2408    tmpOptions[i]:=SCIntFunc.IBistellarRMoves(i,dim+1,tmpOptions[i],tmpFaces);
2409  od;
2410
2411  if mode=2 then
2412    if not SCIsSubcomplex(refComplex,complex) then
2413      Info(InfoSimpcomp,1,"SCReduceComplexEx: complex is not a sub-complex.");
2414      return fail;
2415    fi;
2416
2417    refFaces:=SCFaceLatticeEx(refComplex);
2418    if refFaces=fail then
2419      return fail;
2420    fi;
2421  fi;
2422
2423  if mode = 1 then
2424    refF:=SCFVector(refComplex);
2425
2426    if refF=fail then
2427      return fail;
2428    fi;
2429  fi;
2430
2431
2432
2433  #loop..
2434  while rounds < SCBistellarOptions.MaxInterval and
2435    globalRounds < SCBistellarOptions.MaxRounds do
2436
2437    if mode=1 then
2438      if tmpF = refF then
2439        equivalent:=SCIsIsomorphic(SCFromFacets(tmpFaces[dim+1]),refComplex);
2440      fi;
2441      if equivalent=fail then
2442        Info(InfoSimpcomp,1,"SCReduceComplexEx: can not compute ",
2443          "isomorphism between complexes.");
2444        return fail;
2445      fi;
2446    fi;
2447
2448    if mode<>1 or equivalent=false then
2449      if mode=2 then
2450        # remove bistellar moves that can't be performed in supercomplex
2451        # 'refComplex'
2452        validMoves:=[];
2453        validMoves[1]:=[];
2454        for i in [2..Size(tmpOptions)] do
2455          validMoves[i]:=[];
2456          for move in tmpOptions[i] do
2457            if move[2] in refFaces[Size(move[2])] then
2458              Add(validMoves[i],move);
2459            fi;
2460          od;
2461        od;
2462        tmpOptions:=validMoves;
2463      fi;
2464
2465      #choose a move
2466      move:=choosemove(dim,tmpOptions);
2467      if move=fail then
2468        Info(InfoSimpcomp,1,"SCReduceComplexEx: error in flip strategy.");
2469        return fail;
2470      fi;
2471
2472      if move<>[] then
2473        #move length
2474        i:=Length(move[2]);
2475        if(i>0) then
2476          i:=i-1;
2477        fi;
2478
2479        #do move
2480        tmp:=SCIntFunc.Move(i,dim+1,tmpFaces,tmpF,move,tmpOptions,1,[]);
2481
2482        tmpFaces:=tmp[1];
2483        tmpF:=tmp[2];
2484
2485        for i in [1..dim+1] do
2486          tmpOptions[i]:=SCIntFunc.IBistellarRMoves(i,dim+1,tmp[3][i],tmpFaces);
2487        od;
2488
2489        Info(InfoSimpcomp,3,"round ",globalRounds,", move: ",move,"\nF: ",tmpF);
2490        rounds:=rounds+1;
2491
2492        if tmpF<minF then
2493          rounds := 0;
2494          minComplex:=SCFromFacets(tmpFaces[dim+1]);
2495
2496          if minComplex=fail then
2497            return fail;
2498          fi;
2499
2500          Info(InfoSimpcomp,2,"round ",globalRounds,"\nReduced complex, F: ",
2501            tmpF);
2502
2503          if tmpF[1]<minF[1] or rounds>SCBistellarOptions.MaxInterval then
2504            if SCBistellarOptions.WriteLevel>=1 then
2505              name:=Concatenation(["ReducedComplex_",String(tmpF[1]),
2506                "_vertices_",String(globalRounds)]);
2507              if minComplex<>fail and name<>fail and rep<>fail then
2508                SCRename(minComplex,name);
2509                SCLibAdd(rep,minComplex);
2510              else
2511                Info(InfoSimpcomp,1,"SCReduceComplexEx: illegal complex, ",
2512                  "name or rep.");
2513                return fail;
2514              fi;
2515            fi;
2516            if SCBistellarOptions.WriteLevel=2 then
2517              msg:=Concatenation(["SCReduceComplex:\n\nReduced complex after ",
2518                String(globalRounds)," rounds:\n\n",String(minComplex),"\n"]);
2519              SCMailSend(msg,stime);
2520            fi;
2521          fi;
2522          minF:=ShallowCopy(tmpF);
2523        fi;
2524
2525        globalRounds:=globalRounds+1;
2526
2527        if(globalRounds mod 1000000=0 and SCBistellarOptions.WriteLevel=2) then
2528          elapsed:=SCIntFunc.TimerElapsed();
2529          if elapsed=fail then
2530            return fail;
2531          fi;
2532          if(SCIntFunc.TimerElapsed()>=SCBistellarOptions.MailNotifyInterval) then
2533            SCIntFunc.TimerStart();
2534            msg:=Concatenation(["SCReduceComplex:\n\nStatus report after ",
2535              String(globalRounds)," rounds:\n\n",String(minComplex),
2536              "\n\nMinimal complex so far:\n\n",String(minComplex)]);
2537            SCMailSend(msg,stime);
2538          fi;
2539        fi;
2540
2541      else
2542        # no moves available
2543        if SCBistellarOptions.WriteLevel>=1 then
2544          name:=Concatenation(["ReducedComplex_",String(tmpF[1]),
2545            "_vertices_",String(globalRounds)]);
2546          SCRename(minComplex,name);
2547          SCLibAdd(rep,minComplex);
2548        fi;
2549        if SCBistellarOptions.WriteLevel=2 then
2550          msg:=Concatenation(["SCReduceComplex:\n\nComputed locally minimal ",
2551            "complex after ",String(globalRounds)," rounds:\n\n",
2552            String(minComplex),"\n"]);
2553          SCMailClearPending();
2554          SCMailSend(msg,stime,true);
2555        fi;
2556        if mode=1 then
2557          Info(InfoSimpcomp,1,"SCReduceComplexEx: could not prove bistellar ",
2558          "equivalence between 'complex' and 'refComplex'\n(reached local ",
2559          "minimum after  ",String(globalRounds)," rounds).");
2560        elif mode<>1 then
2561          Info(InfoSimpcomp,2,"SCReduceComplexEx: computed locally minimal ",
2562            "complex after ",String(globalRounds)," rounds.");
2563        fi;
2564
2565        return [fail,SCFromFacets(tmpFaces[dim+1]),globalRounds];
2566
2567        if mode=1 then
2568          return [fail,minComplex,globalRounds];
2569        elif mode=3 then
2570          return [fail,SCFromFacets(tmpFaces[dim+1]),globalRounds];
2571        else
2572          return [true,minComplex,globalRounds];
2573        fi;
2574      fi;
2575    else
2576      # equivalent<>false and mode=1 -> bistellarly equivalent
2577      if SCBistellarOptions.WriteLevel>=1 then
2578        name:=Concatenation(["ReducedComplex_",String(tmpF[1]),"_vertices_",
2579          String(globalRounds)]);
2580        SCRename(minComplex,name);
2581        SCLibAdd(rep,minComplex);
2582      fi;
2583
2584      if SCBistellarOptions.WriteLevel=2 then
2585        msg:=Concatenation(["SCReduceComplexEx:\n\nComplexes are bistellarly ",
2586          "equivalent.\n\n",String(minComplex),"\n"]);
2587        SCMailClearPending();
2588        SCMailSend(msg,stime,true);
2589      fi;
2590      if mode=1 then
2591        Info(InfoSimpcomp,1,"SCReduceComplexEx: complexes are bistellarly ",
2592          "equivalent.");
2593      fi;
2594
2595      if mode <> 3 then
2596        return [true,minComplex,globalRounds];
2597      else
2598        return [true,SCFromFacets(tmpFaces[dim+1]),globalRounds];
2599      fi;
2600    fi;
2601  od;
2602
2603  if SCBistellarOptions.WriteLevel>=1 then
2604    name:=Concatenation(["ReducedComplex_",String(tmpF[1]),"_vertices_",
2605      String(globalRounds)]);
2606    SCRename(minComplex,name);
2607    SCLibAdd(rep,minComplex);
2608  fi;
2609
2610  if SCBistellarOptions.WriteLevel=2 then
2611    msg:=Concatenation(["SCReduceComplexEx:\n\nReached maximal number of ",
2612      "rounds ",String(globalRounds)," rounds. Reduced complex to:\n\n",
2613      String(minComplex),"\n"]);
2614    SCMailClearPending();
2615    SCMailSend(msg,stime,true);
2616  fi;
2617
2618  if mode=1 then
2619    Info(InfoSimpcomp,1,"SCReduceComplexEx: could not prove bistellar ",
2620      "equivalence between 'complex' and 'refComplex'.");
2621  elif mode<>1 and mode <> 3 then
2622    Info(InfoSimpcomp,2,"SCReduceComplexEx: reached maximal number of ",
2623      "rounds. Returning smallest complex found.");
2624  fi;
2625
2626  return [fail,SCFromFacets(tmpFaces[dim+1]),globalRounds];
2627
2628  if mode <> 3 then
2629    return [fail,minComplex,globalRounds];
2630  else
2631    return [fail,SCFromFacets(tmpFaces[dim+1]),globalRounds];
2632  fi;
2633
2634end;
2635
2636SCIntFunc.SCMakeFlagComplex:=
2637  function(complex)
2638
2639  local d,f,h,links, result, linkidx, verts, writelevel, maxrounds,
2640    type, movable, ks, cc, try, maxtries, flagStrategy, ball, tmp;
2641
2642  flagStrategy:=function(dim,moves)
2643    local options,i,tmp;
2644
2645    #allow 1..(dim/2)-moves
2646    options:=[];
2647    for i in [1..Int(dim/2)] do
2648      Append(options,moves[i+1]);
2649    od;
2650
2651    #choose move at random
2652    if options=[] then
2653      return [];
2654    else
2655      tmp:=RandomList(options);
2656      return tmp;
2657    fi;
2658  end;
2659
2660  if(not SCIsSimplicialComplex(complex)) then
2661    Info(InfoSimpcomp,1,"SCMakeFlagComplex: first argument must be of type ",
2662      "SCSimplicialComplex.");
2663    return fail;
2664  fi;
2665
2666  ks:=SCIsFlag(complex);
2667
2668  if ks<>fail and IsBool(ks) then
2669    return ks;
2670  fi;
2671
2672  d:=SCDim(complex);
2673  f:=SCFVector(complex);
2674
2675  if(d=fail or f=fail) then
2676    return fail;
2677  fi;
2678
2679  #set bistellar flip options
2680  maxrounds:=Sum(f)*10;
2681  SCBistellarOptions.MaxInterval:=SCBistellarOptions.MaxIntervalIsManifold;
2682  writelevel:=SCBistellarOptions.WriteLevel;
2683  SCBistellarOptions.WriteLevel:=0;
2684
2685  Info(InfoSimpcomp,1,"SCMakeFlagComplex: trying to make flag complex...");
2686
2687  maxtries:=50;
2688  for try in [1..maxtries] do
2689
2690    cc:=SCCopy(complex);
2691    SCRelabelStandard(cc);
2692
2693    Info(InfoSimpcomp,1,Concatenation("SCMakeFlagComplex: try ",String(try),
2694      "/",String(maxtries)));
2695
2696    movable:=SCIsMovableComplex(cc);
2697    if movable = fail then
2698      Info(InfoSimpcomp,1,"SCMakeFlagComplex: invalid complex.");
2699      return fail;
2700    fi;
2701
2702    if movable then
2703      result:=SCReduceComplexEx(cc,SCEmpty(),0,flagStrategy);
2704    else
2705      Info(InfoSimpcomp,1,"SCMakeFlagComplex: complex is not a closed ",
2706        "pseudomanifold.");
2707      return false;
2708    fi;
2709
2710    if result=fail then
2711      Info(InfoSimpcomp,1,"SCMakeFlagComplex: SCReduceComplexEx returned ",
2712        "fail.");
2713      return fail;
2714    fi;
2715
2716  od;
2717
2718  SCBistellarOptions.MaxInterval:=maxrounds;
2719  SCBistellarOptions.WriteLevel:=writelevel;
2720
2721  Info(InfoSimpcomp,1,"SCMakeFlagComplex: could not determine whether given ",
2722    "complex is flag.");
2723  return false;
2724end;
2725
2726
2727################################################################################
2728##<#GAPDoc Label="SCReduceComplexFast">
2729## <ManSection>
2730## <Func Name="SCReduceComplexFast" Arg="complex"/>
2731## <Returns>a simplicial complex upon success, <K>fail</K> otherwise.</Returns>
2732## <Description>
2733## Same as <Ref Func="SCReduceComplex" Style="Text" />, but calls an external
2734## binary provided with the simpcomp package.
2735## </Description>
2736## </ManSection>
2737##<#/GAPDoc>
2738################################################################################
2739InstallGlobalFunction(SCReduceComplexFast,
2740  function(complex)
2741
2742  local
2743  movable, dir, bin, stream, line, resultingcomplex;
2744
2745  movable:=SCIsMovableComplex(complex);
2746  if movable = fail then
2747    Info(InfoSimpcomp, 2, "SCReduceComplexFast: invalid complex.");
2748    return fail;
2749  fi;
2750
2751  dir := DirectoriesPackageLibrary("simpcomp", "bin");
2752  if dir = fail then
2753    Info(InfoSimpcomp, 1, "SCReduceComplexFast: cannot find executable.");
2754    return fail;
2755  fi;
2756
2757  bin := Filename(dir, "bistellar");
2758  if bin = fail then
2759    Info(InfoSimpcomp, 1, "SCReduceComplexFast: cannot find executable.");
2760    return fail;
2761  fi;
2762
2763  stream := InputOutputLocalProcess(DirectoryCurrent(), bin, []);
2764  if stream = fail then
2765    Info(InfoSimpcomp, 2, "SCReduceComplexFast: cannot open executable.");
2766    return fail;
2767  fi;
2768
2769  WriteLine(stream, Concatenation("reduce ",
2770                SCIntFunc.ListToDenseString(complex.Facets),
2771                " with rounds=", String(SCBistellarOptions.MaxRounds),
2772                ", heating=",
2773                String(SCBistellarOptions.BaseHeating),
2774                " and relaxation=",
2775                String(SCBistellarOptions.BaseRelaxation)));
2776
2777  repeat
2778    line := ReadAllLine(stream, true);
2779
2780    if line{[1..5]} = "found" then
2781      Info(InfoSimpcomp, 2, Concatenation("SCReduceComplexFast: ", line));
2782    fi;
2783  until line{[1..5]} <> "found";
2784
2785  CloseStream(stream);
2786
2787  if line{[1..9]} = "resulting" then
2788    resultingcomplex :=
2789      SC(SCIntFunc.ReadArray(line{[22..(Position(line, ' ', 22)-1)]}));
2790    return resultingcomplex;
2791  else
2792    return fail;
2793  fi;
2794end);
2795
2796
2797