avoid .vertices() in rankwidth.pyx #26831

dcoudert · 2018-12-05T03:08:39Z

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

Component: graph theory

Author: David Coudert

Branch: ab927cd

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/26831

The text was updated successfully, but these errors were encountered:

dcoudert · 2018-12-05T03:09:59Z

New commits:

`ab927cd`	`trac #26831: avoid .vertices() and clean rankwidth.pyx`

dcoudert · 2018-12-05T03:09:59Z

Commit: ab927cd

dcoudert · 2018-12-05T03:09:59Z

Branch: public/26831_rankwidth

fchapoton · 2018-12-29T20:02:41Z

Reviewer: Frédéric Chapoton

fchapoton · 2018-12-29T20:02:41Z

comment:2

ok

vbraun · 2018-12-31T10:37:05Z

Changed branch from public/26831_rankwidth to ab927cd

timokau · 2019-01-06T10:35:28Z

comment:4

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?

timokau · 2019-01-06T10:35:28Z

Changed commit from ab927cd to none

timokau · 2019-01-06T10:58:17Z

comment:5

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

dcoudert added this to the sage-8.5 milestone Dec 5, 2018

dcoudert added c: graph theory labels Dec 5, 2018

dcoudert added the s: needs review label Dec 5, 2018

fchapoton added s: positive review and removed s: needs review labels Dec 29, 2018

vbraun removed the s: positive review label Dec 31, 2018

vbraun closed this as completed in 808abb4 Dec 31, 2018

This was referenced Feb 14, 2019

meta-ticket for cleaning graph decompositions #26520

Closed

Meta-ticket: make graphs compatible with Python 3 #26640

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

avoid .vertices() in rankwidth.pyx #26831

avoid .vertices() in rankwidth.pyx #26831

dcoudert commented Dec 5, 2018

dcoudert commented Dec 5, 2018

dcoudert commented Dec 5, 2018

dcoudert commented Dec 5, 2018

fchapoton commented Dec 29, 2018

fchapoton commented Dec 29, 2018

vbraun commented Dec 31, 2018

timokau commented Jan 6, 2019

timokau commented Jan 6, 2019

timokau commented Jan 6, 2019

avoid .vertices() in rankwidth.pyx #26831

avoid .vertices() in rankwidth.pyx #26831

Comments

dcoudert commented Dec 5, 2018

dcoudert commented Dec 5, 2018

dcoudert commented Dec 5, 2018

dcoudert commented Dec 5, 2018

fchapoton commented Dec 29, 2018

fchapoton commented Dec 29, 2018

vbraun commented Dec 31, 2018

timokau commented Jan 6, 2019

timokau commented Jan 6, 2019

timokau commented Jan 6, 2019