Opened 7 years ago

Closed 6 years ago

#15753 closed enhancement (fixed)

Add BasisExchangeMatroid.isomorphism()

Reported by: Rudi Owned by:
Priority: minor Milestone: sage-6.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:

Status badges

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 Rudi

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

  • Commit set to ddfd7bdfcf587c8d3736fa68887fe7f15721b21c

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:

ddfd7bdAdded ._isomorphism to both BasisExchangeMatroid and BasisMatroid.

comment:3 Changed 7 years ago by git

  • Commit changed from ddfd7bdfcf587c8d3736fa68887fe7f15721b21c to 077a75419879432860ad22ac87bbf9e14b81cdb9

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

077a754Added Matroid.isomorphism() and Matroid._isomorphism()

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 7 years ago by Rudi

  • Status changed from new to needs_review

I'm happy with this implementation, so have a look.

comment:6 Changed 7 years ago by rohan

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 git

  • Commit changed from 077a75419879432860ad22ac87bbf9e14b81cdb9 to d2088e2ecfd8115fa36ed16af684d1ebdc66fe8e

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

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

comment:8 Changed 7 years ago by Rudi

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 Rudi

  • Authors set to Rudi Pendavingh

comment:10 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:12 follow-up: Changed 7 years ago by jdemeyer

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 jdemeyer

  • Status changed from needs_review to needs_info

comment:14 in reply to: ↑ 12 Changed 7 years ago by Rudi

Replying to jdemeyer:

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.

OK, I'll remove these then.

Also, what's the advantage of making isomorphism() (without underscore) a cpdef method as opposed to just def?

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, high-level 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 -mmacosx-version-min 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 Rudi

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 typedef-name '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 Stefan

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 git-trac 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 git

  • Commit changed from d2088e2ecfd8115fa36ed16af684d1ebdc66fe8e to 3173b33f49757e8e4d247e0aebe618fa744a0ded

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

db8762aAdded ._isomorphism to both BasisExchangeMatroid and BasisMatroid.
6f700c4Added Matroid.isomorphism() and Matroid._isomorphism()
ffbb3aeBasisExchangeMatroid._isomorphism() and BasisMatroid._isomorphism() now properly handle rank<2.
c863756removed cpdef _isomorphism(self,other) from basis_exchange_matroid.pyx and basis_matroid.py
3173b33Merge branch 'u/Rudi/ticket/15753' of git://trac.sagemath.org/sage into t/15753/ticket/15753

comment:18 Changed 6 years ago by Rudi

  • 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 follow-up: Changed 6 years ago by 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.
  • 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 git

  • Commit changed from 3173b33f49757e8e4d247e0aebe618fa744a0ded to c6edefd889cf9331b43e0ac30a6cad45d41ebf42

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

c6edefdDoctest fixes

comment:21 in reply to: ↑ 19 Changed 6 years ago by Rudi

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:

c6edefdDoctest fixes

New commits:

c6edefdDoctest fixes

comment:22 Changed 6 years ago by Stefan

  • Status changed from needs_review to positive_review

This one's good to go!

comment:23 Changed 6 years ago by Stefan

  • Reviewers set to Stefan van Zwam

comment:24 Changed 6 years ago by vbraun

  • Branch changed from u/Rudi/ticket/15753 to c6edefd889cf9331b43e0ac30a6cad45d41ebf42
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.