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