Opened 6 years ago

Closed 6 years ago

# Timeout in graphs/tutte_polynomial.py

Reported by: Owned by: vbraun major sage-duplicate/invalid/wontfix graph theory random_fail Frédéric Chapoton, Steven Trogdon N/A

This fails randomly:

```sage -t --long src/sage/graphs/tutte_polynomial.py
Timed out
**********************************************************************
Tests run before process (pid=75288) timed out:
sage: from sage.graphs.tutte_polynomial import removed_multiedge ## line 62 ##
sage: G = Graph(multiedges=True) ## line 63 ##
sage: G.add_edges([(0,1,'a'),(0,1,'b')]) ## line 64 ##
sage: G.edges() ## line 65 ##
[(0, 1, 'a'), (0, 1, 'b')]
sage: with removed_multiedge(G,(0,1)) as Y:
G.edges() ## line 67 ##
[]
sage: G.edges() ## line 70 ##
[(0, 1, 'a'), (0, 1, 'b')]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 72 ##
0
sage: from sage.graphs.tutte_polynomial import removed_edge ## line 91 ##
sage: G = Graph() ## line 92 ##
sage: G.add_edge(0,1) ## line 93 ##
sage: G.edges() ## line 94 ##
[(0, 1, None)]
sage: with removed_edge(G,(0,1)) as Y:
G.edges(); G.vertices() ## line 96 ##
[]
[0, 1]
sage: G.edges() ## line 100 ##
[(0, 1, None)]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 102 ##
0
sage: from sage.graphs.tutte_polynomial import contracted_edge ## line 118 ##
sage: G = Graph(multiedges=True) ## line 119 ##
sage: G.add_edges([(0,1,'a'),(1,2,'b'),(0,3,'c')]) ## line 120 ##
sage: G.edges() ## line 121 ##
[(0, 1, 'a'), (0, 3, 'c'), (1, 2, 'b')]
sage: with contracted_edge(G,(0,1)) as Y:
G.edges(); G.vertices() ## line 123 ##
[(1, 2, 'b'), (1, 3, 'c')]
[1, 2, 3]
sage: G.edges() ## line 127 ##
[(0, 1, 'a'), (0, 3, 'c'), (1, 2, 'b')]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 129 ##
0
sage: from sage.graphs.tutte_polynomial import removed_loops ## line 160 ##
sage: G = Graph(multiedges=True, loops=True) ## line 161 ##
sage: G.add_edges([(0,1,'a'),(1,2,'b'),(0,0,'c')]) ## line 162 ##
sage: G.edges() ## line 163 ##
[(0, 0, 'c'), (0, 1, 'a'), (1, 2, 'b')]
sage: with removed_loops(G) as Y:
G.edges(); G.vertices(); Y ## line 165 ##
[(0, 1, 'a'), (1, 2, 'b')]
[0, 1, 2]
[(0, 0, 'c')]
sage: G.edges() ## line 170 ##
[(0, 0, 'c'), (0, 1, 'a'), (1, 2, 'b')]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 172 ##
0
sage: from sage.graphs.tutte_polynomial import underlying_graph ## line 190 ##
sage: G = Graph(multiedges=True) ## line 191 ##
sage: G.add_edges([(0,1,'a'),(0,1,'b')]) ## line 192 ##
sage: G.edges() ## line 193 ##
[(0, 1, 'a'), (0, 1, 'b')]
sage: underlying_graph(G).edges() ## line 195 ##
[(0, 1, None)]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 197 ##
0
sage: from sage.graphs.tutte_polynomial import edge_multiplicities ## line 212 ##
sage: G = Graph({1: [2,2,3], 2: [2], 3: [4,4], 4: [2,2,2]}) ## line 213 ##
sage: sorted(edge_multiplicities(G).iteritems()) ## line 214 ##
[((1, 2), 2), ((1, 3), 1), ((2, 2), 1), ((2, 4), 3), ((3, 4), 2)]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 216 ##
0
sage: G = graphs.PathGraph(4) ## line 246 ##
sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) ## line 247 ##
sage: from sage.graphs.tutte_polynomial import Ear ## line 248 ##
sage: E = Ear(G,[0,3],[1,2],False) ## line 249 ##
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 250 ##
0
sage: G = graphs.PathGraph(4) ## line 263 ##
sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) ## line 264 ##
sage: from sage.graphs.tutte_polynomial import Ear ## line 265 ##
sage: E = Ear(G,[0,3],[1,2],False) ## line 266 ##
sage: E.s ## line 267 ##
3
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 269 ##
0
sage: G = graphs.PathGraph(4) ## line 279 ##
sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) ## line 280 ##
sage: from sage.graphs.tutte_polynomial import Ear ## line 281 ##
sage: E = Ear(G,[0,3],[1,2],False) ## line 282 ##
sage: E.vertices ## line 283 ##
[0, 1, 2, 3]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 285 ##
0
sage: G = graphs.PathGraph(4) ## line 295 ##
sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) ## line 296 ##
sage: from sage.graphs.tutte_polynomial import Ear ## line 297 ##
sage: E = Ear(G,[0,3],[1,2],False) ## line 298 ##
sage: E.unlabeled_edges ## line 299 ##
[(0, 1), (1, 2), (2, 3)]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 301 ##
0
sage: G = graphs.PathGraph(4) ## line 311 ##
sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) ## line 312 ##
sage: from sage.graphs.tutte_polynomial import Ear ## line 313 ##
sage: E = Ear.find_ear(G) ## line 314 ##
sage: E.s ## line 315 ##
3
sage: E.unlabeled_edges ## line 317 ##
[(0, 1), (1, 2), (2, 3)]
sage: E.vertices ## line 319 ##
[0, 1, 2, 3]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 321 ##
0
sage: G = graphs.PathGraph(4) ## line 351 ##
sage: G.add_edges([(0,4),(0,5),(3,6),(3,7)]) ## line 352 ##
sage: len(G.edges()) ## line 353 ##
7
sage: from sage.graphs.tutte_polynomial import Ear ## line 355 ##
sage: E = Ear.find_ear(G) ## line 356 ##
sage: with E.removed_from(G) as Y:
G.edges() ## line 357 ##
[(0, 4, None), (0, 5, None), (3, 6, None), (3, 7, None)]
sage: len(G.edges()) ## line 360 ##
7
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 362 ##
0
sage: from sage.graphs.tutte_polynomial import VertexOrder ## line 390 ##
sage: A = VertexOrder([4,6,3,2,1,7]) ## line 391 ##
sage: A.order ## line 392 ##
[4, 6, 3, 2, 1, 7]
sage: A.inverse_order ## line 394 ##
{1: 4, 2: 3, 3: 2, 4: 0, 6: 1, 7: 5}
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 396 ##
0
sage: from sage.graphs.tutte_polynomial import VertexOrder ## line 404 ##
sage: A = VertexOrder([4,0,3,2,1,5]) ## line 405 ##
sage: G = graphs.PathGraph(6) ## line 406 ##
sage: A(G) ## line 407 ##
(3, 4, None)
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 409 ##
0
sage: from sage.graphs.tutte_polynomial import MinimizeSingleDegree ## line 423 ##
sage: G = graphs.PathGraph(6) ## line 424 ##
sage: MinimizeSingleDegree()(G) ## line 425 ##
(0, 1, None)
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 427 ##
0
sage: from sage.graphs.tutte_polynomial import MinimizeDegree ## line 441 ##
sage: G = graphs.PathGraph(6) ## line 442 ##
sage: MinimizeDegree()(G) ## line 443 ##
(0, 1, None)
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 445 ##
0
sage: from sage.graphs.tutte_polynomial import MaximizeDegree ## line 459 ##
sage: G = graphs.PathGraph(6) ## line 460 ##
sage: MaximizeDegree()(G) ## line 461 ##
(3, 4, None)
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 463 ##
0
sage: from sage.graphs.tutte_polynomial import tutte_polynomial ## line 493 ##
sage: G = graphs.PetersenGraph() ## line 494 ##
sage: T = tutte_polynomial(G)  #indirect doctest ## line 495 ##
sage: tutte_polynomial(G)(1,1)  #indirect doctest ## line 496 ##
2000
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 498 ##
0
sage: all(T.tutte_polynomial() == x**9 for T in graphs.trees(10)) ## line 534 ##
True
sage: P = graphs.PetersenGraph() ## line 539 ##
sage: P.tutte_polynomial() ## line 540 ##
x^9 + 6*x^8 + 21*x^7 + 56*x^6 + 12*x^5*y + y^6 + 114*x^5 + 70*x^4*y + 30*x^3*y^2 + 15*x^2*y^3 + 10*x*y^4 + 9*y^5 + 170*x^4 + 170*x^3*y + 105*x^2*y^2 + 65*x*y^3 + 35*y^4 + 180*x^3 + 240*x^2*y + 171*x*y^2 + 75*y^3 + 120*x^2 + 168*x*y + 84*y^2 + 36*x + 36*y
sage: G = graphs.RandomGNP(10,0.6) ## line 549 ##
sage: G.tutte_polynomial()(1,1) == G.spanning_trees_count() ## line 550 ##
True
sage: G = graphs.OctahedralGraph() ## line 557 ##
sage: T = G.tutte_polynomial() ## line 558 ##
sage: R = PolynomialRing(ZZ, 'x') ## line 559 ##
sage: R((-1)^5*x*T(1-x,0)).factor() ## line 560 ##
(x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32)
sage: G.chromatic_polynomial().factor() ## line 562 ##
(x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32)
sage: cache = {} ## line 569 ##
sage: _ = graphs.RandomGNP(7,.5).tutte_polynomial(cache=cache) ## line 570 ##
sage: len(cache) > 0 ## line 571 ##
True
sage: g = Graph(multiedges=True) ## line 576 ##
sage: g.add_edges([(0,1,1),(1,5,2),(5,3,3),(5,2,4),(2,4,5),(0,2,6),(0,3,7),(0,4,8),(0,5,9)]); ## line 577 ##
sage: g.tutte_polynomial()(1,1) ## line 578 ##

**********************************************************************
```

