Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package gap-grape for openSUSE:Factory checked in at 2024-10-16 23:54:22 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/gap-grape (Old) and /work/SRC/openSUSE:Factory/.gap-grape.new.19354 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "gap-grape" Wed Oct 16 23:54:22 2024 rev:3 rq:1208481 version:4.9.2 Changes: -------- --- /work/SRC/openSUSE:Factory/gap-grape/gap-grape.changes 2024-09-04 13:27:03.351869542 +0200 +++ /work/SRC/openSUSE:Factory/.gap-grape.new.19354/gap-grape.changes 2024-10-16 23:54:48.917157150 +0200 @@ -1,0 +2,13 @@ +Wed Oct 16 16:37:33 UTC 2024 - Jan Engelhardt <[email protected]> + +- Update to release 4.9.2 + * Included new functions ``IsVertexColouring`` and + ``GRAPE_ExactSetCover``. + * Made new documentation chapter ``Auxiliary Functions``, + currently containing documentation for ``SmallestImageSet`` + and ``GRAPE_ExactSetCover``. + * Made a performance improvement for + ``CompleteSubgraphsOfGivenSize`` for the case when all + weightvectors are (0,1)-vectors of dimension greater than 1. + +------------------------------------------------------------------- Old: ---- grape-4.9.1.tar.gz New: ---- grape-4.9.2.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ gap-grape.spec ++++++ --- /var/tmp/diff_new_pack.DDLXvI/_old 2024-10-16 23:54:51.097248070 +0200 +++ /var/tmp/diff_new_pack.DDLXvI/_new 2024-10-16 23:54:51.113248738 +0200 @@ -17,7 +17,7 @@ Name: gap-grape -Version: 4.9.1 +Version: 4.9.2 Release: 0 Summary: GAP: GRaph Algorithms using PErmutation groups License: GPL-2.0-or-later ++++++ _scmsync.obsinfo ++++++ --- /var/tmp/diff_new_pack.DDLXvI/_old 2024-10-16 23:54:51.245254243 +0200 +++ /var/tmp/diff_new_pack.DDLXvI/_new 2024-10-16 23:54:51.257254743 +0200 @@ -1,5 +1,5 @@ -mtime: 1725404969 -commit: 77e7e059e6a5f37f4c781079a473be3c72a72cd57994a2827fe2099164d46eea +mtime: 1729096685 +commit: 09edcffc0202bb227d158016e295569f773804f3d8fff5eba7abb1139ad19ab7 url: https://src.opensuse.org/jengelh/gap-grape revision: master ++++++ build.specials.obscpio ++++++ diff: old/*: No such file or directory diff: new/*: No such file or directory ++++++ grape-4.9.1.tar.gz -> grape-4.9.2.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/CHANGES.md new/grape-4.9.2/CHANGES.md --- old/grape-4.9.1/CHANGES.md 2024-08-30 14:31:32.000000000 +0200 +++ new/grape-4.9.2/CHANGES.md 2024-10-11 17:24:02.000000000 +0200 @@ -1,3 +1,17 @@ +Main changes from GRAPE 4.9.1 to GRAPE 4.9.2 (11 October 2024) +-------------------------------------------------------------- + +1. Included new functions ``IsVertexColouring`` and +``GRAPE_ExactSetCover``. + +2. Made new documentation chapter ``Auxiliary Functions``, +currently containing documentation for ``SmallestImageSet`` and +``GRAPE_ExactSetCover``. + +3. Made a performance improvement for ``CompleteSubgraphsOfGivenSize`` +for the case when all weightvectors are (0,1)-vectors of dimension +greater than 1. + Main changes from GRAPE 4.9.0 to GRAPE 4.9.1 (30 August 2024) ------------------------------------------------------------- diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/PackageInfo.g new/grape-4.9.2/PackageInfo.g --- old/grape-4.9.1/PackageInfo.g 2024-08-30 14:31:32.000000000 +0200 +++ new/grape-4.9.2/PackageInfo.g 2024-10-11 17:24:02.000000000 +0200 @@ -10,10 +10,10 @@ ## See '?Extending: Version Numbers' in GAP help for an explanation ## of valid version numbers. -Version := "4.9.1", +Version := "4.9.2", ## Release date of the current version in dd/mm/yyyy format. -Date := "30/08/2024", +Date := "11/10/2024", ## Machine readable license information (as an SPDX identifier) License := "Apache-2.0 AND GPL-2.0-or-later", @@ -133,7 +133,7 @@ ## *Optional*: Here you can list some keyword related to the topic ## of the package. -Keywords := ["graph","geometry","design"] +Keywords := ["graph","design","finite geometry","clique number","chromatic number"] )); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/README.md new/grape-4.9.2/README.md --- old/grape-4.9.1/README.md 2024-08-30 14:31:32.000000000 +0200 +++ new/grape-4.9.2/README.md 2024-10-11 17:24:02.000000000 +0200 @@ -1,5 +1,5 @@ -The GRAPE 4.9.1 Package for GAP +The GRAPE 4.9.2 Package for GAP =============================== GRAPE is a GAP package for computing with graphs and groups, by @@ -26,7 +26,7 @@ Please reference your use of the GRAPE package in a published work as follows: -L.H. Soicher, The GRAPE package for GAP, Version 4.9.1, 2024, +L.H. Soicher, The GRAPE package for GAP, Version 4.9.2, 2024, <https://gap-packages.github.io/grape>. Questions, remarks, suggestions, and issues diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/doc/auxil.tex new/grape-4.9.2/doc/auxil.tex --- old/grape-4.9.1/doc/auxil.tex 1970-01-01 01:00:00.000000000 +0100 +++ new/grape-4.9.2/doc/auxil.tex 2024-10-11 18:17:41.000000000 +0200 @@ -0,0 +1,92 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% +%A auxil.tex GRAPE documentation Leonard Soicher +% +% +% +\def\GRAPE{\sf GRAPE} +\def\nauty{\it nauty} +\def\G{\Gamma} +\def\Aut{{\rm Aut}\,} +\def\x{\times} +\Chapter{Auxiliary Functions} + +This chapter documents some auxiliary functions used in {\GRAPE}, +which may be of wider interest. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\Section{Steve Linton's Function SmallestImageSet} + +\>SmallestImageSet( <G>, <S> ) +\>SmallestImageSet( <G>, <S>, <H> ) + +Let <G> be a permutation group on $\{1,\ldots,n\}$, and let <S> +be a subset of $\{1,\ldots,n\}$. Then this function returns the +lexicographically least set in the <G>-orbit of <S>, with respect to the +action `OnSets', without explicitly computing this (possibly huge) orbit. + +Thus, if <C> is a list of subsets of $\{1,\ldots,n\}$ and we +want to determine a set of (canonical) representatives for the +distinct <G>-orbits of the elements of <C>, we can do this as +`Set(<C>,c->SmallestImageSet(<G>,c))'. + +If the setwise stabilizer in <G> of <S> is known, then this should be +given as the optional third parameter, to avoid the recomputation of +this stabilizer. + +The function `SmallestImageSet' was written by Steve Linton, based +on his algorithm described in \cite{Lin04}. + +\beginexample +gap> J:=JohnsonGraph(12,5);; +gap> OrderGraph(J); +792 +gap> G:=J.group;; +gap> Size(G); +479001600 +gap> S:=[67,93,100,204,677,750];; +gap> SmallestImageSet(G,S); +[ 1, 2, 22, 212, 242, 446 ] +\endexample + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\Section{Exact Set-cover} + +\>GRAPE_ExactSetCover( <G>, <blocks>, <n> ) +\>GRAPE_ExactSetCover( <G>, <blocks>, <n>, <H> ) + +Suppose <n> is a non-negative integer, <G> is a permutation group +on $\{1,\ldots,n\}$, <blocks> is a list of non-empty subsets +of $\{1,\ldots,n\}$, and the optional parameter <H> (default: +`Group(())') is a subgroup of <G>. + +Then this function returns an <H>-invariant exact +set-cover of $\{1,\ldots,n\}$, consisting of elements from the union of +`Orbits(<G>,<blocks>,OnSets)', if such a cover exists, +and returns `fail' otherwise. An exact set-cover is given as a set of +sets forming a partition of $\{1,\ldots,n\}$. + +\beginexample +gap> G:=PSL(2,5);; +gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); +fail +gap> G:=PGL(2,5);; +gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); +[ [ 1, 2, 3 ], [ 4, 5, 6 ] ] +gap> n:=280;; +gap> G:=OnePrimitiveGroup(NrMovedPoints,n,Size,604800*2); +J_2.2 +gap> gamma:=First(GeneralizedOrbitalGraphs(G),x->VertexDegrees(x)=[135]);; +gap> omega:=CliqueNumber(gamma); +28 +gap> blocks:=CompleteSubgraphsOfGivenSize(ComplementGraph(gamma),n/omega,2);; +gap> Collected(List(blocks,Length)); +[ [ 10, 2 ] ] +gap> H:=SylowSubgroup(G,7);; +gap> partition:=GRAPE_ExactSetCover(G,blocks,n,H);; +gap> Collected(List(partition,Length)); +[ [ 10, 28 ] ] +gap> Union(partition)=[1..n]; +true +\endexample + diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/doc/colour.tex new/grape-4.9.2/doc/colour.tex --- old/grape-4.9.1/doc/colour.tex 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/doc/colour.tex 2024-10-11 18:17:41.000000000 +0200 @@ -69,6 +69,35 @@ \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\Section{IsVertexColouring} + +\>IsVertexColouring( <gamma>, <C> ) +\>IsVertexColouring( <gamma>, <C>, <k> ) + +Suppose that <gamma> is a simple graph, <C> is a list of positive integers +of length `OrderGraph(<gamma>)', and <k> is a non-negative integer +(default: `OrderGraph(<gamma>)'). + +Then this function returns `true' if <C> is a vertex <k>-colouring of +<gamma>, that is, a proper vertex-colouring using at most <k>-colours (for +which $<C>[i]$ is the colour of the $i$-th vertex), and `false' if not. + +See also "VertexColouring". + +\beginexample +gap> gamma:=JohnsonGraph(7,3);; +gap> C:=VertexColouring(gamma,6);; +gap> IsVertexColouring(gamma,C); +true +gap> IsVertexColouring(gamma,C,7); +true +gap> IsVertexColouring(gamma,C,6); +true +gap> IsVertexColouring(gamma,C,5); +false +\endexample + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MinimumVertexColouring} \>MinimumVertexColouring( <gamma> ) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/doc/grape.tex new/grape-4.9.2/doc/grape.tex --- old/grape-4.9.1/doc/grape.tex 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/doc/grape.tex 2024-10-11 18:17:41.000000000 +0200 @@ -12,7 +12,7 @@ \Chapter{Grape} -This manual describes the {\GRAPE} (Version~4.9.1) package for computing +This manual describes the {\GRAPE} (Version~4.9.2) package for computing with graphs and groups. {\GRAPE} is primarily designed for the construction and analysis of @@ -48,7 +48,7 @@ If you use {\GRAPE} in a published work, then please reference the package as follows: -L.H. Soicher, The {GRAPE} package for {GAP}, Version~4.9.1, 2024, +L.H. Soicher, The {GRAPE} package for {GAP}, Version~4.9.2, 2024, \URL{https://gap-packages.github.io/grape}. For questions, remarks, suggestions, and issues, please use the issue Binary files old/grape-4.9.1/doc/manual.dvi and new/grape-4.9.2/doc/manual.dvi differ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/doc/manual.lab new/grape-4.9.2/doc/manual.lab --- old/grape-4.9.1/doc/manual.lab 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/doc/manual.lab 2024-10-11 18:17:41.000000000 +0200 @@ -160,24 +160,27 @@ \makelabel{grape:VertexColouring}{7.1.1} \makelabel{grape:VertexColouring}{7.1.1} \makelabel{grape:VertexColouring}{7.1.1} -\makelabel{grape:MinimumVertexColouring}{7.2} -\makelabel{grape:MinimumVertexColouring}{7.2.1} -\makelabel{grape:ChromaticNumber}{7.3} -\makelabel{grape:ChromaticNumber}{7.3.1} -\makelabel{grape:CompleteSubgraphs}{7.4} -\makelabel{grape:CompleteSubgraphs}{7.4.1} -\makelabel{grape:CompleteSubgraphs}{7.4.1} -\makelabel{grape:CompleteSubgraphs}{7.4.1} -\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.5} -\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.5.1} -\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.5.1} -\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.5.1} -\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.5.1} -\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.5.1} -\makelabel{grape:MaximumClique}{7.6} -\makelabel{grape:MaximumClique}{7.6.1} -\makelabel{grape:CliqueNumber}{7.7} -\makelabel{grape:CliqueNumber}{7.7.1} +\makelabel{grape:IsVertexColouring}{7.2} +\makelabel{grape:IsVertexColouring}{7.2.1} +\makelabel{grape:IsVertexColouring}{7.2.1} +\makelabel{grape:MinimumVertexColouring}{7.3} +\makelabel{grape:MinimumVertexColouring}{7.3.1} +\makelabel{grape:ChromaticNumber}{7.4} +\makelabel{grape:ChromaticNumber}{7.4.1} +\makelabel{grape:CompleteSubgraphs}{7.5} +\makelabel{grape:CompleteSubgraphs}{7.5.1} +\makelabel{grape:CompleteSubgraphs}{7.5.1} +\makelabel{grape:CompleteSubgraphs}{7.5.1} +\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.6} +\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.6.1} +\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.6.1} +\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.6.1} +\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.6.1} +\makelabel{grape:CompleteSubgraphsOfGivenSize}{7.6.1} +\makelabel{grape:MaximumClique}{7.7} +\makelabel{grape:MaximumClique}{7.7.1} +\makelabel{grape:CliqueNumber}{7.8} +\makelabel{grape:CliqueNumber}{7.8.1} \makelabel{grape:Automorphism groups and isomorphism testing for graphs}{8} \makelabel{grape:Graphs with colour-classes}{8.1} \makelabel{grape:AutGroupGraph}{8.2} @@ -199,10 +202,13 @@ \makelabel{grape:PartialLinearSpaces}{9.1.1} \makelabel{grape:PartialLinearSpaces}{9.1.1} \makelabel{grape:A research application of PartialLinearSpaces}{9.2} -\makelabel{grape:Steve Linton's function SmallestImageSet}{10} -\makelabel{grape:SmallestImageSet}{10.1} +\makelabel{grape:Auxiliary Functions}{10} +\makelabel{grape:Steve Linton's Function SmallestImageSet}{10.1} \makelabel{grape:SmallestImageSet}{10.1.1} \makelabel{grape:SmallestImageSet}{10.1.1} +\makelabel{grape:Exact Set-cover}{10.2} +\makelabel{grape:GRAPE_ExactSetCover}{10.2.1} +\makelabel{grape:GRAPE_ExactSetCover}{10.2.1} \makelabel{grape:Bibliography}{} \setcitlab {BCN89}{BCN89} \setcitlab {Cam99}{Cam99} Binary files old/grape-4.9.1/doc/manual.pdf and new/grape-4.9.2/doc/manual.pdf differ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/doc/manual.six new/grape-4.9.2/doc/manual.six --- old/grape-4.9.1/doc/manual.six 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/doc/manual.six 2024-10-11 18:17:41.000000000 +0200 @@ -164,31 +164,34 @@ F 7.1. VertexColouring F 7.1. VertexColouring I 7.1. proper vertex-colouring -S 7.2. MinimumVertexColouring -F 7.2. MinimumVertexColouring -I 7.2. minimum vertex-colouring -S 7.3. ChromaticNumber -F 7.3. ChromaticNumber -I 7.3. chromatic number -S 7.4. CompleteSubgraphs -F 7.4. CompleteSubgraphs -F 7.4. CompleteSubgraphs -F 7.4. CompleteSubgraphs -I 7.4. Cliques -S 7.5. CompleteSubgraphsOfGivenSize -F 7.5. CompleteSubgraphsOfGivenSize -F 7.5. CompleteSubgraphsOfGivenSize -F 7.5. CompleteSubgraphsOfGivenSize -F 7.5. CompleteSubgraphsOfGivenSize -F 7.5. CompleteSubgraphsOfGivenSize -I 7.5. CliquesOfGivenSize -S 7.6. MaximumClique -F 7.6. MaximumClique -I 7.6. maximum clique -I 7.6. MaximumCompleteSubgraph -S 7.7. CliqueNumber -F 7.7. CliqueNumber -I 7.7. clique number +S 7.2. IsVertexColouring +F 7.2. IsVertexColouring +F 7.2. IsVertexColouring +S 7.3. MinimumVertexColouring +F 7.3. MinimumVertexColouring +I 7.3. minimum vertex-colouring +S 7.4. ChromaticNumber +F 7.4. ChromaticNumber +I 7.4. chromatic number +S 7.5. CompleteSubgraphs +F 7.5. CompleteSubgraphs +F 7.5. CompleteSubgraphs +F 7.5. CompleteSubgraphs +I 7.5. Cliques +S 7.6. CompleteSubgraphsOfGivenSize +F 7.6. CompleteSubgraphsOfGivenSize +F 7.6. CompleteSubgraphsOfGivenSize +F 7.6. CompleteSubgraphsOfGivenSize +F 7.6. CompleteSubgraphsOfGivenSize +F 7.6. CompleteSubgraphsOfGivenSize +I 7.6. CliquesOfGivenSize +S 7.7. MaximumClique +F 7.7. MaximumClique +I 7.7. maximum clique +I 7.7. MaximumCompleteSubgraph +S 7.8. CliqueNumber +F 7.8. CliqueNumber +I 7.8. clique number C cnauty.tex 8. Automorphism groups and isomorphism testing for graphs S 8.1. Graphs with colour-classes S 8.2. AutGroupGraph @@ -210,7 +213,10 @@ F 9.1. PartialLinearSpaces F 9.1. PartialLinearSpaces S 9.2. A research application of PartialLinearSpaces -C smallestim.tex 10. Steve Linton's function SmallestImageSet -S 10.1. SmallestImageSet +C auxil.tex 10. Auxiliary Functions +S 10.1. Steve Linton's Function SmallestImageSet F 10.1. SmallestImageSet F 10.1. SmallestImageSet +S 10.2. Exact Set-cover +F 10.2. GRAPE_ExactSetCover +F 10.2. GRAPE_ExactSetCover diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/doc/manual.tex new/grape-4.9.2/doc/manual.tex --- old/grape-4.9.1/doc/manual.tex 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/doc/manual.tex 2024-10-11 18:17:41.000000000 +0200 @@ -71,7 +71,7 @@ \Input{colour} \Input{cnauty} \Input{partlin} -\Input{smallestim} +\Input{auxil} % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/doc/smallestim.tex new/grape-4.9.2/doc/smallestim.tex --- old/grape-4.9.1/doc/smallestim.tex 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/doc/smallestim.tex 1970-01-01 01:00:00.000000000 +0100 @@ -1,51 +0,0 @@ -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% -%A smallestim.tex GRAPE documentation Leonard Soicher -% -% -% -\def\GRAPE{\sf GRAPE} -\def\nauty{\it nauty} -\def\G{\Gamma} -\def\Aut{{\rm Aut}\,} -\def\x{\times} -\Chapter{Steve Linton's function SmallestImageSet} - -This chapter documents the straightforward application of Steve Linton's -function `SmallestImageSet' \cite{Lin04}, which is included and used -in {\GRAPE}. The function is of use when classifying objects up to -the action of a given permutation group $G$, when the objects can be -represented as subsets of the permutation domain of $G$. - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\Section{SmallestImageSet} - -\>SmallestImageSet( <G>, <S> ) -\>SmallestImageSet( <G>, <S>, <H> ) - -Let <G> be a permutation group on $\{1,\ldots,n\}$, and let <S> -be a subset of $\{1,\ldots,n\}$. Then this function returns the -lexicographically least set in the <G>-orbit of <S>, with respect to the -action `OnSets', without explicitly computing this (possibly huge) orbit. - -Thus, if <C> is a list of subsets of $\{1,\ldots,n\}$ and we -want to determine a set of (canonical) representatives for the -distinct <G>-orbits of the elements of <C>, we can do this as -`Set(<C>,c->SmallestImageSet(<G>,c))'. - -If the setwise stabilizer in <G> of <S> is known, then this should be -given as the optional third parameter, to avoid the recomputation of -this stabilizer. - -\beginexample -gap> J:=JohnsonGraph(12,5);; -gap> OrderGraph(J); -792 -gap> G:=J.group;; -gap> Size(G); -479001600 -gap> S:=[67,93,100,204,677];; -gap> SmallestImageSet(G,S); -[ 1, 2, 22, 220, 453 ] -\endexample - diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP001.htm new/grape-4.9.2/htm/CHAP001.htm --- old/grape-4.9.1/htm/CHAP001.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP001.htm 2024-10-11 18:17:41.000000000 +0200 @@ -11,7 +11,7 @@ <li> <A HREF="CHAP001.htm#SECT004">Examples of the use of GRAPE</a> </ol><p> <p> -This manual describes the GRAPE (Version 4.9.1) package for computing +This manual describes the GRAPE (Version 4.9.2) package for computing with graphs and groups. <p> GRAPE is primarily designed for the construction and analysis of @@ -47,7 +47,7 @@ If you use GRAPE in a published work, then please reference the package as follows: <p> -L.H. Soicher, The GRAPE package for GAP, Version 4.9.1, 2024, +L.H. Soicher, The GRAPE package for GAP, Version 4.9.2, 2024, <a href="https://gap-packages.github.io/grape";>https://gap-packages.github.io/grape</a>. <p> For questions, remarks, suggestions, and issues, please use the issue @@ -237,5 +237,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP002.htm new/grape-4.9.2/htm/CHAP002.htm --- old/grape-4.9.1/htm/CHAP002.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP002.htm 2024-10-11 18:17:41.000000000 +0200 @@ -465,5 +465,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP003.htm new/grape-4.9.2/htm/CHAP003.htm --- old/grape-4.9.1/htm/CHAP003.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP003.htm 2024-10-11 18:17:41.000000000 +0200 @@ -440,5 +440,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Previous</a>] [<a href ="CHAP004.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP004.htm new/grape-4.9.2/htm/CHAP004.htm --- old/grape-4.9.1/htm/CHAP004.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP004.htm 2024-10-11 18:17:41.000000000 +0200 @@ -284,5 +284,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP005.htm new/grape-4.9.2/htm/CHAP005.htm --- old/grape-4.9.1/htm/CHAP005.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP005.htm 2024-10-11 18:17:41.000000000 +0200 @@ -140,7 +140,7 @@ An error is signalled if <var>indset</var> and <var>forbidden</var> have non-trivial intersection. <p> -See also <a href="CHAP007.htm#SSEC004.1">CompleteSubgraphs</a> and <a href="CHAP007.htm#SSEC005.1">CompleteSubgraphsOfGivenSize</a>, which +See also <a href="CHAP007.htm#SSEC005.1">CompleteSubgraphs</a> and <a href="CHAP007.htm#SSEC006.1">CompleteSubgraphsOfGivenSize</a>, which can be used on the complement graph of <var>gamma</var> to look seriously for independent sets. <p> @@ -151,5 +151,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP004.htm">Previous</a>] [<a href ="CHAP006.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP006.htm new/grape-4.9.2/htm/CHAP006.htm --- old/grape-4.9.1/htm/CHAP006.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP006.htm 2024-10-11 18:17:41.000000000 +0200 @@ -526,5 +526,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP005.htm">Previous</a>] [<a href ="CHAP007.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP007.htm new/grape-4.9.2/htm/CHAP007.htm --- old/grape-4.9.1/htm/CHAP007.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP007.htm 2024-10-11 18:17:41.000000000 +0200 @@ -6,12 +6,13 @@ <H3>Sections</H3> <oL> <li> <A HREF="CHAP007.htm#SECT001">VertexColouring</a> -<li> <A HREF="CHAP007.htm#SECT002">MinimumVertexColouring</a> -<li> <A HREF="CHAP007.htm#SECT003">ChromaticNumber</a> -<li> <A HREF="CHAP007.htm#SECT004">CompleteSubgraphs</a> -<li> <A HREF="CHAP007.htm#SECT005">CompleteSubgraphsOfGivenSize</a> -<li> <A HREF="CHAP007.htm#SECT006">MaximumClique</a> -<li> <A HREF="CHAP007.htm#SECT007">CliqueNumber</a> +<li> <A HREF="CHAP007.htm#SECT002">IsVertexColouring</a> +<li> <A HREF="CHAP007.htm#SECT003">MinimumVertexColouring</a> +<li> <A HREF="CHAP007.htm#SECT004">ChromaticNumber</a> +<li> <A HREF="CHAP007.htm#SECT005">CompleteSubgraphs</a> +<li> <A HREF="CHAP007.htm#SECT006">CompleteSubgraphsOfGivenSize</a> +<li> <A HREF="CHAP007.htm#SECT007">MaximumClique</a> +<li> <A HREF="CHAP007.htm#SECT008">CliqueNumber</a> </ol><p> <p> The following sections describe functions for (proper) vertex-colouring @@ -75,9 +76,39 @@ </pre> <p> <p> -<h2><a name="SECT002">7.2 MinimumVertexColouring</a></h2> +<h2><a name="SECT002">7.2 IsVertexColouring</a></h2> <p><p> <a name = "SSEC002.1"></a> +<li><code>IsVertexColouring( </code><var>gamma</var><code>, </code><var>C</var><code> )</code> +<li><code>IsVertexColouring( </code><var>gamma</var><code>, </code><var>C</var><code>, </code><var>k</var><code> )</code> +<p> +Suppose that <var>gamma</var> is a simple graph, <var>C</var> is a list of positive integers +of length <code>OrderGraph(</code><var>gamma</var><code>)</code>, and <var>k</var> is a non-negative integer +(default: <code>OrderGraph(</code><var>gamma</var><code>)</code>). +<p> +Then this function returns <code>true</code> if <var>C</var> is a vertex <var>k</var>-colouring of +<var>gamma</var>, that is, a proper vertex-colouring using at most <var>k</var>-colours (for +which <var><var>C</var>[i]</var> is the colour of the <var>i</var>-th vertex), and <code>false</code> if not. +<p> +See also <a href="CHAP007.htm#SSEC001.1">VertexColouring</a>. +<p> +<pre> +gap> gamma:=JohnsonGraph(7,3);; +gap> C:=VertexColouring(gamma,6);; +gap> IsVertexColouring(gamma,C); +true +gap> IsVertexColouring(gamma,C,7); +true +gap> IsVertexColouring(gamma,C,6); +true +gap> IsVertexColouring(gamma,C,5); +false +</pre> +<p> +<p> +<h2><a name="SECT003">7.3 MinimumVertexColouring</a></h2> +<p><p> +<a name = "SSEC003.1"></a> <li><code>MinimumVertexColouring( </code><var>gamma</var><code> )</code> <p> This function returns a minimum vertex-colouring <var>C</var> for the graph @@ -107,9 +138,9 @@ </pre> <p> <p> -<h2><a name="SECT003">7.3 ChromaticNumber</a></h2> +<h2><a name="SECT004">7.4 ChromaticNumber</a></h2> <p><p> -<a name = "SSEC003.1"></a> +<a name = "SSEC004.1"></a> <li><code>ChromaticNumber( </code><var>gamma</var><code> )</code> <p> This function returns the chromatic number of the given graph <var>gamma</var>, @@ -120,7 +151,7 @@ <var>gamma</var>, that is, the number of colours used in a minimum vertex-colouring of <var>gamma</var>. <p> -See also <a href="CHAP007.htm#SSEC002.1">MinimumVertexColouring</a>. +See also <a href="CHAP007.htm#SSEC003.1">MinimumVertexColouring</a>. <p> <pre> gap> ChromaticNumber(JohnsonGraph(5,2)); @@ -132,9 +163,9 @@ </pre> <p> <p> -<h2><a name="SECT004">7.4 CompleteSubgraphs</a></h2> +<h2><a name="SECT005">7.5 CompleteSubgraphs</a></h2> <p><p> -<a name = "SSEC004.1"></a> +<a name = "SSEC005.1"></a> <li><code>CompleteSubgraphs( </code><var>gamma</var><code> )</code> <li><code>CompleteSubgraphs( </code><var>gamma</var><code>, </code><var>k</var><code> )</code> <li><code>CompleteSubgraphs( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code> )</code> @@ -185,7 +216,7 @@ <a name = "I4"></a> <p> -See also <a href="CHAP007.htm#SSEC005.1">CompleteSubgraphsOfGivenSize</a>. +See also <a href="CHAP007.htm#SSEC006.1">CompleteSubgraphsOfGivenSize</a>. <p> <pre> gap> gamma := JohnsonGraph(5,2); @@ -204,9 +235,9 @@ </pre> <p> <p> -<h2><a name="SECT005">7.5 CompleteSubgraphsOfGivenSize</a></h2> +<h2><a name="SECT006">7.6 CompleteSubgraphsOfGivenSize</a></h2> <p><p> -<a name = "SSEC005.1"></a> +<a name = "SSEC006.1"></a> <li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code> )</code> <li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code> )</code> <li><code>CompleteSubgraphsOfGivenSize( </code><var>gamma</var><code>, </code><var>k</var><code>, </code><var>alls</var><code>, </code><var>maxi</var><code> )</code> @@ -296,7 +327,7 @@ <a name = "I5"></a> <p> -See also <a href="CHAP007.htm#SSEC004.1">CompleteSubgraphs</a>. +See also <a href="CHAP007.htm#SSEC005.1">CompleteSubgraphs</a>. <p> <pre> gap> gamma:=JohnsonGraph(6,2); @@ -326,9 +357,9 @@ [ 13, 14 ] ] </pre> <p> -<h2><a name="SECT006">7.6 MaximumClique</a></h2> +<h2><a name="SECT007">7.7 MaximumClique</a></h2> <p><p> -<a name = "SSEC006.1"></a> +<a name = "SSEC007.1"></a> <li><code>MaximumClique( </code><var>gamma</var><code> )</code> <p> This function returns a maximum clique of the graph <var>gamma</var>, which must @@ -343,7 +374,7 @@ <a name = "I7"></a> <p> -See also <a href="CHAP007.htm#SSEC005.1">CompleteSubgraphsOfGivenSize</a>. +See also <a href="CHAP007.htm#SSEC006.1">CompleteSubgraphsOfGivenSize</a>. <p> <pre> gap> J:=JohnsonGraph(5,2); @@ -358,9 +389,9 @@ </pre> <p> <p> -<h2><a name="SECT007">7.7 CliqueNumber</a></h2> +<h2><a name="SECT008">7.8 CliqueNumber</a></h2> <p><p> -<a name = "SSEC007.1"></a> +<a name = "SSEC008.1"></a> <li><code>CliqueNumber( </code><var>gamma</var><code> )</code> <p> This function returns the clique number of the given graph <var>gamma</var>, @@ -381,5 +412,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP006.htm">Previous</a>] [<a href ="CHAP008.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP008.htm new/grape-4.9.2/htm/CHAP008.htm --- old/grape-4.9.1/htm/CHAP008.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP008.htm 2024-10-11 18:17:41.000000000 +0200 @@ -287,5 +287,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP007.htm">Previous</a>] [<a href ="CHAP009.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP009.htm new/grape-4.9.2/htm/CHAP009.htm --- old/grape-4.9.1/htm/CHAP009.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP009.htm 2024-10-11 18:17:41.000000000 +0200 @@ -200,5 +200,5 @@ <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP008.htm">Previous</a>] [<a href ="CHAP010.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/CHAP010.htm new/grape-4.9.2/htm/CHAP010.htm --- old/grape-4.9.1/htm/CHAP010.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/CHAP010.htm 2024-10-11 18:17:41.000000000 +0200 @@ -1,21 +1,19 @@ -<html><head><title>[grape] 10 Steve Linton's function SmallestImageSet</title></head> +<html><head><title>[grape] 10 Auxiliary Functions</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP009.htm">Previous</a>] [<a href = "theindex.htm">Index</a>] -<h1>10 Steve Linton's function SmallestImageSet</h1><p> +<h1>10 Auxiliary Functions</h1><p> <P> <H3>Sections</H3> <oL> -<li> <A HREF="CHAP010.htm#SECT001">SmallestImageSet</a> +<li> <A HREF="CHAP010.htm#SECT001">Steve Linton's Function SmallestImageSet</a> +<li> <A HREF="CHAP010.htm#SECT002">Exact Set-cover</a> </ol><p> <p> -This chapter documents the straightforward application of Steve Linton's -function <code>SmallestImageSet</code> <a href="biblio.htm#Lin04"><cite>Lin04</cite></a>, which is included and used -in GRAPE. The function is of use when classifying objects up to -the action of a given permutation group <var>G</var>, when the objects can be -represented as subsets of the permutation domain of <var>G</var>. +This chapter documents some auxiliary functions used in GRAPE, +which may be of wider interest. <p> <p> -<h2><a name="SECT001">10.1 SmallestImageSet</a></h2> +<h2><a name="SECT001">10.1 Steve Linton's Function SmallestImageSet</a></h2> <p><p> <a name = "SSEC001.1"></a> <li><code>SmallestImageSet( </code><var>G</var><code>, </code><var>S</var><code> )</code> @@ -35,6 +33,9 @@ given as the optional third parameter, to avoid the recomputation of this stabilizer. <p> +The function <code>SmallestImageSet</code> was written by Steve Linton, based +on his algorithm described in <a href="biblio.htm#Lin04"><cite>Lin04</cite></a>. +<p> <pre> gap> J:=JohnsonGraph(12,5);; gap> OrderGraph(J); @@ -42,13 +43,55 @@ gap> G:=J.group;; gap> Size(G); 479001600 -gap> S:=[67,93,100,204,677];; +gap> S:=[67,93,100,204,677,750];; gap> SmallestImageSet(G,S); -[ 1, 2, 22, 220, 453 ] +[ 1, 2, 22, 212, 242, 446 ] +</pre> +<p> +<p> +<h2><a name="SECT002">10.2 Exact Set-cover</a></h2> +<p><p> +<a name = "SSEC002.1"></a> +<li><code>GRAPE_ExactSetCover( </code><var>G</var><code>, </code><var>blocks</var><code>, </code><var>n</var><code> )</code> +<li><code>GRAPE_ExactSetCover( </code><var>G</var><code>, </code><var>blocks</var><code>, </code><var>n</var><code>, </code><var>H</var><code> )</code> +<p> +Suppose <var>n</var> is a non-negative integer, <var>G</var> is a permutation group +on <var>{1,...,n}</var>, <var>blocks</var> is a list of non-empty subsets +of <var>{1,...,n}</var>, and the optional parameter <var>H</var> (default: +<code>Group(())</code>) is a subgroup of <var>G</var>. +<p> +Then this function returns an <var>H</var>-invariant exact +set-cover of <var>{1,...,n}</var>, consisting of elements from the union of +<code>Orbits(</code><var>G</var><code>,</code><var>blocks</var><code>,OnSets)</code>, if such a cover exists, +and returns <code>fail</code> otherwise. An exact set-cover is given as a set of +sets forming a partition of <var>{1,...,n}</var>. +<p> +<pre> +gap> G:=PSL(2,5);; +gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); +fail +gap> G:=PGL(2,5);; +gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); +[ [ 1, 2, 3 ], [ 4, 5, 6 ] ] +gap> n:=280;; +gap> G:=OnePrimitiveGroup(NrMovedPoints,n,Size,604800*2); +J_2.2 +gap> gamma:=First(GeneralizedOrbitalGraphs(G),x->VertexDegrees(x)=[135]);; +gap> omega:=CliqueNumber(gamma); +28 +gap> blocks:=CompleteSubgraphsOfGivenSize(ComplementGraph(gamma),n/omega,2);; +gap> Collected(List(blocks,Length)); +[ [ 10, 2 ] ] +gap> H:=SylowSubgroup(G,7);; +gap> partition:=GRAPE_ExactSetCover(G,blocks,n,H);; +gap> Collected(List(partition,Length)); +[ [ 10, 28 ] ] +gap> Union(partition)=[1..n]; +true </pre> <p> <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP009.htm">Previous</a>] [<a href = "theindex.htm">Index</a>] <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/biblio.htm new/grape-4.9.2/htm/biblio.htm --- old/grape-4.9.1/htm/biblio.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/biblio.htm 2024-10-11 18:17:41.000000000 +0200 @@ -109,5 +109,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/chapters.htm new/grape-4.9.2/htm/chapters.htm --- old/grape-4.9.1/htm/chapters.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/chapters.htm 2024-10-11 18:17:41.000000000 +0200 @@ -14,12 +14,12 @@ <li><a href="CHAP007.htm">Vertex-Colouring and Complete Subgraphs</a> <li><a href="CHAP008.htm">Automorphism groups and isomorphism testing for graphs</a> <li><a href="CHAP009.htm">Partial Linear Spaces</a> -<li><a href="CHAP010.htm">Steve Linton's function SmallestImageSet</a> +<li><a href="CHAP010.htm">Auxiliary Functions</a> </ol> <ul> <li><a href="biblio.htm">References</a> <li><a href="theindex.htm">Index</a> </ul><p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxA.htm new/grape-4.9.2/htm/indxA.htm --- old/grape-4.9.1/htm/indxA.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxA.htm 2024-10-11 18:17:41.000000000 +0200 @@ -31,8 +31,9 @@ <dt>AssignVertexNames <a href="CHAP002.htm#SECT011">2.11</a> <a href="CHAP002.htm#SSEC011.1">2.11.1</a> <dt>AutGroupGraph <a href="CHAP008.htm#SECT002">8.2</a> <a href="CHAP008.htm#SSEC002.1">8.2.1</a> <dt>Automorphism groups and isomorphism testing for graphs <a href="CHAP008.htm">8.0</a> +<dt>Auxiliary Functions <a href="CHAP010.htm">10.0</a> </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxB.htm new/grape-4.9.2/htm/indxB.htm --- old/grape-4.9.1/htm/indxB.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxB.htm 2024-10-11 18:17:41.000000000 +0200 @@ -29,5 +29,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxC.htm new/grape-4.9.2/htm/indxC.htm --- old/grape-4.9.1/htm/indxC.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxC.htm 2024-10-11 18:17:41.000000000 +0200 @@ -25,23 +25,23 @@ <a href="indxU.htm">U</A> <a href="indxV.htm">V</A> <dt>CayleyGraph <a href="CHAP002.htm#SECT007">2.7</a> <a href="CHAP002.htm#SSEC007.1">2.7.1</a> -<dt>chromatic number <a href="CHAP007.htm#I3">7.3</a> -<dt>ChromaticNumber <a href="CHAP007.htm#SECT003">7.3</a> <a href="CHAP007.htm#SSEC003.1">7.3.1</a> -<dt>clique number <a href="CHAP007.htm#I8">7.7</a> -<dt>CliqueNumber <a href="CHAP007.htm#SECT007">7.7</a> <a href="CHAP007.htm#SSEC007.1">7.7.1</a> -<dt>Cliques <a href="CHAP007.htm#I4">7.4</a> -<dt>CliquesOfGivenSize <a href="CHAP007.htm#I5">7.5</a> +<dt>chromatic number <a href="CHAP007.htm#I3">7.4</a> +<dt>ChromaticNumber <a href="CHAP007.htm#SECT004">7.4</a> <a href="CHAP007.htm#SSEC004.1">7.4.1</a> +<dt>clique number <a href="CHAP007.htm#I8">7.8</a> +<dt>CliqueNumber <a href="CHAP007.htm#SECT008">7.8</a> <a href="CHAP007.htm#SSEC008.1">7.8.1</a> +<dt>Cliques <a href="CHAP007.htm#I4">7.5</a> +<dt>CliquesOfGivenSize <a href="CHAP007.htm#I5">7.6</a> <dt>CollapsedAdjacencyMat <a href="CHAP004.htm#SECT005">4.5</a> <a href="CHAP004.htm#SSEC005.1">4.5.1</a> <dt>CollapsedCompleteOrbitsGraph <a href="CHAP006.htm#SECT013">6.13</a> <a href="CHAP006.htm#SSEC013.1">6.13.1</a> <dt>CollapsedIndependentOrbitsGraph <a href="CHAP006.htm#SECT012">6.12</a> <a href="CHAP006.htm#SSEC012.1">6.12.1</a> <dt>ComplementGraph <a href="CHAP006.htm#SECT004">6.4</a> <a href="CHAP006.htm#SSEC004.1">6.4.1</a> <dt>CompleteGraph <a href="CHAP002.htm#SECT004">2.4</a> <a href="CHAP002.htm#SSEC004.1">2.4.1</a> -<dt>CompleteSubgraphs <a href="CHAP007.htm#SECT004">7.4</a> <a href="CHAP007.htm#SSEC004.1">7.4.1</a> -<dt>CompleteSubgraphsOfGivenSize <a href="CHAP007.htm#SECT005">7.5</a> <a href="CHAP007.htm#SSEC005.1">7.5.1</a> +<dt>CompleteSubgraphs <a href="CHAP007.htm#SECT005">7.5</a> <a href="CHAP007.htm#SSEC005.1">7.5.1</a> +<dt>CompleteSubgraphsOfGivenSize <a href="CHAP007.htm#SECT006">7.6</a> <a href="CHAP007.htm#SSEC006.1">7.6.1</a> <dt>ConnectedComponent <a href="CHAP005.htm#SECT001">5.1</a> <a href="CHAP005.htm#SSEC001.1">5.1.1</a> <dt>ConnectedComponents <a href="CHAP005.htm#SECT002">5.2</a> <a href="CHAP005.htm#SSEC002.1">5.2.1</a> </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxD.htm new/grape-4.9.2/htm/indxD.htm --- old/grape-4.9.1/htm/indxD.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxD.htm 2024-10-11 18:17:41.000000000 +0200 @@ -33,5 +33,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxE.htm new/grape-4.9.2/htm/indxE.htm --- old/grape-4.9.1/htm/indxE.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxE.htm 2024-10-11 18:17:41.000000000 +0200 @@ -26,9 +26,10 @@ <a href="indxV.htm">V</A> <dt>EdgeGraph <a href="CHAP006.htm#SECT006">6.6</a> <a href="CHAP006.htm#SSEC006.1">6.6.1</a> <dt>EdgeOrbitsGraph <a href="CHAP002.htm#SECT002">2.2</a> <a href="CHAP002.htm#SSEC002.1">2.2.1</a> +<dt>Exact Set-cover <a href="CHAP010.htm#SECT002">10.2</a> <dt>Examples of the use of GRAPE <a href="CHAP001.htm#SECT004">1.4</a> </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxF.htm new/grape-4.9.2/htm/indxF.htm --- old/grape-4.9.1/htm/indxF.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxF.htm 2024-10-11 18:17:41.000000000 +0200 @@ -31,5 +31,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxG.htm new/grape-4.9.2/htm/indxG.htm --- old/grape-4.9.1/htm/indxG.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxG.htm 2024-10-11 18:17:41.000000000 +0200 @@ -30,6 +30,7 @@ <dt>Girth <a href="CHAP003.htm#SECT017">3.17</a> <a href="CHAP003.htm#SSEC017.1">3.17.1</a> <dt>GlobalParameters <a href="CHAP004.htm#SECT003">4.3</a> <a href="CHAP004.htm#SSEC003.1">4.3.1</a> <dt>Grape <a href="CHAP001.htm">1.0</a> +<dt>GRAPE_ExactSetCover <a href="CHAP010.htm#SSEC002.1">10.2.1</a> <dt>Graph <a href="CHAP002.htm#SECT001">2.1</a> <a href="CHAP002.htm#SSEC001.1">2.1.1</a> <dt>GraphImage <a href="CHAP006.htm#SECT015">6.15</a> <a href="CHAP006.htm#SSEC015.1">6.15.1</a> <dt>GraphIsomorphism <a href="CHAP008.htm#SECT003">8.3</a> <a href="CHAP008.htm#SSEC003.1">8.3.1</a> @@ -38,5 +39,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxH.htm new/grape-4.9.2/htm/indxH.htm --- old/grape-4.9.1/htm/indxH.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxH.htm 2024-10-11 18:17:41.000000000 +0200 @@ -28,5 +28,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxI.htm new/grape-4.9.2/htm/indxI.htm --- old/grape-4.9.1/htm/indxI.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxI.htm 2024-10-11 18:17:41.000000000 +0200 @@ -39,8 +39,9 @@ <dt>IsRegularGraph <a href="CHAP004.htm#SECT001">4.1</a> <a href="CHAP004.htm#SSEC001.1">4.1.1</a> <dt>IsSimpleGraph <a href="CHAP003.htm#SECT010">3.10</a> <a href="CHAP003.htm#SSEC010.1">3.10.1</a> <dt>IsVertex <a href="CHAP003.htm#SECT003">3.3</a> <a href="CHAP003.htm#SSEC003.1">3.3.1</a> +<dt>IsVertexColouring <a href="CHAP007.htm#SECT002">7.2</a> <a href="CHAP007.htm#SSEC002.1">7.2.1</a> </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxJ.htm new/grape-4.9.2/htm/indxJ.htm --- old/grape-4.9.1/htm/indxJ.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxJ.htm 2024-10-11 18:17:41.000000000 +0200 @@ -28,5 +28,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxL.htm new/grape-4.9.2/htm/indxL.htm --- old/grape-4.9.1/htm/indxL.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxL.htm 2024-10-11 18:17:41.000000000 +0200 @@ -30,5 +30,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxM.htm new/grape-4.9.2/htm/indxM.htm --- old/grape-4.9.1/htm/indxM.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxM.htm 2024-10-11 18:17:41.000000000 +0200 @@ -24,13 +24,13 @@ <a href="indxT.htm">T</A> <a href="indxU.htm">U</A> <a href="indxV.htm">V</A> -<dt>maximum clique <a href="CHAP007.htm#I6">7.6</a> -<dt>MaximumClique <a href="CHAP007.htm#SECT006">7.6</a> <a href="CHAP007.htm#SSEC006.1">7.6.1</a> -<dt>MaximumCompleteSubgraph <a href="CHAP007.htm#I7">7.6</a> -<dt>minimum vertex-colouring <a href="CHAP007.htm#I2">7.2</a> -<dt>MinimumVertexColouring <a href="CHAP007.htm#SECT002">7.2</a> <a href="CHAP007.htm#SSEC002.1">7.2.1</a> +<dt>maximum clique <a href="CHAP007.htm#I6">7.7</a> +<dt>MaximumClique <a href="CHAP007.htm#SECT007">7.7</a> <a href="CHAP007.htm#SSEC007.1">7.7.1</a> +<dt>MaximumCompleteSubgraph <a href="CHAP007.htm#I7">7.7</a> +<dt>minimum vertex-colouring <a href="CHAP007.htm#I2">7.3</a> +<dt>MinimumVertexColouring <a href="CHAP007.htm#SECT003">7.3</a> <a href="CHAP007.htm#SSEC003.1">7.3.1</a> </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxN.htm new/grape-4.9.2/htm/indxN.htm --- old/grape-4.9.1/htm/indxN.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxN.htm 2024-10-11 18:17:41.000000000 +0200 @@ -29,5 +29,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxO.htm new/grape-4.9.2/htm/indxO.htm --- old/grape-4.9.1/htm/indxO.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxO.htm 2024-10-11 18:17:41.000000000 +0200 @@ -29,5 +29,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxP.htm new/grape-4.9.2/htm/indxP.htm --- old/grape-4.9.1/htm/indxP.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxP.htm 2024-10-11 18:17:41.000000000 +0200 @@ -31,5 +31,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxQ.htm new/grape-4.9.2/htm/indxQ.htm --- old/grape-4.9.1/htm/indxQ.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxQ.htm 2024-10-11 18:17:41.000000000 +0200 @@ -28,5 +28,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxR.htm new/grape-4.9.2/htm/indxR.htm --- old/grape-4.9.1/htm/indxR.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxR.htm 2024-10-11 18:17:41.000000000 +0200 @@ -28,5 +28,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxS.htm new/grape-4.9.2/htm/indxS.htm --- old/grape-4.9.1/htm/indxS.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxS.htm 2024-10-11 18:17:41.000000000 +0200 @@ -24,12 +24,12 @@ <a href="indxT.htm">T</A> <a href="indxU.htm">U</A> <a href="indxV.htm">V</A> -<dt>SmallestImageSet <a href="CHAP010.htm#SECT001">10.1</a> <a href="CHAP010.htm#SSEC001.1">10.1.1</a> +<dt>SmallestImageSet <a href="CHAP010.htm#SSEC001.1">10.1.1</a> <dt>Some special vertex subsets of a graph <a href="CHAP005.htm">5.0</a> -<dt>Steve Linton's function SmallestImageSet <a href="CHAP010.htm">10.0</a> +<dt>Steve Linton's Function SmallestImageSet <a href="CHAP010.htm#SECT001">10.1</a> <dt>SwitchedGraph <a href="CHAP006.htm#SECT007">6.7</a> <a href="CHAP006.htm#SSEC007.1">6.7.1</a> </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxT.htm new/grape-4.9.2/htm/indxT.htm --- old/grape-4.9.1/htm/indxT.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxT.htm 2024-10-11 18:17:41.000000000 +0200 @@ -28,5 +28,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxU.htm new/grape-4.9.2/htm/indxU.htm --- old/grape-4.9.1/htm/indxU.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxU.htm 2024-10-11 18:17:41.000000000 +0200 @@ -29,5 +29,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/indxV.htm new/grape-4.9.2/htm/indxV.htm --- old/grape-4.9.1/htm/indxV.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/indxV.htm 2024-10-11 18:17:41.000000000 +0200 @@ -36,5 +36,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/htm/theindex.htm new/grape-4.9.2/htm/theindex.htm --- old/grape-4.9.1/htm/theindex.htm 2024-08-30 15:27:18.000000000 +0200 +++ new/grape-4.9.2/htm/theindex.htm 2024-10-11 18:17:41.000000000 +0200 @@ -27,5 +27,5 @@ </dl><p> [<a href="chapters.htm">Up</a>]<p> <P> -<address>grape manual<br>August 2024 +<address>grape manual<br>October 2024 </address></body></html> \ No newline at end of file diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/lib/grape.g new/grape-4.9.2/lib/grape.g --- old/grape-4.9.1/lib/grape.g 2024-08-30 14:31:32.000000000 +0200 +++ new/grape-4.9.2/lib/grape.g 2024-10-11 17:24:02.000000000 +0200 @@ -1,6 +1,6 @@ ############################################################################## ## -## grape.g (Version 4.9.1) GRAPE Library Leonard Soicher +## grape.g (Version 4.9.2) GRAPE Library Leonard Soicher ## ## Copyright (C) 1992-2024 Leonard Soicher, School of Mathematical Sciences, ## Queen Mary University of London, London E1 4NS, U.K. @@ -1702,7 +1702,6 @@ fi; end); - DeclareOperation("ConnectedComponent",[IsRecord,IsPosInt]); InstallMethod(ConnectedComponent,"for GRAPE graph",[IsRecord,IsPosInt],0, function(gamma,v) @@ -2836,7 +2835,7 @@ # giving dovector the value [1..d]. # local IsFixedPoint,HasLargerEntry,k,smallorder,smallorder1,weights,weighted, - originalG,originalgamma,includingallmaximalreps, + originalG,originalgamma,includingallmaximalreps,zeroonevectorweighted, CompleteSubgraphsSearch,K,clique,cliquenumber,chromaticnumber; IsFixedPoint := function(G,point) @@ -2871,7 +2870,7 @@ # gamma, each of which is given as a dense list of distinct vertex-names. # # The variables smallorder, smallorder1, originalG, -# allsubs, allmaxes, weights, weightvectors, weighted, +# allsubs, allmaxes, weights, weightvectors, weighted, # partialcolour, dovector, IsFixedPoint, and HasLargerEntry # are global. (originalG is the group of automorphisms # associated with the original graph.) @@ -2948,7 +2947,7 @@ # forbidmask is the empty set. # # The variables n, A, names, allmaxes, allsubs, partialcolour, -# weights, weightvectors, weighted, dovector, +# weights, weightvectors, weighted, zeroonevectorweighted, dovector, # and HasLargerEntry are global. # The parameter mask may be changed by this function, and if # allmaxes=true then forbidmask may be changed by this function. @@ -3082,18 +3081,22 @@ # # Now determine doposition. # -# Standard heuristic: -doposition:=First(dovector,x->kvector[x]<>0); -# -# # Alternative heuristic: -# doposition:=0; -# for i in [1..Length(kvector)] do -# if kvector[i]<>0 then -# if doposition=0 or nactivevector[i]<nactivevector[doposition] then -# doposition:=i; -# fi; -# fi; -# od; +if not zeroonevectorweighted then + # Use the standard heuristic. + doposition:=First(dovector,x->kvector[x]<>0); +else + # The weight-vectors have dimension > 1 and + # all weight-vector entries are <= 1. + # Use the alternative heuristic. + doposition:=0; + for i in [1..Length(kvector)] do + if kvector[i]<>0 then + if doposition=0 or nactivevector[i]<nactivevector[doposition] then + doposition:=i; + fi; + fi; + od; +fi; # # Now order the vertices in active for processing. # @@ -3632,6 +3635,8 @@ gamma:=NewGroupGraph(gamma.autGroup,gamma); fi; fi; +zeroonevectorweighted:=weightvectors<>[] and Length(weightvectors[1])>1 and + ForAll(weightvectors,x->ForAll(x,y->y<=1)); K:=CompleteSubgraphsSearch(gamma,kvector,[],[]); for clique in K do Sort(clique); @@ -4089,6 +4094,72 @@ return Length(MaximumClique(gamma)); end); +BindGlobal("GRAPE_ExactSetCover",function(arg) +# +# Let n:=arg[3] be a non-negative integer, +# let G:=arg[1] be a permutation group on [1..n], +# let blocks:=arg[2] be a list of non-empty subsets of [1..n], +# and let H:=arg[4] (default: Group(())) be a subgroup of G. +# +# Then this function returns an H-invariant exact set-cover +# of [1..n] by elements from Concatenation(Orbits(G,blocks,OnSets)), +# if such a cover exists, and returns `fail' otherwise. +# +local G,blocks,n,H,gamma,hom,i,j,wts,K,N; +if not Length(arg) in [3,4] then + Error("GRAPE_ExactSetCover should have 3 or 4 arguments"); +fi; +n:=arg[3]; +if not IsInt(n) and n>=0 then + Error("<n> must be a non-negative integer"); +fi; +G:=arg[1]; +if not (IsPermGroup(G) and LargestMovedPoint(G)<=n) then + Error("<G> must be a permutation group on [1..<n>]"); +fi; +blocks:=arg[2]; +if not IsList(blocks) and + ForAll(blocks,x->IsSet(x) and x<>[] and IsSubset([1..n],x)) then + Error("<blocks> must be a list of non-empty subsets of [1..<n>]"); +fi; +if IsBound(arg[4]) then + H:=arg[4]; + if not IsSubgroup(G,H) then + Error("<H> must be a subgroup of <G>"); + fi; +else + H:=Group(()); +fi; +if n=0 then + return []; +elif blocks=[] then + return fail; +fi; +gamma:=Graph(G,blocks,OnSets,function(x,y) return Intersection(x,y)=[]; end); +if Size(H)>1 then + hom:=ActionHomomorphism(G,VertexNames(gamma),OnSets); + N:=Image(hom,Normalizer(G,H)); + H:=Image(hom,H); + gamma:=CollapsedCompleteOrbitsGraph(H,gamma,N); +else + AssignVertexNames(gamma,List(VertexNames(gamma),x->[x])); +fi; +wts:=[]; +for i in [1..gamma.order] do + wts[i]:=ListWithIdenticalEntries(n,0); + for j in Concatenation(gamma.names[i]) do + wts[i][j]:=1; + od; +od; +K:=CompleteSubgraphsOfGivenSize(gamma,ListWithIdenticalEntries(n,1), + 0,true,true,wts); +if K=[] then + return fail; +else + return Union(gamma.names{K[1]}); +fi; +end); + BindGlobal("GRAPE_CliqueCovering",function(arg) # # Let gamma:=arg[1] be a simple graph and let k:=arg[2] be @@ -4137,8 +4208,7 @@ # In addition, we assume that on the initial call to this recursive function # that m is an integer and delta.names=[1..delta.order]. # -local m,C,CC,c,d,t,s,cov,newdelta,D,K,A,translation,wts,i,j, - exclude,eps,dtranslation; +local m,C,CC,c,d,t,s,cov,newdelta,K,A,translation,i,exclude,eps,dtranslation; if IsInt(start) then m:=start; else @@ -4213,20 +4283,11 @@ fi; if s*k=delta.order and Size(delta.group)<=smallorder then # Use exact cover. - D:=Graph(delta.group,C,OnSets, - function(x,y) return Intersection(x,y)=[]; end); - wts:=List([1..D.order],x->ListWithIdenticalEntries(delta.order,0)); - for i in [1..D.order] do - for j in D.names[i] do - wts[i][j]:=1; - od; - od; - K:=CompleteSubgraphsOfGivenSize(D, - ListWithIdenticalEntries(delta.order,1),0,true,true,wts); - if K=[] then + K:=GRAPE_ExactSetCover(delta.group,C,delta.order); + if K=fail then return fail; else - return List(K[1],x->delta.names{D.names[x]}); + return List(K,x->delta.names{x}); fi; elif not IsTrivial(delta.group) then C:=Set(C,x->SmallestImageSet(delta.group,x)); @@ -4317,24 +4378,59 @@ Sort(c); od; Sort(cov); -# -# Check. -# -if not IsSet(cov) - or Length(cov)>k - or not ForAll(cov,x->x<>[] and IsSet(x)) - or Union(cov)<>Vertices(gamma) - or Sum(List(cov,Length))<>gamma.order - or not ForAll(cov,x->IsCompleteGraph(InducedSubgraph(gamma,x))) then - # This should never happen. - Error("BUG: returned cov is not a clique k-covering given as a set of pairwise disjoint non-empty cliques"); -fi; -# -# End of check. -# return cov; end); +BindGlobal("IsVertexColouring",function(arg) +# +# Let gamma:=arg[1] be a simple graph, let C:=arg[2] be a list of +# positive integers of length OrderGraph(gamma), and let k:=arg[3] +# be a non-negative integer (default: Length(C)). +# +# Then this function returns true if C is a vertex k-colouring +# of gamma, and returns false if not. (The list C is a vertex +# k-colouring of gamma iff C[v]<>C[w] whenever [v,w] is an edge of +# gamma, and the number of distinct elements of C (the colours) is +# at most k. A proper vertex-colouring of gamma is the same thing +# as a vertex OrderGraph(gamma)-colouring of gamma.) +# +local gamma,C,k,v,w; +if not Length(arg) in [2,3] then + Error("IsVertexColouring should have 2 or 3 arguments"); +fi; +gamma:=arg[1]; +if not IsSimpleGraph(gamma) then + Error("<gamma> must be a simple graph"); +fi; +C:=arg[2]; +if not (IsList(C) and Length(C)=OrderGraph(gamma) and ForAll(C,IsPosInt)) then + Error("<C> must be a list of length OrderGraph(<gamma>) of positive integers"); +fi; +if IsBound(arg[3]) then + k:=arg[3]; + if not (IsInt(k) and k>=0) then + Error("<k> must be a non-negative integer"); + fi; +else + k:=OrderGraph(gamma); +fi; +if Length(Set(C))>k then + # too many colours + return false; +fi; +for v in Vertices(gamma) do + for w in Adjacency(gamma,v) do + if v<w then + if C[v]=C[w] then + # The adjacent vertices v and w have the same colour. + return false; + fi; + fi; + od; +od; +return true; +end); + BindGlobal("VertexColouring",function(arg) # # Let gamma:=arg[1] be a simple graph. Then this function returns @@ -4466,7 +4562,11 @@ fi; od; if maxcolour<=k then - # C is a k-colouring. + # C is a vertex k-colouring of gamma. + if not IsVertexColouring(gamma,C,k) then + # This should not happen! + Error("BUG: <C> should be a (proper) vertex <k>-colouring of <gamma>"); + fi; if IsBound(gamma.maximumClique) and Length(gamma.maximumClique)=Length(Set(C)) then # C is a minimum vertex-colouring of gamma. gamma.minimumVertexColouring:=Immutable(C); @@ -4489,6 +4589,10 @@ C[j]:=i; od; od; +if not IsVertexColouring(gamma,C,k) then + # This should not happen! + Error("BUG: <C> should be a (proper) vertex <k>-colouring of <gamma>"); +fi; if IsBound(gamma.maximumClique) and Length(gamma.maximumClique)=Length(Set(C)) then # C is a minimum vertex-colouring of gamma. gamma.minimumVertexColouring:=Immutable(C); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/grape-4.9.1/tst/testall.tst new/grape-4.9.2/tst/testall.tst --- old/grape-4.9.1/tst/testall.tst 2024-08-30 14:31:32.000000000 +0200 +++ new/grape-4.9.2/tst/testall.tst 2024-10-11 17:24:02.000000000 +0200 @@ -24,15 +24,6 @@ # loaded) gap> LoadPackage("grape",false); true -gap> J:=JohnsonGraph(12,5);; -gap> OrderGraph(J); -792 -gap> G:=J.group;; -gap> Size(G); -479001600 -gap> S:=[67,93,100,204,677];; -gap> SmallestImageSet(G,S); -[ 1, 2, 22, 220, 453 ] gap> P := Graph( SymmetricGroup(5), [[1,2]], OnSets, > function(x,y) return Intersection(x,y)=[]; end );; gap> Diameter(P); @@ -460,6 +451,46 @@ > colourClasses:=[[1],[6],[2,3,4,5,7,8,9,10]]) ] );; gap> Length(R); 3 +gap> J:=JohnsonGraph(12,5);; +gap> OrderGraph(J); +792 +gap> G:=J.group;; +gap> Size(G); +479001600 +gap> S:=[67,93,100,204,677,750];; +gap> SmallestImageSet(G,S); +[ 1, 2, 22, 212, 242, 446 ] +gap> G:=PSL(2,5);; +gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); +fail +gap> G:=PGL(2,5);; +gap> GRAPE_ExactSetCover(G,[[1,2,3]],6); +[ [ 1, 2, 3 ], [ 4, 5, 6 ] ] +gap> n:=280;; +gap> G:=OnePrimitiveGroup(NrMovedPoints,n,Size,604800*2); +J_2.2 +gap> gamma:=First(GeneralizedOrbitalGraphs(G),x->VertexDegrees(x)=[135]);; +gap> omega:=CliqueNumber(gamma); +28 +gap> blocks:=CompleteSubgraphsOfGivenSize(ComplementGraph(gamma),n/omega,2);; +gap> Collected(List(blocks,Length)); +[ [ 10, 2 ] ] +gap> H:=SylowSubgroup(G,7);; +gap> partition:=GRAPE_ExactSetCover(G,blocks,n,H);; +gap> Collected(List(partition,Length)); +[ [ 10, 28 ] ] +gap> Union(partition)=[1..n]; +true +gap> gamma:=JohnsonGraph(7,3);; +gap> C:=VertexColouring(gamma,6);; +gap> IsVertexColouring(gamma,C); +true +gap> IsVertexColouring(gamma,C,7); +true +gap> IsVertexColouring(gamma,C,6); +true +gap> IsVertexColouring(gamma,C,5); +false gap> GRAPE_DREADNAUT_INPUT_USE_STRING:=not GRAPE_DREADNAUT_INPUT_USE_STRING;; gap> # gap> # Now repeat certain tests.
