#17227: Add new cutting rules for computing hyperbolicity
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers: Nathann Cohen
theory | Work issues:
Keywords: | Commit:
Authors: David | 48345733408db3721c5bbeba3031b2f4c0673492
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17227 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by dcoudert):
* status: needs_work => needs_review
* reviewer: => Nathann Cohen
Comment:
Replying to [comment:14 ncohen]:
> Yo David !
>
> I just finished the first review. It is 16h38 right now, and I have been
working
> on this code for the last 4h hours. It is too much. This ticket should
have been
> implemented into several small tickets. It is also very very difficult
to keep
> track of what is happening, as the main functions handle many different
> algorithms at the same time. Please think for a while about how you
could make
> it more modular, so that it becomes easier to understand in the future.
Really sorry about that. Next time I will try to make small patches only,
although it is not always easy to do.
> Besides: the function {{{hyperbolicity}}} contains the following
algorithms:
> {{{"'basic'", "'basic+'", "'cuts'", "'cuts+'", "'dom'"}}}. Not only the
names
> are unclear, but that is probably too much. I do not expect that all
will be
> useful to users, or useful for us to keep, especially when handling them
all
> makes the code so complicated. Could you think about those we do not
really
> need, to remove them in another ticket ?
Well, since we have 'basic+', we don't need 'basic' anymore.
We could also rename 'cuts' as 'CCL', but I don't know if it is more
explicit...
We can try in another ticket.
> Besides making the comments below, I implemented some modifications to
> understand the code a bit better. The most important changes, in terms
of lines
> of code, only move "malloc" together, so that memory allocation problems
are all
> checked at the same time.
>
> Here is the review:
>
> - For each of the three methods explained in the section "Algorithms and
> complexity" of the module header, could you mention the corresponding
flag of
> `hyperbolicity` ?
done
> - You say in the doc that Soto proved that `hyp(a,b,c,d)<= dist(a,b)/2`
but in
> the code we have
>
> {{{
> if 2*distances[a][b] <= h_LB:
> continue
> }}}
>
> I expected `distances[a][b]/2 <= h_LB`. Or actually, maybe the bound
proved by
> Soto was actually `hyp(a,b,c,d)<= 2*dist(a,b)` (in which case the code
is
> correct and the doc is wrong), as otherwise his bound is better than
ours.
I have corrected the documentation. Soto proved that `hyp(a,b,c,d) <=
2*dist(a,b)`.
So we can skip 4-tuples such that `2*dist(a,b) <= h_LB`.
> - It is more compact to make all memory allocations at the same place,
and only
> have one block of code to free everything if there was a problem.
`free(NULL)`
> is valid.
>
> - your `unsigned short ** c_far_apart` only stores 0s and 1 (the amount
of
> unused memory is `15/16=93%` `:-P`). We have something in
`mic/binary_matrix`
> that you may like (though it may not be worth the extra complexity in
this
> case).
I'm clearly consuming much more memory than necessary.
If the extra cost is not too high, I may propose the modification in
another patch.
> - The function which returns all far-apart pairs considers points in
different
> connected components to be a far-away pair. Is that what you want ?
Either
> way, please document it.
far-apart pairs are defined only in connected graphs. I have updated the
documentation of the method to precise that it assumes that the input
graph is connected.
> - The documentation of __hyperbolicity__ claims that the function
implements an
> algorithm from CCL12. Also, the comment just above the function talks
about a
> decreasing pair ordering.
I have changed the comment to `Compute the hyperbolicity using a the
algorithm of [CCL12]_`.
> - There are many variables that you specialise to uint32_t when actually
nobody
> cares. The code would be easier to read if they were int variables.
>
> - `__hyperbolicity__` is only meant for connected graphs (you ask for a
> diameter) -- could you write this explicitly somewhere ?
I added a comment.
> ... after something like two hours of review: this patch is too big.
Really, really, really, sorry about that.
> - What about renaming this "STOP" thing to "GOTO_RETURN" ?
>
> - Please do not write a commit that changes the indentation of a block
of
> code. Modify the first commit itself.
>
> - Is there any reason why this block
>
> {{{
> # Termination if required approximation is found
> }}}
>
> Is not on the same level as
>
> {{{
> # If we cannot improve further, we stop
> }}}
>
> It feels like the two play the same role in the algorithm.
>
> - You define two values for 'STOP' but you never use them. Was that
meant to
> only leave one loop instead or two, and remove one of the two copies
of the
> blocks:
>
> {{{
> # If we cannot improve further, we stop
> # Termination if required approximation is found
> }}}
>
> It would be a nice change indeed, the implementation is already
sufficiently
> complicated.
>
> - {{{h_UB if STOP==2 else h}}} : why don't you just set the right value
of h_UB
> right before setting `STOP==2` ?
Following your comments, I have:
* renamed "STOP" to "GOTO_RETURN".
* Remove the `STOP==2` test by setting `h_UB = h` when optimality is
proven.
* Put some tests at same level.
I don't see how to remove one of the two blocks of tests since one is used
each time the upper bound is reduced and the other each time the lower
bound is improved.
> - In "hyperbolicity" a large portion of the code deals with the
> block-decomposition. Why couldn't you just call hyperbolicity on each
block ?
> You would not have to allocate memory in a loop, and the is_clique
test would
> be done automatically too (+the others)... You may lose a bit of time
as the
> block_decomposition would be recomputed on each block, but I do not
think that
> it is such a big problem compared to the cost of the algorithm.
Actually, I
> doubt that many real instances have a cut-vertex. That would remove a
big
> chunck of code, too.
Actually, many real instances have many cut-vertices! For instance, the
graphs of the autonomous systems of the Internet collected by CAIDA have a
large number of cut-vertices. The largest 2-connected component has 2/3 of
the vertices only. The same hold for co-authors graphs and so on.
I have however modified the method. This is easier to read this way.
It is also faster when the input graph is 2-connected since we avoid a
useless copy of the graph.
> - {{{while len(DOM)<4: DOM.append(H.random_vertex())}}} what if that new
vertex
> was in {{{DOM}}} already ?
I fixed this issue using a set instead of a list for DOM.
> Nathann
Many, many thanks Nathann.
David.
PS: sorry for the multiple commits. I'm still lost with git. For instance,
I don't know how to modify a commit without creating a new commit.
--
Ticket URL: <http://trac.sagemath.org/ticket/17227#comment:15>
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.
