#6578: [with patch, positive review] fast subgraphs by building the graph
instead
of deleting things
---------------------------+------------------------------------------------
Reporter: jason | Owner: rlm
Type: defect | Status: new
Priority: major | Milestone: sage-4.1.1
Component: graph theory | Keywords:
Reviewer: Robert Miller | Author: Jason Grout
Merged: |
---------------------------+------------------------------------------------
Changes (by rlm):
* reviewer: => Robert Miller
Comment:
Replying to [comment:4 jason]:
> I think delete copies the graph, which doesn't *add* every edge, but
probably just copies the edge dictionary, which should be *way* faster.
What is this opinion based on? If it's not an inplace subgraph then it
creates a copy, which calls networkx_graph, which calls NX's copy, which
has the following lines:
{{{
for e in self.edges_iter():
H.add_edge(e)
}}}
So we're definitely not using the adjacency dictionary there. The
crossover between add and delete you observed above is most likely due to
overhead from the fact that calling Sage's add_edge is using several
layers of Python functions.
I expect this to change drastically once the graph backends are optimized.
This may be a while in the future, but you should keep this in mind for
when that does eventually happen. In general, this patch is an
improvement, since it provides both options, but thinking in terms of
optimization at this stage is going to result in wasted effort, since the
floor is about to drop out from underneath any current timings.
Anyway, everything looks good here (especially, applies to 4.1.1.alpha0
and passes tests), so let's go ahead and merge it!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6578#comment:5>
Sage <http://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 post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
