#19014: Tarjan Strongly Connected Components Algorithm
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_work
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: | cbe780c0862c46304ce2b0da4c844178a9ecc8e6
u/borassi/tarjan_strongly_connected_components_algorithm| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by dcoudert):
* status: needs_review => needs_work
Comment:
In method `tarjan_strongly_connected_components_C`, you could do the
following:
{{{
if visited[v]:
continue
}}}
and then remove one level of indentation.
In method `strongly_connected_components_digraph_C`.
{{{
output.edges = <uint32_t *> sage_malloc(m*sizeof(uint32_t))
if output.edges == NULL and output.m != 0:
raise ValueError("Problem while allocating memory (edges)")
output.neighbors = <uint32_t **>
sage_malloc((1+<int>output.n)*sizeof(uint32_t *))
if output.neighbors == NULL and output.m != 0:
raise ValueError("Problem while allocating memory (neighbors)")
}}}
must be replaced by something link
{{{
if output.m==0:
<< DO APPROPRIATE OPERATIONS FOR THIS CASE >>
<< RETURN >>
output.edges = <uint32_t *> sage_malloc(m*sizeof(uint32_t))
output.neighbors = <uint32_t **>
sage_malloc((1+<int>output.n)*sizeof(uint32_t *))
if output.edges == NULL or output.neighbors == NULL:
raise MemoryError("Problem while allocating memory (edges or
neighbors).")
}}}
This is not only a cosmetic change since when `m==0` you allow
`output.neighbors==NULL` before the instruction `output.neighbors[0] =
output.edges`. So your code is currently not safe.
Otherwise, the method is working very well
{{{
Before
sage: set_random_seed(0)
sage: D = digraphs.RandomDirectedGNM(100000,500000)
sage: D.is_strongly_connected()
False
sage: %time res = D.strongly_connected_components()
len(res)
CPU times: user 3min 50s, sys: 4.28 s, total: 3min 55s
Wall time: 3min 56s
sage: len(res)
1413
With this patch
sage: set_random_seed(0)
sage: D = digraphs.RandomDirectedGNM(100000,500000)
sage: D.is_strongly_connected()
False
sage: %time res = D.strongly_connected_components()
CPU times: user 481 ms, sys: 16.2 ms, total: 497 ms
Wall time: 499 ms
sage: len(res)
1413
sage: D.allow_multiple_edges(True)
sage: D
Multi-digraph on 100000 vertices
sage: D.add_edges(D.edges())
sage: D.size()
1000000
sage: %time res = D.strongly_connected_components()
CPU times: user 566 ms, sys: 20.4 ms, total: 587 ms
Wall time: 594 ms
sage: len(res)
1413
}}}
and as you can see, I also tried with a multi-digraph and its working as
expected.
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/19014#comment:18>
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.
