summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichele Borassi <michele.borassi@imtlucca.it>2015-08-06 11:47:49 +0200
committerMichele Borassi <michele.borassi@imtlucca.it>2015-08-06 11:47:49 +0200
commit93dee5e3d8e20b2fd19da57644f0f67e645171de (patch)
tree6dc3e4afbe472697de0e007a9f31927c57fb1a04
parentSimplified handling of labels (diff)
parentUpdated Sage version to 6.9.beta1 (diff)
Merged with beta1
Conflicts: src/sage/graphs/digraph.py src/sage/graphs/generic_graph.py src/sage/graphs/graph.py
-rw-r--r--VERSION.txt2
-rw-r--r--build/pkgs/configure/checksums.ini6
-rw-r--r--build/pkgs/configure/package-version.txt2
-rw-r--r--build/pkgs/ecl/SPKG.txt2
-rw-r--r--build/pkgs/ecl/checksums.ini6
-rw-r--r--build/pkgs/ecl/package-version.txt2
-rw-r--r--build/pkgs/ecl/patches/gmp.patch34
-rw-r--r--build/pkgs/ecl/patches/implib.patch236
-rw-r--r--build/pkgs/ecl/patches/write_error.patch14
-rwxr-xr-xbuild/pkgs/ecl/spkg-install12
-rwxr-xr-xbuild/pkgs/ecl/spkg-src46
-rwxr-xr-xbuild/pkgs/gf2x/spkg-install4
-rw-r--r--build/pkgs/graphs/SPKG.txt16
-rw-r--r--build/pkgs/graphs/checksums.ini6
-rw-r--r--build/pkgs/graphs/package-version.txt2
-rw-r--r--build/pkgs/ipython/checksums.ini6
-rw-r--r--build/pkgs/ipython/package-version.txt2
-rw-r--r--build/pkgs/ncurses/patches/work_around_changed_output_of_GNU_cpp_5.x.patch6
-rw-r--r--src/bin/sage-banner2
-rwxr-xr-xsrc/bin/sage-list-packages2
-rw-r--r--src/bin/sage-version.sh4
-rwxr-xr-xsrc/doc/common/builder.py6
-rw-r--r--src/doc/en/reference/graphs/index.rst1
-rw-r--r--src/doc/en/reference/structure/index.rst2
-rw-r--r--src/module_list.py3
-rw-r--r--src/sage/calculus/calculus.py10
-rw-r--r--src/sage/calculus/wester.py3
-rw-r--r--src/sage/combinat/designs/bibd.py124
-rw-r--r--src/sage/combinat/designs/database.py320
-rw-r--r--src/sage/combinat/designs/difference_family.py2
-rw-r--r--src/sage/combinat/designs/incidence_structures.py1
-rw-r--r--src/sage/combinat/finite_state_machine.py336
-rw-r--r--src/sage/combinat/finite_state_machine_generators.py5
-rw-r--r--src/sage/functions/orthogonal_polys.py2
-rw-r--r--src/sage/functions/piecewise.py2
-rw-r--r--src/sage/geometry/polyhedron/base.py41
-rw-r--r--src/sage/geometry/polyhedron/library.py45
-rw-r--r--src/sage/graphs/base/boost_graph.pxd34
-rw-r--r--src/sage/graphs/base/boost_graph.pyx274
-rw-r--r--src/sage/graphs/base/boost_interface.cpp58
-rw-r--r--src/sage/graphs/base/c_graph.pyx14
-rw-r--r--src/sage/graphs/digraph.py11
-rw-r--r--src/sage/graphs/distances_all_pairs.pyx19
-rw-r--r--src/sage/graphs/generators/families.py3
-rw-r--r--src/sage/graphs/generators/random.py5
-rw-r--r--src/sage/graphs/generators/smallgraphs.py44
-rw-r--r--src/sage/graphs/generic_graph.py1801
-rw-r--r--src/sage/graphs/graph.py11
-rw-r--r--src/sage/graphs/graph_decompositions/bandwidth.pyx12
-rw-r--r--src/sage/graphs/graph_generators.py7
-rw-r--r--src/sage/graphs/graph_plot.py11
-rw-r--r--src/sage/graphs/spanning_tree.pyx21
-rw-r--r--src/sage/graphs/strongly_regular_db.pyx1252
-rw-r--r--src/sage/homology/chain_complex.py44
-rw-r--r--src/sage/homology/delta_complex.py2
-rw-r--r--src/sage/homology/examples.py12
-rw-r--r--src/sage/interfaces/chomp.py5
-rw-r--r--src/sage/libs/pari/pari_instance.pxd2
-rw-r--r--src/sage/libs/pari/pari_instance.pyx18
-rw-r--r--src/sage/matroids/utilities.py2
-rw-r--r--src/sage/misc/sagedoc.py29
-rw-r--r--src/sage/numerical/interactive_simplex_method.py363
-rw-r--r--src/sage/rings/fraction_field_element.pyx30
-rw-r--r--src/sage/rings/number_field/number_field_element.pyx2
-rw-r--r--src/sage/rings/polynomial/polynomial_element.pyx233
-rw-r--r--src/sage/rings/polynomial/polynomial_element_generic.py78
-rw-r--r--src/sage/rings/polynomial/polynomial_real_mpfr_dense.pyx2
-rw-r--r--src/sage/rings/polynomial/polynomial_zz_pex.pyx2
-rw-r--r--src/sage/schemes/elliptic_curves/ell_rational_field.py3
-rw-r--r--src/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py154
-rw-r--r--src/sage/structure/set_factories.py1180
-rw-r--r--src/sage/structure/set_factories_example.py527
-rw-r--r--src/sage/symbolic/expression.pyx57
-rw-r--r--src/sage/version.py4
74 files changed, 6529 insertions, 1112 deletions
diff --git a/VERSION.txt b/VERSION.txt
index c5de210..a93c3a4 100644
--- a/VERSION.txt
+++ b/VERSION.txt
@@ -1 +1 @@
-Sage version 6.9.beta0, released 2015-07-29
+Sage version 6.9.beta1, released 2015-08-05
diff --git a/build/pkgs/configure/checksums.ini b/build/pkgs/configure/checksums.ini
index e6e6098..bdf80f5 100644
--- a/build/pkgs/configure/checksums.ini
+++ b/build/pkgs/configure/checksums.ini
@@ -1,4 +1,4 @@
tarball=configure-VERSION.tar.gz
-sha1=74c12f15bd843d9bb723a17bac629846e4e8f57a
-md5=84df33fa9762cb8826ced5a7e6aadbc0
-cksum=4042526937
+sha1=8be9070797613265821e1660191e41fddff58d59
+md5=7ea664318dc0543591e39456676d208b
+cksum=1278202916
diff --git a/build/pkgs/configure/package-version.txt b/build/pkgs/configure/package-version.txt
index fe4afb0..e34885b 100644
--- a/build/pkgs/configure/package-version.txt
+++ b/build/pkgs/configure/package-version.txt
@@ -1 +1 @@
-106
+107
diff --git a/build/pkgs/ecl/SPKG.txt b/build/pkgs/ecl/SPKG.txt
index ab2ffe8..ee1f125 100644
--- a/build/pkgs/ecl/SPKG.txt
+++ b/build/pkgs/ecl/SPKG.txt
@@ -34,6 +34,8 @@ Website: http://ecls.sourceforge.net/
* boehm_gc
== Special Update/Build Instructions ==
+ * As autotools need to be run after most of the patches are applied,
+ we do all the patching in spkg-source.
* Deleting the following directories saves space: without doing
this, the tarball can grow from under 3 megabytes to more than 7
megabytes. Deleting these files is done automatically by the
diff --git a/build/pkgs/ecl/checksums.ini b/build/pkgs/ecl/checksums.ini
index f0e6ca9..7b0e8c9 100644
--- a/build/pkgs/ecl/checksums.ini
+++ b/build/pkgs/ecl/checksums.ini
@@ -1,4 +1,4 @@
tarball=ecl-VERSION.tar.bz2
-sha1=f9ee0699433be837e90d04f6f038acf9209cf5f6
-md5=db91e48a9f140bd0c571c9f82bc74eb2
-cksum=2161474303
+sha1=d5b9f2f19847697f3cbe54e69daf609d1ea1b9ca
+md5=ba1d8acd05b2921c556a488191ff4b6b
+cksum=1247067343
diff --git a/build/pkgs/ecl/package-version.txt b/build/pkgs/ecl/package-version.txt
index 34603f3..74a1062 100644
--- a/build/pkgs/ecl/package-version.txt
+++ b/build/pkgs/ecl/package-version.txt
@@ -1 +1 @@
-13.5.1.p0
+15.3.7p0
diff --git a/build/pkgs/ecl/patches/gmp.patch b/build/pkgs/ecl/patches/gmp.patch
index 9ac008a..50a5a79 100644
--- a/build/pkgs/ecl/patches/gmp.patch
+++ b/build/pkgs/ecl/patches/gmp.patch
@@ -1,33 +1,13 @@
-diff -druN src.orig/src/configure.in src/src/configure.in
---- src.orig/src/configure.in 2012-12-07 22:01:02.000000000 +0100
-+++ src/src/configure.in 2014-04-09 15:17:50.282780900 +0200
-@@ -11,7 +11,7 @@
- AC_INIT([ecl],[13.5.1],[])
+diff --git b/src/configure.ac a/src/configure.ac
+index bc8d84b..e076e09 100644
+--- b/src/configure.ac
++++ a/src/configure.ac
+@@ -11,7 +11,7 @@ dnl
+ AC_INIT([ecl],[15.3.7],[])
AC_REVISION([$Revision$])
AC_CONFIG_SRCDIR([bare.lsp.in])
-AC_CONFIG_AUX_DIR([gmp])
+AC_CONFIG_AUX_DIR([.])
- AC_PREREQ(2.59)
+ AC_PREREQ(2.69)
dnl -----------------------------------------------------------------------
-diff -druN src.orig/src/configure src/src/configure
---- src.orig/src/configure 2012-12-07 22:01:02.000000000 +0100
-+++ src/src/configure 2014-04-09 15:20:21.360905900 +0200
-@@ -2546,7 +2546,7 @@
-
-
- ac_aux_dir=
--for ac_dir in gmp "$srcdir"/gmp; do
-+for ac_dir in . "$srcdir"/.; do
- if test -f "$ac_dir/install-sh"; then
- ac_aux_dir=$ac_dir
- ac_install_sh="$ac_aux_dir/install-sh -c"
-@@ -2562,7 +2562,7 @@
- fi
- done
- if test -z "$ac_aux_dir"; then
-- as_fn_error $? "cannot find install-sh, install.sh, or shtool in gmp \"$srcdir\"/gmp" "$LINENO" 5
-+ as_fn_error $? "cannot find install-sh, install.sh, or shtool in . \"$srcdir\"/." "$LINENO" 5
- fi
-
- # These three variables are undocumented and unsupported,
diff --git a/build/pkgs/ecl/patches/implib.patch b/build/pkgs/ecl/patches/implib.patch
index 818f537..ab11e18 100644
--- a/build/pkgs/ecl/patches/implib.patch
+++ b/build/pkgs/ecl/patches/implib.patch
@@ -1,71 +1,8 @@
-diff -durN src.orig/src/configure.in src/src/configure.in
---- src.orig/src/configure.in 2012-12-17 11:08:10.000000000 +0100
-+++ src/src/configure.in 2013-01-18 11:34:30.012132746 +0100
-@@ -582,6 +582,19 @@
- AC_SUBST(SONAME)
- AC_SUBST(SONAME_LDFLAGS)
-
-+dnl ----------------------------------------------------------------------
-+dnl IMPLIB_NAME is only active when IMPLIB_NAME is non nil
-+dnl
-+AC_MSG_CHECKING(for import name)
-+if test "${enable_soname}" != yes; then
-+ IMPLIB_NAME=''
-+ AC_MSG_RESULT([none])
-+else
-+ AC_MSG_RESULT([${IMPLIB_NAME}])
-+fi
-+AC_SUBST(IMPLIB_NAME)
-+AC_SUBST(IMPLIB_LDFLAGS)
-+
- dnl Related to that, the package version number
- ECL_VERSION_NUMBER=$(($PACKAGE_MAJOR * 10000 + $PACKAGE_MINOR * 100 + $PACKAGE_LEAST))
- AC_SUBST(ECL_VERSION_NUMBER)
-diff -durN src.orig/src/Makefile.in src/src/Makefile.in
---- src.orig/src/Makefile.in 2012-12-17 11:08:06.000000000 +0100
-+++ src/src/Makefile.in 2013-01-18 11:34:30.012132746 +0100
-@@ -174,10 +174,14 @@
- if test -s $$i ; then \
- if echo $$i | grep dll; then \
- $(INSTALL_LIBRARY) $$i $(DESTDIR)$(bindir); \
-- fi; \
-- $(INSTALL_LIBRARY) $$i $(DESTDIR)$(libdir); \
-+ else \
-+ $(INSTALL_LIBRARY) $$i $(DESTDIR)$(libdir); \
-+ fi \
- fi \
- done
-+ if [ "x@IMPLIB_NAME@" != "x" -a -f "@IMPLIB_NAME@" ]; then \
-+ $(INSTALL_LIBRARY) @IMPLIB_NAME@ $(DESTDIR)$(libdir); \
-+ fi
- if [ "x@SONAME@" != "x" -a -f "@SONAME@" ]; then \
- ( cd $(DESTDIR)$(libdir) && $(RM) -f @SONAME3@ @SONAME2@ @SONAME1@ && \
- mv @SONAME@ @SONAME3@ && \
-diff -durN src.orig/src/compile.lsp.in src/src/compile.lsp.in
---- src.orig/src/compile.lsp.in 2012-12-17 11:08:05.000000000 +0100
-+++ src/src/compile.lsp.in 2013-01-18 11:34:30.012132746 +0100
-@@ -58,7 +58,7 @@
- ;;;
- ;;; * Add include path to not yet installed headers, and remove include flag
- ;;; (-I) to installed directory, and Notice that we must explicitely mention
--;;; libecl.so/ecl.dll instead of using -lecl. This is to avoid interference
-+;;; libecl.so/cygecl.dll instead of using -lecl. This is to avoid interference
- ;;; with an already installed copy of ECL.
- ;;;
- (setq c::*cc-flags*
-@@ -140,7 +140,7 @@
- ;;;
- ;;; We do not need the -rpath flag for the library, nor -lecl.
- ;;;
--(let* ((c::*ld-shared-flags* #-msvc "@SHARED_LDFLAGS@ @LDFLAGS@ @SONAME_LDFLAGS@ @CORE_LIBS@ @FASL_LIBS@ @LIBS@"
-+(let* ((c::*ld-shared-flags* #-msvc " @IMPLIB_LDFLAGS@ @SHARED_LDFLAGS@ @LDFLAGS@ @SONAME_LDFLAGS@ @CORE_LIBS@ @FASL_LIBS@ @LIBS@"
- #+msvc "@SHARED_LDFLAGS@ @LDFLAGS@ @STATICLIBS@ @CLIBS@")
- (c::*cc-flags* (concatenate 'string "-DECL_API -I@true_builddir@/c " c::*cc-flags*))
- (extra-args nil))
-diff -durN src.orig/src/aclocal.m4 src/src/aclocal.m4
---- src.orig/src/aclocal.m4 2012-12-17 11:08:05.000000000 +0100
-+++ src/src/aclocal.m4 2013-01-18 11:34:30.012132746 +0100
-@@ -232,6 +232,8 @@
+diff --git a/src/aclocal.m4 b/src/aclocal.m4
+index 63d8997..79ff24d 100644
+--- a/src/aclocal.m4
++++ b/src/aclocal.m4
+@@ -233,6 +233,8 @@ AC_SUBST(LIBPREFIX)dnl Name components of a statically linked library
AC_SUBST(LIBEXT)
AC_SUBST(SHAREDEXT)dnl Name components of a dynamically linked library
AC_SUBST(SHAREDPREFIX)
@@ -74,7 +11,7 @@ diff -durN src.orig/src/aclocal.m4 src/src/aclocal.m4
AC_SUBST(OBJEXT)dnl These are set by autoconf
AC_SUBST(EXEEXT)
AC_SUBST(INSTALL_TARGET)dnl Which type of installation: flat directory or unix like.
-@@ -241,6 +243,8 @@
+@@ -242,6 +244,8 @@ ECL_GC_DIR=gc-unstable
ECL_LDRPATH=''
SHAREDEXT='so'
SHAREDPREFIX='lib'
@@ -83,7 +20,7 @@ diff -durN src.orig/src/aclocal.m4 src/src/aclocal.m4
LIBPREFIX='lib'
LIBEXT='a'
PICFLAG='-fPIC'
-@@ -252,6 +256,8 @@
+@@ -253,6 +257,8 @@ THREAD_OBJ="$THREAD_OBJ threads/process threads/queue threads/mutex threads/cond
clibs=''
SONAME=''
SONAME_LDFLAGS=''
@@ -92,7 +29,7 @@ diff -durN src.orig/src/aclocal.m4 src/src/aclocal.m4
case "${host_os}" in
# libdir may have a dollar expression inside
linux*)
-@@ -354,10 +360,14 @@
+@@ -355,10 +361,14 @@ case "${host_os}" in
shared='yes'
THREAD_CFLAGS='-D_THREAD_SAFE'
THREAD_LIBS='-lpthread'
@@ -108,9 +45,9 @@ diff -durN src.orig/src/aclocal.m4 src/src/aclocal.m4
+ IMPLIB_NAME="${IMPLIB_PREFIX}ecl.${IMPLIB_EXT}"
+ IMPLIB_LDFLAGS="-Wl,--out-implib,${IMPLIB_NAME}"
PICFLAG=''
- ;;
- mingw*)
-@@ -367,10 +377,14 @@
+ if test "x$host_cpu" = "xx86_64" ; then
+ # Our GMP library is too old and does not support
+@@ -373,10 +383,14 @@ case "${host_os}" in
enable_threads='yes'
THREAD_CFLAGS='-D_THREAD_SAFE'
THREAD_GC_FLAGS='--enable-threads=win32'
@@ -127,102 +64,71 @@ diff -durN src.orig/src/aclocal.m4 src/src/aclocal.m4
PICFLAG=''
INSTALL_TARGET='flatinstall'
TCPLIBS='-lws2_32'
-diff -durN src.orig/src/configure src/src/configure
---- src.orig/src/configure 2012-12-17 11:08:11.000000000 +0100
-+++ src/src/configure 2013-01-18 11:35:15.231702758 +0100
-@@ -643,6 +643,8 @@
- CL_FIXNUM_TYPE
- XMKMF
- ECL_VERSION_NUMBER
-+IMPLIB_LDFLAGS
-+IMPLIB_NAME
- SONAME_LDFLAGS
- SONAME
- SONAME1
-@@ -659,6 +661,8 @@
- ECL_GC_DIR
- thehost
- INSTALL_TARGET
-+IMPLIB_PREFIX
-+IMPLIB_EXT
- SHAREDPREFIX
- SHAREDEXT
- LIBEXT
-@@ -4855,10 +4859,13 @@
-
-
-
-+
- ECL_GC_DIR=gc-unstable
- ECL_LDRPATH=''
- SHAREDEXT='so'
- SHAREDPREFIX='lib'
-+IMPLIB_EXT=''
-+IMPLIB_PREFIX=''
- LIBPREFIX='lib'
- LIBEXT='a'
- PICFLAG='-fPIC'
-@@ -4870,6 +4877,8 @@
- clibs=''
- SONAME=''
- SONAME_LDFLAGS=''
-+IMPLIB_NAME=''
-+IMPLIB_LDFLAGS=''
- case "${host_os}" in
- # libdir may have a dollar expression inside
- linux*)
-@@ -4972,10 +4981,14 @@
- shared='yes'
- THREAD_CFLAGS='-D_THREAD_SAFE'
- THREAD_LIBS='-lpthread'
-- SHARED_LDFLAGS="-shared ${LDFLAGS}"
-- BUNDLE_LDFLAGS="-shared ${LDFLAGS}"
-- SHAREDPREFIX=''
-+ SHARED_LDFLAGS="-shared -Wl,--enable-auto-image-base ${LDFLAGS}"
-+ BUNDLE_LDFLAGS="-shared -Wl,--enable-auto-image-base ${LDFLAGS}"
-+ SHAREDPREFIX='cyg'
- SHAREDEXT='dll'
-+ IMPLIB_PREFIX='lib'
-+ IMPLIB_EXT='dll.a'
-+ IMPLIB_NAME="${IMPLIB_PREFIX}ecl.${IMPLIB_EXT}"
-+ IMPLIB_LDFLAGS="-Wl,--out-implib,${IMPLIB_NAME}"
- PICFLAG=''
- ;;
- mingw*)
-@@ -4985,10 +4998,14 @@
- enable_threads='yes'
- THREAD_CFLAGS='-D_THREAD_SAFE'
- THREAD_GC_FLAGS='--enable-threads=win32'
-- SHARED_LDFLAGS=''
-- BUNDLE_LDFLAGS=''
-+ SHARED_LDFLAGS="-shared -Wl,--enable-auto-image-base ${LDFLAGS}"
-+ BUNDLE_LDFLAGS="-shared -Wl,--enable-auto-image-base ${LDFLAGS}"
- SHAREDPREFIX=''
- SHAREDEXT='dll'
-+ IMPLIB_PREFIX='lib'
-+ IMPLIB_EXT='dll.a'
-+ IMPLIB_NAME="${IMPLIB_PREFIX}ecl.${IMPLIB_EXT}"
-+ IMPLIB_LDFLAGS="-Wl,--out-implib,${IMPLIB_NAME}"
- PICFLAG=''
- INSTALL_TARGET='flatinstall'
- TCPLIBS='-lws2_32'
-@@ -6131,6 +6148,19 @@
-
-
+diff --git a/src/compile.lsp.in b/src/compile.lsp.in
+index 773fe99..697c115 100755
+--- a/src/compile.lsp.in
++++ b/src/compile.lsp.in
+@@ -58,7 +58,7 @@
+ ;;;
+ ;;; * Add include path to not yet installed headers, and remove include flag
+ ;;; (-I) to installed directory, and Notice that we must explicitely mention
+-;;; libecl.so/ecl.dll instead of using -lecl. This is to avoid interference
++;;; libecl.so/cygecl.dll instead of using -lecl. This is to avoid interference
+ ;;; with an already installed copy of ECL.
+ ;;;
+ (setq c::*cc-flags*
+@@ -140,7 +140,7 @@
+ ;;;
+ ;;; We do not need the -rpath flag for the library, nor -lecl.
+ ;;;
+-(let* ((c::*ld-shared-flags* #-msvc "@SHARED_LDFLAGS@ @LDFLAGS@ @SONAME_LDFLAGS@ @CORE_LIBS@ @FASL_LIBS@ @LIBS@"
++(let* ((c::*ld-shared-flags* #-msvc " @IMPLIB_LDFLAGS@ @SHARED_LDFLAGS@ @LDFLAGS@ @SONAME_LDFLAGS@ @CORE_LIBS@ @FASL_LIBS@ @LIBS@"
+ #+msvc "@SHARED_LDFLAGS@ @LDFLAGS@ @STATICLIBS@ @CLIBS@")
+ (c::*cc-flags* (concatenate 'string "-DECL_API -I@true_builddir@/c " c::*cc-flags*))
+ (extra-args nil))
+diff --git a/src/configure.ac b/src/configure.ac
+index e076e09..15d307a 100644
+--- a/src/configure.ac
++++ b/src/configure.ac
+@@ -588,6 +588,20 @@ AC_SUBST(SONAME1)
+ AC_SUBST(SONAME)
+ AC_SUBST(SONAME_LDFLAGS)
-+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for import name" >&5
-+$as_echo_n "checking for import name... " >&6; }
++dnl ----------------------------------------------------------------------
++dnl IMPLIB_NAME is only active when IMPLIB_NAME is non nil
++dnl
++AC_MSG_CHECKING(for import name)
+if test "${enable_soname}" != yes; then
+ IMPLIB_NAME=''
-+ { $as_echo "$as_me:${as_lineno-$LINENO}: result: none" >&5
-+$as_echo "none" >&6; }
++ AC_MSG_RESULT([none])
+else
-+ { $as_echo "$as_me:${as_lineno-$LINENO}: result: ${IMPLIB_NAME}" >&5
-+$as_echo "${IMPLIB_NAME}" >&6; }
++ AC_MSG_RESULT([${IMPLIB_NAME}])
+fi
++AC_SUBST(IMPLIB_NAME)
++AC_SUBST(IMPLIB_LDFLAGS)
+
+
-+
+ dnl Related to that, the package version number
ECL_VERSION_NUMBER=$(($PACKAGE_MAJOR * 10000 + $PACKAGE_MINOR * 100 + $PACKAGE_LEAST))
-
-
+ AC_SUBST(ECL_VERSION_NUMBER)
+diff --git a/src/Makefile.in b/src/Makefile.in
+index 12e9f05..74bc216 100644
+--- a/src/Makefile.in
++++ b/src/Makefile.in
+@@ -174,10 +174,14 @@ install:
+ if test -s $$i ; then \
+ if echo $$i | grep dll; then \
+ $(INSTALL_LIBRARY) $$i $(DESTDIR)$(bindir); \
+- fi; \
+- $(INSTALL_LIBRARY) $$i $(DESTDIR)$(libdir); \
++ else \
++ $(INSTALL_LIBRARY) $$i $(DESTDIR)$(libdir); \
++ fi \
+ fi \
+ done
++ if [ "x@IMPLIB_NAME@" != "x" -a -f "@IMPLIB_NAME@" ]; then \
++ $(INSTALL_LIBRARY) @IMPLIB_NAME@ $(DESTDIR)$(libdir); \
++ fi
+ if [ "x@SONAME@" != "x" -a -f "@SONAME@" ]; then \
+ ( cd $(DESTDIR)$(libdir) && $(RM) -f @SONAME3@ @SONAME2@ @SONAME1@ && \
+ mv @SONAME@ @SONAME3@ && \
diff --git a/build/pkgs/ecl/patches/write_error.patch b/build/pkgs/ecl/patches/write_error.patch
index 8ddcf68..658b864 100644
--- a/build/pkgs/ecl/patches/write_error.patch
+++ b/build/pkgs/ecl/patches/write_error.patch
@@ -1,13 +1,15 @@
-diff -ru src/src/c/file.d b/src/c/file.d
---- src/src/c/file.d 2012-12-07 22:01:02.000000000 +0100
-+++ b/src/c/file.d 2013-04-10 09:07:24.537513659 +0200
-@@ -3335,7 +3335,8 @@
+diff --git b/src/c/file.d a/src/c/file.d
+index de7ba7b..c1f8c1e 100755
+--- b/src/c/file.d
++++ a/src/c/file.d
+@@ -3341,7 +3341,9 @@ output_stream_write_byte8(cl_object strm, unsigned char *c, cl_index n)
ecl_disable_interrupts();
do {
out = fwrite(c, sizeof(char), n, IO_STREAM_FILE(strm));
- } while (out < n && restartable_io_error(strm, "fwrite"));
-+ /* Ignore write errors to stderr to avoid an infinite loop */
-+ } while (out < n && (IO_STREAM_FILE(strm) != stderr) && restartable_io_error(strm, "fwrite"));
++ /* Ignore write errors to stderr to avoid an infinite loop */
++ } while (out < n && (IO_STREAM_FILE(strm) != stderr) && restartable_io_error(strm, "fwrite"));
++
ecl_enable_interrupts();
return out;
}
diff --git a/build/pkgs/ecl/spkg-install b/build/pkgs/ecl/spkg-install
index b5056c3..f478c45 100755
--- a/build/pkgs/ecl/spkg-install
+++ b/build/pkgs/ecl/spkg-install
@@ -7,16 +7,6 @@ if [ -z "$SAGE_LOCAL" ] ; then
fi
cd src
-# For some of the patches, Cygwin also has upstream fixes that are
-# closely related, keep track. See Trac 11119, for example.
-for patch in ../patches/*.patch; do
- [ -f "$patch" ] || continue
- patch -p1 <"$patch"
- if [ $? -ne 0 ]; then
- echo >&2 "Error applying '$patch'"
- exit 1
- fi
-done
if [ -z "$CFLAG64" ] ; then
CFLAG64=-m64
@@ -60,6 +50,8 @@ echo "Using CPPFLAGS=$CPPFLAGS"
echo "Using LDFLAGS=$LDFLAGS"
echo "configure scripts and/or makefiles might override these later"
echo ""
+echo "Note that the patches were applied by spkg-source"
+echo ""
# export everything. Probably not necessary in most cases.
export CFLAGS
diff --git a/build/pkgs/ecl/spkg-src b/build/pkgs/ecl/spkg-src
index fe8a075..587331c 100755
--- a/build/pkgs/ecl/spkg-src
+++ b/build/pkgs/ecl/spkg-src
@@ -6,11 +6,15 @@
# and its subdirectories!
#
# HOW TO MAKE THE TARBALL:
-# 1) copy upstream ecl-$ECLVERSION.tgz to this directory
+# 1) copy upstream the tarball from gitlab; it will be named by the commit
+# hash, e.g. ecl-a014bd2c23a9ba863ecdd28c1c48d67de04d3620.tar.gz
+# Untar ECL tarball; the root dir will be named ecl.git/
# 2) ./spkg-src
-# 3) compress ecl-$ECLVERSION into a .tar.bz2 file
+#
+# needs autotools and sage in your PATH.
#
# AUTHOR: Jeroen Demeyer (November 2011)
+# Dima Pasechnik (July 2015)
# Sanity check: must be run from current directory
if ! [ -f spkg-src ]; then
@@ -21,12 +25,40 @@ fi
# Exit on failure
set -e
-# Untar ECL tarball
-ECLVERSION=13.5.1
-tar xf ecl-"$ECLVERSION".tgz
+# now we automate the task:
+ECLVERSION=`cat package-version.txt`
+ECLTARBALL=ecl-"$ECLVERSION".tar
+
+mv ecl.git ecl-"$ECLVERSION"
cd ecl-"$ECLVERSION"
+# the patches are applied here, as it has to be done before
+# running autoconf.
+cd src
+echo "applying patches in ecl-$ECLVERSION/src"
+# For some of the patches, Cygwin also has upstream fixes that are
+# closely related, keep track. See Trac 11119, for example.
+for patch in ../../patches/*.patch; do
+ patch --verbose -p2 <"$patch"
+ if [ $? -ne 0 ]; then
+ echo >&2 "Error applying '$patch'"
+ exit 1
+ fi
+done
+
+
+cd ..
# Remove unneeded files to save space
-rm -rf msvc
+rm -rf msvc/
cd src
-rm -rf gc-unstable gmp libffi
+rm -rf gc-unstable/ gmp/ libffi/
+libtoolize # to generate configure script
+autoreconf -ivf
+
+cd ../../
+rm -f "$ECLTARBALL".* "$ECLTARBALL"
+tar cf "$ECLTARBALL" ecl-"$ECLVERSION"/
+bzip2 "$ECLTARBALL"
+mv -f "$ECLTARBALL".bz2 ../../../upstream/
+sage -sh sage-fix-pkg-checksums
+rm -rf ecl-"$ECLVERSION"/
diff --git a/build/pkgs/gf2x/spkg-install b/build/pkgs/gf2x/spkg-install
index ee7e6a0..31798a5 100755
--- a/build/pkgs/gf2x/spkg-install
+++ b/build/pkgs/gf2x/spkg-install
@@ -26,8 +26,8 @@ touch aclocal.m4 configure Makefile.in gf2x/gf2x-config.h.in
if [ "$SAGE_DEBUG" = "yes" ]; then
echo "Building a debug version of gf2x."
export CFLAGS="-O0 -g $CFLAGS"
-elif $CC --version 2>/dev/null |grep 'gcc.* 5[.]1' >/dev/null; then
- echo "Using compiler flags to work around problems with GCC 5.1 (Trac #18580)"
+elif $CC --version 2>/dev/null |grep 'gcc.* 5[.][12]' >/dev/null; then
+ echo "Using compiler flags to work around problems with GCC 5.1/5.2 (Trac #18580,#18978)"
export CFLAGS="-O2 -fno-forward-propagate -g $CFLAGS"
else
export CFLAGS="-O2 -g $CFLAGS"
diff --git a/build/pkgs/graphs/SPKG.txt b/build/pkgs/graphs/SPKG.txt
index e959d94..f163b4d 100644
--- a/build/pkgs/graphs/SPKG.txt
+++ b/build/pkgs/graphs/SPKG.txt
@@ -12,7 +12,18 @@ Grout. Since April 2012 it also contains the ISGCI graph database.
== Upstream Contact ==
- * For ISGCI : H.N. de Ridder (hnridder@graphclasses.org)
+ * For ISGCI:
+
+ H.N. de Ridder (hnridder@graphclasses.org)
+
+ * For Andries Brouwer's database:
+
+ The data is taken from from Andries E. Brouwer's website
+ (http://www.win.tue.nl/~aeb/). Anything related to the data should be
+ reported to him directly (aeb@cwi.nl)
+
+ The code used to parse the data and create the .json file is available at
+ https://github.com/nathanncohen/strongly_regular_graphs_database.
== Dependencies ==
@@ -20,6 +31,9 @@ N/A
== Changelog ==
+== graphs-20150724.p6 (Nathann Cohen, 2013-07-24 ==
+ * Added the database on strongly regular graphs
+
== graphs-20130920.p5 (Nathann Cohen, 2013-09-20) ==
* #14396: Update of isgci_sage.xml, added smallgraphs.txt
diff --git a/build/pkgs/graphs/checksums.ini b/build/pkgs/graphs/checksums.ini
index 8978e68..f4b488d 100644
--- a/build/pkgs/graphs/checksums.ini
+++ b/build/pkgs/graphs/checksums.ini
@@ -1,4 +1,4 @@
tarball=graphs-VERSION.tar.bz2
-sha1=f78fa61daf3baafa088921f5e578ea19f556f963
-md5=2621b6cfd61797ab0be179653d7bcf3e
-cksum=2747417664
+sha1=252564f5ef2b5ba020dc981523dda725046df72a
+md5=261a521fcdcab90a52992b166efc9293
+cksum=668305216
diff --git a/build/pkgs/graphs/package-version.txt b/build/pkgs/graphs/package-version.txt
index fbae6e7..a917e05 100644
--- a/build/pkgs/graphs/package-version.txt
+++ b/build/pkgs/graphs/package-version.txt
@@ -1 +1 @@
-20130920.p5
+20150724.p6
diff --git a/build/pkgs/ipython/checksums.ini b/build/pkgs/ipython/checksums.ini
index 7f91179..0f4ffb4 100644
--- a/build/pkgs/ipython/checksums.ini
+++ b/build/pkgs/ipython/checksums.ini
@@ -1,4 +1,4 @@
tarball=ipython-VERSION.tar.gz
-sha1=a77731d25519a0f76cd9aab2dcadaa555cbcc04c
-md5=41aa9b34f39484861e77c46ffb29b699
-cksum=3783479410
+sha1=b3556744deddf619dbb8c878ba33672133b12a6c
+md5=61c2d5665ff1bd65eceb19fa7f1b23c7
+cksum=4207832546
diff --git a/build/pkgs/ipython/package-version.txt b/build/pkgs/ipython/package-version.txt
index 944880f..e4604e3 100644
--- a/build/pkgs/ipython/package-version.txt
+++ b/build/pkgs/ipython/package-version.txt
@@ -1 +1 @@
-3.2.0
+3.2.1
diff --git a/build/pkgs/ncurses/patches/work_around_changed_output_of_GNU_cpp_5.x.patch b/build/pkgs/ncurses/patches/work_around_changed_output_of_GNU_cpp_5.x.patch
index af82739..619b37c 100644
--- a/build/pkgs/ncurses/patches/work_around_changed_output_of_GNU_cpp_5.x.patch
+++ b/build/pkgs/ncurses/patches/work_around_changed_output_of_GNU_cpp_5.x.patch
@@ -1,5 +1,5 @@
-Building ncurses with GCC 5.1 (or more precisely, with its 'cpp') fails with
-a syntax error, caused by earlier preprocessing.
+Building ncurses with GCC 5 (or more precisely, with its 'cpp') fails with a
+syntax error, caused by earlier preprocessing.
(I'm not entirely sure whether it's a GCC bug or rather caused by a new
feature which breaks further processing with 'awk' and 'sed'; I *think*
@@ -19,7 +19,7 @@ output of 'cpp' w.r.t. line directives [1]. Anyway, the patch fixes the issue.)
+# Work around "unexpected" output of GCC 5.1.0's cpp w.r.t. #line directives
+# by simply suppressing them:
+case `$1 -dumpversion 2>/dev/null` in
-+ 5.[01].*) # assume a "broken" one
++ 5.*.*) # assume a "broken" one
+ preprocessor="$1 -P -DNCURSES_INTERNALS -I../include"
+ ;;
+ *)
diff --git a/src/bin/sage-banner b/src/bin/sage-banner
index acc11a4..273e5a9 100644
--- a/src/bin/sage-banner
+++ b/src/bin/sage-banner
@@ -1,5 +1,5 @@
┌────────────────────────────────────────────────────────────────────┐
-│ SageMath Version 6.9.beta0, Release Date: 2015-07-29 │
+│ SageMath Version 6.9.beta1, Release Date: 2015-08-05 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
diff --git a/src/bin/sage-list-packages b/src/bin/sage-list-packages
index 88f0f55..e809e40 100755
--- a/src/bin/sage-list-packages
+++ b/src/bin/sage-list-packages
@@ -52,6 +52,8 @@ installed = dict(pkgname_split(pkgname)
SAGE_PKGS = os.path.join(SAGE_ROOT, "build", "pkgs")
local = {}
for p in os.listdir(SAGE_PKGS):
+ if not os.path.isdir(os.path.join(SAGE_PKGS, p)):
+ continue
with open(os.path.join(SAGE_PKGS, p, "package-version.txt")) as f:
version = f.read().strip()
with open(os.path.join(SAGE_PKGS, p, "type")) as f:
diff --git a/src/bin/sage-version.sh b/src/bin/sage-version.sh
index 493e910..9f78140 100644
--- a/src/bin/sage-version.sh
+++ b/src/bin/sage-version.sh
@@ -1,4 +1,4 @@
# Sage version information for shell scripts
# This file is auto-generated by the sage-update-version script, do not edit!
-SAGE_VERSION='6.9.beta0'
-SAGE_RELEASE_DATE='2015-07-29'
+SAGE_VERSION='6.9.beta1'
+SAGE_RELEASE_DATE='2015-08-05'
diff --git a/src/doc/common/builder.py b/src/doc/common/builder.py
index d7e70ae..851b7ee 100755
--- a/src/doc/common/builder.py
+++ b/src/doc/common/builder.py
@@ -1582,7 +1582,7 @@ if __name__ == '__main__':
except ValueError:
help_message_short(parser=parser, error=True)
sys.exit(1)
- delete_empty_directories(SAGE_DOC)
+ delete_empty_directories(SAGE_DOC, verbose=False)
# Set up module-wide logging.
logger = setup_logger(options.verbose, options.color)
@@ -1627,4 +1627,6 @@ if __name__ == '__main__':
except Exception:
print_build_error()
raise
-
+
+ # Clean up empty directories.
+ delete_empty_directories(SAGE_DOC, verbose=False)
diff --git a/src/doc/en/reference/graphs/index.rst b/src/doc/en/reference/graphs/index.rst
index 0473492..9802e75 100644
--- a/src/doc/en/reference/graphs/index.rst
+++ b/src/doc/en/reference/graphs/index.rst
@@ -90,6 +90,7 @@ Libraries of algorithms
sage/graphs/graph_editor
sage/graphs/graph_list
sage/graphs/hyperbolicity
+ sage/graphs/strongly_regular_db
sage/graphs/tutte_polynomial
sage/graphs/generic_graph_pyx
diff --git a/src/doc/en/reference/structure/index.rst b/src/doc/en/reference/structure/index.rst
index d00892d..a7b4120 100644
--- a/src/doc/en/reference/structure/index.rst
+++ b/src/doc/en/reference/structure/index.rst
@@ -80,6 +80,8 @@ Sets
sage/sets/non_negative_integers
sage/sets/primes
sage/sets/real_set
+ sage/structure/set_factories
+ sage/structure/set_factories_example
Use of Heuristic and Probabilistic Algorithms
---------------------------------------------
diff --git a/src/module_list.py b/src/module_list.py
index 38d3577..8958bbf 100644
--- a/src/module_list.py
+++ b/src/module_list.py
@@ -358,6 +358,9 @@ ext_modules = [
sources = ['sage/graphs/planarity.pyx'],
libraries=['planarity']),
+ Extension('sage.graphs.strongly_regular_db',
+ sources = ['sage/graphs/strongly_regular_db.pyx']),
+
Extension('sage.graphs.graph_decompositions.rankwidth',
sources = ['sage/graphs/graph_decompositions/rankwidth.pyx'],
libraries=['rw']),
diff --git a/src/sage/calculus/calculus.py b/src/sage/calculus/calculus.py
index 66654ae..c895e9c 100644
--- a/src/sage/calculus/calculus.py
+++ b/src/sage/calculus/calculus.py
@@ -889,16 +889,16 @@ def minpoly(ex, var='x', algorithm=None, bits=None, degree=None, epsilon=0):
sage: f = a.minpoly(); f
x^8 - 40*x^6 + 352*x^4 - 960*x^2 + 576
sage: f(a)
- ((((sqrt(5) + sqrt(3) + sqrt(2))^2 - 40)*(sqrt(5) + sqrt(3) + sqrt(2))^2 + 352)*(sqrt(5) + sqrt(3) + sqrt(2))^2 - 960)*(sqrt(5) + sqrt(3) + sqrt(2))^2 + 576
+ (sqrt(5) + sqrt(3) + sqrt(2))^8 - 40*(sqrt(5) + sqrt(3) + sqrt(2))^6 + 352*(sqrt(5) + sqrt(3) + sqrt(2))^4 - 960*(sqrt(5) + sqrt(3) + sqrt(2))^2 + 576
sage: f(a).expand()
0
::
- sage: a = sin(pi/5)
- sage: f(x) = a.minpoly(algorithm='numerical'); f
- x |--> 1/4*(4*x^2 - 5)*x^2 + 5/16
- sage: f(a).numerical_approx(100)
+ sage: a = sin(pi/7)
+ sage: f = a.minpoly(algorithm='numerical'); f
+ x^6 - 7/4*x^4 + 7/8*x^2 - 7/64
+ sage: f(a).horner(a).numerical_approx(100)
0.00000000000000000000000000000
The degree must be high enough (default tops out at 24).
diff --git a/src/sage/calculus/wester.py b/src/sage/calculus/wester.py
index 833fcbe..b251993 100644
--- a/src/sage/calculus/wester.py
+++ b/src/sage/calculus/wester.py
@@ -617,9 +617,8 @@ explicit calls to Maxima or other systems.
sage: # (YES) Convert the above to Horner's form.
sage: # Verify(Horner(p, x), ((((a[5]*x+a[4])*x
sage: # +a[3])*x+a[2])*x+a[1])*x);
- sage: # We use the trick of evaluating the algebraic poly at a symbolic variable:
sage: restore('x')
- sage: p(x)
+ sage: SR(p).horner(x)
((((a4*x + a3)*x + a2)*x + a1)*x + a0)*x
::
diff --git a/src/sage/combinat/designs/bibd.py b/src/sage/combinat/designs/bibd.py
index f83e07e..ebfc486 100644
--- a/src/sage/combinat/designs/bibd.py
+++ b/src/sage/combinat/designs/bibd.py
@@ -113,10 +113,10 @@ def balanced_incomplete_block_design(v, k, existence=False, use_LJCR=False):
[[0, 1, 2, 3, 4, 65], [0, 5, 24, 25, 39, 57], [0, 6, 27, 38, 44, 55], ...
sage: designs.balanced_incomplete_block_design(66, 6, use_LJCR=True) # optional - internet
Incidence structure with 66 points and 143 blocks
- sage: designs.balanced_incomplete_block_design(141, 6)
+ sage: designs.balanced_incomplete_block_design(216, 6)
Traceback (most recent call last):
...
- NotImplementedError: I don't know how to build a (141,6,1)-BIBD!
+ NotImplementedError: I don't know how to build a (216,6,1)-BIBD!
TESTS::
@@ -146,10 +146,10 @@ def balanced_incomplete_block_design(v, k, existence=False, use_LJCR=False):
For `k > 5` there are currently very few constructions::
- sage: [v for v in xrange(150) if designs.balanced_incomplete_block_design(v,6,existence=True) is True]
- [1, 6, 31, 91, 121]
- sage: [v for v in xrange(150) if designs.balanced_incomplete_block_design(v,6,existence=True) is Unknown]
- [51, 61, 66, 76, 81, 96, 106, 111, 126, 136, 141]
+ sage: [v for v in xrange(300) if designs.balanced_incomplete_block_design(v,6,existence=True) is True]
+ [1, 6, 31, 66, 76, 91, 96, 106, 111, 121, 126, 136, 141, 151, 156, 171, 181, 186, 196, 201, 211, 241, 271]
+ sage: [v for v in xrange(300) if designs.balanced_incomplete_block_design(v,6,existence=True) is Unknown]
+ [51, 61, 81, 166, 216, 226, 231, 246, 256, 261, 276, 286, 291]
Here are some constructions with `k \geq 7` and `v` a prime power::
@@ -1231,3 +1231,115 @@ class BalancedIncompleteBlockDesign(PairwiseBalancedDesign):
k = len(self._blocks[0]) if self._blocks else 0
l = self._lambd
return "({},{},{})-Balanced Incomplete Block Design".format(v,k,l)
+
+ def arc(self, s=2, solver=None, verbose=0):
+ r"""
+ Return the ``s``-arc with maximum cardinality.
+
+ A `s`-arc is a subset of points in a BIBD that intersects each block on
+ at most `s` points. It is one possible generalization of independent set
+ for graphs.
+
+ A simple counting shows that the cardinality of a `s`-arc is at most
+ `(s-1) * r + 1` where `r` is the number of blocks incident to any point.
+ A `s`-arc in a BIBD with cardinality `(s-1) * r + 1` is called maximal
+ and is characterized by the following property: it is not empty and each
+ block either contains `0` or `s` points of this arc. Equivalently, the
+ trace of the BIBD on these points is again a BIBD (with block size `s`).
+
+ For more informations, see :wikipedia:`Arc_(projective_geometry)`.
+
+ INPUT:
+
+ - ``s`` - (default to ``2``) the maximum number of points from the arc
+ in each block
+
+ - ``solver`` -- (default: ``None``) Specify a Linear Program (LP)
+ solver to be used. If set to ``None``, the default one is used. For
+ more information on LP solvers and which default solver is used, see
+ the method
+ :meth:`solve <sage.numerical.mip.MixedIntegerLinearProgram.solve>`
+ of the class
+ :class:`MixedIntegerLinearProgram <sage.numerical.mip.MixedIntegerLinearProgram>`.
+
+ - ``verbose`` -- integer (default: ``0``). Sets the level of
+ verbosity. Set to 0 by default, which means quiet.
+
+ EXAMPLES::
+
+ sage: B = designs.balanced_incomplete_block_design(21, 5)
+ sage: a2 = B.arc()
+ sage: a2 # random
+ [5, 9, 10, 12, 15, 20]
+ sage: len(a2)
+ 6
+ sage: a4 = B.arc(4)
+ sage: a4 # random
+ [0, 1, 2, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20]
+ sage: len(a4)
+ 16
+
+ The `2`-arc and `4`-arc above are maximal. One can check that they
+ intersect the blocks in either 0 or `s` points. Or equivalently that the
+ traces are again BIBD::
+
+ sage: r = (21-1)/(5-1)
+ sage: 1 + r*1
+ 6
+ sage: 1 + r*3
+ 16
+
+ sage: B.trace(a2).is_t_design(2, return_parameters=True)
+ (True, (2, 6, 2, 1))
+ sage: B.trace(a4).is_t_design(2, return_parameters=True)
+ (True, (2, 16, 4, 1))
+
+ Some other examples which are not maximal::
+
+ sage: B = designs.balanced_incomplete_block_design(25, 4)
+ sage: a2 = B.arc(2)
+ sage: r = (25-1)/(4-1)
+ sage: print len(a2), 1 + r
+ 8 9
+ sage: sa2 = set(a2)
+ sage: set(len(sa2.intersection(b)) for b in B.blocks())
+ {0, 1, 2}
+ sage: B.trace(a2).is_t_design(2)
+ False
+
+ sage: a3 = B.arc(3)
+ sage: print len(a3), 1 + 2*r
+ 15 17
+ sage: sa3 = set(a3)
+ sage: set(len(sa3.intersection(b)) for b in B.blocks())
+ {0, 1, 2, 3}
+ sage: B.trace(a3).is_t_design(3)
+ False
+
+ TESTS:
+
+ Test consistency with relabeling::
+
+ sage: b = designs.balanced_incomplete_block_design(7,3)
+ sage: b.relabel(list("abcdefg"))
+ sage: set(b.arc()).issubset(b.ground_set())
+ True
+ """
+ s = int(s)
+
+ # trivial cases
+ if s <= 0:
+ return []
+ elif s >= max(self.block_sizes()):
+ return self._points[:]
+
+ # linear program
+ from sage.numerical.mip import MixedIntegerLinearProgram
+
+ p = MixedIntegerLinearProgram(solver=solver)
+ b = p.new_variable(binary=True)
+ p.set_objective(p.sum(b[i] for i in range(len(self._points))))
+ for i in self._blocks:
+ p.add_constraint(p.sum(b[k] for k in i) <= s)
+ p.solve(log=verbose)
+ return [self._points[i] for (i,j) in p.get_values(b).items() if j == 1]
diff --git a/src/sage/combinat/designs/database.py b/src/sage/combinat/designs/database.py
index bd268a5..68a8378 100644
--- a/src/sage/combinat/designs/database.py
+++ b/src/sage/combinat/designs/database.py
@@ -21,6 +21,9 @@ This module implements:
- :func:`RBIBD(120,8,1) <RBIBD_120_8_1>`
+- `(v,k,\lambda)`-BIBD:
+{LIST_OF_BIBD}
+
- `(v,k,\lambda)`-difference families:
{LIST_OF_DF}
@@ -2788,6 +2791,10 @@ DF = {
[0,11,31,35],[0,12,26,34,],[0,5,30,33]]},
( 91, 6, 1):
{(91,): [[0,1,3,7,25,38], [0,16,21,36,48,62], [0,30,40,63,74,82]]},
+
+( 91, 7, 1): # from the La Jolla covering repository, attributed to Jan de Heer and Steve Muir
+ {(91,): [[8, 9, 14, 25, 58, 81, 85], [5, 33, 35, 42, 45, 67, 88], [4, 17, 30, 43, 56, 69, 82]]},
+
(121, 5, 1):
{(121,): [[0,14,26,51,60],[0,15,31,55,59],[0,10,23,52,58],
[0,3,36,56,57],[0,7,18,45,50],[0,8,30,47,49]]},
@@ -4114,6 +4121,299 @@ def RBIBD_120_8_1():
equiv = [[M.nonzero_positions_in_row(x) for x in S] for S in equiv]
return [B for S in equiv for B in S]
+def BIBD_66_6_1():
+ r"""
+ Return a (66,6,1)-BIBD.
+
+ This BIBD was obtained from La Jolla covering repository
+ (https://www.ccrwest.org/cover.html) where it is attributed to Colin Barker.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_66_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(66, BIBD_66_6_1())
+ (66,6,1)-Balanced Incomplete Block Design
+ """
+ BIBD = [frozenset([(x+i*5)%65 if x<65 else x for x in b])
+ for i in range(65)
+ for b in
+ [6, 38, 42, 46, 53, 62], [9, 11, 21, 49, 56, 60], [18, 31, 37, 44, 52, 60],
+ [0, 12, 29, 46, 51, 63], [0, 6, 21, 30, 43, 48], [4, 17, 22, 36, 47, 59],
+ [0, 1, 2, 3, 4, 65], [23, 39, 44, 53, 59, 63], [12, 22, 28, 48, 55, 60],
+ [19, 22, 25, 40, 49, 50], [4, 30, 37, 50, 58, 61]]
+ return map(list,frozenset(BIBD))
+
+def BIBD_76_6_1():
+ r"""
+ Return a (76,6,1)-BIBD.
+
+ This BIBD was obtained from La Jolla covering repository
+ (https://www.ccrwest.org/cover.html) where it is attributed to Colin Barker.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_76_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(76, BIBD_76_6_1())
+ (76,6,1)-Balanced Incomplete Block Design
+ """
+ BIBD = [frozenset([(x+i*4)%76 if x<76 else x for x in b])
+ for i in range(76)
+ for b in
+ [[3, 5, 21, 33, 72, 73], [4, 37, 57, 58, 64, 75], [7, 14, 44, 47, 59, 63],
+ [10, 20, 61, 63, 71, 72], [13, 26, 30, 39, 45, 67], [11, 21, 25, 30, 55, 58],
+ [2, 5, 34, 52, 54, 70], [6, 8, 29, 48, 70, 71], [10, 15, 36, 41, 44, 56],
+ [0, 6, 13, 27, 44, 72]]]
+ return map(list,frozenset(BIBD))
+
+def BIBD_96_6_1():
+ r"""
+ Return a (96,6,1)-BIBD.
+
+ This BIBD was obtained from La Jolla covering repository
+ (https://www.ccrwest.org/cover.html) where it is attributed to Colin Barker.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_96_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(96, BIBD_96_6_1())
+ (96,6,1)-Balanced Incomplete Block Design
+ """
+ BIBD = [frozenset([(x+i*2)%96 if x<96 else x for x in b])
+ for i in range(96)
+ for b in
+ [[3, 13, 32, 47, 68, 87], [9, 36, 70, 75, 81, 88], [22, 52, 72, 76, 78, 79],
+ [15, 23, 41, 43, 46, 58], [7, 8, 21, 57, 66, 94], [8, 22, 30, 51, 55, 93],
+ [15, 31, 47, 63, 79, 95], [2, 18, 34, 50, 66, 82]]]
+ return map(list,frozenset(BIBD))
+
+def BIBD_106_6_1():
+ r"""
+ Return a (106,6,1)-BIBD.
+
+ This constructions appears in II.3.32 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_106_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(106, BIBD_106_6_1())
+ (106,6,1)-Balanced Incomplete Block Design
+ """
+ bibd = [((0,0), ( 1,0), ( 3,0), (11,0), (38,0), ( 0,1)),
+ ((0,0), (13,0), (30,0), (23,1), (35,1), (51,1)),
+ ((0,0), ( 5,0), (19,0), (25,0), (36,1), (39,1)),
+ ((0,0), ( 4,0), (28,1), (30,1), (37,1), (47,1)),
+ ((0,0), ( 7,0), (29,0), ( 8,1), (16,1), (48,1)),
+ ((0,0), ( 2,1), ( 7,1), (25,1), (29,1), (49,1)),
+ ((0,0), ( 9,0), (21,0), (12,1), (13,1), (27,1))]
+
+ return [[((x+i)%53+y*53) for x,y in B] for i in range(53) for B in bibd]
+
+def BIBD_111_6_1():
+ r"""
+ Return a (111,6,1)-BIBD.
+
+ This constructions appears in II.3.32 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_111_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(111, BIBD_111_6_1())
+ (111,6,1)-Balanced Incomplete Block Design
+ """
+ from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
+ from incidence_structures import IncidenceStructure
+ bibd = [(( 0,0), ( 1,0), ( 3,0), ( 7,0), (17,0), ( 0,1)),
+ (( 0,0), ( 5,0), (19,1), (28,1), (10,2), (30,2)),
+ (( 5,0), (33,0), (13,1), (34,1), (19,2), ( 7,2)),
+ (( 9,0), (27,0), (16,1), (11,1), (12,2), (36,2)),
+ ((10,0), (23,0), (26,1), ( 8,1), ( 1,2), ( 6,2)),
+ ((13,0), (24,0), (19,1), (18,1), ( 5,2), (32,2)),
+ ((26,0), (34,0), ( 1,1), ( 7,1), (10,2), (33,2))]
+ gens = lambda B: [frozenset(((x*10)%37,(y+1)%3) for x,y in B),
+ frozenset(((x+1) %37, y) for x,y in B)]
+ bibd = RecursivelyEnumeratedSet(map(frozenset,bibd), successors=gens)
+ return IncidenceStructure(bibd)._blocks
+
+def BIBD_126_6_1():
+ r"""
+ Return a (126,6,1)-BIBD.
+
+ This constructions appears in VI.16.92 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_126_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(126, BIBD_126_6_1())
+ (126,6,1)-Balanced Incomplete Block Design
+ """
+ from itertools import product
+ bibd = [[((x+xx)%5, (y+yy)%5, (z+zz)%5) for x,y,z in B]
+ for xx,yy,zz in product(range(5),repeat=3)
+ for B in
+ [[(0,0,1),(0,0,4),(1,2,2),(1,3,3),(4,2,1),(4,3,4)],
+ [(0,0,2),(0,0,3),(1,4,4),(1,1,1),(4,4,2),(4,1,3)],
+ [(0,4,3),(0,1,2),(2,2,0),(2,3,0),(3,3,2),(3,2,3)],
+ [(0,3,1),(0,2,4),(2,4,0),(2,1,0),(3,1,4),(3,4,1)]]]
+
+ bibd.extend([[(125,0,0), (0,x,y),(1,x,y),(2,x,y),(3,x,y),(4,x,y)]
+ for x,y in product(range(5),repeat=2)])
+ return [[x+y*5+z*25 for x,y,z in B]
+ for B in bibd]
+
+def BIBD_136_6_1():
+ r"""
+ Return a (136,6,1)-BIBD.
+
+ This constructions appears in II.3.32 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_136_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(136, BIBD_136_6_1())
+ (136,6,1)-Balanced Incomplete Block Design
+ """
+ from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
+ from incidence_structures import IncidenceStructure
+ inf=(None,None)
+ bibd = [((0,0), ( 3,0), (15,0), (35,0), ( 6,2), (10,2)),
+ ((0,0), (22,0), (11,1), (30,1), ( 1,2), (18,2)),
+ ((0,0), ( 5,0), (18,1), (41,1), (13,2), (42,2)),
+ ((0,0), (11,0), (17,0), ( 4,2), ( 5,2), (28,2)),
+ ((0,0), ( 1,0), ( 0,1), (16,1), ( 0,2), (31,2)),
+ ( inf ,( 0,0), ( 9,0), (18,0), (27,0), (36,0))]
+ gens = lambda B: [frozenset(((x*16)%45,(y+1)%3) if (x,y)!=inf else inf for x,y in B),
+ frozenset(((x+1) %45,y) if (x,y)!=inf else inf for x,y in B)]
+ bibd = RecursivelyEnumeratedSet(map(frozenset,bibd), successors=gens)
+ return IncidenceStructure(bibd)._blocks
+
+
+def BIBD_141_6_1():
+ r"""
+ Return a (141,6,1)-BIBD.
+
+ This constructions appears in II.3.32 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_141_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(141, BIBD_141_6_1())
+ (141,6,1)-Balanced Incomplete Block Design
+ """
+ from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
+ from incidence_structures import IncidenceStructure
+ a = 'a'
+ inf = (None,None)
+ bibd = [((0,0), (16,0), (24,0), (24,1), (15,2), (25,2)),
+ ((0,0), ( 3,0), (26,0), (13,1), (33,1), (34,a)),
+ ((0,0), (13,0), (18,0), (15,1), ( 7,2), ( 0,a)),
+ ((0,0), ( 2,0), (14,1), (23,1), (26,a), (32,a)),
+ ((0,0), ( 4,0), (29,1), ( 6,2), ( 9,a), (20,a)),
+ ((0,0), ( 1,0), (12,2), ( 2,a), ( 4,a), (19,a)),
+ ( inf ,( 0,0), ( 7,0), (14,0), (21,0), (28,0)),
+ ( inf ,( 0,a), ( 7,a), (14,a), (21,a), (28,a))]
+
+ gens = lambda B: [frozenset(((x*16)%35,(y+1)%3 if y!=a else a) if (x,y)!=inf else inf for x,y in B),
+ frozenset(((x+1) %35, y ) if (x,y)!=inf else inf for x,y in B)]
+ bibd = RecursivelyEnumeratedSet(map(frozenset,bibd), successors=gens)
+ return IncidenceStructure(bibd)._blocks
+
+def BIBD_171_6_1():
+ r"""
+ Return a (171,6,1)-BIBD.
+
+ This constructions appears in II.3.32 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_171_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(171, BIBD_171_6_1())
+ (171,6,1)-Balanced Incomplete Block Design
+ """
+ from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
+ from incidence_structures import IncidenceStructure
+ bibd = [(( 0,0), (19,0), (39,0), (41,0), (14,1), (38,2)),
+ (( 0,0), (21,0), (44,0), (48,0), (26,1), (11,2)),
+ (( 0,0), ( 1,0), (43,0), ( 8,2), (15,2), (44,2)),
+ (( 0,0), ( 3,0), (31,0), (23,1), (43,1), (36,2)),
+ (( 0,0), (40,0), (50,0), (11,1), (25,2), (34,2)),
+ (( 0,0), (12,0), ( 0,1), (27,1), ( 0,2), (18,2)),
+ ((37,0), (42,0), (31,1), ( 9,1), (46,2), ( 6,2))]
+
+ gens = lambda B: [frozenset(((x*7) %57,(y+1)%3) for x,y in B),
+ frozenset(((x+1) %57, y) for x,y in B)]
+ bibd = RecursivelyEnumeratedSet(map(frozenset,bibd), successors=gens)
+ return IncidenceStructure(bibd)._blocks
+
+def BIBD_196_6_1():
+ r"""
+ Return a (196,6,1)-BIBD.
+
+ This constructions appears in II.3.32 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_196_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(196, BIBD_196_6_1())
+ (196,6,1)-Balanced Incomplete Block Design
+ """
+ from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
+ from incidence_structures import IncidenceStructure
+ a = 'a'
+ bibd = [((0,0), ( 2,0), (12,0), (45,0), ( 3,1), (11,a)),
+ ((0,0), ( 3,0), ( 8,0), ( 5,1), (17,1), (39,a)),
+ ((0,0), ( 9,0), (36,0), (24,1), (44,1), (37,a)),
+ ((0,0), (15,0), (34,1), (41,1), (47,2), (18,a)),
+ ((0,0), ( 7,0), (31,0), (13,1), (35,2), (41,a)),
+ ((0,0), (14,0), (32,1), (10,2), (22,a), (44,a)),
+ ((0,0), (23,0), (21,1), (39,1), (19,a), (25,a)),
+ ((0,0), (33,1), ( 0,a), ( 5,a), (29,a), (47,a)),
+ ((0,0), ( 1,0), ( 0,1), (30,1), ( 0,2), (18,2)),
+ ((8,0), (19,0), (44,1), (31,1), (46,2), (48,2))]
+
+ gens = lambda B: [frozenset(((x*30)%49,(y+1)%3 if y!=a else a) for x,y in B),
+ frozenset(((x+1) %49, y) for x,y in B)]
+ bibd = RecursivelyEnumeratedSet(map(frozenset,bibd), successors=gens)
+ return IncidenceStructure(bibd)._blocks
+
+def BIBD_201_6_1():
+ r"""
+ Return a (201,6,1)-BIBD.
+
+ This constructions appears in II.3.32 from [DesignHandbook]_.
+
+ EXAMPLE::
+
+ sage: from sage.combinat.designs.database import BIBD_201_6_1
+ sage: from sage.combinat.designs.bibd import BalancedIncompleteBlockDesign
+ sage: BalancedIncompleteBlockDesign(201, BIBD_201_6_1())
+ (201,6,1)-Balanced Incomplete Block Design
+ """
+ from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
+ from incidence_structures import IncidenceStructure
+ bibd = [((0,0), ( 1,0), ( 4,2), ( 9,2), (34,2), (62,2)),
+ ((0,1), ( 2,1), (15,1), ( 8,2), (27,2), (49,2)),
+ ((0,0), ( 3,0), (22,0), (54,1), (13,2), (40,2)),
+ ((0,0), (36,0), (40,0), (31,1), (34,1), ( 5,2)),
+ ((0,0), (50,0), (55,0), ( 6,1), (24,1), (26,2)),
+ ((0,0), ( 2,0), ( 3,1), (14,1), (35,1), (25,2)),
+ ((3,1), (20,1), (44,1), (36,2), (39,2), (59,2)),
+ ((0,0), ( 0,1), (30,1), (38,1), (66,1), ( 0,2))]
+
+ gens = lambda B: [frozenset(((x*29)%67,y) for x,y in B),
+ frozenset(((x+1) %67,y) for x,y in B)]
+ bibd = RecursivelyEnumeratedSet(map(frozenset,bibd), successors=gens)
+ return IncidenceStructure(bibd)._blocks
+
# Index of the BIBD constructions
#
# Associates to triple (v,k,lambda) a function that return a
@@ -4122,9 +4422,26 @@ def RBIBD_120_8_1():
# This dictionary is used by designs.BalancedIncompleteBlockDesign
BIBD_constructions = {
+ ( 66,6,1): BIBD_66_6_1,
+ ( 76,6,1): BIBD_76_6_1,
+ ( 96,6,1): BIBD_96_6_1,
(120,8,1): RBIBD_120_8_1,
+ (106,6,1): BIBD_106_6_1,
+ (111,6,1): BIBD_111_6_1,
+ (126,6,1): BIBD_126_6_1,
+ (136,6,1): BIBD_136_6_1,
+ (141,6,1): BIBD_141_6_1,
+ (171,6,1): BIBD_171_6_1,
+ (196,6,1): BIBD_196_6_1,
+ (201,6,1): BIBD_201_6_1,
}
+# Create the list of DF for the documentation
+_all_l = sorted(set(l for v,k,l in BIBD_constructions.keys()))
+LIST_OF_BIBD = "\n".join(" - `\lambda={}`:\n ".format(l) +
+ ", ".join("`({},{},{})`".format(v,k,l) for v,k,_ in sorted(BIBD_constructions) if _ == l)
+ for l in _all_l)
+
# Evenly Distributed Sets (EDS)
#
# For the definition see the documentation of the class
@@ -4417,9 +4734,10 @@ __doc__ = __doc__.format(
LIST_OF_OA_CONSTRUCTIONS = LIST_OF_OA_CONSTRUCTIONS,
LIST_OF_MOLS_CONSTRUCTIONS = LIST_OF_MOLS_CONSTRUCTIONS,
LIST_OF_VMT_VECTORS = LIST_OF_VMT_VECTORS,
+ LIST_OF_BIBD = LIST_OF_BIBD,
LIST_OF_DF = LIST_OF_DF,
LIST_OF_DM = LIST_OF_DM,
LIST_OF_QDM = LIST_OF_QDM,
LIST_OF_EDS = LIST_OF_EDS)
-del LIST_OF_OA_CONSTRUCTIONS, LIST_OF_MOLS_CONSTRUCTIONS, LIST_OF_VMT_VECTORS,LIST_OF_DF, LIST_OF_DM, LIST_OF_QDM, LIST_OF_EDS
+del LIST_OF_OA_CONSTRUCTIONS, LIST_OF_MOLS_CONSTRUCTIONS, LIST_OF_VMT_VECTORS,LIST_OF_DF, LIST_OF_DM, LIST_OF_QDM, LIST_OF_EDS, LIST_OF_BIBD
del PolynomialRing, ZZ, a,
diff --git a/src/sage/combinat/designs/difference_family.py b/src/sage/combinat/designs/difference_family.py
index 9e79cd0..7048b9e 100644
--- a/src/sage/combinat/designs/difference_family.py
+++ b/src/sage/combinat/designs/difference_family.py
@@ -1139,7 +1139,7 @@ def difference_family(v, k, l=1, existence=False, explain_construction=False, ch
83: (2,1)
85: (4,1), (7,2), (7,3), (8,2)
89: (2,1), (4,3), (8,7)
- 91: (6,1)
+ 91: (6,1), (7,1)
97: (2,1), (3,1), (3,2), (4,1), (4,3), (6,5), (8,7), (9,3)
TESTS:
diff --git a/src/sage/combinat/designs/incidence_structures.py b/src/sage/combinat/designs/incidence_structures.py
index 6d670a6..60bd6a3 100644
--- a/src/sage/combinat/designs/incidence_structures.py
+++ b/src/sage/combinat/designs/incidence_structures.py
@@ -1172,7 +1172,6 @@ class IncidenceStructure(object):
- ``verbose`` -- integer (default: ``0``). Sets the level of
verbosity. Set to 0 by default, which means quiet.
- Only useful when ``algorithm == "LP"``.
EXAMPLE::
diff --git a/src/sage/combinat/finite_state_machine.py b/src/sage/combinat/finite_state_machine.py
index 7888363..902a788 100644
--- a/src/sage/combinat/finite_state_machine.py
+++ b/src/sage/combinat/finite_state_machine.py
@@ -100,7 +100,7 @@ Properties
:meth:`~FiniteStateMachine.is_monochromatic` | Checks whether the colors of all states are equal
:meth:`~FiniteStateMachine.asymptotic_moments` | Main terms of expectation and variance of sums of labels
:meth:`~FiniteStateMachine.epsilon_successors` | Epsilon successors of a state
-
+ :meth:`Automaton.shannon_parry_markov_chain` | Compute Markov chain with Parry measure
Operations
^^^^^^^^^^
@@ -110,7 +110,7 @@ Operations
:widths: 30, 70
:delim: |
- :meth:`~FiniteStateMachine.disjoint_union` | Disjoint union (not implemented)
+ :meth:`~FiniteStateMachine.disjoint_union` | Disjoint union
:meth:`~FiniteStateMachine.concatenation` | Concatenation (not implemented)
:meth:`~FiniteStateMachine.Kleene_closure` | Kleene closure (not implemented)
:meth:`Automaton.intersection` | Intersection of automata
@@ -3412,7 +3412,7 @@ class FiniteStateMachine(SageObject):
def __or__(self, other):
"""
- Returns the disjoint union of the finite state machines self and other.
+ Return the disjoint union of this and another finite state machine.
INPUT:
@@ -3422,15 +3422,25 @@ class FiniteStateMachine(SageObject):
A new finite state machine.
+ .. SEEALSO::
+
+ :meth:`.disjoint_union`, :meth:`.__and__`,
+ :meth:`Automaton.intersection`,
+ :meth:`Transducer.intersection`
+
TESTS::
sage: FiniteStateMachine() | FiniteStateMachine([('A', 'B')])
+ Finite state machine with 2 states
+ sage: FiniteStateMachine() | 42
Traceback (most recent call last):
...
- NotImplementedError
+ TypeError: Can only add finite state machine
"""
if is_FiniteStateMachine(other):
return self.disjoint_union(other)
+ else:
+ raise TypeError("Can only add finite state machine")
__add__ = __or__
@@ -5475,7 +5485,7 @@ class FiniteStateMachine(SageObject):
def is_deterministic(self):
"""
- Returns whether the finite finite state machine is deterministic.
+ Return whether the finite finite state machine is deterministic.
INPUT:
@@ -5489,9 +5499,10 @@ class FiniteStateMachine(SageObject):
each transition has input label of length one and for each
pair `(q,a)` where `q` is a state and `a` is an element of the
input alphabet, there is at most one transition from `q` with
- input label `a`.
+ input label `a`. Furthermore, the finite state may not have
+ more than one initial state.
- TESTS::
+ EXAMPLES::
sage: fsm = FiniteStateMachine()
sage: fsm.add_transition(('A', 'B', 0, []))
@@ -5506,7 +5517,18 @@ class FiniteStateMachine(SageObject):
Transition from 'A' to 'B': 0,1|-
sage: fsm.is_deterministic()
False
+
+ Check that :trac:`18556` is fixed::
+
+ sage: Automaton().is_deterministic()
+ True
+ sage: Automaton(initial_states=[0]).is_deterministic()
+ True
+ sage: Automaton(initial_states=[0, 1]).is_deterministic()
+ False
"""
+ if len(self.initial_states())>1:
+ return False
for state in self.iter_states():
for transition in state.transitions:
if len(transition.word_in) != 1:
@@ -6645,16 +6667,172 @@ class FiniteStateMachine(SageObject):
def disjoint_union(self, other):
"""
- TESTS::
+ Return the disjoint union of this and another finite state
+ machine.
- sage: F = FiniteStateMachine([('A', 'A')])
- sage: FiniteStateMachine().disjoint_union(F)
+ INPUT:
+
+ - ``other`` -- a :class:`FiniteStateMachine`.
+
+ OUTPUT:
+
+ A finite state machine of the same type as this finite state
+ machine.
+
+ In general, the disjoint union of two finite state machines is
+ non-deterministic. In the case of a automata, the language
+ accepted by the disjoint union is the union of the languages
+ accepted by the constituent automata. In the case of
+ transducer, for each successful path in one of the constituent
+ transducers, there will be one successful path with the same input
+ and output labels in the disjoint union.
+
+ The labels of the states of the disjoint union are pairs ``(i,
+ s)``: for each state ``s`` of this finite state machine, there
+ is a state ``(0, s)`` in the disjoint union; for each state
+ ``s`` of the other finite state machine, there is a state ``(1,
+ s)`` in the disjoint union.
+
+ The input alphabet is the union of the input alphabets (if
+ possible) and ``None`` otherwise. In the latter case, try
+ calling :meth:`.determine_alphabets`.
+
+ The disjoint union can also be written as ``A + B`` or ``A | B``.
+
+ EXAMPLES::
+
+ sage: A = Automaton([(0, 1, 0, 0), (1, 0, 1, 0)],
+ ....: initial_states=[0],
+ ....: final_states=[0])
+ sage: A([0, 1, 0, 1])
+ True
+ sage: B = Automaton([(0, 1, 0, 0), (1, 2, 0, 0), (2, 0, 1, 0)],
+ ....: initial_states=[0],
+ ....: final_states=[0])
+ sage: B([0, 0, 1])
+ True
+ sage: C = A.disjoint_union(B)
+ sage: C
+ Automaton with 5 states
+ sage: C.transitions()
+ [Transition from (0, 0) to (0, 1): 0|0,
+ Transition from (0, 1) to (0, 0): 1|0,
+ Transition from (1, 0) to (1, 1): 0|0,
+ Transition from (1, 1) to (1, 2): 0|0,
+ Transition from (1, 2) to (1, 0): 1|0]
+ sage: C([0, 0, 1])
+ True
+ sage: C([0, 1, 0, 1])
+ True
+ sage: C([1])
+ False
+ sage: C.initial_states()
+ [(0, 0), (1, 0)]
+
+ Instead of ``.disjoint_union``, alternative notations are
+ available::
+
+ sage: C1 = A + B
+ sage: C1 == C
+ True
+ sage: C2 = A | B
+ sage: C2 == C
+ True
+
+ In general, the disjoint union is not deterministic::
+
+ sage: C.is_deterministic()
+ False
+ sage: D = C.determinisation().minimization().relabeled()
+ sage: D.initial_states()
+ [1]
+ sage: D.transitions()
+ [Transition from 0 to 0: 0|-,
+ Transition from 0 to 0: 1|-,
+ Transition from 1 to 7: 0|-,
+ Transition from 1 to 0: 1|-,
+ Transition from 2 to 6: 0|-,
+ Transition from 2 to 0: 1|-,
+ Transition from 3 to 5: 0|-,
+ Transition from 3 to 0: 1|-,
+ Transition from 4 to 0: 0|-,
+ Transition from 4 to 2: 1|-,
+ Transition from 5 to 0: 0|-,
+ Transition from 5 to 3: 1|-,
+ Transition from 6 to 4: 0|-,
+ Transition from 6 to 0: 1|-,
+ Transition from 7 to 4: 0|-,
+ Transition from 7 to 3: 1|-]
+
+ Disjoint union of transducers::
+
+ sage: T1 = Transducer([(0, 0, 0, 1)],
+ ....: initial_states=[0],
+ ....: final_states=[0])
+ sage: T2 = Transducer([(0, 0, 0, 2)],
+ ....: initial_states=[0],
+ ....: final_states=[0])
+ sage: T1([0])
+ [1]
+ sage: T2([0])
+ [2]
+ sage: T = T1.disjoint_union(T2)
+ sage: T([0])
Traceback (most recent call last):
...
- NotImplementedError
+ ValueError: Found more than one accepting path.
+ sage: T.process([0])
+ [(True, (1, 0), [2]), (True, (0, 0), [1])]
+
+ Handling of the input alphabet (see :trac:`18989`)::
+
+ sage: A = Automaton([(0, 0, 0)])
+ sage: B = Automaton([(0, 0, 1)], input_alphabet=[1, 2])
+ sage: C = Automaton([(0, 0, 2)], determine_alphabets=False)
+ sage: D = Automaton([(0, 0, [[0, 0]])], input_alphabet=[[0, 0]])
+ sage: A.input_alphabet
+ [0]
+ sage: B.input_alphabet
+ [1, 2]
+ sage: C.input_alphabet is None
+ True
+ sage: D.input_alphabet
+ [[0, 0]]
+ sage: (A + B).input_alphabet
+ [0, 1, 2]
+ sage: (A + C).input_alphabet is None
+ True
+ sage: (A + D).input_alphabet is None
+ True
+
+ .. SEEALSO::
+
+ :meth:`Automaton.intersection`,
+ :meth:`Transducer.intersection`, :meth:`.determine_alphabets`.
"""
- raise NotImplementedError
+ result = self.empty_copy()
+ for s in self.iter_states():
+ result.add_state(s.relabeled((0, s)))
+ for s in other.iter_states():
+ result.add_state(s.relabeled((1, s)))
+ for t in self.iter_transitions():
+ result.add_transition((0, t.from_state),
+ (0, t.to_state),
+ t.word_in,
+ t.word_out)
+ for t in other.iter_transitions():
+ result.add_transition((1, t.from_state),
+ (1, t.to_state),
+ t.word_in,
+ t.word_out)
+ try:
+ result.input_alphabet = list(set(self.input_alphabet)
+ | set(other.input_alphabet))
+ except TypeError:
+ # e.g. None or unhashable letters
+ result.input_alphabet = None
+ return result
def concatenation(self, other):
"""
@@ -10016,6 +10194,140 @@ class Automaton(FiniteStateMachine):
return accept_input
+ def shannon_parry_markov_chain(self):
+ """
+ Compute a time homogeneous Markov chain such that all words of a
+ given length recognized by the original automaton occur as the
+ output with the same weight; the transition probabilities
+ correspond to the Parry measure.
+
+ OUTPUT:
+
+ A Markov chain. Its input labels are the transition probabilities, the
+ output labels the labels of the original automaton. In order to obtain
+ equal weight for all words of the same length, an "exit weight" is
+ needed. It is stored in the attribute ``color`` of the states of the
+ Markov chain. The weights of the words of the same length sum up to one
+ up to an exponentially small error.
+
+ The stationary distribution of this Markov chain is
+ saved as the initial probabilities of the states.
+
+ The transition probabilities correspond to the Parry measure
+ (see [S1948]_ and [P1964]_).
+
+ The automaton is assumed to be deterministic, irreducible and
+ aperiodic. All states must be final.
+
+ EXAMPLES::
+
+ sage: NAF = Automaton([(0, 0, 0), (0, 1, 1), (0, 1, -1),
+ ....: (1, 0, 0)], initial_states=[0],
+ ....: final_states=[0, 1])
+ sage: P_NAF = NAF.shannon_parry_markov_chain()
+ sage: P_NAF.transitions()
+ [Transition from 0 to 0: 1/2|0,
+ Transition from 0 to 1: 1/4|1,
+ Transition from 0 to 1: 1/4|-1,
+ Transition from 1 to 0: 1|0]
+ sage: for s in P_NAF.iter_states():
+ ....: print s.color
+ 3/4
+ 3/2
+
+ The stationary distribution is also computed and saved as the
+ initial probabilities of the returned Markov chain::
+
+ sage: for s in P_NAF.states():
+ ....: print s, s.initial_probability
+ 0 2/3
+ 1 1/3
+
+ The automaton is assumed to be deterministic, irreducible and aperiodic::
+
+ sage: A = Automaton([(0, 0, 0), (0, 1, 1), (1, 1, 1), (1, 1, 0)],
+ ....: initial_states=[0])
+ sage: A.shannon_parry_markov_chain()
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: Automaton must be strongly connected.
+ sage: A = Automaton([(0, 0, 0), (0, 1, 0)],
+ ....: initial_states=[0])
+ sage: A.shannon_parry_markov_chain()
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: Automaton must be deterministic.
+ sage: A = Automaton([(0, 1, 0), (1, 0, 0)],
+ ....: initial_states=[0])
+ sage: A.shannon_parry_markov_chain()
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: Automaton must be aperiodic.
+
+ All states must be final::
+
+ sage: A = Automaton([(0, 1, 0), (0, 0, 1), (1, 0, 0)],
+ ....: initial_states=[0])
+ sage: A.shannon_parry_markov_chain()
+ Traceback (most recent call last):
+ ...
+ NotImplementedError: All states must be final.
+
+ ALGORITHM:
+
+ See [HKP2015a]_, Lemma 4.1.
+
+ REFERENCES:
+
+ .. [HKP2015a] Clemens Heuberger, Sara Kropf, and Helmut
+ Prodinger, *Analysis of Carries in Signed Digit Expansions*,
+ :arxiv:`1503.08816`.
+ .. [P1964] William Parry, *Intrinsic Markov chains*, Transactions
+ of the American Mathematical Society 112, 1964, pp. 55-66.
+ :doi:`10.1090/S0002-9947-1964-0161372-1`.
+ .. [S1948] Claude E. Shannon, *A mathematical theory of communication*,
+ The Bell System Technical Journal 27, 1948, 379-423,
+ :doi:`10.1002/j.1538-7305.1948.tb01338.x`.
+ """
+ from sage.modules.free_module_element import vector
+ if not self.is_deterministic():
+ raise NotImplementedError("Automaton must be deterministic.")
+ if not self.digraph().is_aperiodic():
+ raise NotImplementedError("Automaton must be aperiodic.")
+ if not self.digraph().is_strongly_connected():
+ raise NotImplementedError("Automaton must be strongly connected.")
+ if not all(s.is_final for s in self.iter_states()):
+ raise NotImplementedError("All states must be final.")
+ M = self.adjacency_matrix().change_ring(ZZ)
+ states = {state: i for i, state in enumerate(self.iter_states())}
+ w_all = sorted(M.eigenvectors_right(),
+ key=lambda x: abs(x[0]),
+ reverse=True)
+ w = w_all[0][1][0]
+ mu = w_all[0][0]
+ u_all = sorted(M.eigenvectors_left(),
+ key=lambda x: abs(x[0]),
+ reverse=True)
+ u = u_all[0][1][0]
+ u = 1/(u*w) * u
+ final = vector(int(s.is_final) for s in self.iter_states())
+ ff = u*final
+
+ assert u*w == 1
+ P = Transducer(initial_states=[s.label() for s in self.iter_initial_states()],
+ final_states=[s.label() for s in self.iter_final_states()],
+ on_duplicate_transition=duplicate_transition_add_input)
+ for t in self.iter_transitions():
+ P.add_transition(t.from_state.label(),
+ t.to_state.label(),
+ w[states[t.to_state]]/w[states[t.from_state]]/mu,
+ t.word_in)
+ for s in self.iter_states():
+ P.state(s.label()).color = 1/(w[states[s]] * ff)
+ P.state(s.label()).initial_probability = w[states[s]] * u[states[s]]
+ return P
+
+
def with_output(self, word_out_function=None):
r"""
Construct a transducer out of this automaton.
diff --git a/src/sage/combinat/finite_state_machine_generators.py b/src/sage/combinat/finite_state_machine_generators.py
index 8e0e84f..d58e43e 100644
--- a/src/sage/combinat/finite_state_machine_generators.py
+++ b/src/sage/combinat/finite_state_machine_generators.py
@@ -127,7 +127,6 @@ class TransducerGenerators(object):
[0, 1]
sage: T.output_alphabet
[0, 1]
- sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage: T([0, 1, 0, 1, 1])
[0, 1, 0, 1, 1]
@@ -185,7 +184,6 @@ class TransducerGenerators(object):
Check some sequence::
- sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage: T([0, 1, 0, 1, 1, 0])
[0, 0, 1, 0, 0, 1]
@@ -203,7 +201,6 @@ class TransducerGenerators(object):
Check some sequence::
- sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage: T([0, 1, 0, 1, 1, 0])
[0, 0, 0, 0, 1, 0]
@@ -228,7 +225,6 @@ class TransducerGenerators(object):
Transition from (1, 0, 1) to (): 2|0]
sage: input = [0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 2]
sage: output = [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0]
- sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage: T(input) == output
True
@@ -752,7 +748,6 @@ class TransducerGenerators(object):
sage: G = transducers.GrayCode()
sage: G
Transducer with 3 states
- sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage: for v in srange(0, 10):
....: print v, G(v.digits(base=2))
0 []
diff --git a/src/sage/functions/orthogonal_polys.py b/src/sage/functions/orthogonal_polys.py
index 2939b99..a8fe315 100644
--- a/src/sage/functions/orthogonal_polys.py
+++ b/src/sage/functions/orthogonal_polys.py
@@ -1225,7 +1225,7 @@ def gen_legendre_P(n,m,x):
sage: gen_legendre_P(3, 1, t)
-3/2*(5*t^2 - 1)*sqrt(-t^2 + 1)
sage: gen_legendre_P(4, 3, t)
- 105*(t^2 - 1)*sqrt(-t^2 + 1)*t
+ 105*(t^3 - t)*sqrt(-t^2 + 1)
sage: gen_legendre_P(7, 3, I).expand()
-16695*sqrt(2)
sage: gen_legendre_P(4, 1, 2.5)
diff --git a/src/sage/functions/piecewise.py b/src/sage/functions/piecewise.py
index 28bcf97..d417ab4 100644
--- a/src/sage/functions/piecewise.py
+++ b/src/sage/functions/piecewise.py
@@ -491,7 +491,7 @@ class PiecewisePolynomial:
sage: Q = tf.plot(rgbcolor=(0.7,0.6,0.6), plot_points=40)
sage: L = add([line([[a,0],[a,f(a)]],rgbcolor=(0.7,0.6,0.6)) for (a,b),f in tf.list()])
sage: P+Q+L
- Graphics object consisting of 14 graphics primitives
+ Graphics object consisting of 13 graphics primitives
TESTS:
diff --git a/src/sage/geometry/polyhedron/base.py b/src/sage/geometry/polyhedron/base.py
index 01e5f4b..605ef5c 100644
--- a/src/sage/geometry/polyhedron/base.py
+++ b/src/sage/geometry/polyhedron/base.py
@@ -3107,7 +3107,38 @@ class Polyhedron_base(Element):
sage: s4.is_eulerian()
True
"""
- return Graph(self.vertex_adjacency_matrix(), loops=False)
+ from itertools import combinations
+ inequalities = self.inequalities()
+ vertices = self.vertices()
+
+ # Associated to 'v' the inequalities in contact with v
+ vertex_ineq_incidence = [frozenset([i for i,ineq in enumerate(inequalities) if self._is_zero(ineq.eval(v))])
+ for i,v in enumerate(vertices)]
+
+ # the dual incidence structure
+ ineq_vertex_incidence = [set() for _ in range(len(inequalities))]
+ for v,ineq_list in enumerate(vertex_ineq_incidence):
+ for ineq in ineq_list:
+ ineq_vertex_incidence[ineq].add(v)
+
+ d = self.dim()
+ n = len(vertices)
+ X = set(range(n))
+
+ pairs = []
+ for i,j in combinations(range(n),2):
+ common_ineq = vertex_ineq_incidence[i]&vertex_ineq_incidence[j]
+ if not common_ineq: # or len(common_ineq) < d-2:
+ continue
+
+ if len(X.intersection(*[ineq_vertex_incidence[k] for k in common_ineq])) == 2:
+ pairs.append((i,j))
+
+ from sage.graphs.graph import Graph
+ g = Graph()
+ g.add_vertices(vertices)
+ g.add_edges((vertices[i],vertices[j]) for i,j in pairs)
+ return g
graph = vertex_graph
@@ -4149,10 +4180,10 @@ class Polyhedron_base(Element):
Permutation Group with generators [(3,4)]
"""
G = Graph()
- for edge in self.vertex_graph().edges():
- i = edge[0]
- j = edge[1]
- G.add_edge(i+1, j+1, (self.Vrepresentation(i).type(), self.Vrepresentation(j).type()) )
+ for u,v in self.vertex_graph().edges(labels=False):
+ i = u.index()
+ j = v.index()
+ G.add_edge(i+1, j+1, (u.type(), v.type()) )
group = G.automorphism_group(edge_labels=True)
self._combinatorial_automorphism_group = group
diff --git a/src/sage/geometry/polyhedron/library.py b/src/sage/geometry/polyhedron/library.py
index 12b2a83..b1368de 100644
--- a/src/sage/geometry/polyhedron/library.py
+++ b/src/sage/geometry/polyhedron/library.py
@@ -605,6 +605,51 @@ class Polytopes():
[-1, 1, 0], [-1, 0,-1], [-1,-1, 0] ]
return Polyhedron(vertices=v, base_ring=ZZ)
+ def icosidodecahedron(self, exact=True):
+ """
+ Return the Icosidodecahedron
+
+ The Icosidodecahedron is a polyhedron with twenty triangular faces and
+ twelve pentagonal faces. For more information see the
+ :wikipedia:`Icosidodecahedron`.
+
+ INPUT:
+
+ - ``exact`` -- (boolean, default ``True``) If ``False`` use an
+ approximate ring for the coordinates.
+
+ EXAMPLES::
+
+ sage: gr = polytopes.icosidodecahedron()
+ sage: gr.f_vector()
+ (1, 30, 60, 32, 1)
+
+ TESTS::
+
+ sage: polytopes.icosidodecahedron(exact=False)
+ A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 30 vertices
+ """
+ from sage.rings.number_field.number_field import QuadraticField
+ from itertools import product
+
+ K = QuadraticField(5, 'sqrt5')
+ one = K.one()
+ phi = (one+K.gen())/2
+
+ gens = [((-1)**a*one/2, (-1)**b*phi/2, (-1)**c*(one+phi)/2)
+ for a,b,c in product([0,1],repeat=3)]
+ gens.extend([(0,0,phi), (0,0,-phi)])
+
+ verts = []
+ for p in AlternatingGroup(3):
+ verts.extend(p(x) for x in gens)
+
+ if exact:
+ return Polyhedron(vertices=verts,base_ring=K)
+ else:
+ verts = [(RR(x),RR(y),RR(z)) for x,y,z in verts]
+ return Polyhedron(vertices=verts)
+
def buckyball(self, exact=True, base_ring=None):
"""
Return the bucky ball.
diff --git a/src/sage/graphs/base/boost_graph.pxd b/src/sage/graphs/base/boost_graph.pxd
index 2977116..2b517eb 100644
--- a/src/sage/graphs/base/boost_graph.pxd
+++ b/src/sage/graphs/base/boost_graph.pxd
@@ -27,6 +27,13 @@ cdef extern from "boost/graph/adjacency_list.hpp" namespace "boost":
pass
cdef cppclass bidirectionalS:
pass
+ cdef cppclass no_property:
+ pass
+ cdef cppclass edge_weight_t:
+ pass
+ cdef cppclass property[T, U]:
+ pass
+
cdef extern from "boost_interface.cpp":
ctypedef unsigned long v_index
@@ -40,30 +47,43 @@ cdef extern from "boost_interface.cpp":
float average_clustering_coefficient
vector[float] clust_of_v
- cdef cppclass BoostGraph[OutEdgeListS, VertexListS, DirectedS, EdgeListS]:
+ cdef cppclass BoostGraph[OutEdgeListS, VertexListS, DirectedS, EdgeListS, EdgeProperty]:
BoostGraph()
void add_vertex()
v_index num_verts()
void add_edge(v_index u, v_index v)
+ void add_edge(v_index u, v_index v, double w)
e_index num_edges()
result_ec edge_connectivity()
double clustering_coeff(v_index v)
result_cc clustering_coeff_all()
vector[v_index] dominator_tree(v_index v)
+ vector[v_index] bandwidth_ordering(bool)
+ vector[v_index] kruskal_min_spanning_tree()
+ vector[v_index] prim_min_spanning_tree()
-ctypedef BoostGraph[vecS, vecS, undirectedS, vecS] BoostVecGraph
-ctypedef BoostGraph[vecS, vecS, bidirectionalS, vecS] BoostVecDiGraph
+ctypedef property[edge_weight_t, double] EdgeWeight
-ctypedef BoostGraph[setS, vecS, undirectedS, vecS] BoostSetGraph
+ctypedef BoostGraph[vecS, vecS, undirectedS, vecS, no_property] BoostVecGraph
+ctypedef BoostGraph[vecS, vecS, bidirectionalS, vecS, no_property] BoostVecDiGraph
+
+ctypedef BoostGraph[vecS, vecS, undirectedS, vecS, EdgeWeight] BoostVecWeightedGraph
+ctypedef BoostGraph[vecS, vecS, bidirectionalS, vecS, EdgeWeight] BoostVecWeightedDiGraph
+
+ctypedef BoostGraph[setS, vecS, undirectedS, vecS, no_property] BoostSetGraph
ctypedef fused BoostVecGenGraph:
BoostVecGraph
BoostVecDiGraph
+ctypedef fused BoostWeightedGraph:
+ BoostVecWeightedGraph
+ BoostVecWeightedDiGraph
+
ctypedef fused BoostGenGraph:
BoostVecGraph
BoostVecDiGraph
- BoostGraph[vecS, vecS, directedS, vecS]
+ BoostGraph[vecS, vecS, directedS, vecS, no_property]
BoostSetGraph
- BoostGraph[setS, vecS, directedS, vecS]
- BoostGraph[setS, vecS, bidirectionalS, vecS]
+ BoostGraph[setS, vecS, directedS, vecS, no_property]
+ BoostGraph[setS, vecS, bidirectionalS, vecS, no_property]
diff --git a/src/sage/graphs/base/boost_graph.pyx b/src/sage/graphs/base/boost_graph.pyx
index 8b167b3..e67882e 100644
--- a/src/sage/graphs/base/boost_graph.pyx
+++ b/src/sage/graphs/base/boost_graph.pyx
@@ -34,6 +34,8 @@ with ``delete()``.
:func:`clustering_coeff` | Returns the clustering coefficient of all vertices in the graph.
:func:`edge_connectivity` | Returns the edge connectivity of the graph.
:func:`dominator_tree` | Returns a dominator tree of the graph.
+ :func:`bandwidth_heuristics` | Uses heuristics to approximate the bandwidth of the graph.
+ :func:`min_spanning_tree` | Computes a minimum spanning tree of a (weighted) graph.
Functions
---------
@@ -66,6 +68,57 @@ cdef boost_graph_from_sage_graph(BoostGenGraph *g, g_sage):
for u,v in g_sage.edge_iterator(labels=None):
g.add_edge(vertex_to_int[u], vertex_to_int[v])
+cdef boost_weighted_graph_from_sage_graph(BoostWeightedGraph *g,
+ g_sage,
+ weight_function = None):
+ r"""
+ Initializes the Boost weighted graph ``g`` to be equal to ``g_sage``.
+
+ The Boost graph ``*g`` must represent an empty weighted graph. The edge
+ weights are chosen as follows, and they must be convertible to floats,
+ otherwise an error is raised.
+
+ - If ``weight_function`` is not ``None``, this function is used.
+
+ - If ``weight_function`` is ``None`` and ``g`` is weighted, the edge labels
+ of ``g`` are used; in other words, the weight of an edge ``e=(u,v,l)`` is
+ ``l``.
+
+ - Otherwise, all weights are set to 1.
+
+ In particular, the ``weight_function`` must be a function which inputs an
+ edge ``e`` and outputs a number.
+ """
+
+ from sage.graphs.generic_graph import GenericGraph
+
+ if not isinstance(g_sage, GenericGraph):
+ raise ValueError("The input parameter must be a Sage graph.")
+
+ if g.num_verts() > 0:
+ raise ValueError("The Boost graph in input must be empty")
+
+ N = g_sage.num_verts()
+ cdef dict vertex_to_int = {v:i for i,v in enumerate(g_sage.vertices())}
+
+ for i in range(N):
+ g.add_vertex()
+
+ if weight_function is not None:
+ for e in g_sage.edge_iterator():
+ g.add_edge(vertex_to_int[e[0]],
+ vertex_to_int[e[1]],
+ float(weight_function(e)))
+
+ elif g_sage.weighted():
+ for u,v,w in g_sage.edge_iterator():
+ g.add_edge(vertex_to_int[u], vertex_to_int[v], float(w))
+
+ else:
+ for u,v in g_sage.edge_iterator(labels=False):
+ g.add_edge(vertex_to_int[u], vertex_to_int[v], 1)
+
+
cdef boost_edge_connectivity(BoostVecGenGraph *g):
r"""
Computes the edge connectivity of the input Boost graph.
@@ -362,3 +415,224 @@ cpdef dominator_tree(g, root, return_dict = False):
return g
else:
return Graph(edges)
+
+
+cpdef bandwidth_heuristics(g, algorithm = 'cuthill_mckee'):
+ r"""
+ Uses Boost heuristics to approximate the bandwidth of the input graph.
+
+ The bandwidth `bw(M)` of a matrix `M` is the smallest integer `k` such that
+ all non-zero entries of `M` are at distance `k` from the diagonal. The
+ bandwidth `bw(g)` of an undirected graph `g` is the minimum bandwidth of
+ the adjacency matrix of `g`, over all possible relabellings of its vertices
+ (for more information, see the
+ :mod:`~sage.graphs.graph_decompositions.bandwidth`
+ module).
+
+ Unfortunately, exactly computing the bandwidth is NP-hard (and an
+ exponential algorithm is implemented in Sagemath in routine
+ :func:`~sage.graphs.graph_decompositions.bandwidth.bandwidth`). Here, we
+ implement two heuristics to find good orderings: Cuthill-McKee, and King.
+
+ This function works only in undirected graphs, and its running time is
+ `O(md_{max}\log d_{max})` for the Cuthill-McKee ordering, and
+ `O(md_{max}^2\log d_{max})` for the King ordering, where `m` is the number
+ of edges, and `d_{max}` is the maximum degree in the graph.
+
+ INPUT:
+
+ - ``g`` (``Graph``) - the input graph.
+
+ - ``algorithm`` (``'cuthill_mckee'`` or ``'king'``) - the heuristic used to
+ compute the ordering: Cuthill-McKee, or King.
+
+ OUTPUT:
+
+ A pair ``[bandwidth, ordering]``, where ``ordering`` is the ordering of
+ vertices, ``bandwidth`` is the bandwidth of that specific ordering (which
+ is not necessarily the bandwidth of the graph, because this is a heuristic).
+
+ EXAMPLES::
+
+ sage: from sage.graphs.base.boost_graph import bandwidth_heuristics
+ sage: bandwidth_heuristics(graphs.PathGraph(10))
+ (1, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
+ sage: bandwidth_heuristics(graphs.GridGraph([3,3]))
+ (3, [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)])
+ sage: bandwidth_heuristics(graphs.GridGraph([3,3]), algorithm='king')
+ (3, [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)])
+
+ TESTS:
+
+ Given an input which is not a graph::
+
+ sage: from sage.graphs.base.boost_graph import bandwidth_heuristics
+ sage: bandwidth_heuristics(digraphs.Path(10))
+ Traceback (most recent call last):
+ ...
+ ValueError: The input g must be a Graph.
+ sage: bandwidth_heuristics("I am not a graph!")
+ Traceback (most recent call last):
+ ...
+ ValueError: The input g must be a Graph.
+
+ Given a wrong algorithm::
+
+ from sage.graphs.base.boost_graph import bandwidth_heuristics
+ sage: bandwidth_heuristics(graphs.PathGraph(3), algorithm='tip top')
+ Traceback (most recent call last):
+ ...
+ ValueError: Algorithm 'tip top' not yet implemented. Please contribute.
+
+ Given a graph with no edges::
+
+ from sage.graphs.base.boost_graph import bandwidth_heuristics
+ sage: bandwidth_heuristics(Graph())
+ (0, [])
+ sage: bandwidth_heuristics(graphs.RandomGNM(10,0))
+ (0, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
+
+ """
+ from sage.graphs.graph import Graph
+
+ # Tests for errors and trivial cases
+ if not isinstance(g, Graph):
+ raise ValueError("The input g must be a Graph.")
+ if not algorithm in ['cuthill_mckee', 'king']:
+ raise ValueError("Algorithm '%s' not yet implemented. Please contribute." %(algorithm))
+ if g.num_edges()==0:
+ return (0, g.vertices());
+
+ sig_on()
+ # These variables are automatically deleted when the function terminates.
+ cdef BoostVecGraph g_boost
+ cdef vector[v_index] result
+ cdef dict vertex_to_int = {v:i for i,v in enumerate(g.vertices())}
+ cdef dict int_to_vertex = {i:v for i,v in enumerate(g.vertices())}
+
+ boost_graph_from_sage_graph(&g_boost, g)
+ result = <vector[v_index]> g_boost.bandwidth_ordering(algorithm=='cuthill_mckee')
+
+ cdef int n = g.num_verts()
+ cdef dict pos = {int_to_vertex[result[i]]:i for i in range(n)}
+ cdef int bandwidth = max([abs(pos[u]-pos[v]) for u,v in g.edges(labels=False)])
+
+ sig_off()
+ return (bandwidth, [int_to_vertex[result[i]] for i in range(n)])
+
+cpdef min_spanning_tree(g,
+ weight_function=None,
+ algorithm='Kruskal'):
+ r"""
+ Uses Boost to compute the minimum spanning tree of the input graph.
+
+ INPUT:
+
+ - ``g`` (``Graph``) - the input graph.
+
+ - ``weight_function`` (function) - a function that inputs an edge ``e`` and
+ outputs its weight. An edge has the form ``(u,v,l)``, where ``u`` and
+ ``v`` are vertices, ``l`` is a label (that can be of any kind). The
+ ``weight_function`` can be used to transform the label into a weight (see
+ the example below). In particular:
+
+ - if ``weight_function`` is not ``None``, the weight of an edge ``e`` is
+ ``weight_function(e)``;
+
+ - if ``weight_function`` is ``None`` (default) and ``g`` is weighted (that
+ is, ``g.weighted()==True``), for each edge ``e=(u,v,l)``, we set weight
+ ``l``;
+
+ - if ``weight_function`` is ``None`` and ``g`` is not weighted, we set all
+ weights to 1 (hence, the output can be any spanning tree).
+
+ Note that, if the weight is not convertible to a number with function
+ ``float()``, an error is raised (see tests below).
+
+ - ``algorithm`` (``'Kruskal'`` or ``'Prim'``) - the algorithm used.
+
+ OUTPUT:
+
+ The edges of a minimum spanning tree of ``g``, if one exists, otherwise
+ the empty list.
+
+ .. seealso::
+
+ - :meth:`sage.graphs.generic_graph.GenericGraph.min_spanning_tree`
+
+ EXAMPLES::
+
+ sage: from sage.graphs.base.boost_graph import min_spanning_tree
+ sage: min_spanning_tree(graphs.PathGraph(4))
+ [(0, 1, None), (1, 2, None), (2, 3, None)]
+
+ sage: G = Graph([(0,1,{'name':'a','weight':1}), (0,2,{'name':'b','weight':3}), (1,2,{'name':'b','weight':1})])
+ sage: min_spanning_tree(G, weight_function=lambda e: e[2]['weight'])
+ [(0, 1, {'name': 'a', 'weight': 1}), (1, 2, {'name': 'b', 'weight': 1})]
+
+ TESTS:
+
+ Given an input which is not a graph::
+
+ sage: min_spanning_tree("I am not a graph!")
+ Traceback (most recent call last):
+ ...
+ ValueError: The input g must be a Sage Graph.
+
+ Given a wrong algorithm::
+
+ sage: min_spanning_tree(graphs.PathGraph(3), algorithm='tip top')
+ Traceback (most recent call last):
+ ...
+ ValueError: Algorithm 'tip top' not yet implemented. Please contribute.
+
+ If the weight is not a number::
+
+ sage: g = Graph([(0,1,1), (1,2,'a')], weighted=True)
+ sage: min_spanning_tree(g)
+ Traceback (most recent call last):
+ ...
+ ValueError: could not convert string to float: a
+
+ sage: g = Graph([(0,1,1), (1,2,[1,2,3])], weighted=True)
+ sage: min_spanning_tree(g)
+ Traceback (most recent call last):
+ ...
+ TypeError: float() argument must be a string or a number
+ """
+ from sage.graphs.graph import Graph
+
+ if not isinstance(g, Graph):
+ raise ValueError("The input g must be a Sage Graph.")
+ if not algorithm in ['Kruskal', 'Prim']:
+ raise ValueError("Algorithm '%s' not yet implemented. Please contribute." %(algorithm))
+
+ if g.allows_loops() or g.allows_multiple_edges():
+ g = g.to_simple()
+ # Now g has no self loops and no multiple edges.
+ sig_on()
+ # These variables are automatically deleted when the function terminates.
+ cdef BoostVecWeightedGraph g_boost
+ cdef vector[v_index] result
+ cdef dict vertex_to_int = {v:i for i,v in enumerate(g.vertices())}
+ cdef dict int_to_vertex = {i:v for i,v in enumerate(g.vertices())}
+
+ try:
+ boost_weighted_graph_from_sage_graph(&g_boost, g, weight_function)
+ except Exception, e:
+ sig_off()
+ raise e
+
+ if algorithm=='Kruskal':
+ result = <vector[v_index]> g_boost.kruskal_min_spanning_tree()
+ elif algorithm=='Prim':
+ result = <vector[v_index]> g_boost.prim_min_spanning_tree()
+
+ cdef int n = g.num_verts()
+ sig_off()
+
+ if result.size() != 2 * (n - 1):
+ return []
+ else:
+ edges = [(int_to_vertex[result[2*i]], int_to_vertex[result[2*i+1]]) for i in range(n-1)]
+ return sorted([(min(e[0],e[1]), max(e[0],e[1]), g.edge_label(e[0], e[1])) for e in edges])
diff --git a/src/sage/graphs/base/boost_interface.cpp b/src/sage/graphs/base/boost_interface.cpp
index cf895eb..6fbb57d 100644
--- a/src/sage/graphs/base/boost_interface.cpp
+++ b/src/sage/graphs/base/boost_interface.cpp
@@ -5,6 +5,10 @@
#include <boost/graph/exterior_property.hpp>
#include <boost/graph/clustering_coefficient.hpp>
#include <boost/graph/dominator_tree.hpp>
+#include <boost/graph/cuthill_mckee_ordering.hpp>
+#include <boost/graph/king_ordering.hpp>
+#include <boost/graph/kruskal_min_spanning_tree.hpp>
+#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <iostream>
@@ -32,7 +36,8 @@ typedef struct {
template <class OutEdgeListS, // How neighbors are stored
class VertexListS, // How vertices are stored
class DirectedS, // The kind of graph (undirectedS, directedS, or bidirectionalS)
- class EdgeListS> // How the list of edges is stored
+ class EdgeListS, // How the list of edges is stored
+ class EdgeProperty> // Properties of edges (weight)
class BoostGraph
/*
* This generic class wraps a Boost graph, in order to make it Cython-friendly.
@@ -50,7 +55,7 @@ class BoostGraph
*/
{
typedef typename boost::adjacency_list<OutEdgeListS, VertexListS, DirectedS,
- property<vertex_index_t, v_index>, no_property, no_property, EdgeListS> adjacency_list;
+ property<vertex_index_t, v_index>, EdgeProperty, no_property, EdgeListS> adjacency_list;
typedef typename boost::graph_traits<adjacency_list>::vertex_descriptor vertex_descriptor;
typedef typename boost::graph_traits<adjacency_list>::edge_descriptor edge_descriptor;
typedef typename std::vector<edge_descriptor> edge_container;
@@ -87,6 +92,10 @@ public:
boost::add_edge((*vertices)[u], (*vertices)[v], *graph);
}
+ void add_edge(v_index u, v_index v, double weight) {
+ boost::add_edge((*vertices)[u], (*vertices)[v], weight, *graph);
+ }
+
result_ec edge_connectivity() {
result_ec to_return;
edge_container disconnecting_set;
@@ -132,6 +141,51 @@ public:
}
return fathers;
}
+
+ // Works only in undirected graphs!
+ vector<v_index> bandwidth_ordering(bool cuthill) {
+ vector<v_index> to_return;
+ vector<vertex_descriptor> inv_perm(num_vertices(*graph));
+
+ if (cuthill) {
+ boost::cuthill_mckee_ordering(*graph, inv_perm.rbegin());
+ } else {
+ boost::king_ordering(*graph, inv_perm.rbegin());
+ }
+
+ for (int i = 0; i < inv_perm.size(); i++) {
+ to_return.push_back(index[inv_perm[i]]);
+ }
+ return to_return;
+ }
+
+ // This function works only on undirected graphs.
+ vector<v_index> kruskal_min_spanning_tree() {
+ vector<v_index> to_return;
+ std::vector <edge_descriptor> spanning_tree;
+ kruskal_minimum_spanning_tree(*graph, std::back_inserter(spanning_tree));
+
+ for (unsigned int i = 0; i < spanning_tree.size(); i++) {
+ to_return.push_back(index[source(spanning_tree[i], *graph)]);
+ to_return.push_back(index[target(spanning_tree[i], *graph)]);
+ }
+ return to_return;
+ }
+
+ // This function works only on undirected graphs with no parallel edge.
+ vector<v_index> prim_min_spanning_tree() {
+ vector<v_index> to_return;
+ vector<vertex_descriptor> predecessors(num_verts());
+ prim_minimum_spanning_tree(*graph, make_iterator_property_map(predecessors.begin(), index));
+
+ for (unsigned int i = 0; i < predecessors.size(); i++) {
+ if (index[predecessors[i]] != i) {
+ to_return.push_back(i);
+ to_return.push_back(index[predecessors[i]]);
+ }
+ }
+ return to_return;
+ }
};
diff --git a/src/sage/graphs/base/c_graph.pyx b/src/sage/graphs/base/c_graph.pyx
index a50261d..665e86f 100644
--- a/src/sage/graphs/base/c_graph.pyx
+++ b/src/sage/graphs/base/c_graph.pyx
@@ -2181,7 +2181,7 @@ cdef class CGraphBackend(GenericGraphBackend):
return []
- def bidirectional_dijkstra(self, x, y):
+ def bidirectional_dijkstra(self, x, y, weight_function=None):
r"""
Returns the shortest path between ``x`` and ``y`` using a
bidirectional version of Dijkstra's algorithm.
@@ -2193,6 +2193,10 @@ cdef class CGraphBackend(GenericGraphBackend):
- ``y`` -- the end vertex in the shortest path from ``x`` to ``y``.
+ - ``weight_function`` -- a function that inputs an edge
+ ``(u, v, l)`` and outputs its weight. If ``None``, we use
+ the edge label ``l`` as a weight.
+
OUTPUT:
- A list of vertices in the shortest path from ``x`` to ``y``.
@@ -2204,6 +2208,9 @@ cdef class CGraphBackend(GenericGraphBackend):
... G.set_edge_label(u,v,1)
sage: G.shortest_path(0, 1, by_weight=True)
[0, 1]
+ sage: G = DiGraph([(1,2,{'weight':1}), (1,3,{'weight':5}), (2,3,{'weight':1})])
+ sage: G.shortest_path(1, 3, weight_function=lambda e:e[2]['weight'])
+ [1, 2, 3]
TEST:
@@ -2264,6 +2271,9 @@ cdef class CGraphBackend(GenericGraphBackend):
cdef int meeting_vertex = -1
cdef float shortest_path_length
+ if weight_function is None:
+ weight_function = lambda e:e[2]
+
# As long as the current side (x or y) is not totally explored ...
while queue:
(distance, side, pred, v) = heappop(queue)
@@ -2299,7 +2309,7 @@ cdef class CGraphBackend(GenericGraphBackend):
if w not in dist_current:
v_obj = self.vertex_label(v)
w_obj = self.vertex_label(w)
- edge_label = self.get_edge_label(v_obj, w_obj) if side == 1 else self.get_edge_label(w_obj, v_obj)
+ edge_label = weight_function((v_obj, w_obj, self.get_edge_label(v_obj, w_obj))) if side == 1 else weight_function((w_obj, v_obj, self.get_edge_label(w_obj, v_obj)))
heappush(queue, (distance + edge_label, side, v, w))
# No meeting point has been found
diff --git a/src/sage/graphs/digraph.py b/src/sage/graphs/digraph.py
index 2731cc7..a1f9f71 100644
--- a/src/sage/graphs/digraph.py
+++ b/src/sage/graphs/digraph.py
@@ -436,12 +436,6 @@ class DiGraph(GenericGraph):
sage: DiGraph({0:Set([1,2,3]), 2:Set([4])}).edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (2, 4, None)]
- Get rid of mutable default argument for `boundary` (:trac:`14794`)::
-
- sage: D = DiGraph(boundary=None)
- sage: D._boundary
- []
-
Demonstrate that digraphs using the static backend are equal to mutable
graphs but can be used as dictionary keys::
@@ -475,7 +469,7 @@ class DiGraph(GenericGraph):
_directed = True
def __init__(self, data=None, pos=None, loops=None, format=None,
- boundary=None, weighted=None, implementation='c_graph',
+ weighted=None, implementation='c_graph',
data_structure="sparse", vertex_labels=True, name=None,
multiedges=None, convert_empty_dict_labels_to_None=None,
sparse=True, immutable=False):
@@ -946,7 +940,7 @@ class DiGraph(GenericGraph):
self._weighted = weighted
self._pos = pos
- self._boundary = boundary if boundary is not None else []
+
if format != 'DiGraph' or name is not None:
self.name(name)
@@ -1142,7 +1136,6 @@ class DiGraph(GenericGraph):
from sage.graphs.all import Graph
G = Graph(name = self.name(),
pos = self._pos,
- boundary = self._boundary,
multiedges = self.allows_multiple_edges(),
loops = self.allows_loops(),
implementation = implementation,
diff --git a/src/sage/graphs/distances_all_pairs.pyx b/src/sage/graphs/distances_all_pairs.pyx
index c9bcc21..1e60d37 100644
--- a/src/sage/graphs/distances_all_pairs.pyx
+++ b/src/sage/graphs/distances_all_pairs.pyx
@@ -1303,11 +1303,12 @@ def diameter(G, method='iFUB', source=None):
EXAMPLES::
+ sage: from sage.graphs.distances_all_pairs import diameter
sage: G = graphs.PetersenGraph()
- sage: G.diameter(method='iFUB')
+ sage: diameter(G, method='iFUB')
2
sage: G = Graph( { 0 : [], 1 : [], 2 : [1] } )
- sage: G.diameter(method='iFUB')
+ sage: diameter(G, method='iFUB')
+Infinity
@@ -1315,21 +1316,21 @@ def diameter(G, method='iFUB', source=None):
never be negative, we define it to be zero::
sage: G = graphs.EmptyGraph()
- sage: G.diameter(method='iFUB')
+ sage: diameter(G, method='iFUB')
0
Comparison of exact methods::
sage: G = graphs.RandomBarabasiAlbert(100, 2)
- sage: d1 = G.diameter(method='standard')
- sage: d2 = G.diameter(method='iFUB')
- sage: d3 = G.diameter(method='iFUB', source=G.random_vertex())
+ sage: d1 = diameter(G, method='standard')
+ sage: d2 = diameter(G, method='iFUB')
+ sage: d3 = diameter(G, method='iFUB', source=G.random_vertex())
sage: if d1!=d2 or d1!=d3: print "Something goes wrong!"
Comparison of lower bound methods::
- sage: lb2 = G.diameter(method='2sweep')
- sage: lbm = G.diameter(method='multi-sweep')
+ sage: lb2 = diameter(G, method='2sweep')
+ sage: lbm = diameter(G, method='multi-sweep')
sage: if not (lb2<=lbm and lbm<=d3): print "Something goes wrong!"
TEST:
@@ -1337,7 +1338,7 @@ def diameter(G, method='iFUB', source=None):
This was causing a segfault. Fixed in :trac:`17873` ::
sage: G = graphs.PathGraph(1)
- sage: G.diameter(method='iFUB')
+ sage: diameter(G, method='iFUB')
0
"""
cdef int n = G.order()
diff --git a/src/sage/graphs/generators/families.py b/src/sage/graphs/generators/families.py
index 2494fcc..c305211 100644
--- a/src/sage/graphs/generators/families.py
+++ b/src/sage/graphs/generators/families.py
@@ -1515,7 +1515,8 @@ def PaleyGraph(q):
"""
from sage.rings.finite_rings.integer_mod import mod
from sage.rings.finite_rings.constructor import FiniteField
- assert q.is_prime_power(), "Parameter q must be a prime power"
+ from sage.rings.arith import is_prime_power
+ assert is_prime_power(q), "Parameter q must be a prime power"
assert mod(q,4)==1, "Parameter q must be congruent to 1 mod 4"
g = Graph([FiniteField(q,'a'), lambda i,j: (i-j).is_square()],
loops=False, name = "Paley graph with parameter %d"%q)
diff --git a/src/sage/graphs/generators/random.py b/src/sage/graphs/generators/random.py
index 25c5fd1..01f9c13 100644
--- a/src/sage/graphs/generators/random.py
+++ b/src/sage/graphs/generators/random.py
@@ -831,7 +831,8 @@ def RandomTriangulation(n, embed=False, base_ring=QQ):
from sage.geometry.polyhedron.plot import ProjectionFuncStereographic
from sage.modules.free_module_element import vector
proj = ProjectionFuncStereographic([0, 0, 1])
- ppoints = [proj(vector(x)) for x in points]
- g.set_pos({i: ppoints[i] for i in range(len(points))})
+ g.set_pos({v: proj(vector(v))
+ for v in g})
+ g.relabel()
return g
diff --git a/src/sage/graphs/generators/smallgraphs.py b/src/sage/graphs/generators/smallgraphs.py
index a7f7cd4..39ca04e 100644
--- a/src/sage/graphs/generators/smallgraphs.py
+++ b/