1############################################################################# 2# This file contains obsolet functions which are to be kept during a while for 3# compatibility 4# WARNING: the manual must be updated before removing the functions 5############################################################################# 6## 7#F GeneratorsOfNumericalSemigroupNC(S) 8## 9## Returns a set of generators of the numerical 10## semigroup S. 11## 12############################################################################# 13# InstallGlobalFunction( GeneratorsOfNumericalSemigroupNC, function(S) 14# if not IsNumericalSemigroup(S) then 15# Error("The argument must be a numerical semigroup"); 16# fi; 17# if HasGenerators(S) then 18# return(Generators(S)); 19# fi; 20# return(MinimalGeneratingSystemOfNumericalSemigroup(S)); 21# end); 22############################################################################# 23## 24#F ReducedSetOfGeneratorsOfNumericalSemigroup(arg) 25## 26## Returns a set with possibly fewer generators than those recorded in <C>S!.generators</C>. It changes <C>S!.generators</C> to the set returned. 27##The function has 1 to 3 arguments. One of them a numerical semigroup. Then an argument is a boolean (<E>true</E> means that all the elements not belonging to the Apery set with respect to the multiplicity are removed; the default is "false") and another argument is a positive integer <M>n</M> (meaning that generators that can be written as the sum of <n> or less generators are removed; the default is "2"). The boolean or the integer may not be present. If a minimal generating set for <M>S</M> is known or no generating set is known, then the minimal generating system is returned. 28## 29# InstallGlobalFunction( ReducedSetOfGeneratorsOfNumericalSemigroup, function(arg) 30# local sumNS, S, apery, n, generators, m, aux, i, g, gen, ss; 31 32# ##################################################### 33# # Computes the sum of subsets of numerical semigroups 34# # WARNING: the arguments have to be non empty sets, not just lists 35# sumNS := function(S,T) 36# local mm, s, t, R; 37# R := []; 38# mm := Maximum(Maximum(S),Maximum(T)); 39# for s in S do 40# for t in T do 41# if s+t > mm then 42# break; 43# else 44# AddSet(R,s+t); 45# fi; 46# od; 47# od; 48# return R; 49# end; 50# ## 51# S := First(arg, s -> IsNumericalSemigroup(s)); 52# if S = fail then 53# Error("Please check the arguments of ReducedSetOfGeneratorsOfNumericalSemigroup"); 54# fi; 55# apery := First(arg, s -> IsBool(s)); 56# if apery = fail then 57# apery := false; 58# fi; 59# n := First(arg, s -> IsInt(s)); 60# if n = fail then 61# n := 2; 62# fi; 63 64# if not IsBound(S!.generators) then 65# S!.generators := MinimalGeneratingSystemOfNumericalSemigroup(S); 66# return S!.generators; 67# else 68# if IsBound(S!.minimalgenerators) then 69# #S!.generators := MinimalGeneratingSystemOfNumericalSemigroup(S); 70# return S!.minimalgenerators; 71# fi; 72# generators := S!.generators; 73# m := Minimum(generators); # the multiplicity 74# if m = 1 then 75# S!.generators := [1]; 76# return S!.generators; 77# elif m = 2 then 78# S!.generators := [2,First(generators, g -> g mod 2 = 1)]; 79# return S!.generators; 80# fi; 81# if apery then 82# aux := [m]; 83# for i in [1..m-1] do 84# g := First(generators, g -> g mod m = i); 85# if g <> fail then 86# Append(aux,[g]); 87# fi; 88# od; 89# gen := Set(aux); 90# else 91# gen := ShallowCopy(generators); 92# fi; 93# ss := sumNS(gen,gen); 94# i := 1; 95# while i < n and ss <> [] do 96# gen := Difference(gen,ss); 97# ss := sumNS(gen,ss); 98# i := i+1; 99# od; 100# fi; 101 102# S!.generators := gen; 103# return S!.generators; 104# end); 105 106## 107############################################################################# 108 109 110 111############################################################################# 112## 113#F NumericalSemigroupByMinimalGenerators(arg) 114## 115## Returns the numerical semigroup minimally generated by arg. 116## If the generators given are not minimal, the minimal ones 117## are computed and used. 118## 119############################################################################# 120InstallGlobalFunction(NumericalSemigroupByMinimalGenerators, function(arg) 121 local L, S, M, l, 122 minimalGSNS, sumNS; 123 124 125 ##################################################### 126 # Computes the sum of subsets of numerical semigroups 127 sumNS := function(S,T) 128 local mm, s, t, R; 129 R := []; 130 mm := Minimum(Maximum(S),Maximum(T)); 131 for s in S do 132 for t in T do 133 if s+t > mm then 134 break; 135 else 136 AddSet(R,s+t); 137 fi; 138 od; 139 od; 140 return R; 141 end; 142 ## End of sumNS(S,T) -- 143 144 145 minimalGSNS := function(L) 146 local res, gen, ss, sss, ssss, i, ngen; 147 148 if 1 in L then 149 return [1]; 150 fi; 151 gen := ShallowCopy(L); 152 # a naive reduction of the number of generators 153 ss := sumNS(gen,gen); 154 gen := Difference(gen,ss); 155 if ss <> [] then 156 sss := sumNS(ss,gen); 157 gen := Difference(gen,sss); 158 if sss <> [] then 159 ssss := sumNS(sss,gen); 160 gen := Difference(gen,ssss); 161 fi; 162 fi; 163 if Length(gen) = 2 then 164 return gen; 165 fi; 166 i := Length(gen); 167 while i >= 2 do 168 ngen := Difference(gen, [gen[i]]); 169 if Gcd(ngen) = 1 and 170 BelongsToNumericalSemigroup(gen[i], NumericalSemigroup(ngen)) then 171 gen := ngen; 172 i := i - 1; 173 else 174 175 i := i - 1; 176 fi; 177 od; 178 return gen; 179 end; 180 ## End of minimalGSNS(L) -- 181 182 183 if IsList(arg[1]) then 184 L := Difference(Set(arg[1]),[0]); 185 else 186 L := Difference(Set(arg),[0]); 187 fi; 188 if L=[] then 189 Error("There should be at least one generator.\n"); 190 fi; 191 if not ForAll(L, x -> IsPosInt(x)) then 192 Error("The arguments should be positive integers.\n"); 193 fi; 194 if Gcd(L) <> 1 then 195 Error("The greatest common divisor is not 1"); 196 fi; 197 198 199 l := minimalGSNS(L); 200 if not Length(L) = Length(l) then 201 Info(InfoWarning,1,"The list ", L, " can not be the minimal generating set. The list ", l, " will be used instead."); 202 L := l; 203 fi; 204 M:= Objectify( NumericalSemigroupsType, rec() ); 205 # Setter(GeneratorsOfNumericalSemigroup)( M, AsList( L ) ); 206 SetMinimalGenerators(M,L); 207 SetGenerators(M,L); 208 return M; 209 210end); 211 212 213 214############################################################################# 215## 216#F NumericalSemigroupByMinimalGeneratorsNC(arg) 217## 218## Returns the numerical semigroup minimally generated by arg. 219## No test is made about args' minimality. 220## 221############################################################################# 222InstallGlobalFunction(NumericalSemigroupByMinimalGeneratorsNC, function(arg) 223 local L, S, M; 224 225 226 if IsList(arg[1]) then 227 L := Difference(Set(arg[1]),[0]); 228 else 229 L := Difference(Set(arg),[0]); 230 fi; 231 if not ForAll(L, x -> IsPosInt(x)) then 232 Error("The arguments should be positive integers"); 233 fi; 234 if Gcd(L) <> 1 then 235 Error("The greatest common divisor is not 1"); 236 fi; 237 238 239 M:= Objectify( NumericalSemigroupsType, rec() ); 240 # Setter(GeneratorsOfNumericalSemigroup)( M, AsList( L ) ); 241 SetMinimalGenerators(M,L); 242 SetGenerators(M,L); 243 return M; 244 245end); 246 247 248 249############################################################################# 250## 251#F FortenTruncatedNCForNumericalSemigroups(l) 252## 253## l contains the list of coefficients of a 254## single linear equation. fortenTruncated gives a minimal generator 255## of the affine semigroup of nonnegative solutions of this equation 256## with the first coordinate equal to one. 257## 258## Used for computing minimal presentations. 259## 260############################################################################# 261InstallGlobalFunction(FortenTruncatedNCForNumericalSemigroups, function(l) 262 local leq, m, solutions, explored, candidates, x, tmp; 263 264 265 # leq(v1,v2) 266 # Compares vectors (lists) v1 and v2, returning true if v1 is less than or 267 # equal than v2 with the usual partial order. 268 leq := function(v1,v2) 269 local v; 270 #one should make sure here that the lengths are the same 271 v:=v2-v1; 272 return (First(v,n->n<0)=fail); 273 end; 274 ## End of leq() -- 275 276 m:=IdentityMat(Length(l)); 277 solutions:=[]; 278 explored:=[]; 279 candidates:=[m[1]]; 280 m:=m{[2..Length(m)]}; 281 while (not(candidates=[])) do 282 x:=candidates[1]; 283 explored:=Union([x],explored); 284 candidates:=candidates{[2..Length(candidates)]}; 285 if(l*x=0) then 286 return x; 287 else 288 tmp:=List(Filtered(m,n->((l*x)*(l*n)<0)),y->y+x); 289 tmp:=Difference(tmp,explored); 290 tmp:=Filtered(tmp,n->(First(solutions,y->leq(y,n))=fail)); 291 candidates:=Union(candidates,tmp); 292 fi; 293 od; 294 return fail; 295end); 296 297#======================================================================== 298## 299#F This function is the NC version of CatenaryDegreeOfElementInNumericalSemigroup. It works 300## well for numbers bigger than the Frobenius number 301## DEPRECATED 302##------------------------------------------------------------------------ 303InstallGlobalFunction(CatenaryDegreeOfElementInNumericalSemigroup_NC, function(n,s) 304 local len, distance, Fn, V, underlyinggraph, i, weights, 305 weightedgraph, j, dd, d, w; 306 307 #---- Local functions definitions ------------------------- 308 #========================================================== 309 #========================================================== 310 #Given two factorizations a and b of n, the distance between a 311 #and b is d(a,b)=max |a-gcd(a,b)|,|b-gcd(a,b)|, where 312 #gcd((a_1,...,a_n),(b_1,...,b_n))=(min(a_1,b_1),...,min(a_n,b_n)). 313 314 315 #---------------------------------------------------------- 316 distance := function(a,b) 317 local k, gcd, i; 318 319 k := Length(a); 320 if k <> Length(b) then 321 Error("The lengths of a and b are different.\n"); 322 fi; 323 324 325 gcd := []; 326 for i in [1..k] do 327 Add(gcd, Minimum(a[i],b[i])); 328 od; 329 return(Maximum(Sum(a-gcd),Sum(b-gcd))); 330 331 end; 332 ## ---- End of distance() ---- 333 334 #========================================================== 335 #---- End of Local functions definitions ------------------ 336 337 #========================================================== 338 #----------- MAIN CODE ------------------------- 339 #---------------------------------------------------------- 340 341 Fn := FactorizationsElementWRTNumericalSemigroup( n, s ); 342 #Print("Factorizations:\n",Fn,"\n"); 343 V := Length(Fn); 344 if V = 1 then 345 return 0; 346 elif V = 2 then 347 return distance(Fn[1],Fn[2]); 348 fi; 349 350 351 # compute the directed weighted graph 352 underlyinggraph := []; 353 for i in [2 .. V] do 354 Add(underlyinggraph, [i..V]); 355 od; 356 Add(underlyinggraph, []); 357 weights := []; 358 weightedgraph := StructuralCopy(underlyinggraph); 359 for i in [1..Length(weightedgraph)] do 360 for j in [1..Length(weightedgraph[i])] do 361 dd := distance(Fn[i],Fn[weightedgraph[i][j]]); 362 Add(weights,dd); 363 weightedgraph[i][j] := [weightedgraph[i][j],dd]; 364 365 od; 366 od; 367 weights:=Set(weights); 368 d := 0; 369 while IsConnectedGraphNCForNumericalSemigroups(underlyinggraph) do 370 w := weights[Length(weights)-d]; 371 d := d+1; 372 for i in weightedgraph do 373 for j in i do 374 if IsBound(j[2]) and j[2]= w then 375 Unbind(i[Position(i,j)]); 376 fi; 377 od; 378 od; 379 for i in [1..Length(weightedgraph)] do 380 weightedgraph[i] := Compacted(weightedgraph[i]); 381 od; 382 underlyinggraph := []; 383 for i in weightedgraph do 384 if i <> [] then 385 Add(underlyinggraph, TransposedMatMutable(i)[1]); 386 else 387 Add(underlyinggraph, []); 388 fi; 389 od; 390 od; 391 392 393 return(weights[Length(weights)-d+1]); 394 395end); 396## ---- End of CatenaryDegreeOfElementInNumericalSemigroup_NC() ---- 397#======================================================================== 398## 399#======================================================================== 400############################################################################ 401## 402#F This function returns true if the graph is connected an false otherwise 403## 404## It is part of the NumericalSGPS package just to avoid the need of using 405## other graph packages only to this effect. It is used in 406## CatenaryDegreeOfElementInNumericalSemigroup 407## 408## 409InstallGlobalFunction( IsConnectedGraphNCForNumericalSemigroups, function(G) 410 local i, j, fl, 411 n, # number of vertices 412 uG, # undirected graph (an edge of the undirected graph may be 413 # seen as a pair of edges of the directed graph) 414 visit, 415 dfs; 416 417 fl := Flat(G); 418 if fl=[] then 419 n := Length(G); 420 else 421 n := Maximum(Length(G),Maximum(fl)); 422 fi; 423 uG := StructuralCopy(G); 424 while Length(uG) < n do 425 Add(uG,[]); 426 od; 427 for i in [1..Length(G)] do 428 for j in G[i] do 429 UniteSet(uG[j],[i]); 430 od; 431 od; 432 433 434 visit := []; # mark the vertices an unvisited 435 for i in [1..n] do 436 visit[i] := 0; 437 od; 438 439 dfs := function(v) #recursive call to Depth First Search 440 local w; 441 visit[v] := 1; 442 for w in uG[v] do 443 if visit[w] = 0 then 444 dfs(w); 445 fi; 446 od; 447 end; 448 dfs(1); 449 if 0 in visit then 450 return false; 451 fi; 452 return true; 453end); 454 455