Opened 7 years ago
Closed 7 years ago
#16083 closed enhancement (fixed)
MCQD to compute max cliques
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  graph theory  Keywords:  
Cc:  azi  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Jernej Azarija 
Report Upstream:  N/A  Work issues:  
Branch:  c0158ed (Commits, GitHub, GitLab)  Commit:  c0158edff1516bbca93ff330acbec1d1a5238049 
Dependencies:  Stopgaps: 
Description (last modified by )
Jernej reported that this solver was faster than cliquer on some instances.
So we need it :P
Nathann
Install the new (optional) spkg : mcqd1.0.tar.bz2
Attachments (1)
Change History (30)
Changed 7 years ago by
comment:1 Changed 7 years ago by
 Commit changed from 66d0e3b709bdf9d06014b487e54ee1e9c0d3e595 to c2dc8ce055b4005bc68f59d90e24f835f9ff9b1e
comment:2 Changed 7 years ago by
 Commit changed from c2dc8ce055b4005bc68f59d90e24f835f9ff9b1e to ad90443749baad49c5b0e0919b7fed13cf2324cc
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ad90443  trac #16083: mcqd solver for max cliques

comment:3 Changed 7 years ago by
Hello,
how do I install the mcqd package? The attached tar.bz2 for one appears to be corrupt..
azi@bodysnatcher:/tmp$ mv mcqd1.0.tar.bz2.1 mcqd1.0.tar.bz2 azi@bodysnatcher:/tmp$ tar xf mcqd1.0.tar.bz2 bzip2: (stdin) is not a bzip2 file.
comment:4 Changed 7 years ago by
The file looks good to me ...
/tmp$ tar xf mcqd1.0.tar.bz2 /tmp$
Nathann
comment:5 Changed 7 years ago by
 Status changed from new to needs_review
God. I had forgotten to set it to needs_review
.. That's dangerous O_O;;;;
comment:6 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 followup: ↓ 8 Changed 7 years ago by
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 3037. 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.
comment:8 in reply to: ↑ 7 ; followup: ↓ 10 Changed 7 years ago by
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 thirdparty 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 3037. 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
comment:9 Changed 7 years ago by
 Commit changed from ad90443749baad49c5b0e0919b7fed13cf2324cc to 303de8966e0c76f31f33b135370cee22edb12b9b
comment:10 in reply to: ↑ 8 Changed 7 years ago by
Replying to ncohen:
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 thirdparty 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 3037. 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
comment:11 Changed 7 years ago by
 Commit changed from 303de8966e0c76f31f33b135370cee22edb12b9b to a555604888f8f5fd3ab4846a379c8719ae7a7de6
Branch pushed to git repo; I updated commit sha1. New commits:
a555604  trac #16083: "del C"

comment:12 followup: ↓ 13 Changed 7 years ago by
BTW, are you sure del is good? Shouldn't you use C++'s delete?
comment:13 in reply to: ↑ 12 Changed 7 years ago by
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
comment:14 Changed 7 years ago by
I am still not able to run the code :(
azi@bodysnatcher:~/sage$ sage f mcqd Found local metadata for mcqd1.0 Found local sources at /home/azi/sage/upstream/mcqd1.0.tar.bz2 .......blahblah............ Finished installing mcqd1.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) <ipythoninput299d3195b7504> 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?
comment:15 followup: ↓ 16 Changed 7 years ago by
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 n*n 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!!
comment:16 in reply to: ↑ 15 Changed 7 years ago by
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 n*n 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
comment:17 followups: ↓ 18 ↓ 19 Changed 7 years ago by
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...n1 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
comment:18 in reply to: ↑ 17 Changed 7 years ago by
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
comment:19 in reply to: ↑ 17 Changed 7 years ago by
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
comment:20 Changed 7 years ago by
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!
comment:21 Changed 7 years ago by
Well, it does in the graph/ folder, and clearly no other code calls that.
Nathann
comment:22 Changed 7 years ago by
 Reviewers set to Jernej Azarija
 Status changed from needs_review to positive_review
comment:24 followup: ↓ 25 Changed 7 years ago by
Actually, thank you for doing all this patches and stuff !!!!!!
comment:25 in reply to: ↑ 24 Changed 7 years ago by
Actually, thank you for doing all this patches and stuff !!!!!!
:D
Nathann
comment:26 Changed 7 years ago by
 Status changed from positive_review to needs_work
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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/release/Sage/local/lib/python2.7/sitepackages/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 **********************************************************************
comment:27 Changed 7 years ago by
 Commit changed from a555604888f8f5fd3ab4846a379c8719ae7a7de6 to c0158edff1516bbca93ff330acbec1d1a5238049
Branch pushed to git repo; I updated commit sha1. New commits:
c0158ed  trac #16083: Broken doctest

comment:28 Changed 7 years ago by
 Status changed from needs_work to positive_review
Sorry.. All the lines except the import statement were tagged with "optional" :/
Nathann
comment:29 Changed 7 years ago by
 Branch changed from public/mcqd to c0158edff1516bbca93ff330acbec1d1a5238049
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
trac #16083: mcqd solver for max cliques