#17408: Faster transitive_reduction (=> faster Poset creation)
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: poset | Commit:
Authors: | ce577a909e3ac2835f975cc9515b54459174e8ca
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17408 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by nbruin):
Replying to [comment:15 jmantysalo]:
> What is the rationale behind current implementation? I mean, there must
be some example where `UniqueRepresentation` makes things faster.
I suspect it was done out of dogma: "Parents are supposed to be unique" in
sage. That statement by itself is not correct: not all parents need to be
unique. However, equal-but-non-identical parents can cause some minor
problems in the coercion framework.
The real catch is if you're building a parent that can serve as base for
other parents that ARE unique representation. Because cache keys there are
looked up by equality and not identity, you can really confuse the
coercion framework to the point of getting buggy behaviour. See
[http://trac.sagemath.org/ticket/15248#comment:2] for an explanation of a
classic example.
There is always a solution to this: do not inherit from
!UniqueRepresentation or !UniqueFactory but do inherit from
!WithEqualityById (or implement that by yourself). It gives you a very
cheap but mathematically not terribly useful equality test. However,
there's something to say for it: The two posets `A={1,2,3}` and
`B={1,2,3}` with trivial relation (ie. x<=y iff x==y) are isomorphic, but
not uniquely so. So unless we're explicitly saying by what isomorphism
`A,B` are to be identified, perhaps we should treat them as not equal.
After all, `C={a,b,c}` (with empty relation) is also isomorphic to `A` and
`B` and there no-one would be tempted to say C is equal to A and B.
However, such strict equality might be too hard to swallow for people who
want their computer algebra system to cater a little more to intuitive,
human reasoning. In that case you can just make your parent non-unique,
but still define equality to be by some looser equivalence relation. You
should just document that your class is not appropriate for use as a base
for another `UniqueRepesentation` parent.
--
Ticket URL: <http://trac.sagemath.org/ticket/17408#comment:16>
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.
