#17711: Pre-processing for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_info
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | f62716539aaf4c236041d1e31dbf59bcb8bba750
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17711 |
Dependencies: |
#17647 |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
Comment:
Yooooooooooooo !
Does the job, very few comments (and a small commit at `public/17711b`):
- Calling `is_strongly_connected` is very cheap while
`g.strongly_connected_components_digraph` actually copies the whole
graph
{{{
sage: g=digraphs.DeBruijn(5,3)
sage: %timeit g.is_strongly_connected()
10000 loops, best of 3: 129 µs per loop
sage: %timeit g.strongly_connected_components_digraph()
1000 loops, best of 3: 1.31 ms per loop
}}}
Better to only copy it if necessary.
- Is there any reason why you only deal with digraphs ? `Digraph(G)` (when
`G`
is a graph) is not always strongly connected: `G` may not be connected.
The
same code could handle everything at once, couldn't it ?
- (unrelated) what on earth is this `random_DAG` function doing in the
global
namespace instead of being in `digraphs.<tab>` ? `O_O`
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17711#comment:5>
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.
