Trac #13850: implement a generic interface for boolean polynomial solving
Merge branch 'master' into u/Bouillaguet/ticket/13850
fix doctest syntax for optional packages
is_linear_extension on posets is rather liberal
is_linear_extension on posets is rather liberal : updating linear_extensions.py
trac #15442: MILP solver CBC  : undefined symbol: dgetrf_
trac #15480: Words.__eq__ returns wrong answers
trac #15480: Two additional doctests
Editting comments and adding warning to class documentation
Fixing a typo
trac #15491: directed immutable graphs report twice too many edges
trac #15491: addressing the reviewer's comments
Trac #15313: is_linear_extension on posets is rather liberal

{{{
sage: P = Poset((divisors(12), attrcall("divides")), facade=True,
linear_extension=True)
sage: list(P)
[1, 2, 3, 4, 6, 12]
sage: P.is_linear_extension([1,2,4,3,6,12,1337])
True
sage: P.is_linear_extension([1,2,4,3,6,666,12,1337])
True
}}}

At the moment I am not planning to do anything about it, since it would
probably involving seeing what other parts of the code using
{{{is_linear_extension}}} and how they are using (my bets that this
error doesn't cause any other problems in the code, and fixing it would
likely incur some speed penalty so one should keep the old functionality
accessible).

URL: http://trac.sagemath.org/15313
Reported by: darij
Ticket author(s): Nathann Cohen
Reviewer(s):
Trac #15480: Words.__eq__ returns wrong answers

Right now equality between sets of words only compares the alphabets:

{{{
sage: Words(3, 10) == Words(3,900)
True
sage: Words(2, finite=False) == Words(2)
True
sage: Words(2) == Words(2,30)
True
sage: Words(10,0) == Words(20,0)
False
sage: WordPaths('abcd') == Words("abcd",3)
True
}}}

I am not proud of this patch's code, but I see NO other way to fix all
these incorrect answers without rewriting the class hierarchy. The fact
that a class of finite words is an instance (i.e. it inherits) from a
class of infinite words makes it really hard to implement `O_o`

{{{
sage: isinstance(Words(4,30), type(Words(3)))
True
}}}

You cannot be sure, when implementing the `__eq__` method of
`Words_all`, that self really represents an infinite class of words.

Besides, the old code reads:

{{{
        if isinstance(other, Words_all):
            return self.alphabet() == other.alphabet()
        else:
            return NotImplemented
}}}

I haven't been able to guess when `not (type(self) is type(other))` does
not mean that the two classes should not be reported as equal.
Though the old code seems to imply that this can happen.

If this can happen we need to add a doctest somewhere.

Nathann

URL: http://trac.sagemath.org/15480
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Andrew Mathas
Trac #15491: directed immutable graphs report twice too many edges

As reported on #15278 :

{{{
sage: g=digraphs.RandomDirectedGNP(10,.3)
sage: gi=DiGraph(g,data_structure="static_sparse")
sage: print gi.size(), len(gi.edges())
68 34
}}}

Simplest bug eve : Sage was taught to return the wrong thing. The sum of
all arcs in the digraph, plus the sum of all arcs in the reversed
digraph. That's clearly more than necessary `:-P`

Sorryyyyyyyyyyyyyyyyyyyy !!

Nathann

URL: http://trac.sagemath.org/15491
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Simon King
Trac #13850: PolynomialSequence.solve()

Polynomial sequences over GF(2) should have a solve method which
supports solving via

 * Gröbner bases (!PolyBoRi)
 * SAT solving (!CryptoMiniSat and friends)
 * exhaustive search (FES library)
 * (Mixed Integer Programming) (Sage's MIP stuff and SCIP)

All these interfaces exist, they only need to be properly exposed.

URL: http://trac.sagemath.org/13850
Reported by: malb
Ticket author(s): Charles Bouillaguet
Reviewer(s): Martin Albrecht
Trac #15442: MILP solver CBC  : undefined symbol: dgetrf_

As reported by Thierry Monteil :

{{{
sage: graphs.PetersenGraph().dominating_set(solver="Coin",verbose=2)
ImportError: /home/ncohen/.Sage/local/lib/libCoinUtils.so.3: undefined
symbol: dgetrf_
}}}

Looks like {{{dgetrf}}} is defined in LAPACK. I added it to the
dependencies and it now works. No idea why it changed, and in particular
I'll be quite happy to see all optional packages automatically tested at
each release `:-P`

Nathann

URL: http://trac.sagemath.org/15442
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s): Thierry Monteil