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