Trac #17163: Speed improvement for DiGraph.in_degree

As reported by Jori, the following is... unexpected:

{{{
sage: g = digraphs.RandomDirectedGNP(300,.2)
sage: %timeit g.sinks() # vertices of outdegree 0
1000 loops, best of 3: 376 µs per loop
sage: %timeit g.sources() # vertices of indegree 0
100 loops, best of 3: 7.78 ms per loop
}}}

With this patch:
{{{
sage: g = digraphs.RandomDirectedGNP(300,.2)
sage: %timeit g.sinks() # vertices of outdegree 0
1000 loops, best of 3: 370 µs per loop
sage: %timeit g.sources() # vertices of indegree 0
1000 loops, best of 3: 361 µs per loop
}}}

Cause:

This is because the function `in_degree` was not implemented at the data
structure level, but "abstractly" by iterating over all incoming edges
of a vertices and counting them. This is bad, especially since any
sensible backends already stores that information.

What the branch does:

1) Add a `in_degree` function in the CGraph backend.

2) Add a `in_degree` and `out_degree` (empty) function in the
`GenericGraph` backend (the only point is to write somewhere that the
`in_degree/out_degree` functions should be implemented by all graph
backends

3) Add a `in_degree/out_degree` function to the NetworkX backend. This
backend is only used in one doctest, and this is the only backend that
did not have this function.

4) Because all backends now have the `in_degree/out_degree` functions,
it is now useless to 'check if the backend has the function' before
calling it. As a result the code of `DiGraph.in_degree/out_degree` is
simplified.

Nathann

URL: http://trac.sagemath.org/17163
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): David Coudert
Trac #17118: Added multiplier computation to affine morphism

Implement function to compute multipliers for periodic points of affine
morphisms.

URL: http://trac.sagemath.org/17118
Reported by: gjorgenson
Ticket author(s): Grayson Jorgenson
Reviewer(s): Ben Hutz
Trac #16233: Exceptions ignored by LeanMatrix operations

Currently, various matroid operations do not stop on
!KeyboardInterrupt()

{{{
^CException KeyboardInterrupt: KeyboardInterrupt() in
'sage.matroids.lean_matrix.QuaternaryMatrix.set' ignored
^CException KeyboardInterrupt: KeyboardInterrupt() in
'sage.matroids.lean_matrix.QuaternaryMatrix.add_multiple_of_row_c'
ignored
}}}

URL: http://trac.sagemath.org/16233
Reported by: yomcat
Ticket author(s): Jeroen Demeyer
Reviewer(s): Volker Braun
Trac #17104: IncidenceStructure.relabel() (no arguments)

One can relabel a graph to 0,...,n-1 by just calling `.relabel()`, and I
found myself typing `IS.relabel({v:i for i,v in
enumerate(IS.ground_set())})` very often these last days.

With this patch one can relabel the point automatically to `0,...,n-1`.

Nathann

URL: http://trac.sagemath.org/17104
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Vincent Delecroix
Trac #17167: Fix Cython "except" values in matroids

Matching "except" values will be required for Cython 0.22

URL: http://trac.sagemath.org/17167
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Volker Braun
Trac #17168: Fix Cython "except" values in various places

Matching "except" values will be required for Cython 0.22

See also other fixes in #11945, #16233, #17167.

URL: http://trac.sagemath.org/17168
Reported by: jdemeyer
Ticket author(s): Jeroen Demeyer
Reviewer(s): Volker Braun
Trac #17073: Documentation for Facade Sets

Nicolas,

I documented two `Poset` functions in #17051 which have a `facade`
boolean argument (the same that `Poset()` has) and added a link toward
the `Facade` module. The problem is that there is no documentation there
to find, and it would help if you could write something to say to the
new users what they need to know about `Facade` in such situations.

This page is also the page that appears first when you type "sage
facade" in google.

Thanks.

Nathann

URL: http://trac.sagemath.org/17073
Reported by: ncohen
Ticket author(s): Nicolas M. Thiéry
Reviewer(s): Jori Mäntysalo
Trac #17103: Random failure in coercion/index.rst

