New algorithm for Max Clique in Graph class using Cython

[nathanncohen]

This depends on #6355.

CC: @rlmill

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller, Minh Van Nguyen

Merged: Sage 4.1.1.rc1

Issue created by migration from https://trac.sagemath.org/ticket/5793

[sagetrac-mabshoff]

comment:1

Hi,

the patch as is will not go into Sage since you are putting the sources for cliquer-1.2 into the Sage library tree where they do not belong.

I have not looked at the cython interface, but my guess would be that we need to change cliquer-1.2 to create a library. Please split the cython interface work (the code you wrote minus the cliquer-1.2 source code) and the cliquer-1.2.spkg work. The Cython code should remain here while spkg should go to #5669.

Cheers,

Michael

[nathanncohen]

comment:2

A new patch using the SPKG you can find at :
#6355

[rlmill]

comment:4

Duplication of #6355.

[jasongrout]

comment:5

To get this going again, here are some specific suggestions for patch 12427.patch and the associated spkg:

• copy the header files to somewhere in $SAGE_LOCAL/include (maybe $SAGE_LOCAL/include/cliquer/*.h

• Make a cliquer.pxd file that declares the necessary functions and structs from the header files. Make sure that you are only doing cdef externs from the header files, not the .c files like the patch is currently doing. Don't include the path; just do cdef extern from "cliquer/graph.h": since the header is in the include path. This cliquer.pxd file can go into sage/graphs.

• Make a cliquer.pyx in sage/graphs that contains the definitions of max_clique, all_max_clique, and clique_number. Document and add doctests to these functions.

• Delete the lines

from sage.graphs.graph import Graph 
#from distutils.core import setup 
#from distutils.extension import Extension 
from Cython.Distutils import build_ext 

• In module_list.py, add a libraries = ['cliquer'] option (see the surrounding declarations for examples of this).

• Compile the cliquer sources into a shared library, named libcliquer.so, using the instructions in the HowTo William posted. Place this shared library into $SAGE_LOCAL/lib.

• In the graphs.py, I don't think you need to do from sage.graphs.cliquer import clique_number. Since the module will be in that directory, I think it would be sufficient to do from cliquer import clique_number.

[jasongrout]

comment:6

rlm: this ticket has what looks like the most current patch, whereas #6355 does not have a patch. I'm reopening this ticket so that the "active" patch is not closed (but I am not opposed to moving this patch to #6355 to consolidate things!). I feel a bit silly commenting on a patch here when the ticket is closed, but the patch clearly has not been moved/merged/etc.

[jasongrout]

comment:7

Suggestions 1 and 6 in my comment above apply to the spkg, not the patch.

[robertwb]

comment:8

Whence the "../../../../local/lib/cliquer-1.2/cliquer.h" if there's no spkg. Also, I belive local/include is in the include path, so no need to have this long path. (And include files belong in local/include, not local/lib.) I would probably drop the 1.2 suffix so we don't have to update the link paths every time the version gets bumped.

[jasongrout]

comment:9

that's what I meant by point 2 (just do cdef extern from "cliquer/graph.h") and point 1 (put the headers in $SAGE_LOCAL/include/cliquer/*.h)

[nathanncohen]

comment:10

Here is a new patch ( number 12428 ) using a shared library !!! I hope you will appreciate it as it took me some time to figure out the inner behavior of Sage ;-)

The new spkg is available on #6355

Nathann

[nathanncohen]

comment:11

My version is working, but I am a bit lost with all the patches... How can I produce a patch containing all the modifications I made since the begining ( since I cloned the original branch, actually ) ?

Thanks !!!

[rlmill]

comment:12

One option is to clone the branch using hg_sage.clone, but to give it the revision number corresponding to the last patch not part of your changes (the base). Then you can copy the affected files over, and it is as if you have done all the work, but you have not checked anything in.

[nathanncohen]

comment:13

New patch "cliquer.patch" containing all the modifications for cliquer since the beginning. And with the good directory's name ;-)

[nathanncohen]

Attachment: cliquer.patch.gz

Cliquer, from the beginning to the end, with the good directory's name !

[rlmill]

comment:14

Nathann,

I have deleted the previous patches to avoid confusion.

When addressing the following issues, please post another patch to be applied on top of the first (this makes review easier).

1. algorithm=='networkx' is never tested, and if it were, it would fail, due to the cliques parameter

2. Why are you using cliquer.pxi instead of cliquer.pxd? If it were pxd instead, then other Cython files could cimport the same data types.

3. It should go:

if algorithm=='networkx':
    ...
elif algorithm=='cliquer':
    ...
else:
    raise NotImplementedError("Only 'networkx' and 'cliquer' are supported.")

Also you need to change one instance of 'Cliquer' to 'cliquer'.

4. In maximum_cliques, "vertex set" should be "vertex sets"

[nathanncohen]

comment:15

I hope all is fixed now... Though I just renamed cliquer.pxi to cliquer.pxd without really understanding the difference ^^;

By the way, I am not really sure this possibility to change the algorithm used to compute the cliquer number is that useful... Just take a look at this :

sage: g=graphs.RandomGNP(100,.5)
sage: time g.clique_number(algorithm="networkx")
CPU times: user 2.49 s, sys: 0.00 s, total: 2.49 s
Wall time: 2.49 s
9
sage: time g.clique_number()
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
9
sage: g=graphs.RandomGNP(150,.5)
sage: time g.clique_number(algorithm="networkx")
CPU times: user 18.45 s, sys: 0.04 s, total: 18.49 s
Wall time: 18.49 s
10
sage: time g.clique_number()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
10
sage: g=graphs.RandomGNP(200,.5)
sage: time g.clique_number(algorithm="networkx")
CPU times: user 82.33 s, sys: 0.18 s, total: 82.52 s
Wall time: 82.54 s
11
sage: time g.clique_number()
CPU times: user 0.07 s, sys: 0.00 s, total: 0.07 s
Wall time: 0.07 s
11

Anyway, from the practical point of view, it works now ;-)

Nathann

[nathanncohen]

Second patch

[nathanncohen]

comment:16

Attachment: cliquer-2.patch.gz

[rlmill]

Attachment: cliquer-4-rebased-sage.4.1.patch.gz

[rlmill]

comment:30

Replying to @nathanncohen:

Concerning the cliques, I agree when you say that a "A maximum clique is just a clique of maximal size", but a "maximal clique" is a clique such that there is no bigger clique in the graph -- according to the subset inclusion order (all the maximal cliques of a graph need not have the same cardinality) -- and this I what I thought I had read in the descriptions of the others functions.

I had realized this some time after writing that comment. Please forgive me.

[rlmill]

Editing.

[rlmill]

Attachment: cliquer-5-ref.patch.gz

Attachment: trac_5793-cliquer-flattened.patch.gz

Flattened patch based on sage-4.1.

[rlmill]

Reviewer: Robert Miller

[rlmill]

Author: Nathann Cohen

[rlmill]

comment:33

In the last patch:

1. I made all clique related functions start with clique_ so that you can do G.clique<tab> and see all of them.

2. Added a few doctests here and there

3. Deprecated cliques, since it is ambiguous.

[sagetrac-mvngu]

comment:34

With the SPKG at #6355 and the patch on this ticket, I got the following doctest failures:

sage -t -long devel/sage-main/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
**********************************************************************
File "/scratch/mvngu/release/sage-4.1.1.alpha0/devel/sage-main/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx", line 318:
    sage: clqs = (HS.complement()).cliques()
Expected nothing
Got:
    doctest:1: DeprecationWarning: The function 'cliques' has been deprecated. Use 'cliques_maximal' or 'cliques_maximum'.
**********************************************************************
1 items had failures:
   1 of  89 in __main__.example_2
***Test Failed*** 1 failures.
For whitespace errors, see the file /scratch/mvngu/release/sage-4.1.1.alpha0/tmp/.doctest_refinement_graphs.py
	 [231.6 s]

<SNIP>

sage -t -long devel/sage-main/sage/graphs/graph_coloring.py
**********************************************************************
File "/scratch/mvngu/release/sage-4.1.1.alpha0/devel/sage-main/sage/graphs/graph_coloring.py", line 208:
    sage: chromatic_number(G)
Expected:
    3
Got:
    doctest:224: DeprecationWarning: The function 'cliques' has been deprecated. Use 'cliques_maximal' or 'cliques_maximum'.
    3
**********************************************************************
1 items had failures:
   1 of   7 in __main__.example_5
***Test Failed*** 1 failures.
For whitespace errors, see the file /scratch/mvngu/release/sage-4.1.1.alpha0/tmp/.doctest_graph_coloring.py
	 [2.3 s]

[rlmill]

comment:35

Note: making the refinement_graphs doctest use Cliquer instead of NetworkX shaves about 21 seconds from the doctest time for the file!

[nathanncohen]

comment:36

I do not really know how to read patch files, but it seems to me you replaced :
m = max([len(c) for c in G.cliques()])
by
m = max([len(c) for c in G.cliques_maximum()])

If right, I have two remarks :

• The syntax of max([len(c) for c in G.cliques()]) makes me think that G.cliques() was meant to return the list of the maximAL cliques, and m is then meant to be the clique number of G. The expression max([len(c) for c in G.cliques_maximum()]) is syntaxically correct, thought as cliques_maximum returns only the maxiMUM cliques we may as well return the length of the first one as they all have the same size.
• In the end, and if I make no mistake, why about just setting m=G.clique_number() ?

I expect it to be way faster than an enumeration of all the cliques ! ;-)

[rlmill]

Apply on top of flattened patch

[rlmill]

comment:37

Attachment: trac_5793-part-6.patch.gz

Nathann,

Thanks for spotting that. The patch is updated!

[sagetrac-mvngu]

comment:38

I applied patches in the following order:

1. the SPKG at Cliquer to compute maximum cliques #6355
2. trac_5793-cliquer-flattened.patch
3. trac_5793-part-6.patch
   All doctests passed with Sage 4.1.1.rc0. So positive review.

[sagetrac-mvngu]

Changed reviewer from Robert Miller to Robert Miller, Minh Van Nguyen

[sagetrac-mvngu]

Merged: Sage 4.1.1.rc1