MCQD to compute max cliques

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Jernej reported that this solver was faster than cliquer on some instances.

So we need it :-P

Nathann

Install the new (optional) spkg : attachment: mcqd-1.0.tar.bz2

CC: @sagetrac-azi

Component: graph theory

Author: Nathann Cohen

Branch/Commit: c0158ed

Reviewer: Jernej Azarija

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 66d0e3b to c2dc8ce

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

comment:1

Attachment: mcqd-1.0.tar.bz2.gz

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c2dc8ce trac #16083: mcqd solver for max cliques

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c2dc8ce to ad90443

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ad90443 trac #16083: mcqd solver for max cliques

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:3

Hello,

how do I install the mcqd package? The attached tar.bz2 for one appears to be corrupt..

azi@bodysnatcher:/tmp$ mv mcqd-1.0.tar.bz2.1 mcqd-1.0.tar.bz2
azi@bodysnatcher:/tmp$ tar -xf mcqd-1.0.tar.bz2 
bzip2: (stdin) is not a bzip2 file.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:4

The file looks good to me ...

/tmp$ tar -xf mcqd-1.0.tar.bz2 
/tmp$

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:5

God. I had forgotten to set it to needs_review.. That's dangerous O_O;;;;

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:7

Nathann,

as promised here are my comments !

I was not able to test the code since I cannot figure out how to install the module. What am I supposed to do with the tar.bz2?
Following are some comments about the code/politics:

2.1. The program mcqd consists of a single .h file. Since the author of the code agrees that we can use the program in Sage, is there any reason not to simply put this .h file along with the .pyx module? This way we can also tweak the file a bit (I'd like to remove debug stuff and unnecessary verbosity counters that are present in the code)

2.2 (mcqd.pyx) The variable c0 is a pointer to c. Hence I am wondering, why do you need to allocate memory ? On line 39 you assign the ptr c to it and lose the reference to the allocated space.

2.3 (mcqd.pyx) Lines 30-37. Can they be made shorter by using the fact (is it true ????) that sage_free(NULL) is legal?

2.4 (mcqd.pyx) Can we get rid of the memset by using sage_calloc on c?

2.5 (mcqd.pyx) At the very end C should be deleted.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:8

Yoooooooooooo !

I was not able to test the code since I cannot figure out how to install the module. What am I supposed to do with the tar.bz2?

Save it in SAGE_ROOT/upstream/ and run "sage -f mcqd" (on the right branch)

2.1. The program mcqd consists of a single .h file. Since the author of the code agrees that we can use the program in Sage, is there any reason not to simply put this .h file along with the .pyx module?

Yes : the code has not been reviewed. And it "may" be updated, which is why we try not to change third-party code.

2.2 (mcqd.pyx) The variable c0 is a pointer to c.

?... No, it is not O_o

c0 is a pointer to n*n booleans.

2.3 (mcqd.pyx) Lines 30-37. Can they be made shorter by using the fact (is it true ????) that sage_free(NULL) is legal?

Right. Done

2.4 (mcqd.pyx) Can we get rid of the memset by using sage_calloc on c?

Done.

2.5 (mcqd.pyx) At the very end C should be deleted.

Why ? This is done automatically, isn't it ? You don't have to dealloc objects when nothing else points toward them.

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`55e2922`	`trac #16083: Merged with 6.3.beta2`
`303de89`	`trac #16083: Reviewer's comments`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from ad90443 to 303de89

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:10

Replying to @nathanncohen:

Yoooooooooooo !

I was not able to test the code since I cannot figure out how to install the module. What am I supposed to do with the tar.bz2?

Save it in SAGE_ROOT/upstream/ and run "sage -f mcqd" (on the right branch)

Thanks I'll check that out and report back!

2.1. The program mcqd consists of a single .h file. Since the author of the code agrees that we can use the program in Sage, is there any reason not to simply put this .h file along with the .pyx module?

Yes : the code has not been reviewed. And it "may" be updated, which is why we try not to change third-party code.

2.2 (mcqd.pyx) The variable c0 is a pointer to c.

?... No, it is not O_o

Nevermind about that I was talking nonsense.

c0 is a pointer to n*n booleans.

2.3 (mcqd.pyx) Lines 30-37. Can they be made shorter by using the fact (is it true ????) that sage_free(NULL) is legal?

Right. Done

2.4 (mcqd.pyx) Can we get rid of the memset by using sage_calloc on c?

Done.

2.5 (mcqd.pyx) At the very end C should be deleted.

Why ? This is done automatically, isn't it ? You don't have to dealloc objects when nothing else points toward them.

No I am not sure this is done. In C++ there is no garbage collector so whatever you allocate with new you have to dealocate with delete()

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

a555604 trac #16083: "del C"

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 303de89 to a555604

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:12

BTW, are you sure del is good? Shouldn't you use C++'s delete?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:13

BTW, are you sure del is good? Shouldn't you use C++'s delete?

http://docs.cython.org/src/userguide/wrapping_CPlusPlus.html C++ objects can now be dynamically allocated with new and del keywords.

Nathann

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:14

I am still not able to run the code :-(

azi@bodysnatcher:~/sage$ sage -f mcqd
Found local metadata for mcqd-1.0
Found local sources at /home/azi/sage/upstream/mcqd-1.0.tar.bz2
.......blahblah............
Finished installing mcqd-1.0.spkg

and then

azi@bodysnatcher:~/sage$ sage
.........blahblah............
Done updating paths.
sage: G = graphs.PetersenGraph()
sage: G.clique_number(algorithm='mcqd')
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-2-99d3195b7504> in <module>()
----> 1 G.clique_number(algorithm='mcqd')

ImportError: Please install the mcqd package

The new code looks good except for a minor question:

Why you use double variables for the adjacency matrix? Is there any benefit from allocating a n*n matrix and using a nested for loop to fill it?

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:15

Okay, so I was missing the step of running sage -b. Thanks Nathann for the private email.

As for this ticket I'd just like to hear the answer to

Why you use double variables for the adjacency matrix? Is there any benefit from allocating a nn matrix and using a nested for loop to fill it?*

(as posted above) and if sage -t works for you then we are good to go!!

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:16

Yo !

As for this ticket I'd just like to hear the answer to

Why you use double variables for the adjacency matrix? Is there any benefit from allocating a nn matrix and using a nested for loop to fill it?*

What do you mean by "double variables" ? Do you mean that I allocate both "c" (linear size) and "c0" (quadratic size) ?

If so, that is because what MCQD expects is the vector c, which points toward the entries of c0.

Nathann

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:17

Yes, I am quite confused by that. Following is how I used to (successfully) call mcqd from a *.pyx file, but I don't seem to be using the same convention as you say. I hope I am not bothering you with this I'd just like to understand what I was doing here and what you're doing in your code :)))

def clique_number_fast(G):
    n = G.order()

    cpdef bool **adj
    cpdef int clorder
    cpdef int *clverts

    adj= <bool **> malloc(sizeof(bool *)*n)
    for i in xrange(n):
        adj[i] = <bool *> calloc(n, sizeof(bool))    

    # Warning we are assuming the vertices are labeled from 0...n-1
    for i,j in G.edges(labels=False):
        adj[i][j] = True
        adj[j][i] = True

    cpdef Maxclique *m = new_Maxclique(adj,n,0.025)
    m.mcqdyn(clverts, clorder); 
    # Yes, I am supposed to free the entire array but the above is just an indication of what is causing the error
    for i in xrange(n): free(adj[i])

    free(adj)

    return clorder

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:18

Hello !

Yes, I am quite confused by that. Following is how I used to (successfully) call mcqd from a *.pyx file, but I don't seem to be using the same convention as you say. I hope I am not bothering you with this I'd just like to understand what I was doing here and what you're doing in your code :)))

I do exactly what you did. The only difference is that I only do ONE memory allocation while you allocate n vectors (all your adj[i]). Now, you should write a check that all vectors have been correctly allocated, and if not deallocate them all, and this is what I wanted to avoid by allocating just one big vector of size n*n and making adj point toward pieces of it.

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:19

I hope I am not bothering you with this I'd just like to understand what I was doing here and what you're doing in your code :)))

