#17316: RegularMatroid.is_isomorphic returns false positives
----------------------------------------+------------------------
Reporter: Stefan | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.4
Component: matroid theory | Resolution:
Keywords: matroid, isomorphism | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
----------------------------------------+------------------------
Comment (by Rudi):
The bug is in _hypertest, or rather in the assumption that any isomorphism
of the labelled graphs produced by _hypergraph() will also be an
isomorphism of the projection matrices up to row/column scaling by -1. I
know how to resolve this, but even with the release candidate I cannot
develop on Yosemite (I cannot checkout this ticket). So here is my
proposed fix, if anyone wants to get it over with right now. Otherwise,
you have to wait until the regular development on Yosemite works again.
1) _hypertest, rather than returning True/False, should return an
isomorphism or None. I think I would prefer it if the isomorphism is
already translated to a map from the groundset of self to the groundset of
other.
2) in _fast_isom_test, the final `return self._hypertest(other)' should be
replaced with:
m=self._hypertest(other)
if m is None: return False
if self.is_field_isomorphism(other, m): return True
In the remaining case, _fast_isom_test should return None, so that really
is the bottom line.
This will solve the issue. Is there a good reason why in _hypergraph, the
vertex labels of the graph are not identical to the labels of the matroid
ground set? If the `isomorphism' method is an implementation of McKay's
algorithm, it may be possible to hand RegularMatroid._is_field_isomorphism
down to that routine, and it will look a matroid isomorphism among the
graph isomorphisms. That would be an even cleaner alternative solution.
In addition, I would make the following optimizations:
3) in _invariant: compute the number of negative triangles of the
projection matrix and stick that number in the hashed invariant:
P = self._projection()
A = {}
B = {}
N = 0
for i in xrange(P.nrows()):
w = P.get_unsafe(i, i)
if w != 0:
if w in A:
A[w] += 1
else:
A[w] = 1
for j in xrange(i):
w = abs(P.get_unsafe(i, j))
if w != 0:
if w in B:
B[w] += 1
else:
B[w] = 1
for k in range(j):
if
P.get_unsafe(i,j)*P.get_unsafe(j,k)*P.get_unsafe(k,i)<0:
N=N+1
self._r_invariant = hash(tuple([tuple([(w, A[w]) for w in
sorted(A)]), tuple([(w, B[w]) for w in sorted(B)]), N]))
return self._r_invariant
4) In _hypergraph, these negative triangles themselves could also be
added, as in the snippet of `old code'.
5) _projection: also looks a bit wasteful to me now. det(X)*X.inverse() is
just X.adjoint(). So:
if self._r_projection is None:
R = self._basic_representation()._matrix_()
self._r_projection = R.transpose() * (R *
R.transpose()).adjoint() * R
return self._r_projection
--
Ticket URL: <http://trac.sagemath.org/ticket/17316#comment:1>
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.
