Opened 6 months ago

Closed 6 months ago

Last modified 5 months ago

#26831 closed enhancement (fixed)

avoid .vertices() in rankwidth.pyx

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.5
Component: graph theory Keywords: py3, graph
Cc: Merged in:
Authors: David Coudert Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: ab927cd (Commits) Commit:
Dependencies: Stopgaps:

Description

We avoid using .vertices() in rankwidth.pyx by using a proper mapping, and we do pep8 cleaning.

Change History (5)

comment:1 Changed 6 months ago by dcoudert

  • Branch set to public/26831_rankwidth
  • Commit set to ab927cd6a011a5f118e981eb4422a3b95a40caa8
  • Status changed from new to needs_review

New commits:

ab927cdtrac #26831: avoid .vertices() and clean rankwidth.pyx

comment:2 Changed 6 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok

comment:3 Changed 6 months ago by vbraun

  • Branch changed from public/26831_rankwidth to ab927cd6a011a5f118e981eb4422a3b95a40caa8
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:4 Changed 5 months ago by gh-timokau

  • Commit ab927cd6a011a5f118e981eb4422a3b95a40caa8 deleted

Since 8.6.beta1, I see random test failures in src/sage/numerical/linear_tensor_element.pyx like this:

Doctesting 1 file using 4 threads.
sage -t --long /nix/store/yx4zba3x42n1npzh8v1vwbz09gyvwpvr-sage-src-8.6.bisect/src/sage/numerical/linear_tensor_element.pyx
glp_free: memory allocation error
Error detected in file env/alloc.c at line 72
------------------------------------------------------------------------
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/site-packages/cysignals/signals.so(+0x7c3b)[0x7ffff1a2dc3b]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/site-packages/cysignals/signals.so(+0x7cff)[0x7ffff1a2dcff]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/site-packages/cysignals/signals.so(+0xa7de)[0x7ffff1a307de]
/nix/store/xdsjx0gba4id3yyqxv66bxnm2sqixkjj-glibc-2.27/lib/libpthread.so.0(+0x11f10)[0x7ffff7592f10]
/nix/store/xdsjx0gba4id3yyqxv66bxnm2sqixkjj-glibc-2.27/lib/libc.so.6(gsignal+0x100)[0x7ffff6a65be0]
/nix/store/xdsjx0gba4id3yyqxv66bxnm2sqixkjj-glibc-2.27/lib/libc.so.6(abort+0x141)[0x7ffff6a66dc1]
/nix/store/vlihd2i8ga221p2hw74dgwjialxw66ip-glpk-4.65/lib/libglpk.so.40(+0x5ec67)[0x7fff6f6b6c67]
/nix/store/vlihd2i8ga221p2hw74dgwjialxw66ip-glpk-4.65/lib/libglpk.so.40(+0x5e348)[0x7fff6f6b6348]
/nix/store/vlihd2i8ga221p2hw74dgwjialxw66ip-glpk-4.65/lib/libglpk.so.40(+0x6d25f)[0x7fff6f6c525f]
/nix/store/vlihd2i8ga221p2hw74dgwjialxw66ip-glpk-4.65/lib/libglpk.so.40(+0x1da7c)[0x7fff6f675a7c]
/nix/store/vlihd2i8ga221p2hw74dgwjialxw66ip-glpk-4.65/lib/libglpk.so.40(glp_delete_prob+0x1f)[0x7fff6f67884f]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/site-packages/sage/numerical/backends/glpk_backend.so(+0x13eac)[0x7fff6f95feac]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/site-packages/sage/numerical/mip.so(+0xcdf2)[0x7fff797f1df2]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0x155a0a)[0x7ffff78f5a0a]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(_PyObject_GC_Malloc+0xcd)[0x7ffff78f668d]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(_PyObject_GC_New+0xd)[0x7ffff78f66cd]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyDictProxy_New+0x14)[0x7ffff7819094]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0xd116a)[0x7ffff787116a]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x2695)[0x7ffff78af7a5]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x7b8)[0x7ffff78b6dd8]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0x8a109)[0x7ffff782a109]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7ffff77f9043]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_CallMethod+0xd8)[0x7ffff77f9518]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0xc661d)[0x7ffff786661d]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0xc6ae6)[0x7ffff7866ae6]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7ffff77f9043]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/lib-dynload/cPickle.so(+0xe287)[0x7ffff3286287]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/lib-dynload/cPickle.so(+0x10bec)[0x7ffff3288bec]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/lib-dynload/cPickle.so(+0xe839)[0x7ffff3286839]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/lib-dynload/cPickle.so(+0x10eda)[0x7ffff3288eda]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7ffff77f9043]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_CallFunctionObjArgs+0x162)[0x7ffff77f9c42]
/nix/store/1sb677l26dbys1gnl4bdi3mvfygb71f2-python-2.7.15-env/lib/python2.7/lib-dynload/_multiprocessing.so(+0x3980)[0x7fffebb26980]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x7bef)[0x7ffff78b4cff]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x7b8)[0x7ffff78b6dd8]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0x8a1ed)[0x7ffff782a1ed]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7ffff77f9043]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x50fd)[0x7ffff78b220d]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x94cb)[0x7ffff78b65db]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x94cb)[0x7ffff78b65db]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x7b8)[0x7ffff78b6dd8]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0x8a109)[0x7ffff782a109]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7ffff77f9043]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0x6865c)[0x7ffff780865c]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7ffff77f9043]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(PyEval_CallObjectWithKeywords+0x47)[0x7ffff78acbc7]
/nix/store/w30zkhdjf6qp4ppx9xzffsh9dic31aq8-python-2.7.15/lib/libpython2.7.so.1.0(+0x156c22)[0x7ffff78f6c22]
/nix/store/xdsjx0gba4id3yyqxv66bxnm2sqixkjj-glibc-2.27/lib/libpthread.so.0(+0x75a7)[0x7ffff75885a7]
/nix/store/xdsjx0gba4id3yyqxv66bxnm2sqixkjj-glibc-2.27/lib/libc.so.6(clone+0x3f)[0x7ffff6b2322f]
------------------------------------------------------------------------
Attaching gdb to process id 619.
Cannot find gdb installed
GDB is not installed.
Install gdb for enhanced tracebacks.
------------------------------------------------------------------------
Unhandled SIGABRT: An abort() occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------
    Killed due to abort
