Opened 4 years ago

# doctests for the english translation of the book "Calcul mathématique avec Sage" — at Version 22

Reported by: Owned by: zimmerma critical sage-8.7 doctest coverage mforets, dcoudert, nthiery, vklein, jhpalmieri Reported upstream. No feedback yet.

the purpose of this ticket is to add the doctests corresponding to the examples given in the english translation of the book "Calcul mathématique avec Sage" (see https://members.loria.fr/PZimmermann/sagebook/english.html).

Sage already includes doctests for the original version of this book (published in french in 2013). These doctests are in `src/sage/tests/french_book`, and should be updated.

We should probably wait for the final version of the book before adding/updating doctests.

bugs found:

1. Using `scipy.sparse.lil_matrix` is now broken: #23867

### comment:2 Changed 4 years ago by zimmerma

one issue we encounter is the following. The code below differs between Sage 8.0 and Sage 8.1beta3:

```   def NearlySingularMatrix(R,n):
M=matrix(R,n,n)
for i in range(0,n):
for j in range(0,n):
M[i,j]= (1+log(R(1+i)))/((i+1)^2+(j+1)^2)
return M
n=35
print NearlySingularMatrix(RDF,n).det()
```

With Sage 8.0 we get `0.0`, whereas with Sage 8.1beta3 we get `-0.0`. I thought the determinant code was deterministic, and since RDF computations follow IEEE 754, we should get a deterministic answer. How can we get different answers?

### comment:3 Changed 4 years ago by zimmerma

another issue:

```┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 8.0, Release Date: 2017-07-21                     │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: C = graphs.ChvatalGraph()
sage: from sage.graphs.graph_coloring import edge_coloring
sage: edge_coloring(C, hex_colors = True)

{'#00ffff': [(0, 6), (1, 5), (2, 8), (3, 4), (7, 11), (9, 10)],
'#7f00ff': [(0, 4), (1, 7), (2, 6), (3, 9), (5, 11), (8, 10)],
'#7fff00': [(0, 9), (1, 2), (3, 7), (4, 8), (5, 10), (6, 11)],
'#ff0000': [(0, 1), (2, 3), (4, 5), (6, 10), (7, 8), (9, 11)]}
```

With Sage 8.1beta3 we get:

```    {'#00ffff': [(0, 9), (1, 5), (2, 6), (3, 4), (7, 11), (8, 10)],
'#7f00ff': [(0, 1), (2, 8), (3, 7), (4, 5), (6, 10), (9, 11)],
'#7fff00': [(0, 4), (1, 2), (3, 9), (5, 10), (6, 11), (7, 8)],
'#ff0000': [(0, 6), (1, 7), (2, 3), (4, 8), (5, 11), (9, 10)]}
```

Is there a way to get a deterministic answer? Is there any random seed that controls the edge coloring algorithm?

### comment:4 Changed 4 years ago by zimmerma

for comment 3, I'll ask David Coudert who worked on `edge_coloring` in #22564.

Paul

### comment:6 Changed 4 years ago by dcoudert

The coloring is done with ILP and the result depends on the ILP solver. #22564 has been merged in 8.1.beta?? The patch only slightly changes the order in which constraints are added to the ILP and it is enough the get a different solution from 8.0.

```sage: from sage.graphs.graph_coloring import edge_coloring
sage: edge_coloring(C, hex_colors = True, solver='GLPK')

{'#00ffff': [(0, 9), (1, 5), (2, 6), (3, 4), (7, 11), (8, 10)],
'#7f00ff': [(0, 1), (2, 8), (3, 7), (4, 5), (6, 10), (9, 11)],
'#7fff00': [(0, 4), (1, 2), (3, 9), (5, 10), (6, 11), (7, 8)],
'#ff0000': [(0, 6), (1, 7), (2, 3), (4, 8), (5, 11), (9, 10)]}
sage: edge_coloring(C, hex_colors = True, solver='Cplex')

{'#00ffff': [(0, 6), (1, 5), (2, 3), (4, 8), (7, 11), (9, 10)],
'#7f00ff': [(0, 1), (2, 6), (3, 4), (5, 10), (7, 8), (9, 11)],
'#7fff00': [(0, 9), (1, 2), (3, 7), (4, 5), (6, 11), (8, 10)],
'#ff0000': [(0, 4), (1, 7), (2, 8), (3, 9), (5, 11), (6, 10)]}
sage: edge_coloring(C, hex_colors = True, solver='PPL')

{'#00ffff': [(0, 9), (1, 5), (2, 8), (3, 4), (6, 10), (7, 11)],
'#7f00ff': [(0, 6), (1, 7), (2, 3), (4, 5), (8, 10), (9, 11)],
'#7fff00': [(0, 4), (1, 2), (3, 9), (5, 10), (6, 11), (7, 8)],
'#ff0000': [(0, 1), (2, 6), (3, 7), (4, 8), (5, 11), (9, 10)]}
sage: edge_coloring(C, hex_colors = True, solver='Coin')

{'#00ffff': [(0, 4), (1, 5), (2, 6), (3, 9), (7, 11), (8, 10)],
'#7f00ff': [(0, 6), (1, 2), (3, 7), (4, 8), (5, 10), (9, 11)],
'#7fff00': [(0, 1), (2, 3), (4, 5), (6, 11), (7, 8), (9, 10)],
'#ff0000': [(0, 9), (1, 7), (2, 8), (3, 4), (5, 11), (6, 10)]}
sage: edge_coloring(C, hex_colors = True, solver='Gurobi')

{'#00ffff': [(0, 1), (2, 6), (3, 9), (4, 5), (7, 11), (8, 10)],
'#7f00ff': [(0, 6), (1, 7), (2, 3), (4, 8), (5, 10), (9, 11)],
'#7fff00': [(0, 4), (1, 5), (2, 8), (3, 7), (6, 11), (9, 10)],
'#ff0000': [(0, 9), (1, 2), (3, 4), (5, 11), (6, 10), (7, 8)]}
```

In doctests, you must set the solver to `GLPK`. Otherwise, the default solver is used (e.g., `Cplex` if you have it).

### comment:7 follow-up: ↓ 8 Changed 4 years ago by zimmerma

David,

1) from the trac page, #22564 has been merged in 8.0, thus the difference I see should be due to subsequent changes

