#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:
-------------------------------------+-------------------------------------
Changes (by Rudi):
* status: needs_review => needs_info
Comment:
Hi Travis,
Code compiles, doctests run. No trailing whitespace anywhere :)
Your code looks mathematically correct to me, but I have not ran tests.
I asked for info because I think your _circuit_chordal works very hard to
get an answer:
{{{
for x in self.groundset():
if x in C:
continue
for i in xrange(len(C)):
for p in combinations(C, i): # p is a list
if (frozenset(p + (x,)) in circuits
and C.difference(p).union([x]) in
circuits):
return True
}}}
The following will accomplish the same without testing all subsets of C:
{{{
X = set(C)
e = X.pop()
for x in self._closure(X)-X: # cl(X)=cl(C), and to be a chord x
must be spanned by C
Ax = self._circuit(X.union([x]))
Bx = C.difference(Ax).union([x])
if self._is_circuit(Bx):
return True # if x is spanned by C, then A+x is the unique
circuit in C-e+x; so x is a chord iff the complementary B is a circuit.
}}}
I expect that is_circuit will be faster than checking membership of
circuits (since C is a very large set in general) but that could perhaps
be tested. Do you have a large chordal graph lying around?
Efficiency will not be a reason to not give that positive review. So let
me know if you want to change your code. If not, I'll proceed to doing
some tests.
--
Ticket URL: <http://trac.sagemath.org/ticket/18484#comment:12>
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.
