#18183: Implement two matroid polytopes
-------------------------+-------------------------------------------------
Reporter: | Owner:
chapoton | Status: needs_review
Type: | Milestone: sage-6.6
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
matroid theory | Work issues: documentation
Keywords: | Commit:
matroid polytope | 6484e7198d41b716f4cb70dcf56ea7d849a6ce90
Authors: | Stopgaps:
Frédéric Chapoton |
Report Upstream: N/A |
Branch: |
u/chapoton/18183 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Hellooooooooo,
> Well, I see your point. The true problem is that there is no
`independent_sets` method for matroids.
You can get one like that:
{{{
def independent_sets_iterator(M):
from sage.combinat.subsets_hereditary import
subsets_with_hereditary_property
for x in
subsets_with_hereditary_property(M.is_independent,M.groundset()):
yield x
}}}
Disclaimers:
1) It is a 'fake' iterator, i.e. the amount of memory it requires is far
from
constant. It does not store all bases at once, but you will store at
some
point the union of 'independent sets of size r or r+1' for all r
2) I have no idea if the method is optimal algorithmically. It is meant to
work
for any 'hereditary' function (a property verified by
`Matroid.is_independent`), and in particular does not use any property
of
matroids
3) I suspect that it is asymptotically faster than what you do right now.
The
matroid algorithm to enumerate all independent sets of size 'r' is to
try all
'r'-subset and run a `is_independent` test.
4) This implementation is at a much higher level than the Matroid
implementation: the matroid code works on bitsets, while
`subsets_with_hereditary_property` works on lists of arbitrary objects.
There
is a (possibly big) loss of time there.
5) There is a nice customization inside of
`subsets_with_hereditary_property`,
which is why I implemented this function: if it detects that `{a,b,c}`
is not
an independent set it will never try a superset of `{a,b,c}` again
(this is
achieved through some caching of the answers of the test function.
> what do you mean about the ref ?
Oh sorry. I thought that it was a half-finishef entry, I had not noticed
that
you were only refering to another one (which is properly written).
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18183#comment:10>
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.
For more options, visit https://groups.google.com/d/optout.