Somebody needs to hold a reference to `QQ^2` here
{{{
File "src/doc/en/reference/coercion/index.rst", line 300, in
doc.en.reference.coercion.index
Failed example:
    (QQ^2).get_action(QQ)
Expected:
    Right scalar multiplication by Rational Field on Vector space of
dimension 2 over Rational Field
Got:
    <repr(<sage.structure.coerce_actions.RightModuleAction at
0x7fe782827628>) failed: RuntimeError: This action acted on a set that
became garbage collected>
**********************************************************************
1 item had failures:
   1 of  98 in doc.en.reference.coercion.index
}}}

URL: http://trac.sagemath.org/17103
Reported by: vbraun
Ticket author(s): Volker Braun
Reviewer(s): Jeroen Demeyer
Trac #16917: Deprecate cuspform_lseries() and modform_lseries()

From #11631:

  the name "cuspform_lseries" is bad, since f is already a cuspform, and
we use the name "lseries" in all other places (e.g., elliptic curves,
abelian varieties), so it is hard to find. In fact, I didn't even think
to look for cuspform_lseries, instead only finding this via lots of
grepping and reading source code.

The same applies to "modform_lseries".

The goal of this ticket is to add a method lseries() to modular forms
which creates the L-function in both cases, and to deprecate the old
two.

URL: http://trac.sagemath.org/16917
Reported by: tornaria
Ticket author(s): Gonzalo Tornaría
Reviewer(s): Michael Neururer, Nicolás Sirolli
Trac #17140: Remove usage of deprecated scipy.linalg.expm2 and expm3

{{{scipy.linalg.expm2}}} and {{{scipy.linalg.expm3}}} have been
deprecated in Scipy 0.13 [0] and will be removed in a later release.
Therefore remove both from sage.

[0] http://docs.scipy.org/doc/scipy-0.14.0/reference/release.0.13.0.html
#expm2-and-expm3

URL: http://trac.sagemath.org/17140
Reported by: aapitzsch
Ticket author(s): André Apitzsch
Reviewer(s): Jeroen Demeyer
Trac #17181: Poset.__repr__ should mention the linear extension

Hello everybody !

A poset with embedded linear extension can never be equal to a "simple
poset", and users are bound to wonder someday why two apparently equal
posets are not detected as such.

With this branch, this:
{{{
sage: Poset(digraphs.Path(5),linear_extension=True)
Finite poset containing 5 elements
}}}

becomes

{{{
sage: Poset(digraphs.Path(5),linear_extension=True)
Finite poset containing 5 elements with embedded linear extension
}}}

So that it is clearer that the Poset is 'not only a poset'.

URL: http://trac.sagemath.org/17181
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Nicolas Thiery
Trac #16559: Brouwer-Van Rees version of Wilson's decomposition

Heeeeeere it is !

Nathann

URL: http://trac.sagemath.org/16559
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Vincent Delecroix
Trac #16911: Update sagenb

This ticket is for

1. updating sagenb. Corresponding upstream ticket is
https://github.com/sagemath/sagenb/pull/218
2. updating documentation inside sage to reflect the new development
model for sagenb

{{{
cd SAGE_ROOT/upstream
wget -c 'https://googledrive.com/host/0B2kYdLdBVFHIZEd4ekpjNUFBNTQ/sagen
b-0.10.8.3.tar'
git checkout -b develop ticket/16911
git trac pull 16911
../sage -i sagenb
../sage -b
}}}

----

To @vbraun: When merging this ticket, merge both this and #16396 since
sagenb upstream has changes to fix doctests in that ticket, and that
ticket in turn depends on an updated sagenb so that it can pass all
doctests.  Also close #11469 as that is incorporated here.

URL: http://trac.sagemath.org/16911
Reported by: ppurka
Ticket author(s): Punarbasu Purkayastha
Reviewer(s): Julien Puydt, Karl-Dieter Crisman
Trac #16920: New V(m,t) vectors

New V(m,t) vectors. Those guys are the fuel for the Brouwer-van Rees
construction.

Nathann

URL: http://trac.sagemath.org/16920
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Vincent Delecroix
Trac #17193: Adding a hash function to weak and strong tableaux

