Opened 7 years ago
Closed 6 years ago
#15753 closed enhancement (fixed)
Add BasisExchangeMatroid.isomorphism()
Reported by:  Rudi  Owned by:  

Priority:  minor  Milestone:  sage6.4 
Component:  matroid theory  Keywords:  
Cc:  Stefan, yomcat  Merged in:  
Authors:  Rudi Pendavingh  Reviewers:  Stefan van Zwam 
Report Upstream:  N/A  Work issues:  
Branch:  c6edefd (Commits, GitHub, GitLab)  Commit:  c6edefd889cf9331b43e0ac30a6cad45d41ebf42 
Dependencies:  Stopgaps: 
Description
Currently the abstract class BasisExchangeMatroid? provides a method .isomorphic() to test if two matroids are isomorphic, but that method does not return an isomorphism, if one exist.
I want to add a function that does.
Change History (24)
comment:1 Changed 7 years ago by
 Branch set to u/Rudi/ticket/15753
 Created changed from 01/28/14 19:57:06 to 01/28/14 19:57:06
 Modified changed from 01/28/14 19:57:06 to 01/28/14 19:57:06
comment:2 Changed 7 years ago by
 Commit set to ddfd7bdfcf587c8d3736fa68887fe7f15721b21c
comment:3 Changed 7 years ago by
 Commit changed from ddfd7bdfcf587c8d3736fa68887fe7f15721b21c to 077a75419879432860ad22ac87bbf9e14b81cdb9
Branch pushed to git repo; I updated commit sha1. New commits:
077a754  Added Matroid.isomorphism() and Matroid._isomorphism()

comment:4 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 7 years ago by
 Status changed from new to needs_review
I'm happy with this implementation, so have a look.
comment:6 Changed 7 years ago by
Hi, I noticed the following about the special cases for rank or corank 0 or 1 in basis_exchange_matroid.pyx and for rank 0 in basis_matroid.pyx. They return the identity map on the ground set of self rather than a map to the ground set of other. For example
sage: M = Matroid(matrix=Matrix(GF(2), [[1,1,0],[0,1,0],[0,0,0]])) sage: N = Matroid(matrix=Matrix(GF(2), [[0,1,1],[0,1,0],[0,0,0]])) sage: M.is_isomorphic(N) True sage: M.is_isomorphism(N, M.isomorphism(N)) False
sage: M = Matroid(groundset='abcde', bases=[[]]) sage: N = Matroid(groundset=range(5), bases=[[]]) sage: M.is_isomorphic(N) True sage: M.is_isomorphism(N, M.isomorphism(N)) ValueError: range of morphism does not contain groundset of other matroid.
For the rank/corank 0 case maybe the line
return {e:e for e in self.groundset()}
should be something like
return {list(self.groundset())[i]:list(other.groundset())[i] for i in range(len(self.groundset()))}
and for the rank 1 case
morphism = {list(M.groundset()M.loops())[i]:list(N.groundset()N.loops())[i] for i in range(len(M.groundset()M.loops()))} morphism2 = {list(M.loops())[i]:list(N.loops())[i] for i in range(len(M.loops()))} morphism.update(morphism2) return morphism
comment:7 Changed 7 years ago by
 Commit changed from 077a75419879432860ad22ac87bbf9e14b81cdb9 to d2088e2ecfd8115fa36ed16af684d1ebdc66fe8e
Branch pushed to git repo; I updated commit sha1. New commits:
d2088e2  BasisExchangeMatroid._isomorphism() and BasisMatroid._isomorphism() now properly handle rank<2.

comment:8 Changed 7 years ago by
Thanks for catching that, Rohan. I changed the rank=0 case as you suggested and removed the separate handling of rank=1.
comment:9 Changed 7 years ago by
comment:10 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:11 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:12 followup: ↓ 14 Changed 7 years ago by
Given that BasisExchangeMatroid
and BasisMatroid
both inherit from Matroid
, there is no point in adding cpdef _isomorphism(self, other)
in the .pxd
files for those.
Also, what's the advantage of making isomorphism()
(without underscore) a cpdef
method as opposed to just def
?
comment:13 Changed 7 years ago by
 Status changed from needs_review to needs_info
