1#############################################################################
2##
3#W CWcomplexThings.gi 			 HAPcryst package		 Marc Roeder
4##
5##
6
7##
8##
9#Y	 Copyright (C) 2006 Marc Roeder
10#Y
11#Y This program is free software; you can redistribute it and/or
12#Y modify it under the terms of the GNU General Public License
13#Y as published by the Free Software Foundation; either version 2
14#Y of the License, or (at your option) any later version.
15#Y
16#Y This program is distributed in the hope that it will be useful,
17#Y but WITHOUT ANY WARRANTY; without even the implied warranty of
18#Y MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19#Y GNU General Public License for more details.
20#Y
21#Y You should have received a copy of the GNU General Public License
22#Y along with this program; if not, write to the Free Software
23#Y Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24##
25#############################################################################
26##
27## undirectedBoundary calculates just the cells occuring in the boundary.
28## signs and multiplicities are ignored.
29##
30InstallMethod(UndirectedBoundaryOfFreeZGLetter,
31        [IsHapResolutionRep,IsInt,IsDenseList],
32        function(resolution,dim,cell)
33    if not IsFreeZGLetter(resolution,dim,cell)
34       then
35        Error("invalid letter");
36    fi;
37    return UndirectedBoundaryOfFreeZGLetterNC(resolution,dim,cell);
38end);
39
40InstallMethod(UndirectedBoundaryOfFreeZGLetterNC,
41        [IsHapResolutionRep,IsInt,IsDenseList],
42        function(resolution,dim,cell)
43    return Set(BoundaryOfFreeZGLetterNC(resolution,dim,cell),i->[AbsInt(i[1]),i[2]]);
44end);
45
46
47
48#############################################################################
49##
50## undirectedBoundary for words
51##
52InstallMethod(UndirectedBoundaryOfFreeZGWord,
53        [IsHapResolutionRep,IsInt,IsDenseList],
54        function(resolution,dim,word)
55    if not IsFreeZGWord(resolution,dim,word)
56       then
57        Error("invalid word");
58    fi;
59    return UndirectedBoundaryOfFreeZGWordNC(resolution,dim,word);
60end);
61
62InstallMethod(UndirectedBoundaryOfFreeZGWordNC,
63        [IsHapResolutionRep,IsInt,IsDenseList],
64        function(resolution,dim,word)
65    return Union(List(word,cell->UndirectedBoundaryOfFreeZGLetterNC(resolution,dim,cell)));
66end);
67
68
69
70#############################################################################
71##
72##
73InstallMethod(SubspaceListFromWord,
74        [IsHapResolutionRep,IsInt,IsDenseList],
75        function(resolution,dim,word)
76    if not IsFreeZGWord(resolution,dim,word)
77       then
78        Error("<word> is not a valid word");
79    fi;
80    return SubspaceListFromWordNC(resolution,dim,word);
81end);
82
83InstallMethod(SubspaceListFromWordNC,
84        [IsHapResolutionRep,IsInt,IsDenseList],
85        function(resolution,dim,word)
86    local   subspaces,  i;
87    subspaces:=List([0..dim],i->[]);
88    subspaces[dim+1]:=Set(word,i->[AbsInt(i[1]),i[2]]);
89    for i in [dim-1,dim-2..0]
90      do
91        subspaces[i+1]:=Union(List(subspaces[i+2],
92                                j->UndirectedBoundaryOfFreeZGLetter(resolution,i+1,j))
93                              );
94    od;
95    return subspaces;
96end);
97
98
99
100
101
102#############################################################################
103##
104## Tests if a word represents a connected supspace.
105##
106InstallMethod(IsConnectedWord,
107        [IsHapResolutionRep,IsInt,IsDenseList],
108        function(resolution,dim,word)
109    if not IsFreeZGWord(resolution,dim,word)
110       then
111        Error("<word> is not a valid word");
112    fi;
113    return IsConnectedWordNC(resolution,dim,word);
114end);
115
116
117InstallMethod(IsConnectedWordNC,
118        [IsHapResolutionRep,IsInt,IsDenseList],
119        function(resolution,dim,word)
120    local   lettersAndBound,  startblob,  blobbound,  addToBlob,
121            addToBlobBound;
122
123    lettersAndBound:=Set(word,letter->
124                         [letter,UndirectedBoundaryOfFreeZGLetter(resolution,dim,letter)]
125                         );
126    # a "blob" is just that. A connected part of word.
127    # We don't generate the blob. As we are just interesed in it's size.
128    startblob:=Remove(lettersAndBound);
129    blobbound:=startblob[2];
130
131    repeat
132        addToBlob:=Filtered(lettersAndBound,i->Intersection(i[2],blobbound)<>[]);
133        if addToBlob<>[]
134           then
135            SubtractSet(lettersAndBound,addToBlob);
136            addToBlobBound:=Union(List(addToBlob,i->i[2]));
137            blobbound:=Union(blobbound,addToBlobBound);
138        fi;
139    until lettersAndBound=[] or addToBlob=[];
140
141    if lettersAndBound=[]
142       then
143        return true;
144    elif addToBlob=[]
145      then
146        return false;
147    fi;
148end);
149
150
151
152
153
154#############################################################################
155##
156## connect a cell <cell> to the subspace <cellblob>.
157##
158InstallMethod(ConnectingPath,
159        [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList,IsDenseList],
160        function(resolution,dim,area,cellblob,cell)
161
162    if not (IsFreeZGWord(resolution,dim,area)
163            and IsFreeZGWord(resolution,dim,cellblob)
164            )
165       then
166        Error("<area> and <cellblob> must be valid words");
167    elif  not IsFreeZGLetter(resolution,dim,cell)
168      then
169        Error("<cell> is not a valid letter");
170    elif not IsSubset(area,cellblob) and cell in area
171       then
172        Error("<area> does not contain <cellblob> and <cell>");
173    fi;
174    return ConnectingPathNC(resolution,dim,area,cellblob,cell);
175end);
176
177
178InstallMethod(ConnectingPathNC,
179        [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList,IsDenseList],
180        function(resolution,dim,area,cellblob,cell)
181    local   pathfinder,  sphereAndBounds,  path;
182
183    ##################################################
184    ##
185    ##  The recursive function "pathfinder" assumes that connectTo is not empty.
186    ##  It calculates a path from a "disk" that connects a given starting part
187    ##  with the space of known homotopies.
188    ##
189    pathfinder:=function(resolution, connectTo, sphereAndBounds, startingBit,startingbitboundary)
190        local   thingsThatCouldBeAdded,  endpoint,  addface,
191                newSphereAndBounds,  newstartingbitboundary,
192                newstartingBit,  returnpath;
193
194        thingsThatCouldBeAdded:=Filtered(sphereAndBounds,i->Intersection(i[2],startingbitboundary)<>[]);
195
196        endpoint:=First(thingsThatCouldBeAdded,i->Intersection(i[2],connectTo)<>[]);
197        if endpoint<>fail
198           then
199            return Concatenation(startingBit,[endpoint[1]]);
200        else
201            newSphereAndBounds:=Difference(sphereAndBounds,thingsThatCouldBeAdded);
202            repeat
203                if thingsThatCouldBeAdded=[]
204                   then
205                    return [];
206                fi;
207                addface:=Remove(thingsThatCouldBeAdded);
208                newstartingbitboundary:=Union(startingbitboundary,addface[2]);
209                newstartingBit:=Concatenation(startingBit,[addface[1]]);
210                returnpath:=pathfinder(resolution,
211                                    connectTo,
212                                    newSphereAndBounds,
213                                    newstartingBit,
214                                    newstartingbitboundary
215                                    );
216            until returnpath<>[];
217            return Unique(returnpath);
218        fi;
219    end;
220
221
222    if cell in cellblob
223       then
224        return [];
225    fi;
226    sphereAndBounds:=Set(area,i->[i,UndirectedBoundaryOfFreeZGLetter(resolution,dim,i)]);
227    path:=pathfinder(resolution,
228                  #                  undirectedReducedBoundaryOfWord(resolution,dim,cellblob),
229                  UndirectedBoundaryOfFreeZGLetter(resolution,dim,cell),
230                  sphereAndBounds,
231                  [cell],
232                   UndirectedBoundaryOfFreeZGLetter(resolution,dim,cell)
233                  );
234    if path=[]
235       then
236        return fail;
237    else
238        return path;
239    fi;
240end);
241
242
243#############################################################################
244##
245## given a word in the <dim>th term of <resolution>, this returns true
246##  if and only if this word represents a contractible subspace.
247##
248## connectedness is not tested.
249## Is this right, anyway?
250##
251InstallMethod(IsContractibleWordNC,
252        [IsHapResolutionRep,IsInt,IsDenseList],
253        function(resolution,dim,subspace)
254    local   chaincomplex,  i;
255    chaincomplex:=ChainComplexFromWordNC(resolution,dim,subspace);
256    return Homology(chaincomplex,dim)=[];
257end);
258
259InstallMethod(IsContractibleWord,
260        [IsHapResolutionRep,IsInt,IsDenseList],
261        function(resolution,dim,subspace)
262    if not IsFreeZGWord(resolution,dim,subspace)
263       then
264        Error("subspace is not a valid word");
265    fi;
266    return IsContractibleWordNC(resolution,dim,subspace);
267end);
268
269#############################################################################
270##
271##
272InstallMethod(IsContractiblePartialSpace,
273        [IsHapResolutionRep,IsInt,IsDenseList],
274        function(resolution,dim,spacelist)
275    if not ForAll(spacelist,subspace->IsFreeZGWord(resolution,dim,subspace))
276       then
277        Error("subspace is not a valid word");
278    fi;
279    return IsContractiblePartialSpaceNC(resolution,dim,spacelist);
280end);
281
282InstallMethod(IsContractiblePartialSpaceNC,
283        [IsHapResolutionRep,IsInt,IsDenseList],
284        function(resolution,dim,spacelist)
285    local   chaincomplex;
286    chaincomplex:=ChainComplexFromPartialSpaceNC(resolution,dim,spacelist);
287    return Homology(chaincomplex,dim)=[];
288end);
289
290
291
292#############################################################################
293##
294## find the sphere that contains <cell>.
295## The list of cells <space> must induce a chain complex with <dim>th
296## homology [0].
297##
298#############################################################################
299##
300## check the input and delegate...
301##
302InstallMethod(SphereContainingCell,
303        [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList],
304        function(resolution,dim,space,cell)
305    local   complex;
306    if not IsFreeZGLetter(resolution,dim,cell)
307       then
308        Error("<cell> is not a valid letter");
309    elif not IsFreeZGWord(resolution,dim,space)
310      then
311        Error("<space> is not a valid word");
312    elif not cell in space
313       then
314        Error("<cell> not in <space>");
315    fi;
316    complex:=ChainComplexFromPartialSpace(resolution,dim,space);
317    if not Homology(complex,dim)=[0]
318       then
319        Error("<space> does not contain a unique sphere");
320    fi;
321    return SphereContainingCellNC(resolution,dim,space,cell);
322end);
323
324#############################################################################
325##
326##
327InstallMethod(SphereContainingCellNC,
328        [IsHapResolutionRep,IsInt,IsDenseList,IsDenseList],
329        function(resolution,dim,space,cell)
330    local   space_and_bounds,  sphere,  spherebound,  sphere_done,
331            subspacelist,  complex,  newcells,  new_subspaces,  i;
332
333    space_and_bounds:=List(space,i->[i,UndirectedBoundaryOfFreeZGWord(resolution,dim,i)]);
334    sphere:=[cell];
335    spherebound:=UndirectedBoundaryOfFreeZGWord(resolution,dim,sphere);
336    sphere_done:=false;
337    subspacelist:=SubspaceListFromWord(resolution,dim,sphere);
338    complex:=ChainComplexFromPartialSpace(resolution,
339                     dim,
340                     subspacelist
341                     );
342    while not Homology(complex,dim)=[0]
343      do
344        newcells:=Filtered(space_and_bounds,c->ForAny(c[2],i->i in spherebound));
345        SubtractSet(space_and_bounds,newcells);
346        UniteSet(sphere,List(newcells,i->i[1]));
347        UniteSet(spherebound,Concatenation(List(newcells,i->i[2])));
348        new_subspaces:=SubspaceListFromWord(resolution,
349                               dim,
350                               List(newcells,i->i[1])
351                               );
352        for i in [1..Size(new_subspaces)]
353          do
354            UniteSet(subspacelist[i],new_subspaces[i]);
355        od;
356    od;
357    return Set(sphere);
358end);
359
360
361
362
363
364
365#############################################################################
366##
367##  Generate a chain complex from a word
368##
369InstallMethod(ChainComplexFromWord,
370        [IsHapResolutionRep,IsInt,IsDenseList],
371        function(resolution,dim,subspace)
372    if not IsFreeZGWord(resolution,dim,subspace)
373       then
374        Error("<subspace> is not a proper word");
375    fi;
376    return ChainComplexFromWordNC(resolution,dim,subspace);
377end);
378
379InstallMethod(ChainComplexFromWordNC,
380        [IsHapResolutionRep,IsInt,IsDenseList],
381        function(resolution,dim,subspace)
382    local   spaces;
383    spaces:=SubspaceListFromWord(resolution,dim,subspace);
384    return ChainComplexFromPartialSpaceNC(resolution,spaces);
385end);
386
387
388
389#############################################################################
390##
391## Generate a chain complex from a list of words
392##
393InstallMethod(ChainComplexFromPartialSpace,
394        [IsHapResolutionRep,IsDenseList],
395        function(resolution,subspaces)
396    if not ForAll([1..Size(subspaces)],dim->
397               IsFreeZGWord(resolution,dim-1,subspaces[dim])
398               )
399       then
400        Error("subspace list contains invalid words");
401    fi;
402    return ChainComplexFromPartialSpaceNC(resolution,subspaces);
403end);
404
405
406#############################################################################
407##
408InstallMethod(ChainComplexFromPartialSpaceNC,
409        [IsHapResolutionRep,IsDenseList],
410        function(resolution,subspaces)
411    local   undirectedLetter,  word2vec,  boundary,  dimension,
412            complex,  properties;
413
414    undirectedLetter:=function(letter)
415        return [AbsInt(letter[1]),letter[2]];
416    end;
417
418    word2vec:=function(generators,word)
419        local   vec,  letter,  pos;
420        vec:=List([1..Size(generators)],i->0);
421        for letter in word
422          do
423            pos:=Position(generators,undirectedLetter(letter));
424            if pos<>fail
425               then
426                vec[pos]:=vec[pos]+SignInt(letter[1]);
427            else
428                Error("word-vector conversion error");
429            fi;
430        od;
431        return vec;
432    end;
433
434
435    boundary:=function(k,j)
436        local   letter,  boundaryAsWord;
437        if k=Size(subspaces+1)
438           then
439            return [];
440        fi;
441        letter:=subspaces[k+1][j];
442        boundaryAsWord:=BoundaryOfFreeZGLetterNC(resolution,k,letter);
443        return word2vec(subspaces[k],boundaryAsWord);
444    end;
445
446
447    dimension:=function(k)
448        if k<Size(subspaces)
449           then
450            return Size(subspaces[k+1]);
451        elif k=Size(subspaces)
452          then
453          return 0;
454        else
455            Error("chain complex too short");
456        fi;
457    end;
458
459    complex:=Objectify(HapChainComplex,
460                     rec(dimension:=dimension,
461                         boundary:=boundary,
462                         subspaces:=List(subspaces),
463                         properties:=
464                         [["length", Size(subspaces)-1],
465                          ["characteristic", 0],
466                          ["type", "chainComplex"]
467                          ])
468                     );
469    return complex;
470end);
471
472
473
474
475