2) is there any reason why the order of the constraints was changed? It makes it difficult to add doctests for this example from our book about Sage

### comment:8 in reply to: ↑ 7 Changed 4 years ago by dcoudert

David,

1) from the trac page, #22564 has been merged in 8.0, thus the difference I see should be due to subsequent changes

2) is there any reason why the order of the constraints was changed? It makes it difficult to add doctests for this example from our book about Sage

I changed the code 1) to split the graph into connected components and color them separately (should be faster), and 2) because I don't understand why we should use list comprehension for adding constraints. It was:

```    #  A vertex can not have two incident edges with the same color.
p.sum([color[R(e),i] for e in g.edges_incident(v, labels=False)]), max=1)
for v in g.vertex_iterator()
for i in range(k)]
# an edge must have a color
[p.add_constraint(p.sum([color[R(e),i] for i in range(k)]), max=1, min=1)
for e in g.edge_iterator(labels=False)]
# anything is good as an objective value as long as it is satisfiable
e = next(g.edge_iterator(labels=False))
p.set_objective(color[R(e),0])
```

Now it is:

```    # A vertex can not have two incident edges with the same color.
for v in h.vertex_iterator():
for i in range(k):
p.add_constraint(p.sum(color[R(u,v),i] for u in h.neighbor_iterator(v)) <= 1)
# Nn edge must have a color
for u,v in h.edge_iterator(labels=False):
p.add_constraint(p.sum(color[R(u,v),i] for i in range(k)) == 1)
# We color the edges of the vertex of maximum degree
for i,v in enumerate(h.neighbors(X)):
```

So the main changes are:

• use of `neighbor_iterator` instead of `edges_incident` in the first set of constraints (it has always been assumed in this method that the graph is simple)
• removal of the objective function (not needed)
• now force the coloring of the edges incident to the vertex of maximum degree (could speed up the resolution).

In fact, I bet that changing the version of `GLPK` could already change the result (e.g., faster algorithm converging to a different optimal solution). Furthermore, I assume that some internal heuristics of the solvers are randomized since we can set random seed of Cplex.

### comment:9 Changed 4 years ago by zimmerma

David, thank you for the explanation (by the way there is a typo: "Nn edge must have a color" should be "An edge...").

Since it seems impossible to have a reliable doctest for this example, we won't test it.

Last edited 2 years ago by zimmerma (previous) (diff)

### comment:10 in reply to: ↑ description Changed 4 years ago by jdemeyer

Sage already includes doctests for the original version of this book (published in french in 2013). These doctests are in `src/sage/tests/french_book`, and should be updated.

Didn't you mention at some point that you didn't care any more about these doctests? I seem to remember something along those lines...

### comment:11 Changed 4 years ago by zimmerma

Jeroen,

what I said is that there were too many changes in Sage upstream (with respect to Sage 5.9 which we used in the french book in 2013) so that we could check them (and even, sometimes, we had no chance to give our opinion on them before they were merged into Sage). Those doctests nevertheless did they job since most of the examples still run with current versions of Sage.

