Input file format

[quantum-brutus]

Hi,

Hope you are doing well.

I was wondering if there was resources available to understand the input file format of the graphs under the DIMACS convention.

I'm having trouble understanding it.

Thanks a lot.

[busygin]

Hi, The original DIMACS doc is here: http://stasbusygin.org/writings/ccformat.pdf Qualex-MS uses only edge inputs from DIMACS format, so your file should look like this:

c Comments (optional)
p edge <n_nodes> <n_edges>
e <v> <w>

With 'e' line for every edge of the graph (vertices are counted from 1). The binary is a bitwise triangle of the adjacency matrix. Vertex weights (for weighted max clique) can be supplied in a separate file. Hope this helps.

[quantum-brutus]

Hi, Thanks for your quick response. It is a bit more clear to me now.

So if I understand, the vertices are counted from 1 in the input file and from 0 in the solution file (by default) ?

Also, do you have an instance of a code to write binary files from graph examples ?

Thanks.

[busygin]

Yes, vertices are counted from 1 in input files but old solvers were printing from 0 in sol files. So, I added a param to count from 1 in .sol files too. The original DIMACS code for format conversion is here: http://archive.dimacs.rutgers.edu/pub/challenge/graph/translators/binformat/ There is also a better written code is in graph.c of Cliquer: https://users.aalto.fi/~pat/cliquer.html BTW, Cliquer is an exact solver and if you are interested in max clique you may find it useful too.

[quantum-brutus]

Thanks!

My goal is to benchmark MWC solvers for a certain problem (for now, I plan on implementing QUALEX-MS, FastWCLq, WLMC-2 and Cliquer).

Are you aware of any other state-of-the-art (open-source) algorithm ?

Thanks a lot already for your answers

[busygin]

Pablo San Segundo had a highly optimized exact max clique solver hosted on his startup BiiCode. But BiiCode doesn't exist anymore (it was supposed to be a Git competitor). Here is his ResearchGate page, maybe you can find how to contact him: https://www.researchgate.net/profile/Pablo-San-Segundo I expect the new generation of solvers like FastWCLq and WLMC-2 will outperform QUALEX-MS, but let me know if you get a surprising result :). I stopped working on it because my goal was more of pure math: define a family of quadratic-subject-to-quadratic relaxations for max independent set/clique and see if we can search for best among them. If you are interested, my write-up is here http://stasbusygin.org/writings/CliqueWrapper.pdf