#17135: Compute diameter using 2sweep, 4sweep and iFUB
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_work
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | c1a7c956bf54c962332303b4411e774b16c4ec10
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
u/dcoudert/help |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
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.
}}}
- {{{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 !
- {{{This method search for}}} -> searches
- {{{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`
- Is it only me or is the `4sweep` function doing much more that 4 sweeps
?
- `diameter_iFUB` frees memory that it did not allocate itself. This feels
wrong `O_o`
- 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
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17135#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.
