#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):
I think you started studying the code in the wrong file. The main entry
point is matroid.pyx. This is an abstract class of which all others
derive. It implements all functionality in terms of just the rank function
(ok... it'll convert to BasisMatroid for things like isomorphism testing).
It should be fairly straightforward, and the code does not swerve far from
pure Python.
BasisExchangeMatroid is a common framework for BasisMatroid and
LinearMatroid. Internally the groundset is translated to a list of
integers, which are used for bitset indexing. So we have
* regular methods. User-facing, expected to be careful with input
checking.
* underscored methods. May assume properties regarding their input (type
is frozenset, elements are from groundset, two sets are disjoint, ...)
* doubly underscored methods. Very internal use (usually cdef). Use the
encoded version of the groundset, and may have bitset arguments into which
the return value is copied.
I think most people who will be adding code, will not move beyond the
first underscore (things like union() belong in the generic Matroid class
anyway). But certainly the cdef methods deserve a little bit of an
explanation.
And yes:
{{{
sage: A = Matrix(GF(7), [[1,0,1,1],[0,1,1,2]])
sage: type(A)
sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float
}}}
In our matroid code we store the entries simply as a list of GF(q)
elements, with some splicing commands for row operations. Results in a 10-
to 20-time speedup in places. It's weird.
I hope I'll get around to doing the further edits soon!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7477#comment:27>
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.
