#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: | 417476495e176150d2ba92bed3b6b894314fc185
u/borassi/tarjan_strongly_connected_components_algorithm| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by dcoudert):
> because the line `if visited[v]:` is followed by an else. Correct?
you did the correct modification.
> > In method `strongly_connected_components_digraph_C`.
> ...
>
> 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
I have checked in files `sage/ext/memory_allocator.pyx`. It uses methods
like `check_allocarray` which can be found in `memory.pxd`. These methods
ensure that if `n==0` then the returned pointer is `NULL`, and this is
compiler independent. Furthermore, these methods raise an error if
something goes wrong with malloc. So no need for opening a ticket, it's
already done ;)
So if you want to be on the safe side and to ease your life, use the
memory allocator and/or the `check_alloc` methods, depending on the
context.
In your code, it means that you can call
{{{
output.edges = <uint32_t *> check_allocarray(m, sizeof(uint32_t))
}}}
and then remove the NULL test.
Of course, what you did for the case `m==0` is also important.
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/19014#comment:21>
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.