Now that we have updated the book to Sage 8.0, we'd like to add the (new) doctests to Sage doctests, so that the new (english) version of the book will not be obsolete too quickly.

### comment:12 follow-ups: ↓ 13 ↓ 14 ↓ 15 Changed 4 years ago by zimmerma

Nicolas Thiery just tested the doctests of our book with Sage 8.1beta5 and several do fail (while all tests pass with Sage 8.0). Here are the issues:

1) the `lil_matrix` do not work any more. Cf the example on page 299 of the english translation:

```  sage: from scipy.sparse.linalg.dsolve import *
sage: from scipy.sparse import lil_matrix
sage: from numpy import array
sage: n = 200
sage: n2 = n*n
sage: A = lil_matrix((n2, n2))
sage: h2 = 1./float((n+1)^2)
sage: for i in range(0,n2):
....:    A[i,i]=4*h2+1.
....:    if i+1<n2: A[i,int(i+1)]=-h2
....:    if i>0:    A[i,int(i-1)]=-h2
....:    if i+n<n2: A[i,int(i+n)]=-h2
....:    if i-n>=0: A[i,int(i-n)]=-h2
sage: Acsc = A.tocsc()
sage: b = array([1 for i in range(0,n2)])
sage: solve = factorized(Acsc) # LU factorisation
sage: S = solve(b)             # resolution
```

Now if fails at the `A = lil_matrix((n2, n2))` line with:

```    TypeError: unrecognized lil_matrix constructor usage
```

Aren't `lil_matrix` tested in the current doctests?

2) the category of `QQ` changed:

```Failed example:
QQ.category()
Expected:
Join of Category of quotient fields and Category of metric spaces
Got:
Join of Category of number fields and Category of quotient fields and Category of metric spaces
```

3) we have different output for graphs of the commands `minor` and `edge_coloring`. We will try to fix those with `solver='GLPK'` (cf comment 6 above). If that does not work, is there a random seed that we can set to make those commands deterministic?

### comment:13 in reply to: ↑ 12 ; follow-up: ↓ 18 Changed 4 years ago by jdemeyer

3) we have different output for graphs of the commands `minor` and `edge_coloring`. We will try to fix those with `solver='GLPK'` (cf comment 6 above). If that does not work, is there a random seed that we can set to make those commands deterministic?

Are these tests really non-deterministic or just different with different versions of Sage?

### comment:14 in reply to: ↑ 12 ; follow-up: ↓ 19 Changed 4 years ago by jdemeyer

2) the category of `QQ` changed:

```Failed example:
QQ.category()
Expected:
Join of Category of quotient fields and Category of metric spaces
Got:
Join of Category of number fields and Category of quotient fields and Category of metric spaces
```

This is a good and intentional change: just change the expected output.

### comment:15 in reply to: ↑ 12 Changed 4 years ago by jdemeyer

Aren't `lil_matrix` tested in the current doctests?

`lil_matrix` is not used or tested anywhere in Sage. I'll have a look.

Last edited 4 years ago by jdemeyer (previous) (diff)

### comment:16 Changed 4 years ago by mforets

1) the lil_matrix do not work any more.

a scipy update? in sage 8.0.beta5 the version is 0.19.1, while in 8.0 it is 0.17.1.

however, the docstring says it's still valid:

```...
lil_matrix((M, N), [dtype])
to construct an empty matrix with shape (M, N)
dtype is optional, defaulting to dtype='d'.
```
Last edited 4 years ago by mforets (previous) (diff)

### comment:17 Changed 4 years ago by jdemeyer

• Description modified (diff)
• Report Upstream changed from N/A to Reported upstream. No feedback yet.

### comment:18 in reply to: ↑ 13 Changed 4 years ago by zimmerma

3) we have different output for graphs of the commands `minor` and `edge_coloring`. We will try to fix those with `solver='GLPK'` (cf comment 6 above). If that does not work, is there a random seed that we can set to make those commands deterministic?

Are these tests really non-deterministic or just different with different versions of Sage?

no idea, I first asked Nicolas to test with `solver='GLPK'`.

### comment:19 in reply to: ↑ 14 ; follow-up: ↓ 20 Changed 4 years ago by zimmerma

2) the category of `QQ` changed:

```Failed example:
QQ.category()
Expected:
Join of Category of quotient fields and Category of metric spaces
Got:
Join of Category of number fields and Category of quotient fields and Category of metric spaces
```

This is a good and intentional change: just change the expected output.

this is not possible, since we currently use Sage 8.0 for the book, and this will make the doctests fail with 8.0.