Opened 4 months ago

Closed 3 months ago

#27787 closed defect (fixed)

py3: matroids.utilities.lift_cross_ratios

Reported by: jhpalmieri Owned by:
Priority: major Milestone: sage-8.8
Component: matroid theory Keywords:
Cc: Stefan, Rudi, zgershkoff Merged in:
Authors: John Palmieri Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: ba75541 (Commits) Commit: ba7554124bd266801d3af8c0dde4a68d9faac878
Dependencies: Stopgaps:

Description

The documentation for the method matroids.utilities.lift_cross_ratios says This method will create a unique candidate representation ``Z``. It gives different answers in Python 2 and Python 3, yielding a doctest failure with py3. Is the representation not unique and both are valid answers? The code contains several loops over dictionaries, and so the loops can happen in different orders; does that matter?

Change History (9)

comment:1 Changed 3 months ago by jhpalmieri

In particular, with Python 3:

File "src/sage/matroids/utilities.py", line 543, in sage.matroids.utilities.lift_cross_ratios
Failed example:
    Z
Expected:
    [ 1  0  1  1  1]
    [ 1  1  0  0  z]
    [ 0  1 -z -1  0]
Got:
    [ 1  0  1  1  1]
    [ 1  1  0  0  z]
    [ 0 -1  z  1  0]

comment:2 Changed 3 months ago by jhpalmieri

A really drastic fix would be to just delete this function entirely, and also its companion lift_map. They are only used in one place, in the representation method in linear_matroid.pyx, and then only if an optional argument lift_map is specified, but no doctests use lift_map and so the code is untested. That makes me wary of keeping it around: does it actually work? Will it continue to work with Python 3?

A proper fix to this ticket would add doctests to representation which use lift_map.

If we end up deleting those two functions, these changes would also be required:

  • src/sage/matroids/advanced.py

    diff --git a/src/sage/matroids/advanced.py b/src/sage/matroids/advanced.py
    index 8d8a02ed1b..61cfa3a187 100644
    a b This adds the following to the main namespace: 
    4040        - :func:`setprint() <sage.matroids.utilities.setprint>`
    4141        - :func:`newlabel() <sage.matroids.utilities.newlabel>`
    4242        - :func:`get_nonisomorphic_matroids() <sage.matroids.utilities.get_nonisomorphic_matroids>`
    43         - :func:`lift_cross_ratios() <sage.matroids.linear_matroid.lift_cross_ratios>`
    44         - :func:`lift_map() <sage.matroids.linear_matroid.lift_map>`
    4543
    4644AUTHORS:
    4745
    from .rank_matroid import RankMatroid 
    5654from .circuit_closures_matroid import CircuitClosuresMatroid
    5755from .basis_matroid import BasisMatroid
    5856from .linear_matroid import LinearMatroid, RegularMatroid, BinaryMatroid, TernaryMatroid, QuaternaryMatroid
    59 from .utilities import setprint, newlabel, get_nonisomorphic_matroids, lift_cross_ratios, lift_map
     57from .utilities import setprint, newlabel, get_nonisomorphic_matroids
    6058from . import lean_matrix
    6159from .extension import LinearSubclasses, MatroidExtensions
    6260from .union_matroid import MatroidUnion, MatroidSum, PartitionMatroid
  • src/sage/matroids/linear_matroid.pxd

    diff --git a/src/sage/matroids/linear_matroid.pxd b/src/sage/matroids/linear_matroid.pxd
    index 3f0c8d8809..a1fe6b455e 100644
    a b cdef class LinearMatroid(BasisExchangeMatroid): 
    1717    cdef list _setup_internal_representation(self, matrix, reduced_matrix, ring, keep_initial_representation)
    1818    cdef __exchange_value(self, long x, long y)
    1919
    20     cpdef representation(self, B=*, reduced=*, labels=*, order=*, lift_map=*)
     20    cpdef representation(self, B=*, reduced=*, labels=*, order=*)
    2121    cpdef _current_rows_cols(self, B=*)
    2222    cpdef representation_vectors(self)
    2323    cpdef LeanMatrix _basic_representation(self, B=*)
  • src/sage/matroids/linear_matroid.pyx

    diff --git a/src/sage/matroids/linear_matroid.pyx b/src/sage/matroids/linear_matroid.pyx
    index 3fb15c4a6e..c4710db327 100644
    a b from sage.matroids.matroid cimport Matroid 
    118118from sage.matroids.basis_exchange_matroid cimport BasisExchangeMatroid
    119119from .lean_matrix cimport LeanMatrix, GenericMatrix, BinaryMatrix, TernaryMatrix, QuaternaryMatrix, PlusMinusOneMatrix, generic_identity
    120120from .set_system cimport SetSystem
    121 from .utilities import newlabel, spanning_stars, spanning_forest, lift_cross_ratios
     121from .utilities import newlabel, spanning_stars, spanning_forest
    122122from sage.graphs.spanning_tree import kruskal
    123123from sage.graphs.graph import Graph
    124124
    cdef class LinearMatroid(BasisExchangeMatroid): 
    465465
    466466    # representations
    467467
    468     cpdef representation(self, B=None, reduced=False, labels=None, order=None, lift_map=None):
     468    cpdef representation(self, B=None, reduced=False, labels=None, order=None):
    469469        r"""
    470470        Return a matrix representing the matroid.
    471471
    cdef class LinearMatroid(BasisExchangeMatroid): 
    501501        - ``order`` -- (default: ``None``) an ordering of the groundset
    502502          elements. If provided, the columns (and, in case of a reduced
    503503          representation, rows) will be presented in the given order.
    504         - ``lift_map`` -- (default: ``None``) a dictionary containing the cross
    505           ratios of the representing matrix in its domain. If provided, the
    506           representation will be transformed by mapping its cross ratios according
    507           to ``lift_map``.
    508504
    509505        OUTPUT:
    510506
    cdef class LinearMatroid(BasisExchangeMatroid): 
    521517        corresponds to an identity. If only ``order`` is not ``None``, the
    522518        columns of this matrix will be permuted accordingly.
    523519
    524         If a ``lift_map`` is provided, then the resulting matrix will be lifted
    525         using the method
    526         :func:`lift_cross_ratios() <sage.matroids.utilities.lift_cross_ratios>`
    527         See the docstring of this method for further details.
    528 
    529520        .. NOTE::
    530521
    531522            A shortcut for ``M.representation()`` is ``Matrix(M)``.
    cdef class LinearMatroid(BasisExchangeMatroid): 
    593584                B = self.__subset(B)
    594585                A = self._basic_representation(B)
    595586            A = A.matrix_from_rows_and_columns(range(A.nrows()), order_idx)
    596             if lift_map is None:
    597                 if labels:
    598                     return (A._matrix_(), order)
    599                 else:
    600                     return A._matrix_()
     587            if labels:
     588                return (A._matrix_(), order)
    601589            else:
    602                 if labels:
    603                     return (lift_cross_ratios(A._matrix_(), lift_map), order)
    604                 else:
    605                     return lift_cross_ratios(A._matrix_(), lift_map)
     590                return A._matrix_()
    606591        else:
    607592            if B is None:
    608593                B = frozenset(self.basis())
    cdef class LinearMatroid(BasisExchangeMatroid): 
    623608                    Ci.append(C.index(e))
    624609                    Cl.append(e)
    625610            A = A.matrix_from_rows_and_columns(Ri, Ci)
    626             if lift_map is None:
    627                 if labels or labels is None:
    628                     return (A._matrix_(), Rl, Cl)
    629                 else:
    630                     return A._matrix_()
     611            if labels or labels is None:
     612                return (A._matrix_(), Rl, Cl)
    631613            else:
    632                 if labels or labels is None:
    633                     return (lift_cross_ratios(A._matrix_(), lift_map), Rl, Cl)
    634                 else:
    635                     return lift_cross_ratios(A._matrix_(), lift_map)
     614                return A._matrix_()
    636615
    637616    cpdef _current_rows_cols(self, B=None):
    638617        """

