Quelle srglib.gi Sprache: unbekannt

Untersuchungsergebnis.gi Download desUnknown {[0] [0] [0]}zum Wurzelverzeichnis wechseln

#############################################################################
##
#W srglib.gi Algebraic Graph Theory package Rhys J. Evans
##
##
#Y Copyright (C) 2020
##
## Implementation file for functions involving strongly regular graphs.
##

#############################################################################
##
#F ComplementSRGParameters( parms )
##
InstallGlobalFunction( ComplementSRGParameters,
function( parms )

 if not IsFeasibleSRGParameters(parms) then
 Error("usage: ComplementSRGParameters(<parms>), where \n\
 <parms> is a feasible strongly regular graph parameter tuple");
 fi;

 return [parms[1],
 parms[1]-parms[2]-1,
 parms[1]-2-2*parms[2]+parms[4],
 parms[1]-2*parms[2]+parms[3]];
end );

#############################################################################
##
#F IsPrimitiveSRGParameters( [ <v>, <k>, <a>, ] )
##
InstallGlobalFunction( IsPrimitiveSRGParameters,
function( parms )

 if not IsFeasibleSRGParameters(parms) then
 return false;
 fi;
 return not (parms[4]=0 or ComplementSRGParameters(parms)[4]=0);
end );

#############################################################################
##
#F IsTypeISRGParameters( [ <v>, <k>, <a>, ] )
##
InstallGlobalFunction( IsTypeISRGParameters,
function( parms )
 local t,ist1;

 if not IsFeasibleSRGParameters(parms) then
 return false;
 fi;

 ist1:=true;
 t:=parms[4];

 ist1:=ist1 and t>0;
 ist1:=ist1 and parms[1]=4*t+1;
 ist1:=ist1 and parms[2]=2*t;
 ist1:=ist1 and parms[3]=t-1;

 return ist1;
end );

#############################################################################
##
#F IsTypeIISRGParameters( [ <v>, <k>, <a>, ] )
##
InstallGlobalFunction( IsTypeIISRGParameters,
function( parms )
 if not IsFeasibleSRGParameters(parms) then
 return false;
 fi;
 return IsInt(LeastEigenvalueFromSRGParameters(parms));
end );

#############################################################################
##
#F SRGToGlobalParameters( <parms> )
##
InstallGlobalFunction( SRGToGlobalParameters,
function( parms )
 if not IsFeasibleSRGParameters(parms) then
Error("usage: SRGToGlobalParameters(<parms>), where \n\
 <parms> is a feasible strongly regular graph parameter tuple");
 fi;
 return [[0,0,parms[2]],
 [1,parms[3],parms[2]-parms[3]-1],
 [parms[4],parms[2]-parms[4],0]];
end );

#############################################################################
##
#F GlobalToSRGParameters( <parms> )
##
InstallGlobalFunction( GlobalToSRGParameters,
function( parms )
 local v,k,a,b;

 if not (IsRectangularTable(parms) and DimensionsMat(parms)=[3,3] \
 and ForAll(parms,x->ForAll(x,IsInt))) then
 Error("usage: GlobalToSRGParameters( <parms> ), where parms is a 3x3 matrix \n\
 with integer entries.");
 fi;


 k:=parms[1][3];
 a:=parms[2][2];
 b:=parms[3][1];

 if b=0 then
 Error("usage: GlobalToSRGParameters( <parms> ), where parms[3][1] is not\n\
 0.");
 fi;

 v:=k+1+k*(k-a-1)/b;

 if not IsFeasibleSRGParameters([ v, k, a, b ]) then
 Error("usage: GlobalToSRGParameters( <parms> ), where parms is the \n\
 global parameters corresponding to a feasible strongly regular\n\
 graph parameter tuple.");
 fi;

 return [ v, k, a, b ];
end );

#############################################################################
##
#O KreinParameters( [ <v>, <k>, <a>, ] )
##
InstallMethod( KreinParameters, "SRG tuple", [IsList],
function( parms )
 local k,r,s,K;

 if not IsFeasibleSRGParameters(parms) then
 TryNextMethod();
 fi;

 K:=[];
 k:=parms[2];
 s:=LeastEigenvalueFromSRGParameters(parms);
 r:=SecondEigenvalueFromSRGParameters(parms);

 K[1]:=(k+r)*(s+1)*(s+1)-(r+1)*(k+r+2*r*s);
 K[2]:=(k+s)*(r+1)*(r+1)-(s+1)*(k+s+2*r*s);

 return K;

end );