This is precisely the reviewer's job :-P

Nathann

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:20

Oh I see it now. OK.

Then as far as I am concerned the code is good to go once you confirm that sage -t passes through for you!

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:21

Well, it does in the graph/ folder, and clearly no other code calls that.

Nathann

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

Reviewer: Jernej Azarija

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Description changed:

--- 
+++ 
@@ -4,3 +4,4 @@

 Nathann

+Install the new (optional) spkg : [attachment: mcqd-1.0.tar.bz2](https://github.com/sagemath/sage-prod/files/10658643/mcqd-1.0.tar.bz2.gz)

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:23

Thaaaaaaaaaaaaanks! :-)

ca0b67cc-9d10-44c6-be51-5d9e2cdee96a commented 10 years ago

comment:24

Actually, thank you for doing all this patches and stuff !!!!!!

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:25

Actually, thank you for doing all this patches and stuff !!!!!!

:-D

Nathann

vbraun commented 10 years ago

comment:26

sage -t --long src/sage/graphs/mcqd.pyx
**********************************************************************
File "src/sage/graphs/mcqd.pyx", line 15, in sage.graphs.mcqd.mcqd
Failed example:
    from sage.graphs.mcqd import mcqd
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.graphs.mcqd.mcqd[0]>", line 1, in <module>
        from sage.graphs.mcqd import mcqd
    ImportError: No module named mcqd
**********************************************************************

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

c0158ed trac #16083: Broken doctest

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from a555604 to c0158ed

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:28

Sorry.. All the lines except the import statement were tagged with "optional" :-/

Nathann

vbraun commented 10 years ago

Changed branch from public/mcqd to c0158ed

sagemath / sage

MCQD to compute max cliques #16083