Pruning off-by-one error

[holmesco]

I think that there is an error in the vertex pruning after the heuristic clique is computed:

clipperp/src/clipperplus_clique.cpp

Line 29 in a524943

if(core_number[i] + 1 >= heuristic_clique.size()) {

There should not be a + 1 in the line above. This is because the only vertexes we should keep are the ones with K-Cores that correspond to a larger clique than what we have found already (i.e., $k(v) \geq |C|$). The algorithm and description in the paper also suggest this:

[KavehFathian]

Hi,

Thanks for the question.
I believe the algorithm that returns core_number[i] is zero-indexed, so we added a +1.

[holmesco]

I don't quite understand what you mean. If returned array is zero-indexed then shouldn't this line use core_number[i+1]?
As it is now, the one is added to the actual core number, regardless of how it's indexed.

[odeaxcsh]

Hello, I just tested the issue. This change was made by me in the last commit a524943.

The difference is between purpose of pruning, are we only looking for strictly larger graphs, or larger or equal graphs? The former seems more logical and is consistent with the paper. Ultimately, using "larger or equal" just makes pruning less effective and may add extra runtime cost.

I made that change because there was an issue with how we initialize the vector u (the initial value for the optimization part). Under some conditions, if parts of the heuristic graph are pruned, then setting u[keep_pose[i]] = 0 can translate to u[-1], which is undefined behavior. I think a much more reasonable fix is to add an if condition instated of assert , as line 9 of Algorithm 3 in the paper suggests.

[holmesco]

I agree with the first part, you definitely want to prune out vertices with core number strictly less than the current max clique size.

I think keep_pose[i]=-1 only occurs if the keep vector is empty, meaning that there are no remaining vertices after pruning. One easy fix is just to check the size of keep. If it is empty, then this serves as a max-clique certificate.

I am already working on this so I can submit a PR to this effect, if you like. The current unit tests are a little broken, do you guys have additional tests that you run?

[odeaxcsh]

Absolutely, a PR would be great and appreciated.

Regarding the tests, they need to be updated, expanded, and possibly refactored. I made a separate #12 on that and I'll gradually work towards that. Also, I used a point-cloud registration pipeline to test the algorithm with different graphs generated in that context. I think that would be a good addition as well.

As I understand it, the clique1 test fails because the graph has two maximum cliques, and an older refactoring caused the algorithm to pick a different one. I kept it intentionally, since it's a good hint about a limitation. The clique2 test fails due to certificates, which I need to look at in more detail, our chromatic certificate was updated, and in this case it wasn't able to certify the maximum clique which now it does. And clique3 fails because of a bug in the latest GCC release (15.2.1), which has been reported on bugzilla.

[holmesco]

On that note, I also noticed that there were other optimal cliques for clique3, I believe. I think maybe it's a good idea for the tests to just verify that the returned clique has the right size and that it actually is a clique (by verifying its edges)