#############################################################################
##
#O IsKreinConditionsSatisfied( [ <v>, <k>, <a>, ] )
##
InstallMethod( IsKreinConditionsSatisfied, "SRG tuple", [IsList],
function( parms )
 if not IsFeasibleSRGParameters(parms) then
 TryNextMethod();
 fi;

 if IsTypeISRGParameters(parms) then
 return true;
 fi;

 return ForAll(KreinParameters(parms),x->x>=0);
end );

#############################################################################
##
#F IsAbsoluteBoundSatisfied( [ <v>, <k>, <a>, ] )
##
InstallGlobalFunction( IsAbsoluteBoundSatisfied,
function( parms )
 local v,f,g;

 if not IsFeasibleSRGParameters(parms) then
 Error("usage: IsAbsoluteBoundSatisifed( <parms> ), where <parms> is a \n \
 feasible strongly regular graph parameter tuple");
 fi;

 v := parms[1];
 f := LeastEigenvalueMultiplicity(parms);
 g := SecondEigenvalueMultiplicity(parms);

 return 2*v <= f*(f+3) and 2*v <= g*(g+3);
end );

#############################################################################
##
#F IsSRGAvailable( <parms> )
##
InstallGlobalFunction( IsSRGAvailable,
function( parms )
 local fn;

 if not IsFeasibleSRGParameters(parms) then
 Error("usage: IsSRGAvailable(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters");
 fi;

 fn := AGT_SRGFilename(parms);

 return fn <> fail and IsReadableFile(fn);
end );

#############################################################################
##
#F SRGLibraryInfo( <parms> )
##
InstallGlobalFunction( SRGLibraryInfo,
function( parms )
 local pos;

 if not IsFeasibleSRGParameters(parms) then
 Error("usage: SRGLibraryInfo(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters");
 fi;

 if parms[1]>AGT_Brouwer_Parameters_MAX then
 Error("usage: SRGLibraryInfo(<parms>), where \n\
 <parms> has first entry at most AGT_Brouwer_Parameters_MAX");
 fi;

 pos:=PositionProperty(AGT_Brouwer_Parameters,x->x[1]=parms);

 return AGT_Brouwer_Parameters[pos];
end );

#############################################################################
##
#F SRG( <parms> , <n> )
##
InstallGlobalFunction( SRG,
function( parms, n )
 local fn, info, gamma;

 if not (IsFeasibleSRGParameters(parms) and IsInt(n) and n>0) then
 Error("usage: SRG(<parms>,<n>), where \n\
 <parms> is feasible strongly regular graph parameters and \n\
 <n> is a positive integer");
 fi;

 if not IsSRGAvailable(parms) then
 return fail;
 fi;

 info:=SRGLibraryInfo(parms);

 if info[3]<n then
 return fail;
 fi;

 fn := AGT_SRGFilename(parms);
 gamma := Graph(ReadDigraphs(fn,n));

 return gamma;
end );

#############################################################################
##
#F NrSRGs( <parms> )
##
InstallGlobalFunction( NrSRGs,
function( parms )
 local info;

 if not IsFeasibleSRGParameters(parms) then
 Error("usage: NrSRGs(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters.");
 fi;

 if parms[1]>AGT_Brouwer_Parameters_MAX then
 return 0;
 fi;

 info:=SRGLibraryInfo(parms);

 return info[3];
end );

#############################################################################
##
#F OneSRG( <parms> )
##
InstallGlobalFunction( OneSRG,
function( parms )
 return SRG(parms,1);
end );

#############################################################################
##
#F AllSRGs( <parms> )
##
InstallGlobalFunction( AllSRGs,
function( parms )
 local fn;

 if not IsFeasibleSRGParameters(parms) then
 Error("usage: AllSRGs(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters.");
 fi;

 if not IsSRGAvailable(parms) then
 return [];
 fi;

 fn := AGT_SRGFilename(parms);

 return List(ReadDigraphs(fn),Graph);
end );

