Script 'mail_helper' called by obssrc
Hello community,
here is the log from the commit of package libsemigroups for openSUSE:Factory
checked in at 2021-12-17 23:54:24
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/libsemigroups (Old)
and /work/SRC/openSUSE:Factory/.libsemigroups.new.2520 (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "libsemigroups"
Fri Dec 17 23:54:24 2021 rev:12 rq:940961 version:2.1.3
Changes:
--------
--- /work/SRC/openSUSE:Factory/libsemigroups/libsemigroups.changes
2021-12-02 02:17:08.362306126 +0100
+++ /work/SRC/openSUSE:Factory/.libsemigroups.new.2520/libsemigroups.changes
2021-12-17 23:54:42.355539309 +0100
@@ -1,0 +2,7 @@
+Thu Dec 16 19:38:20 UTC 2021 - Jan Engelhardt <jeng...@inai.de>
+
+- Update to release 2.1.3
+ * Some performance improvements in ActionDigraph::number_of_paths,
+ the suffix tree implementation, and in KnuthBendix.
+
+-------------------------------------------------------------------
Old:
----
libsemigroups-2.1.2.tar.gz
New:
----
libsemigroups-2.1.3.tar.gz
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ libsemigroups.spec ++++++
--- /var/tmp/diff_new_pack.aG4mcb/_old 2021-12-17 23:54:42.867539733 +0100
+++ /var/tmp/diff_new_pack.aG4mcb/_new 2021-12-17 23:54:42.871539736 +0100
@@ -18,7 +18,7 @@
Name: libsemigroups
%define lname libsemigroups2
-Version: 2.1.2
+Version: 2.1.3
Release: 0
Summary: Library with algorithms for computing finite and finitely
presented semigroups
License: GPL-3.0-or-later
++++++ libsemigroups-2.1.2.tar.gz -> libsemigroups-2.1.3.tar.gz ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/.VERSION
new/libsemigroups-2.1.3/.VERSION
--- old/libsemigroups-2.1.2/.VERSION 2021-11-30 12:24:29.179553312 +0100
+++ new/libsemigroups-2.1.3/.VERSION 2021-12-16 16:57:27.981003307 +0100
@@ -1 +1 @@
-2.1.2
\ No newline at end of file
+2.1.3
\ No newline at end of file
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/Makefile.in
new/libsemigroups-2.1.3/Makefile.in
--- old/libsemigroups-2.1.2/Makefile.in 2021-11-30 12:24:43.148316284 +0100
+++ new/libsemigroups-2.1.3/Makefile.in 2021-12-16 16:57:42.320736823 +0100
@@ -1,4 +1,4 @@
-# Makefile.in generated by automake 1.16.4 from Makefile.am.
+# Makefile.in generated by automake 1.16.5 from Makefile.am.
# @configure_input@
# Copyright (C) 1994-2021 Free Software Foundation, Inc.
@@ -4340,6 +4340,10 @@
$(MAKE) $(AM_MAKEFLAGS) $(check_PROGRAMS)
check: check-am
all-am: Makefile $(LTLIBRARIES) $(DATA) $(HEADERS) all-local
+install-EXTRAPROGRAMS: install-libLTLIBRARIES
+
+install-checkPROGRAMS: install-libLTLIBRARIES
+
installdirs:
for dir in "$(DESTDIR)$(libdir)" "$(DESTDIR)$(pkgconfigdir)"
"$(DESTDIR)$(eigenincludedir)" "$(DESTDIR)$(eigensrccholeskyincludedir)"
"$(DESTDIR)$(eigensrccholmodsupportincludedir)"
"$(DESTDIR)$(eigensrccorearchaltivecincludedir)"
"$(DESTDIR)$(eigensrccorearchavx512includedir)"
"$(DESTDIR)$(eigensrccorearchavxincludedir)"
"$(DESTDIR)$(eigensrccorearchcudaincludedir)"
"$(DESTDIR)$(eigensrccorearchdefaultincludedir)"
"$(DESTDIR)$(eigensrccorearchneonincludedir)"
"$(DESTDIR)$(eigensrccorearchsseincludedir)"
"$(DESTDIR)$(eigensrccorearchzvectorincludedir)"
"$(DESTDIR)$(eigensrccorefunctorsincludedir)"
"$(DESTDIR)$(eigensrccoreincludedir)"
"$(DESTDIR)$(eigensrccoreproductsincludedir)"
"$(DESTDIR)$(eigensrccoreutilincludedir)"
"$(DESTDIR)$(eigensrceigenvaluesincludedir)"
"$(DESTDIR)$(eigensrcgeometryarchincludedir)"
"$(DESTDIR)$(eigensrcgeometryincludedir)"
"$(DESTDIR)$(eigensrchouseholderincludedir)"
"$(DESTDIR)$(eigensrciterativelinearsolversincludedir)"
"$(DESTDIR)$(eigensrcjacobiincl
udedir)" "$(DESTDIR)$(eigensrcluarchincludedir)"
"$(DESTDIR)$(eigensrcluincludedir)"
"$(DESTDIR)$(eigensrcmetissupportincludedir)"
"$(DESTDIR)$(eigensrcmiscincludedir)"
"$(DESTDIR)$(eigensrcorderingmethodsincludedir)"
"$(DESTDIR)$(eigensrcpardisosupportincludedir)"
"$(DESTDIR)$(eigensrcpastixsupportincludedir)"
"$(DESTDIR)$(eigensrcpluginsincludedir)" "$(DESTDIR)$(eigensrcqrincludedir)"
"$(DESTDIR)$(eigensrcsparsecholeskyincludedir)"
"$(DESTDIR)$(eigensrcsparsecoreincludedir)"
"$(DESTDIR)$(eigensrcsparseluincludedir)"
"$(DESTDIR)$(eigensrcsparseqrincludedir)"
"$(DESTDIR)$(eigensrcspqrsupportincludedir)"
"$(DESTDIR)$(eigensrcstlsupportincludedir)"
"$(DESTDIR)$(eigensrcsuperlusupportincludedir)"
"$(DESTDIR)$(eigensrcsvdincludedir)"
"$(DESTDIR)$(eigensrcumfpacksupportincludedir)" "$(DESTDIR)$(fmtincludedir)"
"$(DESTDIR)$(hpcombifallbackincludedir)" "$(DESTDIR)$(hpcombiincludedir)"
"$(DESTDIR)$(pkgincludedir)"; do \
test -z "$$dir" || $(MKDIR_P) "$$dir"; \
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/README.rst
new/libsemigroups-2.1.3/README.rst
--- old/libsemigroups-2.1.2/README.rst 2021-11-30 12:24:38.671704230 +0100
+++ new/libsemigroups-2.1.3/README.rst 2021-12-16 16:57:37.409840068 +0100
@@ -4,7 +4,7 @@
The full license is in the file LICENSE, distributed with this software.
-libsemigroups - Version 2.1.2
+libsemigroups - Version 2.1.3
=============================
.. image:: https://readthedocs.org/projects/libsemigroups/badge/?version=master
@@ -43,23 +43,21 @@
algorithms for computing finite, and finitely presented, semigroups and
monoids. Namely:
-- the `Froidure-Pin algorithm`_ for computing finite semigroups
- :cite:`Froidure1997aa`;
+- the `Froidure-Pin algorithm`_ for computing finite semigroups;
- the `Todd-Coxeter algorithm`_ for finitely presented semigroups and monoids;
- the `Knuth-Bendix algorithm`_ for finitely presented semigroups and monoids;
- the `Schreier-Sims algorithm`_ for permutation groups;
-- a preliminary implementation of the `Konieczny`_ :cite:`Konieczny1994aa` and
- `Lallement-McFadden`_ :cite:`Lallement1990aa` algorithm for computing finite
+- a preliminary implementation of the `Konieczny`_ and
+ `Lallement-McFadden`_ algorithm for computing finite
semigroups which act on sets;
-- an implementation of the `Radoszewski-Rytter`_ :cite:`Radoszewski2010aa`
+- an implementation of the `Radoszewski-Rytter`_
algorithm for testing equivalence of words in free bands.
- an implementation of the algorithm for solving the word problem
for small overlap monoids, and for computing normal forms in such monoids;
- see `Kambites <https://doi.org/10.1016/j.jalgebra.2008.09.038>`__
- :cite:`Kambites2009aa`,
- `Kambites <https://doi.org/10.1016/j.jalgebra.2008.12.028>`__
- :cite:`Kambites2009ab`, and `Mitchell-Tsalakou
- <http://arxiv.org/abs/2105.12125>`__ :cite:`Mitchell2021aa`.
+ see `Kambites <https://doi.org/10.1016/j.jalgebra.2008.09.038>`__,
+ `Kambites <https://doi.org/10.1016/j.jalgebra.2008.12.028>`__, and
+ `Mitchell-Tsalakou
+ <http://arxiv.org/abs/2105.12125>`__.
.. _Froidure-Pin algorithm: https://www.irif.fr/~jep/PDF/Rio.pdf
.. _Todd-Coxeter algorithm:
https://en.wikipedia.org/wiki/Todd%E2%80%93Coxeter_algorithm
@@ -131,8 +129,7 @@
- `R. Cirpons`_ contributed to ``IsObviouslyInfinite``, to integrating
``eigen``, and contributed an implementation of the `Radoszewski-Rytter`_
- :cite:`Radoszewski2010aa` algorithm for testing equivalence of words in free
- bands.
+ algorithm for testing equivalence of words in free bands.
- `F. Hivert`_ contributed many helpful ideas to ``libsemigroups``, an
allocator implementation (to be included in a future version), and
``HPCombi``.
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/aclocal.m4
new/libsemigroups-2.1.3/aclocal.m4
--- old/libsemigroups-2.1.2/aclocal.m4 2021-11-30 12:24:42.163017395 +0100
+++ new/libsemigroups-2.1.3/aclocal.m4 2021-12-16 16:57:41.335844564 +0100
@@ -1,4 +1,4 @@
-# generated automatically by aclocal 1.16.4 -*- Autoconf -*-
+# generated automatically by aclocal 1.16.5 -*- Autoconf -*-
# Copyright (C) 1996-2021 Free Software Foundation, Inc.
@@ -311,7 +311,7 @@
[am__api_version='1.16'
dnl Some users find AM_AUTOMAKE_VERSION and mistake it for a way to
dnl require some minimum version. Point them to the right macro.
-m4_if([$1], [1.16.4], [],
+m4_if([$1], [1.16.5], [],
[AC_FATAL([Do not call $0, use AM_INIT_AUTOMAKE([$1]).])])dnl
])
@@ -327,7 +327,7 @@
# Call AM_AUTOMAKE_VERSION and AM_AUTOMAKE_VERSION so they can be traced.
# This function is AC_REQUIREd by AM_INIT_AUTOMAKE.
AC_DEFUN([AM_SET_CURRENT_AUTOMAKE_VERSION],
-[AM_AUTOMAKE_VERSION([1.16.4])dnl
+[AM_AUTOMAKE_VERSION([1.16.5])dnl
m4_ifndef([AC_AUTOCONF_VERSION],
[m4_copy([m4_PACKAGE_VERSION], [AC_AUTOCONF_VERSION])])dnl
_AM_AUTOCONF_VERSION(m4_defn([AC_AUTOCONF_VERSION]))])
@@ -764,6 +764,10 @@
# release and drop the old call support.
AC_DEFUN([AM_INIT_AUTOMAKE],
[AC_PREREQ([2.65])dnl
+m4_ifdef([_$0_ALREADY_INIT],
+ [m4_fatal([$0 expanded multiple times
+]m4_defn([_$0_ALREADY_INIT]))],
+ [m4_define([_$0_ALREADY_INIT], m4_expansion_stack)])dnl
dnl Autoconf wants to disallow AM_ names. We explicitly allow
dnl the ones we care about.
m4_pattern_allow([^AM_[A-Z]+FLAGS$])dnl
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/benchmarks/bench-digraph.cpp
new/libsemigroups-2.1.3/benchmarks/bench-digraph.cpp
--- old/libsemigroups-2.1.2/benchmarks/bench-digraph.cpp 2021-11-28
12:25:20.013779229 +0100
+++ new/libsemigroups-2.1.3/benchmarks/bench-digraph.cpp 2021-12-02
18:42:52.617463955 +0100
@@ -307,30 +307,29 @@
std::mt19937 mt;
for (size_t M = 100; M < 1000; M += 100) {
std::uniform_int_distribution<size_t> source(0, M - 1);
- size_t v = source(mt);
- uint64_t result;
- auto ad
- = ActionDigraph<size_t>::random(M, 15, detail::magic_number(M) * M);
- BENCHMARK("algorithm::matrix: " + std::to_string(M) + " nodes, "
- + std::to_string(15) + " out-degree!") {
- result = ad.number_of_paths(v, 0, 16, algorithm::matrix);
- };
for (size_t N = 10; N < 20; N += 5) {
for (size_t nr_edges = 0; nr_edges <= detail::magic_number(M) * M;
nr_edges += 500) {
- ad = ActionDigraph<size_t>::random(M, N, nr_edges);
+ auto ad = ActionDigraph<size_t>::random(M, N, nr_edges);
action_digraph_helper::add_cycle(
ad, ad.cbegin_nodes(), ad.cend_nodes());
std::string m = std::to_string(ad.number_of_edges());
size_t w = source(mt);
+ uint64_t expected
+ = ad.number_of_paths(w, 0, 16, algorithm::automatic);
+ BENCHMARK("algorithm::matrix: " + std::to_string(M) + " nodes, "
+ + std::to_string(N) + " out-degree, " + m + " edges") {
+ REQUIRE(ad.number_of_paths(w, 0, 16, algorithm::matrix)
+ == expected);
+ };
BENCHMARK("algorithm::dfs: " + std::to_string(M) + " nodes, "
+ std::to_string(N) + " out-degree, " + m + " edges") {
- result = ad.number_of_paths(w, 0, 16, algorithm::dfs);
+ REQUIRE(ad.number_of_paths(w, 0, 16, algorithm::dfs) == expected);
};
BENCHMARK("algorithm::automatic: " + std::to_string(M) + " nodes, "
+ std::to_string(N) + " out-degree, " + m + " edges") {
- REQUIRE(result
- == ad.number_of_paths(w, 0, 16, algorithm::automatic));
+ REQUIRE(ad.number_of_paths(w, 0, 16, algorithm::automatic)
+ == expected);
};
std::cout << std::endl << std::string(72, '#') << std::endl;
}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/config/config.sub
new/libsemigroups-2.1.3/config/config.sub
--- old/libsemigroups-2.1.2/config/config.sub 2021-11-30 12:24:43.045654066
+0100
+++ new/libsemigroups-2.1.3/config/config.sub 2021-12-16 16:57:42.217597779
+0100
@@ -4,7 +4,7 @@
# shellcheck disable=SC2006,SC2268 # see below for rationale
-timestamp='2021-07-03'
+timestamp='2021-08-14'
# This file is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by
@@ -121,9 +121,11 @@
# Split fields of configuration type
# shellcheck disable=SC2162
+saved_IFS=$IFS
IFS="-" read field1 field2 field3 field4 <<EOF
$1
EOF
+IFS=$saved_IFS
# Separate into logical components for further validation
case $1 in
@@ -172,6 +174,10 @@
basic_machine=$field1
basic_os=$field2
;;
+ zephyr*)
+ basic_machine=$field1-unknown
+ basic_os=$field2
+ ;;
# Manufacturers
dec* | mips* | sequent* | encore* |
pc533* | sgi* | sony* \
| att* | 7300* | 3300* | delta* |
motorola* | sun[234]* \
@@ -931,9 +937,11 @@
*-*)
# shellcheck disable=SC2162
+ saved_IFS=$IFS
IFS="-" read cpu vendor <<EOF
$basic_machine
EOF
+ IFS=$saved_IFS
;;
# We use `pc' rather than `unknown'
# because (1) that's what they normally are, and
@@ -1313,9 +1321,11 @@
;;
*-*)
# shellcheck disable=SC2162
+ saved_IFS=$IFS
IFS="-" read kernel os <<EOF
$basic_os
EOF
+ IFS=$saved_IFS
;;
# Default OS when just kernel was specified
nto*)
@@ -1697,7 +1707,7 @@
# Now, validate our (potentially fixed-up) OS.
case $os in
# Sometimes we do "kernel-libc", so those need to count as OSes.
- musl* | newlib* | uclibc*)
+ musl* | newlib* | relibc* | uclibc*)
;;
# Likewise for "kernel-abi"
eabi* | gnueabi*)
@@ -1738,7 +1748,7 @@
| skyos* | haiku* | rdos* | toppers* | drops* | es* \
| onefs* | tirtos* | phoenix* | fuchsia* | redox* | bme* \
| midnightbsd* | amdhsa* | unleashed* | emscripten* | wasi* \
- | nsk* | powerunix* | genode* | zvmoe* | qnx* | emx*)
+ | nsk* | powerunix* | genode* | zvmoe* | qnx* | emx* | zephyr*)
;;
# This one is extra strict with allowed versions
sco3.2v2 | sco3.2v[4-9]* | sco5v6*)
@@ -1755,11 +1765,12 @@
# As a final step for OS-related things, validate the OS-kernel combination
# (given a valid OS), if there is a kernel.
case $kernel-$os in
- linux-gnu* | linux-dietlibc* | linux-android* | linux-newlib* |
linux-musl* | linux-uclibc* )
+ linux-gnu* | linux-dietlibc* | linux-android* | linux-newlib* \
+ | linux-musl* | linux-relibc* | linux-uclibc* )
;;
uclinux-uclibc* )
;;
- -dietlibc* | -newlib* | -musl* | -uclibc* )
+ -dietlibc* | -newlib* | -musl* | -relibc* | -uclibc* )
# These are just libc implementations, not actual OSes, and thus
# require a kernel.
echo "Invalid configuration \`$1': libc \`$os' needs explicit
kernel." 1>&2
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/configure
new/libsemigroups-2.1.3/configure
--- old/libsemigroups-2.1.2/configure 2021-11-30 12:24:42.526884393 +0100
+++ new/libsemigroups-2.1.3/configure 2021-12-16 16:57:41.702529132 +0100
@@ -1,6 +1,6 @@
#! /bin/sh
# Guess values for system-dependent variables and create Makefiles.
-# Generated by GNU Autoconf 2.71 for libsemigroups 2.1.2.
+# Generated by GNU Autoconf 2.71 for libsemigroups 2.1.3.
#
# Report bugs to <j...@st-andrews.ac.uk>.
#
@@ -621,8 +621,8 @@
# Identity of this package.
PACKAGE_NAME='libsemigroups'
PACKAGE_TARNAME='libsemigroups'
-PACKAGE_VERSION='2.1.2'
-PACKAGE_STRING='libsemigroups 2.1.2'
+PACKAGE_VERSION='2.1.3'
+PACKAGE_STRING='libsemigroups 2.1.3'
PACKAGE_BUGREPORT='j...@st-andrews.ac.uk'
PACKAGE_URL=''
@@ -1429,7 +1429,7 @@
# Omit some internal or obsolete options to make the list less imposing.
# This message is too long to be a string in the A/UX 3.1 sh.
cat <<_ACEOF
-\`configure' configures libsemigroups 2.1.2 to adapt to many kinds of systems.
+\`configure' configures libsemigroups 2.1.3 to adapt to many kinds of systems.
Usage: $0 [OPTION]... [VAR=VALUE]...
@@ -1501,7 +1501,7 @@
if test -n "$ac_init_help"; then
case $ac_init_help in
- short | recursive ) echo "Configuration of libsemigroups 2.1.2:";;
+ short | recursive ) echo "Configuration of libsemigroups 2.1.3:";;
esac
cat <<\_ACEOF
@@ -1642,7 +1642,7 @@
test -n "$ac_init_help" && exit $ac_status
if $ac_init_version; then
cat <<\_ACEOF
-libsemigroups configure 2.1.2
+libsemigroups configure 2.1.3
generated by GNU Autoconf 2.71
Copyright (C) 2021 Free Software Foundation, Inc.
@@ -2481,7 +2481,7 @@
This file contains any messages produced by compilers while
running configure, to aid debugging if configure makes a mistake.
-It was created by libsemigroups $as_me 2.1.2, which was
+It was created by libsemigroups $as_me 2.1.3, which was
generated by GNU Autoconf 2.71. Invocation command line was
$ $0$ac_configure_args_raw
@@ -4090,7 +4090,7 @@
# Define the identity of the package.
PACKAGE='libsemigroups'
- VERSION='2.1.2'
+ VERSION='2.1.3'
printf "%s\n" "#define PACKAGE \"$PACKAGE\"" >>confdefs.h
@@ -23285,7 +23285,7 @@
# report actual input values of CONFIG_FILES etc. instead of their
# values after options handling.
ac_log="
-This file was extended by libsemigroups $as_me 2.1.2, which was
+This file was extended by libsemigroups $as_me 2.1.3, which was
generated by GNU Autoconf 2.71. Invocation command line was
CONFIG_FILES = $CONFIG_FILES
@@ -23353,7 +23353,7 @@
cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1
ac_cs_config='$ac_cs_config_escaped'
ac_cs_version="\\
-libsemigroups config.status 2.1.2
+libsemigroups config.status 2.1.3
configured by $0, generated by GNU Autoconf 2.71,
with options \\"\$ac_cs_config\\"
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/docs/requirements.txt
new/libsemigroups-2.1.3/docs/requirements.txt
--- old/libsemigroups-2.1.2/docs/requirements.txt 2021-11-28
12:30:48.080795090 +0100
+++ new/libsemigroups-2.1.3/docs/requirements.txt 2021-12-16
15:41:37.523000932 +0100
@@ -1,5 +1,5 @@
beautifulsoup4==4.9.3
-lxml==4.6.3
+lxml==4.6.5
breathe==4.31.0
pyyaml>=5.3.1
sphinx_rtd_theme
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/docs/source/changelog.rst
new/libsemigroups-2.1.3/docs/source/changelog.rst
--- old/libsemigroups-2.1.2/docs/source/changelog.rst 2021-11-30
12:24:38.672189590 +0100
+++ new/libsemigroups-2.1.3/docs/source/changelog.rst 2021-12-16
16:57:37.414028116 +0100
@@ -1,6 +1,14 @@
Changelog - version 2
=====================
+v2.1.3 (released 16/12/2021)
+----------------------------
+
+This is a minor release with some performance improvements in:
+``ActionDigraph::number_of_paths`` (`eigen`_ is used in some circumstances when
+available); the suffix tree implementation (used by ``Kambites``); and in
+``KnuthBendix``.
+
v2.1.2 (released 30/11/2021)
----------------------------
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/docs/source/index.rst
new/libsemigroups-2.1.3/docs/source/index.rst
--- old/libsemigroups-2.1.2/docs/source/index.rst 2021-11-30
12:24:38.672600286 +0100
+++ new/libsemigroups-2.1.3/docs/source/index.rst 2021-12-16
16:57:37.419797092 +0100
@@ -1,4 +1,4 @@
-libsemigroups - Version 2.1.2
+libsemigroups - Version 2.1.3
=============================
C++ library for semigroups and monoids
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/docs/source/install.rst
new/libsemigroups-2.1.3/docs/source/install.rst
--- old/libsemigroups-2.1.2/docs/source/install.rst 2021-11-30
12:24:38.673622380 +0100
+++ new/libsemigroups-2.1.3/docs/source/install.rst 2021-12-16
16:57:37.422683288 +0100
@@ -1,4 +1,4 @@
-.. |libsemigroups-version| replace:: 2.1.2
+.. |libsemigroups-version| replace:: 2.1.3
.. _Installation:
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/include/libsemigroups/config.hpp
new/libsemigroups-2.1.3/include/libsemigroups/config.hpp
--- old/libsemigroups-2.1.2/include/libsemigroups/config.hpp 2021-11-30
12:24:48.289779159 +0100
+++ new/libsemigroups-2.1.3/include/libsemigroups/config.hpp 2021-12-16
16:57:47.527046009 +0100
@@ -181,7 +181,7 @@
/* Define to the full name and version of this package. */
#ifndef LIBSEMIGROUPS_PACKAGE_STRING
-#define LIBSEMIGROUPS_PACKAGE_STRING "libsemigroups 2.1.2"
+#define LIBSEMIGROUPS_PACKAGE_STRING "libsemigroups 2.1.3"
#endif
/* Define to the one symbol short name of this package. */
@@ -196,7 +196,7 @@
/* Define to the version of this package. */
#ifndef LIBSEMIGROUPS_PACKAGE_VERSION
-#define LIBSEMIGROUPS_PACKAGE_VERSION "2.1.2"
+#define LIBSEMIGROUPS_PACKAGE_VERSION "2.1.3"
#endif
/* Define to necessary symbol if this constant uses a non-standard name on
@@ -232,7 +232,7 @@
/* Version number of package */
#ifndef LIBSEMIGROUPS_VERSION
-#define LIBSEMIGROUPS_VERSION "2.1.2"
+#define LIBSEMIGROUPS_VERSION "2.1.3"
#endif
/* Define for Solaris 2.5.1 so the uint64_t typedef from <sys/synch.h>,
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/libsemigroups-2.1.2/include/libsemigroups/digraph.hpp
new/libsemigroups-2.1.3/include/libsemigroups/digraph.hpp
--- old/libsemigroups-2.1.2/include/libsemigroups/digraph.hpp 2021-11-28
12:30:48.095937180 +0100
+++ new/libsemigroups-2.1.3/include/libsemigroups/digraph.hpp 2021-12-02
18:42:52.619647452 +0100
@@ -39,6 +39,7 @@
#include <utility> // for pair
#include <vector> // for vector
+#include "config.hpp" // for LIBSEMIGROUPS_EIGEN_ENABLED
#include "constants.hpp" // for UNDEFINED
#include "containers.hpp" // for DynamicArray2
#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
@@ -51,6 +52,10 @@
#include "types.hpp" // for word_type
#include "word.hpp" // for number_of_words
+#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
+#include <Eigen/Core>
+#endif
+
namespace libsemigroups {
namespace detail {
@@ -59,8 +64,14 @@
}
// Implemented at end of this file.
- template <typename T>
- IntMat<0, 0, int64_t> adjacency_matrix(ActionDigraph<T> const& ad);
+ template <typename Mat, typename T>
+ Mat adjacency_matrix(ActionDigraph<T> const& ad);
+
+#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
+ static inline Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>
+ pow(Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic> const& x,
+ size_t e);
+#endif
} // namespace detail
//! Defined in ``digraph.hpp``.
@@ -126,6 +137,13 @@
//! The type of edge labels in a digraph.
using label_type = T;
+#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
+ using adjacency_matrix_type
+ = Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>;
+#else
+ using adjacency_matrix_type = IntMat<0, 0, int64_t>;
+#endif
+
//! The type of an index in a strongly connected component of a digraph.
using scc_index_type = T;
@@ -2544,9 +2562,8 @@
}
}
// Some edges are not defined ...
- // TODO(later) why not use is_acyclic here?
- auto topo = action_digraph_helper::topological_sort(*this, source);
- if (topo.empty() && max == POSITIVE_INFINITY) {
+ if (!action_digraph_helper::is_acyclic(*this, source)
+ && max == POSITIVE_INFINITY) {
// Not acyclic
return POSITIVE_INFINITY;
}
@@ -2574,14 +2591,23 @@
uint64_t number_of_paths_matrix(node_type source,
size_t min,
size_t max) const {
- // #ifdef LIBSEMIGROUPS_EIGEN_ENABLED
- // TODO(later)
- // #else
- auto am = detail::adjacency_matrix(*this);
+ auto am = detail::adjacency_matrix<adjacency_matrix_type>(*this);
+#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
+ auto acc = detail::pow(am, min);
+ uint64_t total = 0;
+ for (size_t i = min; i < max; ++i) {
+ uint64_t add = acc.row(source).sum();
+ if (add == 0) {
+ break;
+ }
+ total += add;
+ acc *= am;
+ }
+#else
auto tmp = am;
uint64_t const N = number_of_nodes();
auto acc = matrix_helpers::pow(am, min);
- size_t total = 0;
+ uint64_t total = 0;
for (size_t i = min; i < max; ++i) {
uint64_t add = std::accumulate(acc.cbegin() + source * N,
acc.cbegin() + source * N + N,
@@ -2593,17 +2619,14 @@
tmp.product_inplace(acc, am);
tmp.swap(acc);
}
+#endif
return total;
- // #endif
}
uint64_t number_of_paths_matrix(node_type source,
node_type target,
size_t min,
size_t max) const {
- // #ifdef LIBSEMIGROUPS_EIGEN_ENABLED
- // TODO(later)
- // #else
if (!action_digraph_helper::is_reachable(*this, source, target)) {
// Complexity is O(number of nodes + number of edges).
return 0;
@@ -2611,11 +2634,23 @@
return POSITIVE_INFINITY;
}
- auto am = detail::adjacency_matrix(*this);
- auto tmp = am;
- uint64_t const N = number_of_nodes();
- auto acc = matrix_helpers::pow(am, min);
- size_t total = 0;
+ auto am = detail::adjacency_matrix<adjacency_matrix_type>(*this);
+#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
+ auto acc = detail::pow(am, min);
+ uint64_t total = 0;
+ for (size_t i = min; i < max; ++i) {
+ uint64_t add = acc(source, target);
+ if (add == 0 && acc.row(source).isZero()) {
+ break;
+ }
+ total += add;
+ acc *= am;
+ }
+#else
+ size_t const N = number_of_nodes();
+ auto tmp = am;
+ auto acc = matrix_helpers::pow(am, min);
+ size_t total = 0;
for (size_t i = min; i < max; ++i) {
uint64_t add = acc(source, target);
@@ -2629,8 +2664,8 @@
tmp.product_inplace(acc, am);
tmp.swap(acc);
}
+#endif
return total;
- // #endif
}
////////////////////////////////////////////////////////////////////////
@@ -2999,11 +3034,64 @@
}
namespace detail {
+
+#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
template <typename T>
- IntMat<0, 0, int64_t> adjacency_matrix(ActionDigraph<T> const& ad) {
- size_t const N = ad.number_of_nodes();
- IntMat<0, 0, int64_t> mat(N, N);
+ void init_adjacency_matrix(
+ ActionDigraph<T> const& ad,
+ Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>& mat) {
+ size_t const N = ad.number_of_nodes();
+ mat.resize(N, N);
+ mat.fill(0);
+ }
+
+ static inline void
+ identity(Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>& x) {
+ x.fill(0);
+ for (size_t i = 0; i < static_cast<size_t>(x.rows()); ++i) {
+ x(i, i) = 1;
+ }
+ }
+
+ static inline Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>
+ pow(Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic> const& x,
+ size_t e) {
+ if (x.cols() != x.rows()) {
+ LIBSEMIGROUPS_EXCEPTION("expected a square matrix, found %llux%llu",
+ static_cast<uint64_t>(x.rows()),
+ static_cast<uint64_t>(x.cols()));
+ }
+ auto y = x;
+ if (e % 2 == 0) {
+ identity(y);
+ if (e == 0) {
+ return y;
+ }
+ }
+ auto z = x;
+ while (e > 1) {
+ z *= z;
+ e /= 2;
+ if (e % 2 == 1) {
+ y *= z;
+ }
+ }
+ return y;
+ }
+#else
+ template <typename T>
+ void init_adjacency_matrix(ActionDigraph<T> const& ad,
+ IntMat<0, 0, int64_t>& mat) {
+ size_t const N = ad.number_of_nodes();
+ mat = IntMat<0, 0, int64_t>(N, N);
std::fill(mat.begin(), mat.end(), 0);
+ }
+#endif
+
+ template <typename Mat, typename T>
+ Mat adjacency_matrix(ActionDigraph<T> const& ad) {
+ Mat mat;
+ init_adjacency_matrix(ad, mat);
for (auto n = ad.cbegin_nodes(); n != ad.cend_nodes(); ++n) {
for (auto e = ad.cbegin_edges(*n); e != ad.cend_edges(*n); ++e) {
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/libsemigroups-2.1.2/include/libsemigroups/knuth-bendix.hpp
new/libsemigroups-2.1.3/include/libsemigroups/knuth-bendix.hpp
--- old/libsemigroups-2.1.2/include/libsemigroups/knuth-bendix.hpp
2021-11-28 12:30:48.098078008 +0100
+++ new/libsemigroups-2.1.3/include/libsemigroups/knuth-bendix.hpp
2021-12-16 15:41:37.523553916 +0100
@@ -633,9 +633,7 @@
void run_impl() override;
- bool finished_impl() const override {
- return confluent();
- }
+ bool finished_impl() const override;
bool is_obviously_infinite_impl() override;
bool is_obviously_finite_impl() override;
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/include/libsemigroups/obvinf.hpp
new/libsemigroups-2.1.3/include/libsemigroups/obvinf.hpp
--- old/libsemigroups-2.1.2/include/libsemigroups/obvinf.hpp 2021-11-28
12:25:20.185367147 +0100
+++ new/libsemigroups-2.1.3/include/libsemigroups/obvinf.hpp 2021-12-02
18:42:52.620117701 +0100
@@ -131,7 +131,6 @@
inline bool matrix_row_sums_to_0(size_t row) {
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
- // static_assert(false, "");
return _matrix.row(row).sum() == 0;
#else
(void) row;
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/src/knuth-bendix-impl.hpp
new/libsemigroups-2.1.3/src/knuth-bendix-impl.hpp
--- old/libsemigroups-2.1.2/src/knuth-bendix-impl.hpp 2021-11-28
12:30:48.106669448 +0100
+++ new/libsemigroups-2.1.3/src/knuth-bendix-impl.hpp 2021-12-16
15:41:37.524175898 +0100
@@ -779,6 +779,10 @@
// KnuthBendixImpl - main methods - public
//////////////////////////////////////////////////////////////////////////
+ bool confluent_known() const noexcept {
+ return _confluence_known;
+ }
+
bool confluent() const {
if (!_stack.empty()) {
return false;
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/src/knuth-bendix.cpp
new/libsemigroups-2.1.3/src/knuth-bendix.cpp
--- old/libsemigroups-2.1.2/src/knuth-bendix.cpp 2021-11-28
12:30:48.106877943 +0100
+++ new/libsemigroups-2.1.3/src/knuth-bendix.cpp 2021-12-16
15:41:37.524568303 +0100
@@ -212,6 +212,10 @@
return _impl->confluent();
}
+ bool KnuthBendix::finished_impl() const {
+ return _impl->confluent_known() && _impl->confluent();
+ }
+
void KnuthBendix::run_impl() {
_impl->knuth_bendix();
report_why_we_stopped();
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/src/suffix-tree.cpp
new/libsemigroups-2.1.3/src/suffix-tree.cpp
--- old/libsemigroups-2.1.2/src/suffix-tree.cpp 2021-11-28 12:30:48.107544304
+0100
+++ new/libsemigroups-2.1.3/src/suffix-tree.cpp 2021-12-16 15:41:37.525077830
+0100
@@ -283,12 +283,10 @@
size_t SuffixTree::distance_from_root(node_index_type i) const {
LIBSEMIGROUPS_ASSERT(i < _nodes.size());
- Node n = _nodes[i];
size_t result = 0;
- while (n.parent != UNDEFINED) {
- result += n.length();
- i = n.parent;
- n = _nodes[i];
+ while (_nodes[i].parent != UNDEFINED) {
+ result += _nodes[i].length();
+ i = _nodes[i].parent;
}
return result;
}
@@ -302,14 +300,14 @@
// Follow the path from the root labelled by _words[i], then go back
// from the leaf to its parent (which is an internal node),
// corresponding to the maximal_piece_prefix.
- index_type l = _word_begin[j];
- index_type r = _word_begin[j + 1];
- Node m = _nodes.front();
+ index_type l = _word_begin[j];
+ index_type r = _word_begin[j + 1];
+ node_index_type m = 0;
while (l < r) {
- m = _nodes[m.child(_word[l])];
- l += m.length();
+ m = _nodes[m].child(_word[l]);
+ l += _nodes[m].length();
}
- return distance_from_root(m.parent);
+ return distance_from_root(_nodes[m].parent);
}
size_t SuffixTree::maximal_piece_suffix(word_index_type j) const {
@@ -340,14 +338,13 @@
// Follow the path from the root labelled by _words[i], then go back
// from the leaf to its parent (which is an internal node),
// corresponding to the maximal_piece_prefix.
- Node m = _nodes.front();
+ node_index_type m = 0;
while (l < r) {
- auto n = m.child(_word[l]);
- LIBSEMIGROUPS_ASSERT(n != UNDEFINED);
- m = _nodes[n];
- l += m.length();
+ m = _nodes[m].child(_word[l]);
+ LIBSEMIGROUPS_ASSERT(m != UNDEFINED);
+ l += _nodes[m].length();
}
- return distance_from_root(m.parent);
+ return distance_from_root(_nodes[m].parent);
}
size_t SuffixTree::number_of_pieces(word_index_type i) const {
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/tests/test-digraph.cpp
new/libsemigroups-2.1.3/tests/test-digraph.cpp
--- old/libsemigroups-2.1.2/tests/test-digraph.cpp 2021-11-28
12:30:48.110680653 +0100
+++ new/libsemigroups-2.1.3/tests/test-digraph.cpp 2021-12-02
18:42:52.620940117 +0100
@@ -1539,6 +1539,7 @@
REQUIRE(ad.number_of_paths_algorithm(0, 0, 16) == algorithm::acyclic);
REQUIRE(ad.number_of_paths(0, 0, 30) == 9);
+ REQUIRE(ad.number_of_paths(1, 0, 10, algorithm::acyclic) == 6);
REQUIRE(ad.number_of_paths(1, 0, 10, algorithm::matrix) == 6);
REQUIRE(ad.number_of_paths(1, 9, 0, 10, algorithm::matrix) == 3);
}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/libsemigroups-2.1.2/tests/test-kambites.cpp
new/libsemigroups-2.1.3/tests/test-kambites.cpp
--- old/libsemigroups-2.1.2/tests/test-kambites.cpp 2021-11-28
12:30:48.111693256 +0100
+++ new/libsemigroups-2.1.3/tests/test-kambites.cpp 2021-12-16
15:41:37.525732395 +0100
@@ -36,6 +36,7 @@
#include "libsemigroups/report.hpp" // for ReportGuard
#include "libsemigroups/siso.hpp" // for const_sislo_iterator
#include "libsemigroups/string.hpp" // for random_string etc
+#include "libsemigroups/transf.hpp" // for LeastTransf
#include "libsemigroups/types.hpp" // for tril etc
#include "libsemigroups/word.hpp" // for number_of_words
@@ -1817,5 +1818,22 @@
REQUIRE(l.word_to_class_index({0, 1, 0, 0}) == 100);
}
+ LIBSEMIGROUPS_TEST_CASE("Kambites",
+ "078",
+ "(cong) large number of rules",
+ "[quick][kambites][cong][congruence]") {
+ FroidurePin<LeastTransf<6>> S({LeastTransf<6>({1, 2, 3, 4, 5, 0}),
+ LeastTransf<6>({1, 0, 2, 3, 4, 5}),
+ LeastTransf<6>({0, 1, 2, 3, 4, 0})});
+ REQUIRE(S.size() == 46'656);
+ Kambites k;
+ k.set_number_of_generators(3);
+ for (auto it = S.cbegin_rules(); it != S.cend_rules(); ++it) {
+ k.add_pair(it->first, it->second);
+ }
+ REQUIRE(k.kambites().small_overlap_class() == 1);
+ }
+
} // namespace congruence
+
} // namespace libsemigroups
