|
#############################################################################
# This file contains obsolet functions which are to be kept during a while for
# compatibility
# WARNING: the manual must be updated before removing the functions
#############################################################################
##
#F GeneratorsOfNumericalSemigroupNC(S)
##
## Returns a set of generators of the numerical
## semigroup S.
##
#############################################################################
# InstallGlobalFunction( GeneratorsOfNumericalSemigroupNC, function(S)
# if not IsNumericalSemigroup(S) then
# Error("The argument must be a numerical semigroup");
# fi;
# if HasGenerators(S) then
# return(Generators(S));
# fi;
# return(MinimalGeneratingSystemOfNumericalSemigroup(S));
# end);
#############################################################################
##
#F ReducedSetOfGeneratorsOfNumericalSemigroup(arg)
##
## 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.
##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.
##
# InstallGlobalFunction( ReducedSetOfGeneratorsOfNumericalSemigroup, function(arg)
# local sumNS, S, apery, n, generators, m, aux, i, g, gen, ss;
# #####################################################
# # Computes the sum of subsets of numerical semigroups
# # WARNING: the arguments have to be non empty sets, not just lists
# sumNS := function(S,T)
# local mm, s, t, R;
# R := [];
# mm := Maximum(Maximum(S),Maximum(T));
# for s in S do
# for t in T do
# if s+t > mm then
# break;
# else
# AddSet(R,s+t);
# fi;
# od;
# od;
# return R;
# end;
# ##
# S := First(arg, s -> IsNumericalSemigroup(s));
# if S = fail then
# Error("Please check the arguments of ReducedSetOfGeneratorsOfNumericalSemigroup");
# fi;
# apery := First(arg, s -> IsBool(s));
# if apery = fail then
# apery := false;
# fi;
# n := First(arg, s -> IsInt(s));
# if n = fail then
# n := 2;
# fi;
# if not IsBound(S!.generators) then
# S!.generators := MinimalGeneratingSystemOfNumericalSemigroup(S);
# return S!.generators;
# else
# if IsBound(S!.minimalgenerators) then
# #S!.generators := MinimalGeneratingSystemOfNumericalSemigroup(S);
# return S!.minimalgenerators;
# fi;
# generators := S!.generators;
# m := Minimum(generators); # the multiplicity
# if m = 1 then
# S!.generators := [1];
# return S!.generators;
# elif m = 2 then
# S!.generators := [2,First(generators, g -> g mod 2 = 1)];
# return S!.generators;
# fi;
# if apery then
# aux := [m];
# for i in [1..m-1] do
# g := First(generators, g -> g mod m = i);
# if g <> fail then
# Append(aux,[g]);
# fi;
# od;
# gen := Set(aux);
# else
# gen := ShallowCopy(generators);
# fi;
# ss := sumNS(gen,gen);
# i := 1;
# while i < n and ss <> [] do
# gen := Difference(gen,ss);
# ss := sumNS(gen,ss);
# i := i+1;
# od;
# fi;
# S!.generators := gen;
# return S!.generators;
# end);
##
#############################################################################
#############################################################################
##
#F NumericalSemigroupByMinimalGenerators(arg)
##
## Returns the numerical semigroup minimally generated by arg.
## If the generators given are not minimal, the minimal ones
## are computed and used.
##
#############################################################################
InstallGlobalFunction(NumericalSemigroupByMinimalGenerators, function(arg)
local L, S, M, l,
minimalGSNS, sumNS;
#####################################################
# Computes the sum of subsets of numerical semigroups
sumNS := function(S,T)
local mm, s, t, R;
R := [];
mm := Minimum(Maximum(S),Maximum(T));
for s in S do
for t in T do
if s+t > mm then
break;
else
AddSet(R,s+t);
fi;
od;
od;
return R;
end;
## End of sumNS(S,T) --
minimalGSNS := function(L)
local res, gen, ss, sss, ssss, i, ngen;
if 1 in L then
return [1];
fi;
gen := ShallowCopy(L);
# a naive reduction of the number of generators
ss := sumNS(gen,gen);
gen := Difference(gen,ss);
if ss <> [] then
sss := sumNS(ss,gen);
gen := Difference(gen,sss);
if sss <> [] then
ssss := sumNS(sss,gen);
gen := Difference(gen,ssss);
fi;
fi;
if Length(gen) = 2 then
return gen;
fi;
i := Length(gen);
while i >= 2 do
ngen := Difference(gen, [gen[i]]);
if Gcd(ngen) = 1 and
BelongsToNumericalSemigroup(gen[i], NumericalSemigroup(ngen)) then
gen := ngen;
i := i - 1;
else
i := i - 1;
fi;
od;
return gen;
end;
## End of minimalGSNS(L) --
if IsList(arg[1]) then
L := Difference(Set(arg[1]),[0]);
else
L := Difference(Set(arg),[0]);
fi;
if L=[] then
Error("There should be at least one generator.\n");
fi;
if not ForAll(L, x -> IsPosInt(x)) then
Error("The arguments should be positive integers.\n");
fi;
if Gcd(L) <> 1 then
Error("The greatest common divisor is not 1");
fi;
l := minimalGSNS(L);
if not Length(L) = Length(l) then
Info(InfoWarning,1,"The list ", L, " can not be the minimal generating set. The list ", l, " will be used instead.");
L := l;
fi;
M:= Objectify( NumericalSemigroupsType, rec() );
# Setter(GeneratorsOfNumericalSemigroup)( M, AsList( L ) );
SetMinimalGenerators(M,L);
SetGenerators(M,L);
return M;
end);
#############################################################################
##
#F NumericalSemigroupByMinimalGeneratorsNC(arg)
##
## Returns the numerical semigroup minimally generated by arg.
## No test is made about args' minimality.
##
#############################################################################
InstallGlobalFunction(NumericalSemigroupByMinimalGeneratorsNC, function(arg)
local L, S, M;
if IsList(arg[1]) then
L := Difference(Set(arg[1]),[0]);
else
L := Difference(Set(arg),[0]);
fi;
if not ForAll(L, x -> IsPosInt(x)) then
Error("The arguments should be positive integers");
fi;
if Gcd(L) <> 1 then
Error("The greatest common divisor is not 1");
fi;
M:= Objectify( NumericalSemigroupsType, rec() );
# Setter(GeneratorsOfNumericalSemigroup)( M, AsList( L ) );
SetMinimalGenerators(M,L);
SetGenerators(M,L);
return M;
end);
#############################################################################
##
#F FortenTruncatedNCForNumericalSemigroups(l)
##
## l contains the list of coefficients of a
## single linear equation. fortenTruncated gives a minimal generator
## of the affine semigroup of nonnegative solutions of this equation
## with the first coordinate equal to one.
##
## Used for computing minimal presentations.
##
#############################################################################
InstallGlobalFunction(FortenTruncatedNCForNumericalSemigroups, function(l)
local leq, m, solutions, explored, candidates, x, tmp;
# leq(v1,v2)
# Compares vectors (lists) v1 and v2, returning true if v1 is less than or
# equal than v2 with the usual partial order.
leq := function(v1,v2)
local v;
#one should make sure here that the lengths are the same
v:=v2-v1;
return (First(v,n->n<0)=fail);
end;
## End of leq() --
m:=IdentityMat(Length(l));
solutions:=[];
explored:=[];
candidates:=[m[1]];
m:=m{[2..Length(m)]};
while (not(candidates=[])) do
x:=candidates[1];
explored:=Union([x],explored);
candidates:=candidates{[2..Length(candidates)]};
if(l*x=0) then
return x;
else
tmp:=List(Filtered(m,n->((l*x)*(l*n)<0)),y->y+x);
tmp:=Difference(tmp,explored);
tmp:=Filtered(tmp,n->(First(solutions,y->leq(y,n))=fail));
candidates:=Union(candidates,tmp);
fi;
od;
return fail;
end);
#========================================================================
##
#F This function is the NC version of CatenaryDegreeOfElementInNumericalSemigroup. It works
## well for numbers bigger than the Frobenius number
## DEPRECATED
##------------------------------------------------------------------------
InstallGlobalFunction(CatenaryDegreeOfElementInNumericalSemigroup_NC, function(n,s)
local len, distance, Fn, V, underlyinggraph, i, weights,
weightedgraph, j, dd, d, w;
#---- Local functions definitions -------------------------
#==========================================================
#==========================================================
#Given two factorizations a and b of n, the distance between a
#and b is d(a,b)=max |a-gcd(a,b)|,|b-gcd(a,b)|, where
#gcd((a_1,...,a_n),(b_1,...,b_n))=(min(a_1,b_1),...,min(a_n,b_n)).
#----------------------------------------------------------
distance := function(a,b)
local k, gcd, i;
k := Length(a);
if k <> Length(b) then
Error("The lengths of a and b are different.\n");
fi;
gcd := [];
for i in [1..k] do
Add(gcd, Minimum(a[i],b[i]));
od;
return(Maximum(Sum(a-gcd),Sum(b-gcd)));
end;
## ---- End of distance() ----
#==========================================================
#---- End of Local functions definitions ------------------
#==========================================================
#----------- MAIN CODE -------------------------
#----------------------------------------------------------
Fn := FactorizationsElementWRTNumericalSemigroup( n, s );
#Print("Factorizations:\n",Fn,"\n");
V := Length(Fn);
if V = 1 then
return 0;
elif V = 2 then
return distance(Fn[1],Fn[2]);
fi;
# compute the directed weighted graph
underlyinggraph := [];
for i in [2 .. V] do
Add(underlyinggraph, [i..V]);
od;
Add(underlyinggraph, []);
weights := [];
weightedgraph := StructuralCopy(underlyinggraph);
for i in [1..Length(weightedgraph)] do
for j in [1..Length(weightedgraph[i])] do
dd := distance(Fn[i],Fn[weightedgraph[i][j]]);
Add(weights,dd);
weightedgraph[i][j] := [weightedgraph[i][j],dd];
od;
od;
weights:=Set(weights);
d := 0;
while IsConnectedGraphNCForNumericalSemigroups(underlyinggraph) do
w := weights[Length(weights)-d];
d := d+1;
for i in weightedgraph do
for j in i do
if IsBound(j[2]) and j[2]= w then
Unbind(i[Position(i,j)]);
fi;
od;
od;
for i in [1..Length(weightedgraph)] do
weightedgraph[i] := Compacted(weightedgraph[i]);
od;
underlyinggraph := [];
for i in weightedgraph do
if i <> [] then
Add(underlyinggraph, TransposedMatMutable(i)[1]);
else
Add(underlyinggraph, []);
fi;
od;
od;
return(weights[Length(weights)-d+1]);
end);
## ---- End of CatenaryDegreeOfElementInNumericalSemigroup_NC() ----
#========================================================================
##
#========================================================================
############################################################################
##
#F This function returns true if the graph is connected an false otherwise
##
## It is part of the NumericalSGPS package just to avoid the need of using
## other graph packages only to this effect. It is used in
## CatenaryDegreeOfElementInNumericalSemigroup
##
##
InstallGlobalFunction( IsConnectedGraphNCForNumericalSemigroups, function(G)
local i, j, fl,
n, # number of vertices
uG, # undirected graph (an edge of the undirected graph may be
# seen as a pair of edges of the directed graph)
visit,
dfs;
fl := Flat(G);
if fl=[] then
n := Length(G);
else
n := Maximum(Length(G),Maximum(fl));
fi;
uG := StructuralCopy(G);
while Length(uG) < n do
Add(uG,[]);
od;
for i in [1..Length(G)] do
for j in G[i] do
UniteSet(uG[j],[i]);
od;
od;
visit := []; # mark the vertices an unvisited
for i in [1..n] do
visit[i] := 0;
od;
dfs := function(v) #recursive call to Depth First Search
local w;
visit[v] := 1;
for w in uG[v] do
if visit[w] = 0 then
dfs(w);
fi;
od;
end;
dfs(1);
if 0 in visit then
return false;
fi;
return true;
end);
[ Dauer der Verarbeitung: 0.45 Sekunden
(vorverarbeitet)
]
|
