Opened 10 years ago
Closed 10 years ago
#11994 closed enhancement (fixed)
Vertex separation and pathwidth in Sage
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.8 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert | Merged in: | sage-4.8.alpha2 |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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
Attachments (1)
Change History (24)
comment:1 Changed 10 years ago by
- Cc dcoudert added
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
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()?
comment:3 Changed 10 years ago by
(there is lots of other code using the bitset structures, so enhancing the bitset code to be better would be a nice plus here).
comment:4 Changed 10 years ago by
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
comment:5 Changed 10 years ago by
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
comment:6 Changed 10 years ago by
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!
comment:7 Changed 10 years ago by
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
comment:8 Changed 10 years ago by
What about the popcount code in this first answer: http://stackoverflow.com/questions/1925964/profiling-a-set-implementation-on-64-bit-machines
comment:9 Changed 10 years ago by
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
comment:10 Changed 10 years ago by
Good point, and good call on the discussion.
At the very least, I guess the includes of bitset.* should be removed at some point...
comment:11 Changed 10 years ago by
That's for sure : updated :-)
Nathann
comment:12 Changed 10 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_work
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...
comment:13 Changed 10 years ago by
- Status changed from needs_work to needs_review
Hello !!!
- God I hate those translations. At least with the MILP code you don't have to deal with it
:-P
- Yeah ! It means that
sage_malloc
actually checks it for me. Good to know ! I removed my test :-D
- Done !
- Well, that's the job of the next patch, isn't it ? We'll have plenty of time to write this function when we will know what it contains, that'll be soon enough to write its documentation, its tests for all different algorithms, checking automatically that they are consistent, etc...
:-)
Patch updated !
Nathann
comment:14 Changed 10 years ago by
- Status changed from needs_review to needs_work
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$
comment:15 Changed 10 years ago by
- Status changed from needs_work to needs_review
Right ! Fixed :-)
Nathann
comment:16 Changed 10 years ago by
- Status changed from needs_review to needs_work
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.
comment:17 Changed 10 years ago by
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
comment:18 Changed 10 years ago by
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
comment:19 Changed 10 years ago by
- Status changed from needs_work to needs_review
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.
comment:20 Changed 10 years ago by
Updated !
Now that I think about it, perhaps one trick would be to rm -fr the folder SAGE_ROOT/devel/sage-<YOURBRANCH>/doc/output/html/en/reference, in the hope that Sphinx does it all again. But this will take some time, and you will not be able to use Sage in the meantime ;-)
Nathann
Changed 10 years ago by
comment:21 Changed 10 years ago by
- Status changed from needs_review to positive_review
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 !
comment:22 Changed 10 years ago by
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
comment:23 Changed 10 years ago by
- Merged in set to sage-4.8.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
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