#17135: Compute diameter using 2sweep, 4sweep and iFUB
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | 6eb88ead909981bc89fea507cc1ea354fa0d175f
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
u/dcoudert/help |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by dcoudert):
* status: needs_work => needs_review
Comment:
Replying to [comment:5 ncohen]:
> Yo !!
>
> A second pass on this code. With this I guess that the 'technical
review' is done, but I haven't checked the correction yet, i.e. looked at
the papers and what they prove. I don't really like to make a non-obvious
algorithm the default one when we have a much simpler way to compute the
same value, but well, if it is faster ...
>
> - About {{{seen}}}. "It must be initialized, but there is no need to
initialize it".
>
> {{{
> + - ``seen`` -- bitset of size ``n`` that must be initialized before
calling
> + this method. owever, there is no nead to initialize it.
> }}}
I have revised the text as follows:
{{{
+ - ``seen`` -- bitset of size ``n`` that must be initialized before
calling
this method (i.e., bitset_init(seen, n)). However, there is no need
to
clear it.
}}}
> - {{{this method check is all}}} --> checkS iF all
>
> - {{{this helps saving}}} --> save
>
> - {{{when we already known}}} --> know
>
> - About your check for connected graphs: I find your {{{if
test_is_connected and len(seen)<n: return big_number}}} a bit weird given
that you just ran a BFS which is supposed to return the eccentricity of a
vertex (which, in particular, tests if the graph is connected}}}. And
actually, while you say that the ` simple_BFS` function returns the
eccentricity of `source`, it only does so when the graph is connected. If
it is not, it returns the (finite) eccentricity of `source` in its
connected component. Is there any reason why you should not do that
`simple_BFS` ?
>
> {{{
> #!diff
> -return distances[waiting_list[waiting_end]]
> +return distances[waiting_list[waiting_end]] if waiting_end ==
waiting_list+n-1 else UINT32_MAX
> }}}
>
> It would make the `simple_BFS` function more correct, and it also
means that you do not need to define this `is_connected` parameter as ...
checking this is totally free !
You are perfectly right! I have changed the code. I have removed the
useless parameter and now return the eccentricity of the source in the
graph:
{{{
return distances[waiting_list[waiting_end]] if waiting_end==n-1 else
UINT32_MAX
}}}
> - {{{This method search for}}} -> searches
ok
> - {{{diameter_lower_bound_4sweep_select_dichotomy}}}: really the
dichotomy should be done through bsearch
(http://www.cplusplus.com/reference/cstdlib/bsearch/) but I don't exactly
know how to provide `distances` as an argument. Too bad `:-/`
>
> By the way, do you really need the if `i==j-1` block ? Or would it be
sufficient to just replace `i=k` with `i=k+1` ?
>
> - In `lower_bound_4sweep`: you do not need a `improved` variable. Use a
`break` with a `while True`. And you can even have a `while tmp>LB` and no
`break` if you compute `tmp` at the end of the loop `:-P`
I agree that calling `bsearch` would be better, but I don't know how to do
it without introducing extra data structure (e.g., array of pairs (vertex,
distance)). I have simplified the code and removed the
{{{diameter_lower_bound_4sweep_select_dichotomy}}} method.
> - Is it only me or is the `4sweep` function doing much more that 4
sweeps ?
You are right. I don't know why they call it `4sweep` instead of
`multisweep`. I can change the name if you think it is more natural.
> - `diameter_iFUB` frees memory that it did not allocate itself. This
feels wrong `O_o`
I have removed these instructions.
> - I do not think that the comments about the data structure in
`diameter()` are necessary. All that this function does is call others.
>
> - There are useless variables in this function
I have shortened the comments and remove useless variables. It should be
cleaner now.
> Nathann
Thanks a lot for all the comments.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=6eb88ead909981bc89fea507cc1ea354fa0d175f
6eb88ea]||{{{multiple corrections and simplifications}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17135#comment:7>
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.
