Closed 6bdad4c1-1e26-4f2f-a442-a01a2292c181 closed 12 years ago
Yet another well-documented patch for Sage's library.
I put the files in the graph_decompositions folder, which is also the one used by rank-decompositions in patch #11754
Now needs a review ! :-)
Nathann
Gee, that looks like some pretty nice bit-counting code. Any chance you could just enhance bitset.pxi and then use the bitset functions, like bitset_len()?
(there is lots of other code using the bitset structures, so enhancing the bitset code to be better would be a nice plus here).
Hello Jason !
Well, there is actually not much bit-counting going on. :-)
I have to count bits very often in integers, hence the corresponding function in the code, but most of the code is really graph theoretical. I would have been glad to use bitsets (and I often do these days in Sage patches), but the code was just faster when I stored a small integer for each object, and not just a bit. So I'm using char * instead of bitsets :-)
Thouh I'm a very, very good fan of bitsets in general. I just love this thing :-)
Nathann
I assure you, I use this code a LOT myself but I really don't think there's anything in my code that could be of use in bitsets. I can actually prove it ! :-D
But I swear there are other examples as well as a wealth of personnal code using it ! I won't be proved unthankful to bitsets. NEVER :-D
Nathann
Just a few more comments about the Cython: "for 1<= i< n" is a backwards-compatible syntax, but I would think that the recommended syntax these days is "for i in range(n)" (see http://docs.cython.org/src/userguide/language_basics.html#integer-for-loops)
I see that you import the bitset functions, but I guess you never use them in fast_digraph.pyx. The popcount function was what I was referring to when I said that it would be useful in the bitset.pxi class.
P.S. I would love to have in-line commenting on patches, like on googlecode, github, or bitbucket!
Oh ! I'll try to remember the "i in range()" thing, it just scares me to use Python abstractions when I am in Cython, but if I can remember that it is totally equivalent for Cython.. :-)
Oops, sorry about the bitsets... Yes, in earlier versions I tried to use them but I found a workaround which improved the performances when using a different data structure... I feel guilty when I don't use bitsets in an enumerative code :-)
The important thing about the bitset function is the following : the best is to use the __builtin_popcount() function from GCC when the processor has the popcnt instruction (it is really faster), and this can be enabled by adding
#cargs -mpopcnt
at the beginning of the code. On the other hand, when the processor does not know this instruction the code crashes ("invalid instruction"). It'd be great to "use this instruction when available", and this other short code otherwise. This would really be GREAT :-)
Nathann
What about the popcount code in this first answer: http://stackoverflow.com/questions/1925964/profiling-a-set-implementation-on-64-bit-machines
Well.. So he's saying "use the builtin and trust GCC to recognize the platform". Only it does not in my situation and I need to say something to GCC about my platfom so that it compiles it with this instruction enabled. We have to find a way to provide this information when Sage gets compiled, or to let it guess if it can be used. Now the thing is that if you compile Sage'binaries on a platform that has it, and somebody else uses it....BOOM ! `:-D
I'd be glad to continue this discussion somewhere else, though. This patch will be long to review, and counting bits should not be the main problem there ^^;
Nathann
Good point, and good call on the discussion.
At the very least, I guess the includes of bitset.* should be removed at some point...
That's for sure : updated :-)
Nathann
Reviewer: David Coudert
Very nice patch Nathann !
I have some comments / improvements propositions that could be discussed
1) You should first use a mapping function from vertex labels to integer, and do the reverse mapping at the end. This is to solve the following problem:
sage: D=digraphs.DeBruijn(2,3)
sage: D.edges()
[('000', '000', '0'), ('000', '001', '1'), ('001', '010', '0'), ('001', '011', '1'), ('010', '100', '0'), ('010', '101', '1'), ('011', '110', '0'), ('011', '111', '1'), ('100', '000', '0'), ('100', '001', '1'), ('101', '010', '0'), ('101', '011', '1'), ('110', '100', '0'), ('110', '101', '1'), ('111', '110', '0'), ('111', '111', '1')]
sage: vs.vertex_separation(D)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage-2/<ipython console> in <module>()
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/vertex_separation.so in sage.graphs.graph_decompositions.vertex_separation.vertex_separation (sage/graphs/graph_decompositions/vertex_separation.c:1603)()
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/vertex_separation.so in sage.graphs.graph_decompositions.vertex_separation.FastDigraph.__cinit__ (sage/graphs/graph_decompositions/vertex_separation.c:687)()
TypeError: an integer is required
sage:
2) The MemoryError message is not displayed. Your code is:
raise MemoryError("Memory allocation failed. Is there enough memory around ?")
and I see
sage: D=digraphs.RandomDirectedGNP(31,.3)
sage: %time vs.vertex_separation(D)
python(26950) malloc: *** mmap(size=18446744071562067968) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
---------------------------------------------------------------------------
MemoryError Traceback (most recent call last)
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage-2/<ipython console> in <module>()
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-packages/IPython/iplib.pyc in ipmagic(self, arg_s)
1180 else:
1181 magic_args = self.var_expand(magic_args,1)
-> 1182 return fn(magic_args)
1183
1184 def ipalias(self,arg_s):
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-packages/IPython/Magic.pyc in magic_time(self, parameter_s)
1979 if mode=='eval':
1980 st = clk()
-> 1981 out = eval(code,glob)
1982 end = clk()
1983 else:
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage-2/<timed eval> in <module>()
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/vertex_separation.so in sage.graphs.graph_decompositions.vertex_separation.vertex_separation (sage/graphs/graph_decompositions/vertex_separation.c:1680)()
MemoryError:
sage:
3) small typos in the doc wll -> will
88 there. This way, a large number of sets wll never be evaluated and *a lot* of
min -> \min
96 it by `\max (c'(S), \min_{\text{next}})` (where `min_{\text{next}}` is the
should translate in english ;-)
320 print "Reservation de la memoire"
4) You could rename your function for instance vertex_separation_32, and then add a frontend function called vertex_separation calling vertex_separation_32. The goal is to have a more generic function allowing to add other implementations / methods for the vertex separation...
Hello !!!
:-P
sage_malloc
actually checks it for me. Good to know ! I removed my test :-D:-)
Patch updated !
Nathann
That's better ;-)
However, I have now a problem to build the documentation...
airgoth-2:sage-2 dcoudert$ ../../sage -docbuild reference html
sphinx-build -b html -d /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/doctrees/en/reference /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/en/reference /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/html/en/reference
Running Sphinx v1.0.4
loading pickled environment... done
building [html]: targets for 1 source files that are out of date
updating environment: 0 added, 1 changed, 0 removed
reading sources... [100%] graphs
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/en/reference/graphs.rst:42: (WARNING/2) toctree references unknown document u'sage/graphs/graph_decompositions/vertex_separation'
looking for now-outdated files... none found
pickling environment... done
checking consistency... done
preparing documents... done
writing output... [100%] index
writing additional files... genindex py-modindex search
copying static files... done
dumping search index... done
dumping object inventory... done
build succeeded, 1 warning.
Build finished. The built documents can be found in /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/html/en/reference
airgoth-2:sage-2 dcoudert$
Right ! Fixed :-)
Nathann
Sorry Nathann, but I still have the same problem :(
airgoth-2:sage-3 dcoudert$ ../../sage -docbuild reference html
sphinx-build -b html -d /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/doctrees/en/reference /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/en/reference /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/html/en/reference
Running Sphinx v1.0.4
loading pickled environment... done
building [html]: targets for 1 source files that are out of date
updating environment: 0 added, 1 changed, 0 removed
reading sources... [100%] graphs
/Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/en/reference/graphs.rst:42: (WARNING/2) toctree references unknown document u'sage/graphs/graph_decompositions/vertex_separation'
looking for now-outdated files... none found
pickling environment... done
checking consistency... done
preparing documents... done
writing output... [100%] index
writing additional files... genindex py-modindex search
copying static files... done
dumping search index... done
dumping object inventory... done
build succeeded, 1 warning.
Build finished. The built documents can be found in /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/html/en/reference
and so I don't see the documentation.
Hmmm... I don't like those bugs much, sphinx has some memory of its own, even when you're dealing with several different clones (branches) in the same copy of Sage. I'll give it a try on musclotte right now, it never saw any of these patches.
Nathann
Well, it works on musclotte ! I guess it's because you had already applied a patch for which it failed, and that updating it did not change anything. Actually, the reason why I sent this patch with a problem in the documentation was before building the doc worked for me, probably because of a detail I had removed since (and so it didn't work for you).
Could you try to build the doc of a different branch (did you recompile sage with sage -b before trying to build the doc ?) or in a different Sage installation ? For instance if you have one ready on one different computer ? I know it's a mess but I still do not know a way around it. It would be nice to be able to say to sphinx "ignore the documentation you've built so far, and do all the work from the start". I had found a line doing just that a long time ago, but I forgot :-/
Nathann
I followed precisely your instructions: create a new branch from a clean branch (original 4.7.2 distribution), then apply the patch on this new branch, test it, and build the doc, (try to) chack it, and finally return to original branch before erasing temporary branch. Believe me, on my macbook air, it takes quit a long time since it recompiles a lot of stuff each time (don't know why).
I will try as soon as I can on another computer.
By the way, another typo line 223 "reulting" -> "resulting" ;-)
223 reulting in a corresponding path decomposition.
Updated !
Now that I think about it, perhaps one trick would be to rm -fr the folder SAGE_ROOT/devel/sage-;-)
Nathann
Attachment: trac_11994.patch.gz
OK, after a full re-installation of sage, creation of clones, and so on... I have finally understand why the doc was not properly displayed: It writes
airgoth-2:sage-1 dcoudert$ ../../sage -docbuild reference html
sphinx-build -b html -d /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/doctrees/en/reference /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/en/reference /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/html/en/reference
Running Sphinx v1.0.4
...
build succeeded.
Build finished. The built documents can be found in /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage/doc/output/html/en/reference
But the last line should be
Build finished. The built documents can be found in /Applications/Sage-4.7.2-OSX-64bit-10.6.app/Contents/Resources/sage/devel/sage-1/doc/output/html/en/reference
The link to the doc should be in the devel/sage-1 directory and note in devel/sage directory. At least now I know...
The function is working well, the results is true, all tests are OK, and the doc is correctly displayed. Consequently, I give a positive review !
You have my thanks for the review but the mystery remains : the "sage" directory you mention is actually a symbolic link toward the "current branch". So that's probably not where the problem comes from :-D
Nathann
Merged: sage-4.8.alpha2
Hello everybody !
This algorithm implements some methods to compute the vertex separation of a digraph and the pathwidth of a digraph for small graphs (less than 32 vertices)
It should be followed by many others dealing with process number an alternative methods to compute the same parameters
CC: @dcoudert
Component: graph theory
Author: Nathann Cohen
Reviewer: David Coudert
Merged: sage-4.8.alpha2
Issue created by migration from https://trac.sagemath.org/ticket/11994