**********************************************************************
Tests run before process (pid=619) failed:
sage: mip.<x> = MixedIntegerLinearProgram('ppl')   # base ring is QQ ## line 6 ##
sage: lt = x[0] * vector([3,4]) + 1;   lt ## line 7 ##
(1, 1) + (3, 4)*x_0
sage: type(lt) ## line 9 ##
<type 'sage.numerical.linear_tensor_element.LinearTensor'>
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 11 ##
0
sage: parent = MixedIntegerLinearProgram().linear_functions_parent().tensor(RDF^2) ## line 47 ##
sage: parent({0: [1,2], 3: [-7,-8]}) ## line 48 ##
(1.0, 2.0)*x_0 + (-7.0, -8.0)*x_3
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 50 ##
0
sage: LT = MixedIntegerLinearProgram().linear_functions_parent().tensor(RDF^2) ## line 70 ##
sage: LT({0: [1,2], 3: [-7,-8]}) ## line 71 ##
(1.0, 2.0)*x_0 + (-7.0, -8.0)*x_3
sage: TestSuite(LT).run(skip=['_test_an_element', '_test_elements_eq_reflexive',
    '_test_elements_eq_symmetric', '_test_elements_eq_transitive',
    '_test_elements_neq', '_test_additive_associativity',
    '_test_elements', '_test_pickling', '_test_zero']) ## line 74 ##
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 78 ##
0
sage: p = MixedIntegerLinearProgram().linear_functions_parent().tensor(RDF^2) ## line 95 ##
sage: lt = p({0:[1,2], 3:[4,5]});  lt ## line 96 ##
(1.0, 2.0)*x_0 + (4.0, 5.0)*x_3
sage: lt[0] ## line 98 ##
x_0 + 4*x_3
sage: lt[1] ## line 100 ##
2*x_0 + 5*x_3
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 102 ##
0
sage: p = MixedIntegerLinearProgram().linear_functions_parent().tensor(RDF^2) ## line 120 ##
sage: lt = p({0:[1,2], 3:[4,5]}) ## line 121 ##
sage: lt.dict() ## line 122 ##
{0: (1.0, 2.0), 3: (4.0, 5.0)}
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 124 ##
0
sage: mip.<b> = MixedIntegerLinearProgram() ## line 144 ##
sage: lt = vector([1,2]) * b[3] + vector([4,5]) * b[0] - 5;  lt ## line 145 ##
(-5.0, -5.0) + (1.0, 2.0)*x_0 + (4.0, 5.0)*x_1
sage: lt.coefficient(b[3]) ## line 147 ##
(1.0, 2.0)
sage: lt.coefficient(0)      # x_0 is b[3] ## line 149 ##
(1.0, 2.0)
sage: lt.coefficient(4) ## line 151 ##
(0.0, 0.0)
sage: lt.coefficient(-1) ## line 153 ##
(-5.0, -5.0)
sage: lt.coefficient(b[3] + b[4]) ## line 158 ##
sage: lt.coefficient(2*b[3]) ## line 162 ##
sage: mip.<q> = MixedIntegerLinearProgram(solver='ppl') ## line 166 ##
sage: lt.coefficient(q[0]) ## line 167 ##
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 171 ##
0
sage: from sage.numerical.linear_functions import LinearFunctionsParent ## line 197 ##
sage: R.<s,t> = RDF[] ## line 198 ##
sage: LT = LinearFunctionsParent(RDF).tensor(R) ## line 199 ##
sage: LT.an_element()  # indirect doctest ## line 200 ##
(s) + (5.0*s)*x_2 + (7.0*s)*x_5
sage: LT = LinearFunctionsParent(RDF).tensor(RDF^2) ## line 203 ##
sage: LT.an_element()  # indirect doctest ## line 204 ##
(1.0, 0.0) + (5.0, 0.0)*x_2 + (7.0, 0.0)*x_5
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 206 ##
0
sage: from sage.numerical.linear_functions import LinearFunctionsParent ## line 235 ##
sage: LT = LinearFunctionsParent(RDF).tensor(RDF^(2,2)) ## line 236 ##
sage: LT.an_element()  # indirect doctest ## line 237 ##
[1 + 5*x_2 + 7*x_5 1 + 5*x_2 + 7*x_5]
[1 + 5*x_2 + 7*x_5 1 + 5*x_2 + 7*x_5]
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 240 ##
0
sage: from sage.numerical.linear_functions import LinearFunctionsParent ## line 278 ##
sage: LT = LinearFunctionsParent(RDF).tensor(RDF^2) ## line 279 ##
sage: LT({0: [1,2], 3: [-7,-8]}) + LT({2: [5,6], 3: [2,-2]}) + 16 ## line 280 ##
(16.0, 16.0) + (1.0, 2.0)*x_0 + (5.0, 6.0)*x_2 + (-5.0, -10.0)*x_3
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 282 ##
0
sage: from sage.numerical.linear_functions import LinearFunctionsParent ## line 298 ##
sage: LT = LinearFunctionsParent(RDF).tensor(RDF^2) ## line 299 ##
sage: -LT({0: [1,2], 3: [-7,-8]}) ## line 300 ##
(-1.0, -2.0)*x_0 + (7.0, 8.0)*x_3
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 302 ##
0
sage: from sage.numerical.linear_functions import LinearFunctionsParent ## line 322 ##
sage: LT = LinearFunctionsParent(RDF).tensor(RDF^2) ## line 323 ##
sage: LT({0: [1,2], 3: [-7,-8]}) - LT({1: [1,2]}) ## line 324 ##
(1.0, 2.0)*x_0 + (-1.0, -2.0)*x_1 + (-7.0, -8.0)*x_3
sage: LT({0: [1,2], 3: [-7,-8]}) - 16 ## line 326 ##
(-16.0, -16.0) + (1.0, 2.0)*x_0 + (-7.0, -8.0)*x_3
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 328 ##
0
sage: from sage.numerical.linear_functions import LinearFunctionsParent ## line 348 ##
sage: LT = LinearFunctionsParent(RDF).tensor(RDF^2) ## line 349 ##
sage: 10 * LT({0: [1,2], 3: [-7,-8]}) ## line 350 ##
(10.0, 20.0)*x_0 + (-70.0, -80.0)*x_3
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 352 ##
0
sage: mip.<x> = MixedIntegerLinearProgram() ## line 364 ##
sage: lt0 = x[0] * vector([1,2]) ## line 365 ##
sage: lt1 = x[1] * vector([2,3]) ## line 366 ##
sage: lt0.__le__(lt1)    # indirect doctest ## line 367 ##
(1.0, 2.0)*x_0 <= (2.0, 3.0)*x_1
sage: mip.<x> = MixedIntegerLinearProgram() ## line 372 ##
sage: from sage.numerical.linear_functions import LinearFunction ## line 373 ##
sage: x[0] * vector([1,2]) <= x[1] * vector([2,3]) ## line 374 ##
(1.0, 2.0)*x_0 <= (2.0, 3.0)*x_1
sage: x[0] * vector([1,2]) >= x[1] * vector([2,3]) ## line 377 ##
(2.0, 3.0)*x_1 <= (1.0, 2.0)*x_0
sage: x[0] * vector([1,2]) == x[1] * vector([2,3]) ## line 380 ##
(1.0, 2.0)*x_0 == (2.0, 3.0)*x_1
sage: x[0] * vector([1,2]) < x[1] * vector([2,3]) ## line 383 ##
sage: x[0] * vector([1,2]) > x[1] * vector([2,3]) ## line 388 ##
sage: lt = x[0] * vector([1,2]) ## line 395 ##
sage: cm = sage.structure.element.get_coercion_model() ## line 396 ##
sage: cm.explain(10, lt, operator.le) ## line 397 ##
Coercion on left operand via
    Coercion map:
      From: Integer Ring
      To:   Tensor product of Vector space of dimension 2 over Real Double Field and Linear functions over Real Double Field