Fixed by #21289.

### comment:1 Changed 6 years ago by chapoton

may be related to #21289

### comment:2 Changed 6 years ago by leif

Note that the file doesn't even have long tests.

For me still passes quickly in 7.4.beta0, but not beta2. (Don't have a beta1 at hand right now.)

### comment:3 Changed 6 years ago by leif

Hmmm, the following takes a few seconds:

```┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.4.beta2, Release Date: 2016-08-26               │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: g = Graph(multiedges=True)
sage: g.tutte_polynomial()(1,1)
52
```

And afterwards this gives an immediate answer:

```sage: g.spanning_trees_count()
52
```

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

The only test that follows doesn't take time either:

```sage: P = graphs.CycleGraph(5)
sage: P.tutte_polynomial() # indirect doctest
x^4 + x^3 + x^2 + x + y
```

### comment:5 Changed 6 years ago by leif

With `./sage -t --verbose` (=> same tests, just shorter time-out) I'm getting

```...
Trying (line 493):    from sage.graphs.tutte_polynomial import tutte_polynomial
Expecting nothing
ok [0.00 s]
Trying (line 494):    G = graphs.PetersenGraph()
Expecting nothing
ok [0.00 s]
Trying (line 495):    T = tutte_polynomial(G)  #indirect doctest
Expecting nothing
ok [51.60 s]
Trying (line 496):    tutte_polynomial(G)(1,1)  #indirect doctest
Expecting:
2000
ok [40.28 s]
Trying (line 498):    sig_on_count() # check sig_on/off pairings (virtual doctest)
Expecting:
0
ok [0.00 s]
Trying (line 534):    all(T.tutte_polynomial() == x**9 for T in graphs.trees(10))
Expecting:
True
ok [76.16 s]
Trying (line 539):    P = graphs.PetersenGraph()
Expecting nothing
ok [0.00 s]
Trying (line 540):    P.tutte_polynomial()
Expecting:
x^9 + 6*x^8 + 21*x^7 + 56*x^6 + 12*x^5*y + y^6 + 114*x^5 + 70*x^4*y
+ 30*x^3*y^2 + 15*x^2*y^3 + 10*x*y^4 + 9*y^5 + 170*x^4 + 170*x^3*y
+ 105*x^2*y^2 + 65*x*y^3 + 35*y^4 + 180*x^3 + 240*x^2*y + 171*x*y^2
+ 75*y^3 + 120*x^2 + 168*x*y + 84*y^2 + 36*x + 36*y
ok [51.65 s]
Trying (line 549):    G = graphs.RandomGNP(10,0.6)
Expecting nothing
ok [0.00 s]
Trying (line 550):    G.tutte_polynomial()(1,1) == G.spanning_trees_count()
Expecting:
True
Timed out
**********************************************************************
```

after 300 seconds.

### comment:6 follow-up: ↓ 7 Changed 6 years ago by strogdon

Much the same here. With verbose turned on the first `odd` looking test is at `line 495`

```Trying (line 493):    from sage.graphs.tutte_polynomial import tutte_polynomial
Expecting nothing
ok [0.00 s]
Trying (line 494):    G = graphs.PetersenGraph()
Expecting nothing
ok [0.00 s]
Trying (line 495):    T = tutte_polynomial(G)  #indirect doctest
Expecting nothing
ok [86.19 s]
Trying (line 496):    tutte_polynomial(G)(1,1)  #indirect doctest
Expecting:
2000
ok [86.19 s]
Trying (line 498):    sig_on_count() # check sig_on/off pairings (virtual doctest)
Expecting:
0
ok [0.00 s]
Trying (line 534):    all(T.tutte_polynomial() == x**9 for T in graphs.trees(10))
Expecting:
True
ok [190.56 s]
Trying (line 539):    P = graphs.PetersenGraph()
Expecting nothing
ok [0.00 s]
Trying (line 540):    P.tutte_polynomial()
Expecting:
x^9 + 6*x^8 + 21*x^7 + 56*x^6 + 12*x^5*y + y^6 + 114*x^5 + 70*x^4*y
+ 30*x^3*y^2 + 15*x^2*y^3 + 10*x*y^4 + 9*y^5 + 170*x^4 + 170*x^3*y
+ 105*x^2*y^2 + 65*x*y^3 + 35*y^4 + 180*x^3 + 240*x^2*y + 171*x*y^2
+ 75*y^3 + 120*x^2 + 168*x*y + 84*y^2 + 36*x + 36*y
ok [86.41 s]
```

### comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 6 years ago by leif

Much the same here. With verbose turned on the first `odd` looking test is at `line 495`.

So which parts differ in your SoG installation?

(The file itself by the way hasn't changed recently, AFAICT.)

### comment:8 in reply to: ↑ 7 Changed 6 years ago by strogdon

Much the same here. With verbose turned on the first `odd` looking test is at `line 495`.

So which parts differ in your SoG installation?

(The file itself by the way hasn't changed recently, AFAICT.)

Corresponding lines from SoG:

```Trying (line 493):    from sage.graphs.tutte_polynomial import tutte_polynomial
Expecting nothing
ok [0.00 s]
Trying (line 494):    G = graphs.PetersenGraph()
Expecting nothing
ok [0.00 s]
Trying (line 495):    T = tutte_polynomial(G)  #indirect doctest
Expecting nothing
ok [0.13 s]
Trying (line 496):    tutte_polynomial(G)(1,1)  #indirect doctest
Expecting:
2000
ok [0.11 s]
Trying (line 498):    sig_on_count() # check sig_on/off pairings (virtual doctest)
Expecting:
0
ok [0.00 s]
Trying (line 534):    all(T.tutte_polynomial() == x**9 for T in graphs.trees(10))
Expecting:
True
ok [0.29 s]
Trying (line 539):    P = graphs.PetersenGraph()
Expecting nothing
ok [0.00 s]
Trying (line 540):    P.tutte_polynomial()
Expecting:
x^9 + 6*x^8 + 21*x^7 + 56*x^6 + 12*x^5*y + y^6 + 114*x^5 + 70*x^4*y
+ 30*x^3*y^2 + 15*x^2*y^3 + 10*x*y^4 + 9*y^5 + 170*x^4 + 170*x^3*y
+ 105*x^2*y^2 + 65*x*y^3 + 35*y^4 + 180*x^3 + 240*x^2*y + 171*x*y^2
+ 75*y^3 + 120*x^2 + 168*x*y + 84*y^2 + 36*x + 36*y
ok [0.11 s]
```

Calculational times are tenths of a second.

### comment:9 Changed 6 years ago by leif

Sure, I meant backends... (Not sure what's used at all.)

### comment:10 follow-up: ↓ 13 Changed 6 years ago by leif

Ah, while there's not a single process actually doing something, I now see frequent calls of `\$SAGE_LOCAL/bin/pip list`... WTF?

(So apparently it is continually looked up whether an optional backend is available / installed.)

### comment:11 follow-up: ↓ 12 Changed 6 years ago by fbissey

Steve, do you have the `bliss` useflag on in SoG?

### comment:12 in reply to: ↑ 11 Changed 6 years ago by strogdon

Steve, do you have the `bliss` useflag on in SoG?

I was just going to copy you. No, I don't have `bliss` enabled.

### comment:13 in reply to: ↑ 10 Changed 6 years ago by strogdon

Ah, while there's not a single process actually doing something, I now see frequent calls of `\$SAGE_LOCAL/bin/pip list`... WTF?

(So apparently it is continually looked up whether an optional backend is available / installed.)

Yep, I see this too.

### comment:14 follow-up: ↓ 16 Changed 6 years ago by leif

`GenericGraph.canonical_label()` (from which `HasseDiagram` indirectly inherits) seems to be the culprit here:

```        from sage.misc.package import is_package_installed
if (algorithm == 'bliss'           or  # explicit request; or
(algorithm is None             and # default choice
is_package_installed('bliss') and
not edge_labels)):
if edge_labels:
raise ValueError("bliss cannot be used when edge_labels is True")
try:
from sage.graphs.bliss import canonical_form
except ImportError:
raise ImportError("You must install the 'bliss' package to run this command.")
return canonical_form(self, partition, return_graph, certificate)

...
```

Did they ever hear of caching results?

(We could of course also mark all tests `# optional -- internet`... B) )

### comment:15 follow-up: ↓ 18 Changed 6 years ago by tscrim

Graphs are mutable, so we cannot cache the results in the graph. IIRC, the reason why we are getting a canonical labeling is so we can cache things for the Tutte polynomial. However, we could split out the check for existence of `bliss` into the Tutte polynomial computation and pass the corresponding choice of algorithm.

### comment:16 in reply to: ↑ 14 Changed 6 years ago by leif

`GenericGraph.canonical_label()` (from which `HasseDiagram` indirectly inherits) seems to be the culprit here...

... together with the commit from #19213 leading to:

```def is_package_installed(package):
return any(p.split('-')[0] == package for p in installed_packages())
```

with

```def installed_packages():
from sage.env import SAGE_SPKG_INST
installed = dict(pkgname_split(pkgname) for pkgname in os.listdir(SAGE_SPKG_INST))
installed.update(pip_installed_packages()) ##### here 'pip' gets called #####
return installed
```

and

```def pip_installed_packages():
proc = subprocess.Popen(["pip", "list"], stdout=subprocess.PIPE)
stdout = proc.communicate()[0]
return dict((name.lower(), version) for name,version in PIP_VERSION.findall(stdout))
```

### comment:17 follow-up: ↓ 19 Changed 6 years ago by fbissey

Stuff using `is_package_installed` is broken inside vanilla sagemath? Do you know how much it makes me my day :) I don't think I need to plug #20382, most people here are aware of it.

### comment:18 in reply to: ↑ 15 ; follow-up: ↓ 20 Changed 6 years ago by leif

Graphs are mutable, so we cannot cache the results in the graph.

That doesn't matter; whether specific backends are available could be cached in a "static" property (here presumably of `GenericGraph`) or even a module variable, if not in `misc.package` itself (whether some package is installed).

While a package could perhaps get installed during runtime, it certainly won't (or shouldn'tTM) get removed while Sage is running.

### comment:19 in reply to: ↑ 17 Changed 6 years ago by leif

Stuff using `is_package_installed` is broken inside vanilla sagemath? Do you know how much it makes me my day :)

