commit a89a02a24b44fd0b2ce1c92ecce22b672bbd9e21
Author: Dima Pasechnik
Date: Tue Aug 4 22:56:26 2015 +0100
another unknown graph, instead of the known one
commit d959afa2fe6093a1ddc6440c444cf2e5cdc62225
Author: Nathann Cohen
Date: Tue Aug 4 22:32:39 2015 +0200
trac #18988: Orthogonal Polar graphs in strongly_regular_graph
commit 449a23ec5b0305fc2f7132bdd38ba0923ec01b89
Author: Dima Pasechnik
Date: Tue Aug 4 21:52:53 2015 +0100
improving seidel_switching()
commit c4269aeae44bbd64afbdee96f04fb120d73f0de1
Author: Dima Pasechnik
Date: Tue Aug 4 20:28:35 2015 +0100
doc and srg DB fixes
commit 758da33a4bd616f97e2b9748236c0d866fb8f79d
Author: Dima Pasechnik
Date: Tue Aug 4 14:33:39 2015 +0100
SRG_279_150_85_75 added.
I don't know how to rebuild the database, so that it is available as
sage: graphs.strongly_regular_graph(279, 150, 85, 75)
commit 5115728f80aa95f87a272feec999e317ccdffba4
Author: Dima Pasechnik
Date: Mon Aug 3 21:36:09 2015 +0100
make descendant computation faster
commit f72b84ea89a0f371a53a965620ca7820886f0f82
Merge: 3b0bd4f a75774f
Author: Dima Pasechnik
Date: Mon Aug 3 13:06:25 2015 +0100
rebase...
commit 3b0bd4f77e7b50f3197631dae88a9669ee13cc2a
Merge: 7331311 dc2d326
Author: Dima Pasechnik
Date: Mon Aug 3 12:46:23 2015 +0100
Merge branch 'u/ncohen/18960' of git://trac.sagemath.org/sage into seidelsw
commit 7331311b78d59d5e932fd92af3a4cb4a3188a348
Author: Dima Pasechnik
Date: Mon Aug 3 12:38:47 2015 +0100
minor typos etc
commit 3eeca75f420da293a72012fe54eddc28de1495fd
Author: Dima Pasechnik
Date: Mon Aug 3 12:29:17 2015 +0100
introducing class TwoGraph
commit a75774fa9f6168b4f0e34c6cdd93496f7283b179
Author: Nathann Cohen
Date: Mon Aug 3 11:40:20 2015 +0200
trac #18948: take into account the BIBD from #18934
commit dc2d3261a823a5ed8db1129497ada25e3059d7ee
Author: Nathann Cohen
Date: Mon Aug 3 11:32:26 2015 +0200
trac #18960: Lint -> vLint
commit 0aafa88f085c4bd0962512831ef2fc39911a1f99
Merge: edb1b08 21b01bc
Author: Dima Pasechnik
Date: Mon Aug 3 10:18:24 2015 +0100
Merge branch 'u/dimpase/seidelsw' of git://trac.sagemath.org/sage into seidelsw
commit 4f51703c4e63909516d4711714a5429cfd4f5050
Author: Nathann Cohen
Date: Mon Aug 3 10:04:17 2015 +0200
trac #18948: DOcstring
commit 21b01bcc384a0bef91b019dbe6914911a3aad5db
Author: Dima Pasechnik
Date: Sun Aug 2 22:54:21 2015 +0100
no need for explicit .eps in LaTeX
commit e5144c17944ba15810fa6add30e1d9a996559607
Author: Dima Pasechnik
Date: Sun Aug 2 22:41:44 2015 +0100
initial version of twograph functionality
commit cf8f2dad1cd90ff5aaa0cec15a25f87c64289719
Author: Nathann Cohen
Date: Sat Aug 1 19:04:05 2015 +0200
trac #18948: guess mu
commit 46bdc550161b3fce56097c8c3f0bf101ea2c5c64
Author: Dmitrii Pasechnik
Date: Sat Aug 1 03:33:45 2015 +0100
switching construction for the Chang graphs
commit a48e9e2c5ca13c44468a42a1420fac8b70ee9faa
Author: Dmitrii Pasechnik
Date: Sat Aug 1 01:41:56 2015 +0100
modifications suggested by Nathann in comment 1
commit 83ed332c58dbad71fe5b74d8c2d9e3aa3fe52d84
Author: Nathann Cohen
Date: Fri Jul 31 10:32:23 2015 +0200
trac #18960: Again...
commit b76c9a0369a5babc98481d6b96125c9b86f1adc9
Author: Dmitrii Pasechnik
Date: Fri Jul 31 02:12:30 2015 +0100
Seidel adj.mat. constructor, creation, switching
commit a9280c9ae07f2703e7d004d463a77d8e6482025f
Author: Nathann Cohen
Date: Thu Jul 30 18:44:48 2015 +0200
trac #18948: Rephrasing the doc
commit 8f254930985e06432a8261c697d2b5e0edf97f9d
Merge: edb1b08 4adcf95
Author: Nathann Cohen
Date: Thu Jul 30 18:42:19 2015 +0200
trac #18948: Merged with 6.9.beta0
commit 606d15fbf46b427ed47a92e7250d75f4711cdd78
Author: Nathann Cohen
Date: Thu Jul 30 17:42:04 2015 +0200
trac #18960: Adding nonzero somewhere
commit 3eee1e76896f8406e2f98c0664ebb0e959798df2
Merge: edb1b08 6390dd9
Author: Nathann Cohen
Date: Thu Jul 30 17:40:50 2015 +0200
trac #18960: Merge 6.9.beta0
commit edb1b0870d25373a1cf8def52c5fe3159245f59d
Author: Volker Braun
Date: Wed Jul 29 17:07:30 2015 +0200
Updated Sage version to 6.9.beta0
commit a7cb38e82628a8a0ae845cc6f714aa0deead3f36
Merge: 5b81e36 1be3c2b
Author: Release Manager
Date: Wed Jul 29 11:24:23 2015 +0200
Trac #18962: Double free in ft2font
As reported at https://groups.google.com/d/msg/sage-
support/K-neaKVSGiE/YMvQqVNQCQAJ
{{{
sage: import matplotlib
sage: matplotlib.rc('text', usetex=True)
sage: plot(sin).save('/tmp/test.svg') # works
sage: plot(sin).save('/tmp/test.svg') # segfault
}}}
This is a bug in freetype 2.5.2 (http://savannah.nongnu.org/bugs/?40997)
Update to freetype-2.6 fixes it.
URL: http://trac.sagemath.org/18962
Reported by: vbraun
Ticket author(s): Volker Braun
Reviewer(s): François Bissey
commit 5b81e3674d0c057baf1d9586f4364b0c2241d5b1
Merge: 0feb845 1a30b06
Author: Release Manager
Date: Wed Jul 29 11:23:34 2015 +0200
Trac #16133: delete deprecation warning in FSM.process and __call__
Delete the deprecation warning and its documentation in
{{{FiniteStateMachine.process}}}.
See #16132 for details. The deprecation warning was active sind #16132
was merged in 6.2.rc0 (2014-04-23), thus also in 6.2 (2014-05-06).
URL: http://trac.sagemath.org/16133
Reported by: dkrenn
Ticket author(s): Daniel Krenn, Clemens Heuberger
Reviewer(s): Daniel Krenn
commit 0feb845c9309c083c11be2e6e054792c5f456a5a
Merge: 79beba9 e35ebe9
Author: Release Manager
Date: Wed Jul 29 11:23:29 2015 +0200
Trac #14243: Try not to pick up user versions of things like numpy, mpl
At [http://ask.sagemath.org/question/1449/sage-uses-system-wide-python
this ask.sagemath.org question], where some users have the system Python
being picked up for some reasons, Volker asks
{{{
Can you try
export PYTHONNOUSERSITE=yes
sage
This should prevent Sage from picking up stuff in .local/lib. If that
fixes your problem we can add it to the next release.
}}}
Apparently this works, and
[https://groups.google.com/forum/?fromgroups=#!topic/sage-
support/Y9bjhb6-dcM this sage-support question] suggests it works a lot.
Maybe we should put this in now.
URL: http://trac.sagemath.org/14243
Reported by: kcrisman
Ticket author(s): John Palmieri
Reviewer(s): Buck Evan
commit 1be3c2b15b3aa1ba78396d549bfc4ba7161cd097
Author: Volker Braun
Date: Wed Jul 29 10:11:59 2015 +0200
Update to freetype 2.6
commit 79beba9dc7a706278b73fb9b17d0be1ab985c0c6
Merge: a24ef7d cfbc7da
Author: Release Manager
Date: Wed Jul 29 00:50:44 2015 +0200
Trac #18760: Posets: Slightly faster is_lattice()
Finite join-semilattice with bottom element is a lattice. (Resp. meet-
semilattice with top element.)
URL: http://trac.sagemath.org/18760
Reported by: jmantysalo
Ticket author(s): Jori Mäntysalo
Reviewer(s): David Einstein
commit a24ef7dd68cad1be4161af1193f6e1a0ca332a0f
Merge: 8b9b5f8 24f7b3b
Author: Release Manager
Date: Wed Jul 29 00:50:40 2015 +0200
Trac #16106: Delete deprecation warning in Transducer.cartesian_product
Delete the deprecation warning and its documentation in
Transducer.cartesian_product.
See #16061 for the reasons for this deprecation warning. The deprecation
warning was active since #16061 was merged, i.e. in 6.2.beta8
(2014-04-14) and 6.2 (2014-05-06).
URL: http://trac.sagemath.org/16106
Reported by: skropf
Ticket author(s): Sara Kropf, Clemens Heuberger
Reviewer(s): Daniel Krenn
commit 8b9b5f856800a27328a37250b4a30c7241fcfe5a
Merge: 30db7a2 1197483
Author: Release Manager
Date: Wed Jul 29 00:50:35 2015 +0200
Trac #18950: Remove make_dlxwrapper from the sage namespace
{{{make_dlxwrapper}}} is used for creating a dlx_solver from a pickled
list:
{{{
$ sage -grep make_dlxwrapper
sage/combinat/matrices/all.py:from dancing_links import make_dlxwrapper
sage/combinat/matrices/dancing_links.pyx: sage: x =
make_dlxwrapper(dumps(rows))
sage/combinat/matrices/dancing_links.pyx: sage: print
make_dlxwrapper(dumps(rows)).__str__()
sage/combinat/matrices/dancing_links.pyx: sage: x =
make_dlxwrapper(dumps(rows))
sage/combinat/matrices/dancing_links.pyx: return
sage.combinat.matrices.dancing_links.make_dlxwrapper,
(dumps(self.rows),)
sage/combinat/matrices/dancing_links.pyx:def make_dlxwrapper(s):
sage/combinat/matrices/dancing_links.pyx: sage: x =
make_dlxwrapper(dumps(rows))
}}}
This is a follow-up for #11814.
URL: http://trac.sagemath.org/18950
Reported by: slabbe
Ticket author(s): Sébastien Labbé
Reviewer(s): Jeroen Demeyer
commit 30db7a2328eee696c4d9e5f99f87c31ba64171eb
Merge: 302e07a 8d86cb3
Author: Release Manager
Date: Wed Jul 29 00:50:29 2015 +0200
Trac #18901: Bug in continued fractions of real literal
As reported in #14567, `continued_fraction` fails for real literals
{{{
sage: continued_fraction_list(1.575709393346379)
Error in lines 1-1
Traceback (most recent call last):
...
ValueError: does not know how to compute the continued fraction of
1.57570939334638
}}}
URL: http://trac.sagemath.org/18901
Reported by: vdelecroix
Ticket author(s): Vincent Delecroix
Reviewer(s): Sébastien Labbé
commit 302e07a2097ee0e7fabda8a42909b2cd16602f51
Merge: b0c423f dcdfd06
Author: Release Manager
Date: Wed Jul 29 00:48:33 2015 +0200
Trac #11814: Catch and fix the segmentation fault in dlx_solver
On a 64-bit Gentoo Linux system running sage-4.7.2.alpha2:
{{{
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search()
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0
x31)[0x7f6c37015e02]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0x7f
6c37015e34]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handl
er+0x20c)[0x7f6c37015a82]
/lib/libpthread.so.0(+0xf400)[0x7f6c3c26e400]
/usr/local/src/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/
combinat/matrices/dancing_links.so(+0x738b)[0x7f6c1612f38b]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x4c32)[0x7f6c3c55d842]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCode+0x32)[0x7f6c3c55f912]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x4ccb)[0x7f6c3c55d8db]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x5a8a)[0x7f6c3c55e69a]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_Ev
alCode+0x32)[0x7f6c3c55f912]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_Fil
eExFlags+0xb0)[0x7f6c3c581d20]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_Sim
pleFileExFlags+0xdf)[0x7f6c3c58275f]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(Py_Main+0
xb23)[0x7f6c3c58fa23]
/lib/libc.so.6(__libc_start_main+0xe6)[0x7f6c3b897ba6]
python[0x4006e9]
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
}}}
Note that this behaviour is actually documented in
`sage/combinat/tiling.py`:
{{{
def is_suitable(self):
r"""
Return whether the volume of the box is equal to sum of the
volume
of the polyominoes and the number of rows sent to the DLX solver
is
larger than zero.
If these conditions are not verified, then the problem is not
suitable
in the sense that there are no solution.
.. NOTE::
The DLX solver throws a Segmentation Fault when the
number of rows is zero::
sage: from sage.combinat.matrices.dancing_links import
dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search() # not tested
BOOM !!!
}}}
For sage-on-gentoo, there is an assertion failure:
{{{
sage: x = dlx_solver(rows)
python2.7: sage/combinat/matrices/dancing_links_c.h:217: void
dancing_links::setup_columns(): Assertion `nr_columns > 0' failed.
/usr/lib64/libcsage.so(print_backtrace+0x24)[0x7fea73a945f7]
/usr/lib64/libcsage.so(sigdie+0x1d)[0x7fea73a94687]
/usr/lib64/libcsage.so(sage_signal_handler+0x157)[0x7fea73a94822]
/lib64/libpthread.so.0(+0xfee0)[0x7fea79206ee0]
/lib64/libc.so.6(gsignal+0x35)[0x7fea78ea5ee5]
/lib64/libc.so.6(abort+0x186)[0x7fea78ea7896]
/lib64/libc.so.6(__assert_fail+0xf5)[0x7fea78e9e7a5]
/usr/lib64/python2.7/site-packages/sage/combinat/matrices/dancing_links.
so(+0x855d)[0x7fea4e73255d]
}}}
Additionally, we can segfault with a different kind of trivial problem,
{{{
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: d = dlx([[]])
sage: d.search()
*boom!*
}}}
And even adding rows can be a problem... this doesn't always go boom
{{{
sage: d = dlx_solver([[0,1],[2]])
sage: d.add_rows([[0,1],[1]])
*boom!*
}}}
Actually... *why the hell* would we ever support the following:
{{{
sage: d = dlx_solver(anything)
sage: d.search()
sage: d.add_rows(anything else)
}}}
URL: http://trac.sagemath.org/11814
Reported by: jdemeyer
Ticket author(s): Sébastien Labbé
Reviewer(s): Jeroen Demeyer
commit 6390dd942ab5c913d08ba183c84be76a876baf93
Author: Nathann Cohen
Date: Tue Jul 28 22:08:26 2015 +0200
trac #18960: Strongly Regular Graphs from two-weight codes
commit e35ebe9bb554e4f00bcd0c4eabe91cb196997a1a
Author: John H. Palmieri
Date: Tue Jul 28 12:58:45 2015 -0700
trac 14243: set PYTHONNOUSERSITE=yes to avoid picking up user's Python files.
commit cf50d705fe5fc6bc1d8dc0174a93cc27fe6f783c
Merge: 7eb8510 4adcf95
Author: Nathann Cohen
Date: Tue Jul 28 21:25:10 2015 +0200
trac #18948: Merged with 6.8
commit dcdfd06c1e924a72a49cf0c13929930ddcb61e08
Author: Sébastien Labbé
Date: Tue Jul 28 21:13:16 2015 +0200
Trac #11814: Fix failing Assertion nr_columns > 0 in setup_columns()
commit b0c423f9543f4fb4518fcabbcff717f2ca60bd76
Merge: 79703ef eb01c42
Author: Release Manager
Date: Tue Jul 28 20:40:44 2015 +0200
Trac #18331: Introduce initial distribution for Markov chains
We introduce the attribute {{{FSMState.initial_probability}}}. It is the
probability of starting in this state of a Markov chain.
In {{{FiniteStateMachine.is_Markov_chain}}}, we additionally check
whether the sum of the initial probabilities over all states is one or
all initial probabilities are set to None.
URL: http://trac.sagemath.org/18331
Reported by: skropf
Ticket author(s): Sara Kropf, Clemens Heuberger
Reviewer(s): Clemens Heuberger
commit 1a30b06dc5c308107f76fa327f85e98011d72541
Author: Clemens Heuberger
Date: Tue Jul 28 12:54:22 2015 +0200
Trac #16133: remove three further instances of FSMOldProcessOutput
commit 6b3172e064b86be2af1b9e4ab72e4f92627c4733
Author: Clemens Heuberger
Date: Tue Jul 28 12:51:45 2015 +0200
Trac #16133: Three docstrings: command instead of description
commit ae135097e391fcb2d480719e2a726894881b187b
Merge: e2fcf3b 24f7b3b
Author: Clemens Heuberger
Date: Tue Jul 28 12:48:23 2015 +0200
Trac #16133: Merge #16106
commit 24f7b3bca8846f551595dc5cd6864be61ad03e48
Author: Clemens Heuberger
Date: Tue Jul 28 11:47:59 2015 +0200
Trac #16106: remove further occurrences of FSMOldCodeTransducerCartesianProduct
commit 4a832851eb3086e6bafd59778b9062864d292561
Merge: 5f45124 7eb8510
Author: Clemens Heuberger
Date: Tue Jul 28 11:46:43 2015 +0200
Merge tag '6.8' into fsm/cartesian-product-intersection-no-deprecation
Sage version 6.8
commit 79703efc9a66ecd0475610467fc2ea92a01646dc
Merge: 7f4edff 0304d9f
Author: Release Manager
Date: Mon Jul 27 17:16:38 2015 +0200
Trac #18868: a MemoryAllocator object for easier Cython memory management
This is a re-implementation of an example appearing in Cython's
documentation (see bottom of [1]).
The idea is simple: an object has a `.malloc` method, and returns arrays
of memory. When that object is garbage-collected, the memory it
allocated is automatically freed.
This makes it much easier to deal with C pointers in Cython code, which
must be freed before any 'return' and whenever an exception can be
raised.
As an illustration of how useful this can be, I removed a *lot* of graph
code.
Nathann
[1] http://docs.cython.org/src/tutorial/memory_allocation.html
URL: http://trac.sagemath.org/18868
Reported by: ncohen
Ticket author(s): Nathann Cohen, Jeroen Demeyer
Reviewer(s): Jeroen Demeyer, Volker Braun
commit cfbc7daccfee560158f7d52a9aa0e00dfeb7d868
Author: Jori Mäntysalo
Date: Mon Jul 27 14:52:14 2015 +0300
Faster is_lattice().
commit 7f4edffef6179b077480d865b54f37ee3aa8781e
Merge: 8a5edad 3b9cb9c
Author: Release Manager
Date: Mon Jul 27 01:50:37 2015 +0200
Trac #18949: a doc typo in graph.py
let us correct that typo
URL: http://trac.sagemath.org/18949
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Nathann Cohen
commit 8a5edad209fbd8732bb32dbb6f23d6af2deccdb0
Merge: bd1cc60 1662110
Author: Release Manager
Date: Mon Jul 27 01:50:31 2015 +0200
Trac #18943: typo in infinity crystal
let us correct a typo there, plus a few pep8/pyflakes details
URL: http://trac.sagemath.org/18943
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Travis Scrimshaw
commit bd1cc60426529b6c3aa0f6fb7f6aaac0df3316b2
Merge: 1e4a91f 8688fd9
Author: Release Manager
Date: Mon Jul 27 01:50:27 2015 +0200
Trac #18925: Poset documentation polishing: covers
Do some polishing to `upper_covers()`, `cover_relations_iterator()` and
so on at `posets.py`.
URL: http://trac.sagemath.org/18925
Reported by: jmantysalo
Ticket author(s): Jori Mäntysalo
Reviewer(s): Travis Scrimshaw
commit 1e4a91fe627ebe1a109686f5eb7acc49eec5e355
Merge: be37bdb ce9d265
Author: Release Manager
Date: Mon Jul 27 01:50:22 2015 +0200
Trac #18864: New method for the eccentricity of undirected graphs
This patch implements the algorithm proposed in [1] for computing the
eccentricity of all vertices of a connected undirected unweighted graph.
It can be faster than the standard algorithm.
{{{
sage: from sage.graphs.distances_all_pairs import eccentricity
sage: G = graphs.PetersenGraph()
sage: %time _= eccentricity(G, method='standard')
CPU times: user 299 µs, sys: 75 µs, total: 374 µs
Wall time: 361 µs
sage: %time _= eccentricity(G, method='bounds')
CPU times: user 218 µs, sys: 29 µs, total: 247 µs
Wall time: 235 µs
sage: G = graphs.RandomBarabasiAlbert(10000,2)
sage: %time _= eccentricity(G, method='standard')
CPU times: user 2.78 s, sys: 7.8 ms, total: 2.78 s
Wall time: 2.79 s
sage: %time _= eccentricity(G, method='bounds')
CPU times: user 1.66 s, sys: 8.06 ms, total: 1.67 s
Wall time: 1.67 s
}}}
Similar method for directed graphs and weighted (di)graphs can be the
object of future tickets.
----
[1] F. W. Takes and W. A. Kosters. Computing the eccentricity
distribution of large graphs. *Algorithms* 6:100-118 (2013)
http://dx.doi.org/10.3390/a6010100
URL: http://trac.sagemath.org/18864
Reported by: dcoudert
Ticket author(s): David Coudert
Reviewer(s): Michele Borassi
commit be37bdb2af7dab8765c4a557def9cf3ea497c1a1
Merge: 745a19d a5ec517
Author: Release Manager
Date: Mon Jul 27 01:50:18 2015 +0200
Trac #18791: Matroid k-connectivity
Decide if a matroid is k-connected using matroid intersection.
URL: http://trac.sagemath.org/18791
Reported by: chaoxu
Ticket author(s): Chao Xu
Reviewer(s): Rudi Pendavingh
commit 745a19ded913bf620074bb3e0d2f523fe99d9bff
Merge: a499206 38d4de5
Author: Release Manager
Date: Mon Jul 27 01:50:13 2015 +0200
Trac #17485: Poset: Documentation of characteristic_polynomial
Documentation says first "Return the characteristic polynomial of a
'''graded''' poset - -", then later "If P is a '''graded poset with - -
a unique minimal element'''" and the function can throw "the poset
should be '''ranked'''". Somebody understanding what is characteristic
polynomial should check this.
Also the list of poset functions at the beginning of the file does not
contain this function.
URL: http://trac.sagemath.org/17485
Reported by: jmantysalo
Ticket author(s): Jori Mäntysalo
Reviewer(s): Frédéric Chapoton
commit a499206775e25101116f7f120f99e484b69d94f2
Merge: 9f03cc2 bd1d6eb
Author: Release Manager
Date: Mon Jul 27 01:50:08 2015 +0200
Trac #18947: Add a -fix-pkg-checksums argument to sage
The 'sage-fix-pkg-checksums' utility is not (yet) available as an option
of 'sage'. This branch fixes it.
Nathann
URL: http://trac.sagemath.org/18947
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Sébastien Labbé
commit 9f03cc29962556d31299537fd6af8e55a287748e
Merge: 16c5a77 37011a4
Author: Release Manager
Date: Mon Jul 27 01:50:04 2015 +0200
Trac #18926: Auto-generated index of functions
This branch implements a new function named {{{gen_rest_table_index}}}
which generates an index of the functions given as arguments.
It can also generate the list of all methods of a given class `A`.
With this functions, it is then very easy to add an index of functions
in a Sage module, that does not have to be kept updated manually.
Nathann
URL: http://trac.sagemath.org/18926
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Johan Sebastian Rosenkilde Nielsen
commit 16c5a772d123eab866fecbe5eecf6acc055738a4
Merge: 4577fde a7b60c5
Author: Release Manager
Date: Mon Jul 27 01:50:00 2015 +0200
Trac #18923: Remove flag METH_OLDARGS
It's deprecated since
[https://www.python.org/download/releases/2.4.1/notes/#id160 Python 2.2]
and has been removed in [https://docs.python.org/3.0/whatsnew/3.0.html
#build-and-c-api-changes Python 3].
URL: http://trac.sagemath.org/18923
Reported by: aapitzsch
Ticket author(s): André Apitzsch
Reviewer(s): Jeroen Demeyer
commit 4577fdef763eebe489c4cb7d91384ec421a66536
Merge: 85339c8 299bc40
Author: Release Manager
Date: Mon Jul 27 01:49:54 2015 +0200
Trac #18906: Refactor min spanning tree
Solve some strange behaviors / bugs in minimum spanning tree routines.
Usually, if the graph is weighted, the weight is ignored, and the
`weight_function` argument is used. If this argument is not provided,
the (rather counterintuitive) behavior is to set all weights to 1 (so
that any spanning tree can be outputted). However, if Kruskal algorithm
is used, and `check` is set to `True`, then edge weights are used,
instead.
{{{
sage: g = Graph(weighted=True)
sage: g.add_edges([[0,1,1],[1,2,1],[2,0,10]])
sage: g.min_spanning_tree(algorithm='Kruskal')
[(0, 1, 1), (0, 2, 10)]
sage: g.min_spanning_tree(algorithm='Prim_fringe')
[(0, 1), (0, 2)]
sage: g.min_spanning_tree(algorithm='Prim_edge')
[(0, 1, 1), (0, 2, 10)]
sage: sage: g.min_spanning_tree(algorithm='Kruskal', check=True)
[(0, 1, 1), (1, 2, 1)]
}}}
This example also shows that the outputs are different.
Moreover, NetworkX algorithm does not work:
{{{
sage: g.min_spanning_tree(algorithm='NetworkX')
------------------------------------------------------------------------
---
TypeError Traceback (most recent call
last)
in ()
----> 1 g.min_spanning_tree(algorithm='NetworkX')
/home/michele/Programmi/sage/local/lib/python2.7/site-
packages/sage/graphs/generic_graph.pyc in min_spanning_tree(self,
weight_function, algorithm, starting_vertex, check)
3433 import networkx
3434 G = networkx.Graph([(u, v,
dict(weight=weight_function((u, v)))) for u, v, l in
self.edge_iterator()])
-> 3435 return list(networkx.mst(G))
3436 else:
3437 raise NotImplementedError("Minimum Spanning Tree
algorithm '%s' is not implemented." % algorithm)
TypeError: 'module' object is not callable
}}}
This ticket will change this behavior, by defining a specific order in
the choice of weights:
* if the function weight_function is provided, it is used as default;
* if the function weight_function is None (default) and the graph is
weighted, the edge weights are used;
* otherwise, all weights are set to 1.
Moreover, it will fix NetworkX problems, and it will standardize the
output.
Finally, it will modify Kruskal algorithm as follows:
* now, the input can only be an undirected graph, so that the behavior
is much more clear, and the documentation becomes much smaller;
* we moved the code to remove self-loops and multiple edges in a
separate routine, because it will be used by Boost.
This is a first step before the inclusion of Boost minimum spanning tree
algorithms.
URL: http://trac.sagemath.org/18906
Reported by: borassi
Ticket author(s): Michele Borassi
Reviewer(s): David Coudert
commit 85339c8adc360494531a8fb9d25646ff302850eb
Merge: 54ef590 1ccf786
Author: Release Manager
Date: Mon Jul 27 01:49:50 2015 +0200
Trac #18898: Fix sorting of riggings when doing complement_rigging
The following does not sort the riggings, breaking an internal
assumption of rigged configurations:
{{{
sage: RC = RiggedConfigurations(['D',4,1], [[2,1], [2,1], [2,3]])
sage: x = RC(partition_list=[[1], [1,1], [1], [1]], rigging_list=[[0],
[2,1], [0], [0]])
sage: x.complement_rigging(True)
0[ ]0
2[ ]0
2[ ]1
0[ ]0
0[ ]0
}}}
URL: http://trac.sagemath.org/18898
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): Anne Schilling
commit 54ef590ebcc7ba9d2aaa1b3cde581fdd6b2c04d8
Merge: f347008 a567eda
Author: Release Manager
Date: Sun Jul 26 16:18:30 2015 +0200
Trac #18871: MILP formulation for cutwidth
This ticket adds a MILP formulation for computing the cutwidth of
graphs. This method has no limit on the size of the input graph, but it
is slow. It also enables to compare results.
URL: http://trac.sagemath.org/18871
Reported by: dcoudert
Ticket author(s): David Coudert
Reviewer(s): Nathann Cohen
commit f34700819fc9eec899ab25dda571c166d56e72ef
Merge: 9a1899b aa93226e
Author: Release Manager
Date: Sun Jul 26 16:18:20 2015 +0200
Trac #18812: latte_int: count integer points
Exposes the counting of the integer points of a polytope.. Mostly a
copy/paste from `ehrhart_polynomial`.
This branch also adds a `file_output` optional flag to
`cdd_Hrepresentation` and `cdd_Vrepresentation`. The functions calling
external executable already contain sufficiently non-mathematical code.
Nathann
URL: http://trac.sagemath.org/18812
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Jeroen Demeyer, Dima Pasechnik
commit 9a1899b3424405220579cd4c22c9569f48f77f43
Merge: f1e2907 f7efbfe
Author: Release Manager
Date: Sun Jul 26 16:18:14 2015 +0200
Trac #18583: Clean up PARI declarations
We should really clean up the declarations in `sage/libs/paridecl.pxd`,
analogous to what has been done for `gmp` for example.
This also fixes the unneeded linking of `pari` in the following Cython
extensions:
{{{
src/build/cythonized/sage/rings/number_field/totallyreal.c
src/build/cythonized/sage/rings/padics/common_conversion.c
src/build/cythonized/sage/rings/padics/padic_capped_absolute_element.c
src/build/cythonized/sage/rings/padics/padic_capped_relative_element.c
src/build/cythonized/sage/rings/padics/padic_fixed_mod_element.c
src/build/cythonized/sage/rings/real_double.c
}}}
URL: http://trac.sagemath.org/18583
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Jean-Pierre Flori
commit f1e2907af0c23fa21c6bece5401bd201133ffe2c
Merge: b41c808 9f3b7e7
Author: Release Manager
Date: Sun Jul 26 16:18:08 2015 +0200
Trac #15463: Implement crystal morphisms, subcrystals, and virtual crystals
This implements:
- Crystal morphisms (usual, twisted, and virtual).
- Subcrystals, so we no long have to do the subset workaround in
`digraph()`.
- Virtual crystals, so we can now view the elements in the virtual
crystal as a crystal graph.
This also reworks `DirectSumOfCrystals` and `TensorProductOfCrystals` to
make them associative as constructions.
After this, we will be able to do coercions between crystals.
URL: http://trac.sagemath.org/15463
Reported by: tscrim
Ticket author(s): Travis Scrimshaw
Reviewer(s): Anne Schilling
commit b41c808e8ad2a4ef8439e536c1f7a4d4334d0d67
Merge: ee47081 96b61e3
Author: Release Manager
Date: Sun Jul 26 16:18:01 2015 +0200
Trac #14585: Make lazy_format and lazy_string faster
At [https://groups.google.com/forum/?fromgroups=#!topic/sage-devel
/Gnw389Bd-0k sage-devel], Nils suggests to use some kind of lazy object
for the error messages of errors that are deeply buried in the coercion
model.
This approach is similar to what we already do with
`sage.structure.misc.AttributeErrorMassage`. However, this is
specifically restricted to error messages of attribute errors. In the
more general case, it makes sense to use either
`sage.misc.lazy_format.LazyFormat` or
`sage.misc.lazy_string.lazy_string`. The latter seems to be faster,
according to these timings that are according to Nils' example:
{{{
sage: from sage.misc.lazy_string import lazy_string
sage: f = lambda op,A,B:"unsupported operand parent(s) for '%s': '%s'
and '%s'"%(op,A,B)
sage: R = GF(5)
sage: S = GF(3)
sage: %timeit Exception(lazy_string(f, '+', R, S))
1000000 loops, best of 3: 1.47 us per loop
sage: lazy_string(f, '+', R, S)
l"unsupported operand parent(s) for '+': 'Finite Field of size 5' and
'Finite Field of size 3'"
sage: %timeit Exception("unsupported operand parent(s) for '%s': '%s'
and '%s'"%('+', R, S))
100000 loops, best of 3: 5.04 us per loop
sage: from sage.misc.lazy_format import LazyFormat
sage: ErrMess = LazyFormat("unsupported operand parent(s) for '%s': '%s'
and '%s'")
sage: %timeit Exception(ErrMess%('+', R, S))
10000 loops, best of 3: 23.1 us per loop
sage: ErrMess%('+', R, S)
unsupported operand parent(s) for '+': 'Finite Field of size 5' and
'Finite Field of size 3'
}}}
We're better off making a fresh `LazyFormat` object every time, due to
an inefficiency in the copying operation required for rebinding such an
object:
{{{
sage: %timeit LazyFormat("unsupported operand parent(s) for '%s': '%s'
and '%s'")%('+', R, S)
1000000 loops, best of 3: 2.08 µs per loop
}}}
Luckily, present use of `LazyFormat` follows this pattern.
So, it would already make sense to replace all error messages using
string formatting by a call to `lazy_string`, while `LazyFormat` seems
to be quite sluggish.
Two tasks:
1. Make `lazy_string` and `LazyFormat` a lot faster (perhaps by using
Cython)
2. Use it for errors raised when trying to find coercions. The problem
is particularly urgent if the string representation of an object is
difficult to compute.
'''__Note__'''
For the second task, we meanwhile have #14592
Apart from making coercion faster, there is the following problem that
we would fix as well. Consider creation of a parent. It may happen that
relatively early during initialisation, a coercion is needed, but only
later, the string representation of the parent will become available.
Hence, if there is an error raised (and caught) inside of the coercion
system that relies on the string representation of the parent, then we
are in trouble.
__Apply__
[attachment:trac14585-cythoned_lazy_string.patch]
URL: http://trac.sagemath.org/14585
Reported by: SimonKing
Ticket author(s): Simon King, Jeroen Demeyer
Reviewer(s): Simon King, Jeroen Demeyer
commit ee47081e36cb966c64ef4976717dbe1e43712e8f
Merge: 7eb8510 09cba3c
Author: Release Manager
Date: Sun Jul 26 16:17:56 2015 +0200
Trac #7744: STL, AMF, X3D and PLY export for 3D printing
{{{
def surface_to_stl(surface):
"""
Return an STL representation of the surface.
INPUT:
- `surface` -- any surface, eg. output of a 3d plot function.
OUTPUT:
A string that represents the surface in the STL format.
COMMENTS:
(1) You must view the surface before plotting it.
Otherwise, this will not work.
(2) In order to do 3d printing with this, you will need to
convert it into gcode. Skeinforge is an open-source
program that can do this.
(3) The size of the surface is not normalized in export.
Sage's units will become the units of the STL
description. These seem to be ~0.05 cm (at least when
printed using skeinforge -> replicatorg -> hacklab.to's
cupcake).
(4) Be aware of the overhang limits of your 3d printer;
most printers can only handle an overhang of Pi/2 (45*)
before your model will start drooping.
EXAMPLES:
sage: x,y,z = var('x,y,z')
sage: a = implicit_plot3d(x^2+y^2+z^2-9, [x,-5,5],
[y,-5,5],[z,-5,5])
sage: a
sage: f=file.open("foo.stl",'w')
sage: f.write(surface_to_stl(a))
sage: f.close()
"""
out = "solid mathsurface\n"
for i in surface.face_list():
n = ( i[1][1]*i[2][2] - i[2][1]*i[1][2],
i[1][2]*i[2][0] - i[1][0]*i[2] 2],
i[1][0]*i[2][1] - i[2][0]*i[1][1] )
abs = (n[0]^2+n[1]^2+n[2]^2)^0.5
n= (n[0]/abs,n[1]/abs,n[2]/abs)
out += " facet normal " + repr(n[0]) + " " + repr(n[1]) + "
" + repr(n[2])
out += " outer loop\n"
out += " vertex " + repr(i[0][0]) + " " + repr(i[0][1]) + "
" + repr(i[0][2]) + "\n"
out += " vertex " + repr(i[1][0]) + " " + repr(i[1][1]) + "
" + repr(i[1][2]) + "\n"
out += " vertex " + repr(i[2][0]) + " " + repr(i[2][1]) + "
" + repr(i[2][2]) + "\n"
out += " endloop\n"
out += " endfacet\n"
out += "endsolid surface\n"
return out
}}}
URL: http://trac.sagemath.org/7744
Reported by: colah
Ticket author(s): Christopher Olah, Frédéric Chapoton
Reviewer(s): Miguel Marco
commit 7eb8510dacf61b691664cd8f1d2e75e5d473e5a0
Author: Volker Braun
Date: Sun Jul 26 15:34:41 2015 +0200
Updated Sage version to 6.8
commit 4adcf950cd34c28460383468b17b59c695633f01
Author: Nathann Cohen
Date: Sun Jul 26 12:56:23 2015 +0200
trac #18948: Two missing graphs
commit bd1d6ebb6136c11fa14cdb3545e4f429782d244e
Author: Sébastien Labbé
Date: Sun Jul 26 08:14:58 2015 +0200
Trac #18947: Move -fix-pkg-checksums in making packages section of sage -advanced
commit 8d86cb325724472a7fe55e1a351ab5958b474ddf
Author: Sébastien Labbé
Date: Sat Jul 25 22:07:40 2015 +0200
Trac #18901: Fix ReST syntax
commit 11974832bf3c6d13ed758a109f537033f56394fb
Author: Sébastien Labbé
Date: Sat Jul 25 21:51:40 2015 +0200
18950: Remove make_dlxwrapper from sage namespace
commit e2b82a4b7b035d84955c3c15a41cd740fc050eaf
Author: Sébastien Labbé
Date: Sat Jul 25 14:05:27 2015 +0200
Fix doctest in games/quantumino.py
commit 56c74ed227fb8def88644a7e2371bd33701d8f28
Author: Sébastien Labbé
Date: Sat Jul 25 13:47:40 2015 +0200
Better __repr__ for dancing links, added rows method
commit 3a3dd8be8ff50d04bc84dc60401ea9af11871af6
Author: Sébastien Labbé
Date: Sat Jul 25 13:04:16 2015 +0200
Removed cimport Integer from dancing links
commit 392b62c70d342679c41799e0b45857c537ad8a8e
Author: Jeroen Demeyer
Date: Sat Jul 25 12:37:42 2015 +0200
Simplify dancing links code
commit 549575955408f4ca4c8c24341c6c8149d14e4a1d
Author: Sébastien Labbé
Date: Sat Jul 25 11:33:30 2015 +0200
Trac #11814: Fix segmentation Fault raised by an assert
commit 38d4de5f072cb50711368d3e1720e5277b1b54db
Author: Jori Mäntysalo
Date: Sat Jul 25 10:56:33 2015 +0300
"to to" -> "to".
commit 35f074c4a0a48af5583582e25fe76d0483ca7778
Author: Sébastien Labbé
Date: Sat Jul 25 09:40:33 2015 +0200
Trac #11814: Added not tested flag for segmentation fault
commit 3b9cb9c7eccebbe96da6e08a0fd779fa53842ae6
Author: Frédéric Chapoton
Date: Fri Jul 24 21:20:41 2015 +0200
just a few details in graph.py
commit 7f538952608ae5f884625148f2d47f67f2c3cd81
Author: Jori Mäntysalo
Date: Fri Jul 24 22:17:42 2015 +0300
Typo corrected.
commit a0173e2789e7a8f79c88a77d753b48788f183e65
Author: Nathann Cohen
Date: Fri Jul 24 17:38:54 2015 +0200
trac #18948: Strongly Regular Graphs database
commit dbd6c1ab34c7c9a40d1cbec975dbddc3ab21c2ec
Author: Nathann Cohen
Date: Fri Jul 24 18:31:27 2015 +0200
trac #18947: Add a -fix-pkg-checksums argument to sage
commit 25741dfc1c52709faa59042024248824247275f4
Merge: 3648190 8ee8dd8
Author: Sébastien Labbé
Date: Fri Jul 24 15:12:16 2015 +0200
Trac #11814: Merge with 6.8.rc1
commit 37011a4187cbd3d91ca68224a82151666682dd67
Author: Nathann Cohen
Date: Fri Jul 24 15:08:45 2015 +0200
trac #18926: Cleaning
commit 8ee8dd81d654d6d68baa335b15251a2427c3dc8e
Author: Sébastien Labbé
Date: Fri Jul 24 14:59:10 2015 +0200
Trac #11814: Catch the segmentation fault in dancing links
commit 62fae3d72ebc65be67fd72a426f744a581dda42d
Author: Johan S. R. Nielsen
Date: Fri Jul 24 14:36:39 2015 +0200
More reviewer^2 comments
commit 978870cf7157ac3b65e98aad4aa6483be9547971
Author: Jori Mäntysalo
Date: Fri Jul 24 15:27:49 2015 +0300
Added a type checking for the poset.
commit 3a9e3b5cbb00db4ffa5f97542ce3d027b19ee006
Author: Johan S. R. Nielsen
Date: Fri Jul 24 14:07:57 2015 +0200
Yet another docstring fix