#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: |
-------------------------------------+-------------------------------------
Comment (by dcoudert):
Hello,
You have inverted the timing for GNM. I got
{{{
OLD algorithm
sage: set_random_seed(0)
sage: g = digraphs.RandomDirectedGNM(10000,30000)
sage: %timeit g.strongly_connected_components()
1 loops, best of 3: 7.87 s per loop
sage: g.add_cycle(g.vertices())
sage: %timeit g.strongly_connected_components()
100 loops, best of 3: 21 ms per loop
sage: g = digraphs.Circuit(100000)
sage: %timeit g.strongly_connected_components()
10 loops, best of 3: 142 ms per loop
NEW algorithm
sage: set_random_seed(0)
sage: g = digraphs.RandomDirectedGNM(10000,30000)
sage: %timeit g.strongly_connected_components()
100 loops, best of 3: 21.5 ms per loop
sage: g.add_cycle(g.vertices())
sage: %timeit g.strongly_connected_components()
10 loops, best of 3: 22.1 ms per loop
sage: g = digraphs.Circuit(100000)
sage: %timeit g.strongly_connected_components()
10 loops, best of 3: 260 ms per loop
}}}
I agree that the gain for non-strongly connected digraphs is so high that
it is worth the small increase for strongly connected digraphs.
I have some remarks:
- Do we really need to have both `_tarjan_strongly_connected_components`
and `tarjan_strongly_connected_components` ? Same for other methods.
What's the motivation behind?
- What's the need for returning a dictionary? it is immediately converted
to a list of lists in `strongly_connected_components`. Do you need this
feature for something else?
- You have let another version of `strongly_connected_components` in
`static_sparse_graph.pyx`. Is this method used somewhere?
- Have you tried using an array of short instead of a bitset for
`in_scc_stack` ? We don't have memory issue here so we can save some
operations, plus you already do that for `visited`
- In `_strongly_connected_components_digraph` you have but you don't use
`MemoryAllocator`. Here also, you could use array of shorts instead of
bitset.
- I don't really see the benefit of using numpy (I don't know it). Is it
just more convenient or also faster that other methods? You could use
something like
{{{
d = {i:list() for i in range(nscc)}
for u,i in scc.iteritems():
d[i].append(u)
output = [d[i] for i in range(nscc)]
}}}
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/19014#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.
