#17225: Degrees of looped *immutable* graphs are wrong
-------------------------+-------------------------------------------------
Reporter: | Owner:
kcrisman | Status: needs_review
Type: | Milestone: sage-6.4
defect | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 58cf24722664d1b299ab4de934455579125e3326
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17225 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Hello !
> Hmm, I see what you mean though, keeping track of all this extra data
could be expensive when people are searching through really large sets of
relatively large graphs (which is when this was implemented in the first
place). I wonder if that will impact efficiency or speed.
You should not worry too much about that. Performance is wasted in other
places, so this probably will not become a problem anytime soon.
The additional caching is only an array of ints of size n (no Python
involved, just real integers). You waste MUCH more ressources if your
graph carries a layout for its vertices, for instance ! `:-)`
Besides, it is indeed good that static graphs are MUCH lighter in memory
than Sage's usual graphs, but it is not why they were implemented: the
low-level data structure was implemented mostly for speed, because at this
level you can work on the graph directly without calling any function,
everything is as fast as it should be. They were later turned into an
immutable Python object because the algebraists wanted graphs as
dictionary keys.
The "main" problem though, is that immutable graphs are immutable, and
consequently you can only build an immutable graph from a mutable graph
(and the mutable graph is MUCH heavier in memory).
This, to say that this caching is not really a problem. What I wanted to
avoid was to add a useless "if" in the 'degree' function of the low-level
data structure. Fortunately, there is no such function for those graphs
are implemented to actually be ... digraphs ! And there we only have an
`out_degree` method, which is perfectly defined and only returns a
difference of pointers. In particular, no ugly 'if' there `:-P`
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17225#comment:8>
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.
