#7477: Matroids
----------------------------------------------------+-----------------------
Reporter: ncohen | Owner: jkantor
Type: enhancement | Status:
needs_review
Priority: major | Milestone: sage-5.10
Component: combinatorics | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Stefan van Zwam, Rudi Pendavingh | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------+-----------------------
Comment (by Stefan):
Thanks for all your kind words, and for your suggestions! Michael Welsh
and I worked on them, and the improved code is now on the ticket. Below
I'll address your concerns one by one.
To ncohenn:
- Similar code for circuits(), cocircuits(), nonspanning_circuits(),
nonspanning_cocircuits().
Organizing the code into a common, abstract function is not worth the
trouble, in my opinion.
It will be hard to do so without incurring a speed loss in these
exponential-in-the-worst-case
methods.
- Lingering commented-out code from development has been removed.
To vbraun:
- PEP8 compliance has been achieved, except for line lengths.
- Docstring markup should be much closer to Sage's standards (we use
imperatives everywhere, EXAMPLES is plural, INPUT, OUTPUT singular. I did
not revisit all inputs to see if they specify type clearly, and did not
work on
referencing markup).
- SetSystem has twofold functionality right now. It serves as return type
for methods like circuits(). We plan to change this in the future: the
"yield" keyword did not work in Cython when we started out.
The other function is partition refinement for isomorphism testing. This
is mostly of internal use, and makes use of some tweaks. I think a revised
SetSystem definitely has its place in sage.sets, but our current effort is
not nearly polished enough, and is best kept for internal use by the
Matroid code.
- Matrix functionality: touching Sage's matrix code was daunting: finite
field matrices seem to use floating-point implementations, and I did not
want to risk speed regressions elsewhere in Sage. I'm following the M4R1
and related efforts with interest, and once they are viable, moving our
code back to them is easy enough.
To darij
- We want this code to be useful enough, and fast enough, to answer our
research questions. These questions routinely generate and compare
hundreds of thousands matroids, so
we aimed for efficiency that matches the best C code out there (Macek
and Gordon Royle's private code). We're not there in all methods, but our
binary matroids and our isomorphism
test are really fast.
- I added an example to the description of BasisExchangeMatroid to clarify
what a child class might do.
- I expanded the description of the (not yet implemented) class
TransversalMatroid a little.
- I fixed the typos mentioned.
- Yes, "augment" will return the maximal such set.
- The B-fundamental circuit of e is the unique circuit contained in B+e.
This is standard terminology in matroid theory. I added a line to the
method explaining this. I was somewhat surprised that we have no user-
facing
version of it, but that'll be for a later trac ticket.
- The B-fundamental cocircuit of e is the unique cocircuit meeting B only
in e. This is the dual notion of the previous item.
- Matroid union is on my wish list. Again, a later trac ticket.
- I added a definition of hyperplane, and removed the offending "if".
- Added an extra check to max_weight_independent and
max_weight_coindependent (and two doctests covering this case)
- Removed the double check on self.full_rank()
- Added the transpose. The minus sign is to ensure the row spaces of the
matrices are orthogonal complements of each other.
- Feature suggestion: I suggest opening a trac ticket. Do you want just
True or False, or a list of all maximizing bases? Maybe an option to
max_weight_independent would suffice (e.g. find_all=False)? Oh, wait, that
is
expensive to compute when the weight function is constant.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7477#comment:25>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
