#17227: Add new cutting rules for computing hyperbolicity
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_work
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | 48345733408db3721c5bbeba3031b2f4c0673492
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17227 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
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.
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 ?
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` ?
- `basic+` : you should have kept this for a different patch. It is not
necessary to implement it with the rest and it makes the review of the
big
thing harder.
- 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.
- 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).
- 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.
- 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.
- 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 ?
... after something like two hours of review: this patch is too big.
- 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` ?
- 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.
- {{{while len(DOM)<4: DOM.append(H.random_vertex())}}} what if that new
vertex
was in {{{DOM}}} already ?
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17227#comment:14>
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.