Nothing is broken, it's just things have sloooooooooooooooooooooooooooooooooooooooooowed down.

We have to adjust the timeouts accordingly, and mark more tests `# long time`.

### comment:20 in reply to: ↑ 18 Changed 6 years ago by tscrim

Graphs are mutable, so we cannot cache the results in the graph.

That doesn't matter; whether specific backends are available could be cached in a "static" property (here presumably of `GenericGraph`) or even a module variable, if not in `misc.package` itself (whether some package is installed).

While a package could perhaps get installed during runtime, it certainly won't (or shouldn'tTM) get removed while Sage is running.

Ah, sorry, I misunderstood what you were asking to cache. Yes, I agree that we should cache the results of the existence of (optional) packages. We currently do this for `dot2tex` (#18570).

### comment:22 Changed 6 years ago by chapoton

• Milestone changed from sage-7.4 to sage-duplicate/invalid/wontfix
• Status changed from new to needs_review

This should be solved by #21289, to be confirmed

### comment:23 Changed 6 years ago by strogdon

OK, without #21289

```sage -t --long src/sage/graphs/tutte_polynomial.py
[105 tests, 1621.87 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 1622.0 seconds
cpu time: 26.9 seconds
cumulative wall time: 1621.9 seconds
```

and with #21289 I now get

```sage -t --long src/sage/graphs/tutte_polynomial.py
[105 tests, 3.45 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 3.6 seconds
cpu time: 3.4 seconds
cumulative wall time: 3.4 seconds
```

So this seems to fix `tutte_polynomial.py`.

### comment:24 Changed 6 years ago by chapoton

• Status changed from needs_review to positive_review

so let us close this one

### comment:25 Changed 6 years ago by leif

• Description modified (diff)
• Resolution set to fixed
• Status changed from positive_review to closed

Fixed by #21289.

### comment:26 Changed 6 years ago by leif

• Reviewers set to Frédéric Chapoton, Steven Trogdon
Note: See TracTickets for help on using tickets.