Add Certificate to is_isomorphic() in the matroids package

[tara]

We are going to add an option to get certificate when testing if two matroids are isomorphic. I will be doing this.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4ee8641

Added an optional parameter cert to allow the user to ask for a certificate if the two matroids are isomorphic.

[tara]

Right now, I'm happy with the code except for in basis_exchange_matroid, M1._is_isomorphic(M2, True) yields the output (True, True) on line 2272, and similarly on line 2278. This doesn't seem to be something that I caused directly, but might be due to the following code found in _isomorphism() in basis_matroid.pyx (lines 980-981).

if not isinstance(other, BasisMatroid):
    return BasisExchangeMatroid._is_isomorphic(self, other)

I'm not sure exactly how to tell what type of matroid a thing is when it gets instigated. Regardless, is there any reason why we don't want to or are unable to return an isomorphism in the above case?

[Stefan]

If you're calling another instance of the is_isomorphic method, you should pass through all parameters. So the line you quote needs to be changed to

if not isinstance(other, BasisMatroid):
    return BasisExchangeMatroid._is_isomorphic(self, other, cert)

[tara]

Replying to Stefan:

If you're calling another instance of the is_isomorphic method, you should pass through all parameters. So the line you quote needs to be changed to

if not isinstance(other, BasisMatroid):
    return BasisExchangeMatroid._is_isomorphic(self, other, cert)

My question was why we are calling is_isomorphic instead of isomorphism. For instance, the following comes from an unedited version of sage. But I would expect a dictionary instead of a boolean.

sage: from sage.matroids.advanced import *
sage: M1 = BasisMatroid(matroids.Wheel(3))
sage: M2 = matroids.CompleteGraphic(4)
sage: M1.isomorphism(M2)
True

So I think that this is a bug in Sage.

[Stefan]

I think you're right. Normally the right thing to do would be to open a separate ticket for the bug, but since you're editing the same methods already, you might as well fix it in this ticket.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ea46145

Fixed bug in basis_matroid, and updated the documentation is basis_exchange_matroid

[yomcat]

I'll have a proper look later, but you should change cert to certificate as is_3connected() has for consistency.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​12a4b3d

Changed cert to certificate

[yomcat]

A few minor things:

• There's some extraneous whitespace after your commas -- use git trac review to see it easily.
• You haven't fully made the cert to certificate change. The pxd files are causing errors upon compilation because of it.
• In the doctests, you should specify the option, ie: M.is_isomorphic(N, certificate=True)
• In the output part of the docstring, you should say what that the dictionary shows the isomorphism, and None is output when the matroids aren't isomorphic.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a584a6e

Fixed errors from comment

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​18db65a

Fixed spacing

[yomcat]

First, you have a bunch of doubled-up doctests (one with the explicit option, one without).

This happens (it's due to a capital C):

sage -t --long --warn-long 69.0 src/sage/matroids/circuit_closures_matroid.pyx
**********************************************************************
File "src/sage/matroids/circuit_closures_matroid.pyx", line 393, in sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid._is_isomorphic
Failed example:
    M1._is_isomorphic(M2, Certificate=True)
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage-devel/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Applications/sage-devel/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 861, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid._is_isomorphic[9]>", line 1, in <module>
        M1._is_isomorphic(M2, Certificate=True)
      File "sage/matroids/circuit_closures_matroid.pyx", line 358, in sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid._is_isomorphic (/Applications/sage-devel/src/build/cythonized/sage/matroids/circuit_closures_matroid.c:4575)
        cpdef _is_isomorphic(self, other, certificate=False):
    TypeError: _is_isomorphic() got an unexpected keyword argument 'Certificate'
**********************************************************************
1 item had failures:
   1 of  12 in sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid._is_isomorphic
    [81 tests, 1 failure, 0.30 s]

Last doctest in BasisExchangeMatroid? is missing the explicit option.

Around line 2694 in linear_matroid.pyx, you've removed an extra space. It should be return True, None.

You've dropped an I from INPUT around line 355 of circuit_closures_matroid.pyx, and lines 3265, 4312, 5941 of linear_matroid.pyx

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​380af24

Fixed errors

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d39e113

Missed one doctest

[yomcat]

You missed one doctest, but I cleaned it up. If you're happy now with that (I'm happy now), set it to positive.

[tara]

I don't see anything wrong with it. My doctest has been acting weird for the last couple of hours. On this file, its now giving me 13 errors, each of which saying that is_isomorphic() or _is_isomorphic() is only supposed to be taking one parameter. Before it was saying that everything passes when it shouldn't have been.

[yomcat]

Replying to tara:

I don't see anything wrong with it. My doctest has been acting weird for the last couple of hours. On this file, its now giving me 13 errors, each of which saying that is_isomorphic() or _is_isomorphic() is only supposed to be taking one parameter. Before it was saying that everything passes when it shouldn't have been.

That sounds like you're partially in the wrong branch (so not all the changes are being applied). Have you run ./sage -br?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d9cc323

A bug was added accidentally. Removed.

[tara]

Replying to yomcat:

Replying to tara:

I don't see anything wrong with it. My doctest has been acting weird for the last couple of hours. On this file, its now giving me 13 errors, each of which saying that is_isomorphic() or _is_isomorphic() is only supposed to be taking one parameter. Before it was saying that everything passes when it shouldn't have been.

That sounds like you're partially in the wrong branch (so not all the changes are being applied). Have you run ./sage -br?

That worked for me. What exactly does ./sage -br do? I don't remember seeing it before.

[yomcat]

Replying to tara:

Replying to yomcat:

Replying to tara:

I don't see anything wrong with it. My doctest has been acting weird for the last couple of hours. On this file, its now giving me 13 errors, each of which saying that is_isomorphic() or _is_isomorphic() is only supposed to be taking one parameter. Before it was saying that everything passes when it shouldn't have been.

That sounds like you're partially in the wrong branch (so not all the changes are being applied). Have you run ./sage -br?

That worked for me. What exactly does ./sage -br do? I don't remember seeing it before.

It rebuilds the sage library (just the bits that have changed). You need to do it to make your updated code work.

​http://doc.sagemath.org/html/en/developer/walk_through.html#section-walkthrough-make