#############################################################################
##
#F SRGIterator( <parms> )
##
InstallGlobalFunction( SRGIterator,
function( parms )
 local filename, decoder, file, record, arg;

 if not IsFeasibleSRGParameters(parms) then
 Error("usage: SRGIterator(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters.");
 fi;

 if not IsSRGAvailable(parms) then
 return Iterator([]);
 fi;

 filename := AGT_SRGFilename(parms);

 file := DigraphFile(filename, "r");

 if file = fail then
 return fail;
 fi;

 record := rec(file := file, current := Graph(file!.coder(file)));

 record.NextIterator := function(iter)
 local next;
 next := iter!.current;
 iter!.current := iter!.file!.coder(iter!.file);
 if iter!.current <> IO_Nothing then
 iter!.current:=Graph(iter!.current);
 fi;
 return next;
 end;

 record.IsDoneIterator := function(iter)
 if iter!.current = IO_Nothing then
 if not iter!.file!.closed then
 IO_Close(iter!.file);
 fi;
 return true;
 else
 return false;
 fi;
 end;

 record.ShallowCopy := function(iter)
 local file;
 file := DigraphFile(UserHomeExpand(filename), decoder, "r");
 return rec(file := file, current := Graph(file!.coder(file)));
 end;

 return IteratorByFunctions(record);
end );

#############################################################################
##
#F SmallFeasibleSRGParameterTuples( v )
##
InstallGlobalFunction( SmallFeasibleSRGParameterTuples,
function( v )
 local parml;

 parml:=Filtered(AGT_Brouwer_Parameters,x->(x[1][1]<=v and x[2]<3));
 parml:=parml{[1..Length(parml)]}[1];

 return parml;

end );

#############################################################################
##
#F IsEnumeratedSRGParameterTuple( [ <v>, <k>, <a>, ] )
##
InstallGlobalFunction( IsEnumeratedSRGParameterTuple,
function( parms )
 local info;

 if not (IsFeasibleSRGParameters(parms) and parms[1]<=AGT_Brouwer_Parameters_MAX) then
 Error("usage: IsEnumeratedSRGParameterTuple(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters, and \n\
 parms[1]<=AGT_Brouwer_Parameters_MAX.");
 fi;

 if not IsPrimitiveSRGParameters(parms) then
 return true;
 fi;

 info := SRGLibraryInfo(parms);

 return info[2]=0 or info[2]=3;

end );

#############################################################################
##
#F IsKnownSRGParameterTuple( [ <v>, <k>, <a>, ] )
##
InstallGlobalFunction( IsKnownSRGParameterTuple,
function( parms )
 local info;

 if not (IsFeasibleSRGParameters(parms) and parms[1]<=AGT_Brouwer_Parameters_MAX) then
 Error("usage: IsKnownSRGParameterTuple(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters, and \n\
 parms[1]<=AGT_Brouwer_Parameters_MAX.");
 fi;

 if not IsPrimitiveSRGParameters(parms) then
 return true;
 fi;

 info := SRGLibraryInfo(parms);

 return info[2]<2;

end );

#############################################################################
##
#F IsAllSRGsStored( [ <v>, <k>, <a>, ] )
##
InstallGlobalFunction( IsAllSRGsStored,
function( parms )
 local info;

 if not (IsFeasibleSRGParameters(parms) and parms[1]<=AGT_Brouwer_Parameters_MAX) then
 Error("usage: IsKnownSRGParameterTuple(<parms>), where \n\
 <parms> is feasible strongly regular graph parameters, and \n\
 parms[1]<=AGT_Brouwer_Parameters_MAX.");
 fi;

 if not IsPrimitiveSRGParameters(parms) then
 return false;
 fi;

 info := SRGLibraryInfo(parms);

 return info[3]=info[4];

end );

#############################################################################
##
#F DisjointUnionOfCliques( <n1> , <n2>, ... )
##
InstallGlobalFunction( DisjointUnionOfCliques,
function( arg... )
 local sum, Grs, Grp, i, fedg, gamma;

 if not ForAll(arg,IsPosInt) then
 Error("usage: DisjointUnionOfCliques(<n1>,<n2>,...), where \n\
 <n1>,<n2>,... are positive integers.");
 fi;

 sum := 0;
 Grs := [];
 fedg := [];

 for i in arg do
 sum := sum + i;
 if i>1 then
 Add(fedg,[sum-i+1,sum-i+2]);
 Add(Grs,SymmetricGroup([sum-i+1..sum]));
 fi;
 od;

 Grp:=DirectProduct(Grs);
 gamma:=EdgeOrbitsGraph(Grp,fedg,sum);
 gamma:=UnderlyingGraph(gamma);

 return NewGroupGraph(AutomorphismGroup(gamma),gamma);
end );