comment:14 in reply to: ↑ 12 Changed 7 years ago by
Replying to jdemeyer:
Given that
BasisExchangeMatroid
andBasisMatroid
both inherit fromMatroid
, there is no point in addingcpdef _isomorphism(self, other)
in the.pxd
files for those.
OK, I'll remove these then.
Also, what's the advantage of making
isomorphism()
(without underscore) acpdef
method as opposed to justdef
?
We did not really think about this. But is there a disadvantage? Cpdef just allows cdef child classes to override the function. While I don't see why anyone would want that, why make it impossible? These are slow, highlevel functions, so a little pointer testing at the start of the function won't affect overall efficiency.
I wanted to upload a patch but today sage b exits with: "src/convert.c:1:0: error: unknown value '10.10' of mmacosxversionmin scons: * * * [src/convert.os] Error 1"
I guess my OSX version is too new.
So feel free to make these changes, or wait until I find another way to test + upload a patch.
comment:15 Changed 6 years ago by
I wanted to finish this up now that my OSX version is not too new anymore, but I get a new type of error when compiling the patch.
RudiPeninghsMBP:sage rudi$ ./sage b Install file: "include/interrupt.h" as "/Users/rudi/Documents/Development/sage/local/include/csage/interrupt.h" Install file: "include/ntl_wrap.h" as "/Users/rudi/Documents/Development/sage/local/include/csage/ntl_wrap.h" gcc o src/interrupt.os c fPIC I/Users/rudi/Documents/Development/sage/local/include I/Users/rudi/Documents/Development/sage/local/include/python2.7 I/Users/rudi/Documents/Development/sage/local/include/NTL Iinclude src/interrupt.c g++ o src/ZZ_pylong.os c fPIC I/Users/rudi/Documents/Development/sage/local/include I/Users/rudi/Documents/Development/sage/local/include/python2.7 I/Users/rudi/Documents/Development/sage/local/include/NTL Iinclude src/ZZ_pylong.cpp In file included from src/ZZ_pylong.cpp:13:0: include/ntl_wrap.h:255:35: error: using typedefname 'NTL::mat_ZZ' after 'struct'
EXTERN void mat_ZZ_SetDims(struct mat_ZZ* mZZ, long nrows, long ncols);
^{ }
In file included from include/ntl_wrap.h:13:0,
from src/ZZ_pylong.cpp:13:
/Users/rudi/Documents/Development/sage/local/include/NTL/mat_ZZ.h:12:17: note: 'NTL::mat_ZZ' has a previous declaration here
typedef Mat<ZZ> mat_ZZ;
Etcetera.
This happens only if I work on the branch related to this ticket, not the master. Can anyone try to compile this patch to confirm that this is related to the patch and not something else?
comment:16 Changed 6 years ago by
This is an old ticket. It'll probably build on the branch after you do a "make distclean" or something. Alternatively, you can merge the ticket with the current develop branch. The easiest way (as a reviewer) is to do
git trac try 15753
(assuming you have the gittrac command installed correctly). For working on the ticket, I'd probably stay on this branch, or look into rebasing (I'm still not sure what the policy is, read up on it in the developer manual).
comment:17 Changed 6 years ago by
 Commit changed from d2088e2ecfd8115fa36ed16af684d1ebdc66fe8e to 3173b33f49757e8e4d247e0aebe618fa744a0ded
Branch pushed to git repo; I updated commit sha1. New commits:
db8762a  Added ._isomorphism to both BasisExchangeMatroid and BasisMatroid.

6f700c4  Added Matroid.isomorphism() and Matroid._isomorphism()

ffbb3ae  BasisExchangeMatroid._isomorphism() and BasisMatroid._isomorphism() now properly handle rank<2.

c863756  removed cpdef _isomorphism(self,other) from basis_exchange_matroid.pyx and basis_matroid.py

3173b33  Merge branch 'u/Rudi/ticket/15753' of git://trac.sagemath.org/sage into t/15753/ticket/15753

comment:18 Changed 6 years ago by
 Status changed from needs_info to needs_review
Thanks, Stefan, for pointing out that I should rebase. Very happy that this problem is out of the way.
I rebased, then made my final edits, and tried to push. Another merge was necessary before I could finally push. Hope it all worked out correctly.
comment:19 followup: ↓ 21 Changed 6 years ago by
Two minor comments and a question:
 In BasisExchangeMatroid?._is_isomorphic you changed four lines in the EXAMPLES section to remove BasisMatroid? conversions. While today that doesn't matter, I would prefer to keep those to ensure that this file's version of the isomorphism test gets used, instead of some subclass's file.
 In Matroid._isomorphism you didn't indent the EXAMPLES block.
Fix those two things and the code gets a positive review from me.
One remark though: in Sage's graph class, there is a fairly common idiom to have an option in the test methods of the form certificate=True/False
. When set to True, the function returns (True, f)
if an isomorphism f is found, and (False, )
otherwise. I'm not saying we should follow this here (isomorphism is important enough to be its own function), but we may want to consider it for other test methods.
comment:20 Changed 6 years ago by
 Commit changed from 3173b33f49757e8e4d247e0aebe618fa744a0ded to c6edefd889cf9331b43e0ac30a6cad45d41ebf42
Branch pushed to git repo; I updated commit sha1. New commits:
c6edefd  Doctest fixes

comment:21 in reply to: ↑ 19 Changed 6 years ago by
Replying to Stefan:
Two minor comments and a question:
 In BasisExchangeMatroid?._is_isomorphic you changed four lines in the EXAMPLES section to remove BasisMatroid? conversions. While today that doesn't matter, I would prefer to keep those to ensure that this file's version of the isomorphism test gets used, instead of some subclass's file.
To make sure that this file's version of the isomorphism test eventually gets used (and in particular, not BasisMatroid?._is_isomorphic), I put back the BasisMatroid? conversions for just one of each pair of matroids.
 In Matroid._isomorphism you didn't indent the EXAMPLES block.
I did so now.
One remark though: in Sage's graph class, there is a fairly common idiom to have an option in the test methods of the form
certificate=True/False
. When set to True, the function returns(True, f)
if an isomorphism f is found, and(False, )
otherwise. I'm not saying we should follow this here (isomorphism is important enough to be its own function), but we may want to consider it for other test methods.
I'll keep it in mind.
New commits:
c6edefd  Doctest fixes

New commits:
c6edefd  Doctest fixes

comment:22 Changed 6 years ago by
 Status changed from needs_review to positive_review
This one's good to go!
comment:23 Changed 6 years ago by
 Reviewers set to Stefan van Zwam
comment:24 Changed 6 years ago by
 Branch changed from u/Rudi/ticket/15753 to c6edefd889cf9331b43e0ac30a6cad45d41ebf42
 Resolution set to fixed
 Status changed from positive_review to closed
Made a first implementation by modifying the existing _is_isomorphic. It compiles and the doctests work. I will run a few tests before I put it up for review.
New commits:
Added ._isomorphism to both BasisExchangeMatroid and BasisMatroid.