Opened 8 years ago

Closed 8 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)

trac_11994.patch (19.0 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (24)

comment:1 Changed 8 years ago by ncohen

  • Cc dcoudert added
  • Status changed from new to needs_review

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

comment:2 Changed 8 years ago by jason

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 8 years ago by jason

(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 8 years ago by ncohen

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 8 years ago by ncohen

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

#11729 #10905 #10432

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 8 years ago by jason

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 8 years ago by ncohen

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:9 Changed 8 years ago by ncohen

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 8 years ago by jason

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 8 years ago by ncohen

That's for sure : updated :-)

Nathann

comment:12 Changed 8 years ago by dcoudert

  • 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 8 years ago by ncohen

  • 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 8 years ago by dcoudert

  • 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 8 years ago by ncohen

  • Status changed from needs_work to needs_review

Right ! Fixed :-)

Nathann

comment:16 Changed 8 years ago by dcoudert

  • 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 8 years ago by ncohen

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 8 years ago by ncohen

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 8 years ago by dcoudert

  • 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 8 years ago by ncohen

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 8 years ago by ncohen

comment:21 Changed 8 years ago by dcoudert

  • 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 8 years ago by ncohen

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 8 years ago by jdemeyer

  • Merged in set to sage-4.8.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.