Vote on including Cliquer standard in Sage

[Robert Miller]

There are clear advantages to including this in Sage:

sage: G = graphs.RandomGNP(400, .1)

sage: time G.clique_number(algorithm='networkx')
CPU times: user 1.79 s, sys: 0.01 s, total: 1.80 s
Wall time: 1.87 s
5

sage: time G.clique_number(algorithm='cliquer')
CPU times: user 0.12 s, sys: 0.00 s, total: 0.12 s
Wall time: 0.13 s
5

The code is lightweight (only five C files), and the spkg uses a very
simple SCons script to build. I've tested it on sage.math and on 32
and 64 bit OS X. It is GPL v2+.

[William Stein]

I don't think voting can happen until people can actually trivially
try it out on several machines? I.e., can you post directions for
people to install the spkg, etc., so they can try it out, look at the
code, etc.

William

[Robert Miller]

I should mention that all you need to try it out is the spkg here:

http://trac.sagemath.org/sage_trac/ticket/6355

and the patch (trac_5793-cliquer-flattened.patch) here:

http://trac.sagemath.org/sage_trac/ticket/5793

[Robert Miller]

Also relevant is the project's homepage:

http://users.tkk.fi/pat/cliquer.html

[William Stein]

Thanks. I installed this into http://alpha.sagenb.org, so people can
easily try it out.
Make sure to do "Action --> Restart worksheet" to get the new version
of Sage with cliquer. Then this should work:

sage: G = graphs.RandomGNP(1000, .1)

sage: time G.clique_number(algorithm='cliquer')

CPU times: user 1.34 s, sys: 0.11 s, total: 1.45 s
Wall time: 1.45 s
6

sage: time G.clique_number(algorithm='networkx')

CPU times: user 17.41 s, sys: 0.00 s, total: 17.41 s
Wall time: 17.41 s
6
sage: 17.41 / 1.45
12.0068965517241
sage:

The cliquer web page says "Cliquer was developed on Linux, and it
should compile without modification on most modern UNIX systems. Other
operating systems may require minor changes to the source code."

What build testing have you done?

How will cliquer be used in the sage library? How hard is porting it
to Microsoft Windows going to be?

William

[Robert Miller]

> What build testing have you done?

As I mentioned in the original post, I've tested it on sage.math and

on 32 and 64 bit OS X.

> How will cliquer be used in the sage library?

Being able to compute maximum cliques has nice applications all over
the place, but at first it will just be in G.cliques_maximum(),
G.clique_number(), etc.

> How hard is porting it to Microsoft Windows going to be?

No idea, but it's a very small C library, so hopefully this will mean
a small amount of work will get it going.

[Robert Miller]

> > How hard is porting it to Microsoft Windows going to be?
>
> No idea, but it's a very small C library, so hopefully this will mean
> a small amount of work will get it going.

I should also mention that everything Cliquer can do, NetworkX can do
as well, but abysmally slower, so that in case it is a problem to port
to Windows, it won't slow anything down too much (in terms of
development, not computation... ;-).

[William Stein]

OK, then I vote +1 to inclusion of Cliquer.

-- William