#18484: Implement k-chordality of a matroid
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner:
Type: enhancement | Status: needs_info
Priority: minor | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: chord | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/matroids/k_chordal-18484 | 6f9e8633781d3843c59d8b89e333b1844c090880
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Replying to [comment:14 tscrim]:
> I'm not quite sure what you mean by this:
>
> > Efficiency will not be a reason to not give that positive review.
>
I just meant to say that I will not demand optimal efficiency as necessary
for a positive review. Making code correct first and efficient later is a
fine way to go. So I will accept code as long as it is correct.
> I'd take the code which is more efficient. However I think checking for
a frozenset being in the ''frozenset'' `circuits` as containment is
(amortized) O(1) and we have to generate all circuits anyways...well at
least for `chordality`.
Generating all the circuits will be the most time-consuming part of
chordality() and is_k_chordal(), I agree. From that perspective, tweaking
_is_circuit_chordal() is not going to matter much for the efficiency.
>I'm not sure that testing for closures would be faster as circuits are
generally relatively small. Will you be running timings between the two
codes or do you want me to?
You do get some improvement. Your code:
{{{
sage: from sage.matroids.advanced import *
sage: M = BinaryMatroid(graphs.CompleteGraph(8).incidence_matrix())
sage: %time M.is_k_chordal()
CPU times: user 806 ms, sys: 2.86 ms, total: 809 ms
Wall time: 809 ms
True
}}}
With my tweaks:
{{{
sage: %time M.is_k_chordal()
CPU times: user 453 ms, sys: 3.82 ms, total: 457 ms
Wall time: 458 ms
True
sage: %time M.circuits()
CPU times: user 359 ms, sys: 1.3 ms, total: 360 ms
Wall time: 361 ms
Iterator over a system of subsets
}}}
So not counting the time spent on computing the circuits, the speedup is
4,5x on this example.
With the example you sent, computing circuits completely dominates the
running time. The effect on the overall running time is essentially zero.
I leave it to you. I'm convinced by now of correctness, and you can set a
positive review for this version if you want. If you want to make changes,
I'll take another look later.
--
Ticket URL: <http://trac.sagemath.org/ticket/18484#comment:15>
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.
