A heuristic algorithm for the Maximum Clique problem

[Peter Kovacs]

The attached patch contains the implementation of a recent heurstic algorithm for the max. clique problem. It applies an iterated local search method that is quite simple but really efficient and robust.

The patch also contains the documentation and a test file.

[Peter Kovacs]

I have two questions about the interface:

• What kinds of query functions would be nice to have apart from the current cliqueSize() and cliqueMap()? Would you like to have e.g. cliqueSet() and/or cliqueVector() to return the clique in standard containers?
• The random number generator options can be specified using one of the three constructors. Do you like this solution?

[Alpar Juttner]

Replying to kpeter:

The attached patch contains the implementation of a recent heurstic algorithm for the max. clique problem

Great!

I have two questions about the interface:

• What kinds of query functions would be nice to have apart from the current cliqueSize() and cliqueMap()? Would you like to have e.g. cliqueSet() and/or cliqueVector() to return the clique in standard containers?

Yes, why not?

Moreover, I would like to see an iterator for the elements of the click.

• The random number generator options can be specified using one of the three constructors. Do you like this solution?

Do you mean the rnd seed? (In fact, two of the three consrtuctors do this.)

Two more comments.

• There are myriad of max click algorithms around. A more specific name for this tool is a must.
• Do we profit from the constructor-run() separation anywhere? Or is it just for the uniformity with the other tools?

[Peter Kovacs]

Replying to alpar:

I have two questions about the interface:

• What kinds of query functions would be nice to have apart from the current cliqueSize() and cliqueMap()? Would you like to have e.g. cliqueSet() and/or cliqueVector() to return the clique in standard containers?

Yes, why not?

Moreover, I would like to see an iterator for the elements of the click.

Yes, this would be good. Moreover, iterator + map seem to be enough. I will implement it soon.

• The random number generator options can be specified using one of the three constructors. Do you like this solution?

Do you mean the rnd seed? (In fact, two of the three consrtuctors do this.)

"one of the three" - I mean you use only one constructor for an object.

Do you like the fact that the random generator options can be given to the constructor (not a separated function) and the three variants I wrote?

Two more comments.

• There are myriad of max click algorithms around. A more specific name for this tool is a must.

Okay. Possible variants (similarly to the min mean cycle algorithms):

• GrossoMc
• GrossoLocatelliPullanMc
• IteratedLocalSearchMc

Maybe, the second one would be the best, because it is the most specific, but it is long.

• Do we profit from the constructor-run() separation anywhere? Or is it just for the uniformity with the other tools?

It is just for uniformity. (But run() can be called several times for the same instance and the graph can be modified between executions.)

[Peter Kovacs]

The current implementation uses vector<char> and vector<vector<char> > data structures for internal representations of the graph and node sets. It is typically faster than using bool, but requires more space. Would it be good/important to introduce a second (optional) template parameter for the class to specify the type used for boolean values?

[Alpar Juttner]

Replying to kpeter:

The current implementation uses vector<char> and vector<vector<char> > data structures for internal representations of the graph and node sets. It is typically faster than using bool,

It's a bit weird to say that. The reality is that vector<bool> is typically faster but we've seen one application where vector<char> turned to be faster. If I remember correctly, the frequent write operation sequentially through the elements is less efficient in case of vector<bool>.

but requires more space.

Would it be good/important to introduce a second (optional) template parameter for the class to specify the type used for boolean values?

Can't we perform a sound test to check which one is better?

[Peter Kovacs]

Replying to alpar:

It's a bit weird to say that. The reality is that vector<bool> is typically faster

I don't think so, it depends on the use case. vector<bool> is usually slower unless you work with huge vectors and access the elements in a random order.

but we've seen one application where vector<char> turned to be faster

No, not only one. I have read a few experiments with similar conclusions on different sites (both for C++ and for other languages that have similar structures, e.g. boolean[] and BitSet in JAVA). Moreover, I made some quick tests before making the decision in this implementation, but I neglected to mention it.

If I remember correctly, the frequent write operation sequentially through the elements is less efficient in case of vector<bool>.

Sequential read and write are both slower in case of vector<bool>. The bottleneck operations of this algorihtm read the values sequentially.

Can't we perform a sound test to check which one is better?

I made a comprehensive test including all the DIMACS problem instances. Their size vary from n=100 to n=3300. Using vector<char> turned out to be significantly faster on _all_ instances. It was faster by a factor between 1.68 and 2.48 (1.92 on average). Therefore, I keep using char. I hope these results are satisfying.

[Peter Kovacs]

[c279b19abc62] contains a new version of the proposal. A CliqueNodeIt iterator class is added and MaxClique is renamed to GrossoLocatelliPullanMc. Do you like this name? It is correct, but maybe too long. GrossoMc would be shorter, but it seems to be unfair to the other authors, and GrossoEtAlMc is awkward.

[Peter Kovacs]

Other possible name would be IteratedLocalSearchMc.

[Alpar Juttner]

[c279b19abc62] is in the main branch.