#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: |
-------------------------------------+-------------------------------------
Comment (by borassi):
Done!
>
> In method `tarjan_strongly_connected_components_C`, you could do the
following:
> {{{
> if visited[v]:
> continue
> }}}
> and then remove one level of indentation.
Probably, you meant
{{{
if visited[u]:
continue
}}}
because the line `if visited[v]:` is followed by an else. Correct?
> 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.
Hmm, I did as you said, but the same problem might occur also in
`init_short_digraph`: if there are no edges, we set `edges=malloc(0)`, and
in the next line we test if edges is `NULL`. The result of `malloc(0)`
depends on the compiler implementation ![1], so for some compilers it
might output `NULL` by default. Do you think we should open a ticket
solving this issue?
[1] !http://stackoverflow.com/questions/1073157/zero-size-malloc
--
Ticket URL: <http://trac.sagemath.org/ticket/19014#comment:19>
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.