comment:3 Changed 3 months ago by jhpalmieri

  • Cc Stefan Rudi zgershkoff added

comment:4 Changed 3 months ago by Rudi

I am the original author of this code.

The output matrix Z is constructed so that a certain collection of entries is equal to 1. This collection is exactly the set of T chosen in line 567--569 of utilities.py.

    T = set()
    for C in G.connected_components():
        T.update(G.subgraph(C).min_spanning_tree())

From the failed doctest, it appears that in py3 the output has a 1 in position (3,4) instead of (3,2) in py2. So T is constructed differently under py3. G is just the support graph of the input matrix, and does not depend on how it is constructed. So this tells me that Graph.min_spanning_tree() has changed its behaviour in py3. It the new behaviour of this routine is consistent between different calls, then the output of lift_cross_ratios will be consistent as well. So then it will suffice to adjust the output Z in the doctest.

Otherwise, it may be possible to force consistency Graph.min_spanning_tree() in py3, but I do not know how. Unfortunately I cannot test this either -- don't have Sage set up for working with py3.

Sorry I cannot do more. Hope this helps.

comment:5 Changed 3 months ago by jhpalmieri

Thanks very much for the comments. min_spanning_tree has indeed changed from Python 2 to Python 3, so we will just have different outputs for the doctests for the two versions.

comment:6 Changed 3 months ago by jhpalmieri

  • Branch set to u/jhpalmieri/matroid-utilities

comment:7 Changed 3 months ago by jhpalmieri

  • Authors set to John Palmieri
  • Commit set to ba7554124bd266801d3af8c0dde4a68d9faac878
  • Status changed from new to needs_review

Here is a branch which has different doctests for py2 and py3, and it also adds a doctest for the representation method which uses the lift_map optional argument. It also has different outputs depending on the version of Python.

I think it is likely that the difference is with min_spanning_tree. At least for the doctest for lift_cross_ratios, I checked the particular matrix involved, and py2 and py3 give different spanning trees for the graph produced from that matrix. I couldn't see a way to get the same spanning tree, hence different doctests depending on the version of Python.


New commits:

ba75541trac 27787: fix py3 doctest for lift_cross_ratios in sage.matroids.utilities

comment:8 Changed 3 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

From Rudi's comment:4, I agree that this is the correct fix.

comment:9 Changed 3 months ago by vbraun

  • Branch changed from u/jhpalmieri/matroid-utilities to ba7554124bd266801d3af8c0dde4a68d9faac878
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.