Currently WeakTableaux and StrongTableaux are not hashable:
{{{
sage: T = WeakTableaux(3, [5,2,1], [1,1,1,1,1,1], representation='core')
sage: t = T[0]
sage: hash(t)
------------------------------------------------------------------------
---
TypeError                                 Traceback (most recent call
last)
<ipython-input-3-36822ba665ca> in <module>()
----> 1 hash(t)

/Applications/sage/local/lib/python2.7/site-
packages/sage/structure/list_clone.so in
sage.structure.list_clone.ClonableArray.__hash__
(build/cythonized/sage/structure/list_clone.c:5686)()

/Applications/sage/local/lib/python2.7/site-
packages/sage/structure/list_clone.so in
sage.structure.list_clone.ClonableArray._hash_
(build/cythonized/sage/structure/list_clone.c:6286)()

TypeError: unhashable type: 'list'
}}}

URL: http://trac.sagemath.org/17193
Reported by: aschilling
Ticket author(s): Anne Schilling
Reviewer(s): Travis Scrimshaw
Trac #16999: Fixing documentation typo.

https://github.com/sagemath/sage/pull/24

URL: http://trac.sagemath.org/16999
Reported by: github/matsen
Ticket author(s): Erick Matsen
Reviewer(s): Robert Bradshaw
Trac #17078: Fix documentation in partition.py

There are probably other places, but at any rate we need this extra line
for it to look correct.

https://github.com/sagemath/sage/pull/26

URL: http://trac.sagemath.org/17078
Reported by: github/kcrisman
Ticket author(s): Karl-Dieter Crisman
Reviewer(s): Nathann Cohen
Trac #17162: Error in semi-symmetric graph documentation

The documentation for [http://www.sagemath.org/doc/reference/graphs/sage
/graphs/graph.html#sage.graphs.graph.Graph.is_semi_symmetric semi-
symmetric graphs] claims that the
[http://en.wikipedia.org/wiki/Gray_graph Gray graph] is the smallest
such graph, but the [http://en.wikipedia.org/wiki/Semi-symmetric_graph
Wikipedia page] referenced in the documentation does not concur.  (It
apparently is the smallest ''cubic'' such graph.)  Either way, there
needs to be a fix - on Wikipedia or, more likely, in our documentation.
(Note that the Folkman graphs is also in Sage.)

URL: http://trac.sagemath.org/17162
Reported by: kcrisman
Ticket author(s): Nathann Cohen
Reviewer(s): Karl-Dieter Crisman
Trac #17182: random spanning trees using the Aldous-Broder algorithm

This implements the Aldous-Broder algorithm that uses a random walk to
find a random spanning tree (with uniform distribution).

URL: http://trac.sagemath.org/17182
Reported by: chapoton
Ticket author(s): Frédéric Chapoton
Reviewer(s): Nathann Cohen
Trac #9827: Intermittent doctest failure in sage/interfaces/psage.py

This happens sometimes:
{{{
#!python
sage -t --long devel/sage/sage/interfaces/psage.py
**********************************************************************
File "devel/sage/sage/interfaces/psage.py", line 37, in
sage.interfaces.psage
Failed example:
    w       # long time, random output
Exception raised:
    Traceback (most recent call last):
      File "/release/buildbot/sage/sage-1/sage_upgrade_4.8/build/sage-5.
9.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line
466, in _run
        self.execute(example, compiled, test.globs)
      File "/release/buildbot/sage/sage-1/sage_upgrade_4.8/build/sage-5.
9.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line
825, in execute
        exec compiled in globs
      File "<doctest sage.interfaces.psage[3]>", line 1, in <module>
        w       # long time, random output
      File "/release/buildbot/sage/sage-1/sage_upgrade_4.8/build/sage-5.
9.beta4/local/lib/python2.7/site-packages/sage/misc/displayhook.py",
line 201, in __call__
        self.oldhook(obj)
      File "/release/buildbot/sage/sage-1/sage_upgrade_4.8/build/sage-5.
9.beta4/local/lib/python2.7/site-packages/sage/interfaces/interface.py",
line 880, in __repr__
        s =  s.replace(self._name, self.__dict__['__custom_name'])
    KeyError: '__custom_name'
**********************************************************************
}}}

See [http://groups.google.com/group/sage-release/browse_thread/thread/b2
827cba9319bfed/14beffeda6842d4b#14beffeda6842d4b this reply] (and
possible follow-ups) for batch-testing results for `psage.py`.

Distantly related: #1991.

URL: http://trac.sagemath.org/9827
Reported by: mpatel
Ticket author(s): Jeroen Demeyer
Reviewer(s): Frédéric Chapoton