#20660 closed enhancement (fixed)

Add Certificate to is_isomorphic() in the matroids package

Reported by: tara Owned by:
Priority: major Milestone: sage-7.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 12 months ago by yomcat

  • Component changed from PLEASE CHANGE to matroid theory
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 12 months ago by tara

  • Branch set to public/ticket/20660

comment:3 Changed 12 months ago by git

  • Commit set to 4ee8641a27d6ac2492f0233c057754af7acfc99f

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

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

comment:4 Changed 12 months ago by 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?

comment:5 follow-up: Changed 12 months ago by 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)

comment:6 in reply to: ↑ 5 Changed 12 months ago by 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.

comment:7 Changed 12 months ago by 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.

comment:8 Changed 12 months ago by git

  • Commit changed from 4ee8641a27d6ac2492f0233c057754af7acfc99f to ea46145fe2a6d8b243e155e54918cb5b9c6a2190

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

ea46145Fixed bug in basis_matroid, and updated the documentation is basis_exchange_matroid

comment:9 Changed 12 months ago by tara

  • Status changed from new to needs_review

comment:10 Changed 12 months ago by yomcat

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

comment:11 Changed 12 months ago by git

  • Commit changed from ea46145fe2a6d8b243e155e54918cb5b9c6a2190 to 12a4b3d50d34912f44c6f700b95fdc7360612162

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

12a4b3dChanged cert to certificate

comment:12 Changed 12 months ago by yomcat

  • 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 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.

comment:13 Changed 12 months ago by git

  • Commit changed from 12a4b3d50d34912f44c6f700b95fdc7360612162 to a584a6e0b6c84e8c7aff4d2258dfc479a8053235

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

a584a6eFixed errors from comment

comment:14 Changed 12 months ago by git

  • Commit changed from a584a6e0b6c84e8c7aff4d2258dfc479a8053235 to 18db65aea44f52153f355a3ebada1a8a421e5876

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

18db65aFixed spacing

comment:15 Changed 12 months ago by yomcat

  • Authors set to Tara Fife
  • Reviewers set to Michael Welsh

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

comment:16 Changed 12 months ago by git

  • Commit changed from 18db65aea44f52153f355a3ebada1a8a421e5876 to 380af24ea18e92f156fb4b5f76b41daee1dc47cb

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

380af24Fixed errors

comment:17 Changed 12 months ago by git

  • Commit changed from 380af24ea18e92f156fb4b5f76b41daee1dc47cb to d39e113b1f206c1351d9699f45186653d5b91b49

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

d39e113Missed one doctest

comment:18 Changed 12 months ago by 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.

comment:19 follow-up: Changed 12 months ago by 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.

comment:20 in reply to: ↑ 19 ; follow-up: Changed 12 months ago by 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?

comment:21 Changed 12 months ago by git

  • Commit changed from d39e113b1f206c1351d9699f45186653d5b91b49 to d9cc323ddb1d66bfe39b40a8191a55a515d13966

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

d9cc323A bug was added accidentally. Removed.

comment:22 in reply to: ↑ 20 ; follow-up: Changed 12 months ago by 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.

comment:23 Changed 12 months ago by tara

  • Status changed from needs_work to positive_review

comment:24 in reply to: ↑ 22 Changed 12 months ago by 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

comment:25 Changed 12 months ago by vbraun

  • Branch changed from public/ticket/20660 to d9cc323ddb1d66bfe39b40a8191a55a515d13966
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.