#19014: Tarjan Strongly Connected Components Algorithm
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: Strongly | Merged in:
connected components, Tarjan | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | 8df530ab5c761501b10ba397e361889b4be91833
u/borassi/tarjan_strongly_connected_components_algorithm| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by borassi):
* status: new => needs_review
Comment:
Hi!
I think Sage was really missing a linear-time algorithm for strongly
connected components (in particular, I implemented it because I need it
for other algorithms). It improves a lot the old algorithm when the graph
has many components, but it is a bit slower when the graph is connected,
as shown by the following examples. In any case, I removed the old
algorithm: I know that it might have been faster in some rare cases, but
the difference is small, and the time spent to input the graph is usually
bigger than the time needed to run this algorithm.
Do you like it?
Michele
{{{
Old algorithm
sage: g = digraphs.RandomDirectedGNM(10000,30000)
sage: %timeit g.strongly_connected_components()
100 loops, best of 3: 18.3 ms per loop
New algorithm
sage: g = digraphs.RandomDirectedGNM(10000,30000)
sage: %timeit g.strongly_connected_components()
1 loops, best of 3: 5.61 s per loop
Old algorithm
sage: g = digraphs.Circuit(100000)
sage: %timeit g.strongly_connected_components()
10 loops, best of 3: 98.4 ms per loop
New algorithm
sage: g = digraphs.Circuit(100000)
sage: %timeit g.strongly_connected_components()
10 loops, best of 3: 183 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/19014#comment:4>
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.
