Opened 18 months ago
Closed 18 months ago
#20660 closed enhancement (fixed)
Add Certificate to is_isomorphic() in the matroids package
Reported by:  tara  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  matroid theory  Keywords:  matroid, isomorphism 
Cc:  Stefan, yomcat  Merged in:  
Authors:  Tara Fife  Reviewers:  Michael Welsh 
Report Upstream:  N/A  Work issues:  
Branch:  d9cc323 (Commits)  Commit:  d9cc323ddb1d66bfe39b40a8191a55a515d13966 
Dependencies:  Stopgaps: 
Description
We are going to add an option to get certificate when testing if two matroids are isomorphic. I will be doing this.
Change History (25)
comment:1 Changed 18 months ago by
 Component changed from PLEASE CHANGE to matroid theory
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 18 months ago by
 Branch set to public/ticket/20660
comment:3 Changed 18 months ago by
 Commit set to 4ee8641a27d6ac2492f0233c057754af7acfc99f
comment:4 Changed 18 months ago by
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 980981).
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?
comment:5 followup: ↓ 6 Changed 18 months ago by
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)
comment:6 in reply to: ↑ 5 Changed 18 months ago by
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.
comment:7 Changed 18 months ago by
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.
comment:8 Changed 18 months ago by
 Commit changed from 4ee8641a27d6ac2492f0233c057754af7acfc99f to ea46145fe2a6d8b243e155e54918cb5b9c6a2190
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

comment:9 Changed 18 months ago by
 Status changed from new to needs_review
comment:10 Changed 18 months ago by
I'll have a proper look later, but you should change cert
to certificate
as is_3connected()
has for consistency.
comment:11 Changed 18 months ago by
 Commit changed from ea46145fe2a6d8b243e155e54918cb5b9c6a2190 to 12a4b3d50d34912f44c6f700b95fdc7360612162
Branch pushed to git repo; I updated commit sha1. New commits:
12a4b3d  Changed cert to certificate

comment:12 Changed 18 months ago by
 Status changed from needs_review to needs_work
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
tocertificate
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.
comment:13 Changed 18 months ago by
 Commit changed from 12a4b3d50d34912f44c6f700b95fdc7360612162 to a584a6e0b6c84e8c7aff4d2258dfc479a8053235
Branch pushed to git repo; I updated commit sha1. New commits:
a584a6e  Fixed errors from comment

comment:14 Changed 18 months ago by
 Commit changed from a584a6e0b6c84e8c7aff4d2258dfc479a8053235 to 18db65aea44f52153f355a3ebada1a8a421e5876
Branch pushed to git repo; I updated commit sha1. New commits:
18db65a  Fixed spacing

comment:15 Changed 18 months ago by
 Reviewers set to Michael Welsh
First, you have a bunch of doubledup doctests (one with the explicit option, one without).
This happens (it's due to a capital C):
sage t long warnlong 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/sagedevel/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 498, in _run self.compile_and_execute(example, compiler, test.globs) File "/Applications/sagedevel/local/lib/python2.7/sitepackages/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/sagedevel/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
comment:16 Changed 18 months ago by
 Commit changed from 18db65aea44f52153f355a3ebada1a8a421e5876 to 380af24ea18e92f156fb4b5f76b41daee1dc47cb
Branch pushed to git repo; I updated commit sha1. New commits:
380af24  Fixed errors

comment:17 Changed 18 months ago by
 Commit changed from 380af24ea18e92f156fb4b5f76b41daee1dc47cb to d39e113b1f206c1351d9699f45186653d5b91b49
Branch pushed to git repo; I updated commit sha1. New commits:
d39e113  Missed one doctest

comment:18 Changed 18 months ago by
You missed one doctest, but I cleaned it up. If you're happy now with that (I'm happy now), set it to positive.
comment:19 followup: ↓ 20 Changed 18 months ago by
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.
comment:20 in reply to: ↑ 19 ; followup: ↓ 22 Changed 18 months ago by
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
?
comment:21 Changed 18 months ago by
 Commit changed from d39e113b1f206c1351d9699f45186653d5b91b49 to d9cc323ddb1d66bfe39b40a8191a55a515d13966
Branch pushed to git repo; I updated commit sha1. New commits:
d9cc323  A bug was added accidentally. Removed.

comment:22 in reply to: ↑ 20 ; followup: ↓ 24 Changed 18 months ago by
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.
comment:23 Changed 18 months ago by
 Status changed from needs_work to positive_review
comment:24 in reply to: ↑ 22 Changed 18 months ago by
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#sectionwalkthroughmake
comment:25 Changed 18 months ago by
 Branch changed from public/ticket/20660 to d9cc323ddb1d66bfe39b40a8191a55a515d13966
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Added an optional parameter cert to allow the user to ask for a certificate if the two matroids are isomorphic.