#############################################################################
##
#F CompleteMultipartiteGraph( <n1> , <n2> , ... )
##
InstallGlobalFunction( CompleteMultipartiteGraph,
function( arg... )
 local sum, Grs, Grp, i, fvtx, comb, gamma;

 if not ForAll(arg,IsPosInt) then
 Error("usage: CompleteMultipartiteGraph(<n1>,<n2>,...), where \n\
 <n1>,<n2>,... are positive integers.");
 fi;

 sum := 0;
 Grs := [];
 fvtx := [];

 for i in arg do
 sum := sum + i;
 Add(fvtx,sum-i+1);
 Add(Grs,SymmetricGroup([sum-i+1..sum]));
 od;

 comb:=Combinations(fvtx,2);
 Grp:=DirectProduct(Grs);
 gamma:=EdgeOrbitsGraph(Grp,comb,sum);
 gamma:=UnderlyingGraph(gamma);

 return NewGroupGraph(AutomorphismGroup(gamma),gamma);
end );

#############################################################################
##
#F TriangularGraph( <n> )
##
InstallGlobalFunction( TriangularGraph,
function( n )
 if not (IsPosInt(n) and n>2) then
 Error("usage: TriangularGraph(<n>), where \n\
 <n> is a positive integer of size at least 2.");
 fi;

 return JohnsonGraph(n,2);
end );

#############################################################################
##
#F SquareLatticeGraph( <n> )
##
InstallGlobalFunction( SquareLatticeGraph,
function( n )
 if not (IsPosInt(n) and n>1) then
 Error("usage: SquareLatticeGraph(<n>), where \n\
 <n> is a positive integer of size at least 1.");
 fi;

 return HammingGraph(2,n);
end );

#############################################################################
##
#F HoffmanSingletonGraph( )
##
InstallGlobalFunction( HoffmanSingletonGraph,
function( )
 local G, cyrng, cyflip, permlist, edgelist, gamma, i,j,h,hi,hij;

 permlist := [];
 edgelist:=[];

 # Create initial groups to add multiple edges as orbit members
 for i in [0..9] do
 cyrng := (5*i+1,5*i+2,5*i+3,5*i+4,5*i+5);
 Add(permlist,cyrng);
 od;

 # Add edge. We have 5 5-cycles and then 5 pentagrams
 for i in [0..4] do
 Append(edgelist,[[5*i+1,5*i+2],[5*i+2,5*i+1]]);
 Append(edgelist,[25+[5*i+1,5*i+3],25+[5*i+3,5*i+1]]);
 od;

 G := Group(permlist);
 gamma := EdgeOrbitsGraph(G,edgelist,50);

 # Get rid of the group as it may not consist of automorphisms of
 # the complete graph
 gamma := NewGroupGraph(Group(()),gamma);


 # Adding edges as described by Brouwer
 for h in [1..5] do
 for i in [1..5] do
 hi := h*i;
 for j in [1..5] do
 hij := ((hi+j) mod 5)+1 ;
 AddEdgeOrbit(gamma,[5*(h-1)+j,20+5*i+hij]);
 AddEdgeOrbit(gamma,[20+5*i+hij,5*(h-1)+j]);
 od;
 od;
 od;

 return NewGroupGraph(AutomorphismGroup(gamma),gamma);
end );

#############################################################################
##
#F HigmanSimsGraph( )
##
InstallGlobalFunction( HigmanSimsGraph,
function( )
 local gamma, cocliqs;

 gamma := HoffmanSingletonGraph();
 gamma := ComplementGraph(gamma);
 gamma := NewGroupGraph(Group(()),gamma);

 cocliqs := CompleteSubgraphsOfGivenSize(gamma,15,2,false);

 gamma := Graph(Group(()),cocliqs,OnSets,
 function(x,y) return Length(Intersection(x,y)) in [0,8]; end);

 return NewGroupGraph(AutomorphismGroup(gamma),gamma);
end );

#############################################################################
##
#F SimsGerwitzGraph( )
##
InstallGlobalFunction( SimsGerwitzGraph,
function( )
 local gamma;
 gamma := HigmanSimsGraph();
 gamma := DistanceSetInduced(gamma,[2],[1,2]);

 return NewGroupGraph(AutomorphismGroup(gamma),gamma);
end );

#############################################################################
##
#E

Quelle srglib.gi Sprache: unbekannt

[ zur Elbe Produktseite wechseln0.99Quellennavigators ]