Arithmetic performed after coercions.
Result lives in Tensor product of Vector space of dimension 2 over Real Double Field and Linear functions over Real Double Field
Tensor product of Vector space of dimension 2 over Real Double Field and Linear functions over Real Double Field
sage: operator.le(10, lt) ## line 406 ##
(10.0, 10.0) <= (1.0, 2.0)*x_0
sage: lt <= 1 ## line 408 ##
(1.0, 2.0)*x_0 <= (1.0, 1.0)
sage: lt >= 1 ## line 410 ##
(1.0, 1.0) <= (1.0, 2.0)*x_0
sage: 1 <= lt ## line 412 ##
(1.0, 1.0) <= (1.0, 2.0)*x_0
sage: 1 >= lt ## line 414 ##
(1.0, 2.0)*x_0 <= (1.0, 1.0)
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 416 ##
0
sage: p = MixedIntegerLinearProgram() ## line 444 ##
sage: lt0 = p[0] * vector([1,2]) ## line 445 ##
sage: hash(lt0)   # random output ## line 446 ##
8795940780823
sage: d = {} ## line 448 ##
sage: d[lt0] = 3 ## line 449 ##
sage: f = p[0] * vector([1]) ## line 455 ##
sage: g = p[0] * vector([1]) ## line 456 ##
sage: set([f, f]) ## line 457 ##
{((1.0))*x_0}
sage: set([f, g]) ## line 459 ##
{((1.0))*x_0, ((1.0))*x_0}
sage: len(set([f, f+1])) ## line 461 ##
2
sage: d = {} ## line 464 ##
sage: d[f] = 123 ## line 465 ##
sage: d[g] = 456 ## line 466 ##
sage: len(list(d)) ## line 467 ##
2
sage: sig_on_count() # check sig_on/off pairings (virtual doctest) ## line 469 ##
0

**********************************************************************
----------------------------------------------------------------------
sage -t --long /nix/store/yx4zba3x42n1npzh8v1vwbz09gyvwpvr-sage-src-8.6.bisect//src/sage/numerical/linear_tensor_element.pyx  # Killed due to abort

git bisect is pointing me to this ticket as the cause. Any idea why that may be?

comment:5 Changed 5 months ago by gh-timokau

Nevermind, its not this ticket after all. Bisecting random issues is annoying.

Note: See TracTickets for help on using tickets.