Vertex separation and pathwidth in Sage #11994

nathanncohen · 2011-11-05T12:16:24Z

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

nathanncohen · 2011-11-05T17:38:57Z

comment:1

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

jasongrout · 2011-11-05T20:06:14Z

comment:2

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()?

jasongrout · 2011-11-05T20:07:04Z

comment:3

(there is lots of other code using the bitset structures, so enhancing the bitset code to be better would be a nice plus here).

nathanncohen · 2011-11-05T20:11:28Z

comment:4

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

nathanncohen · 2011-11-05T20:17:55Z

comment:5

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

jasongrout · 2011-11-05T20:48:36Z

comment:6

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!

nathanncohen · 2011-11-05T20:54:52Z

comment:7

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

jasongrout · 2011-11-05T20:58:07Z

comment:8

What about the popcount code in this first answer: http://stackoverflow.com/questions/1925964/profiling-a-set-implementation-on-64-bit-machines

nathanncohen · 2011-11-05T21:03:49Z

comment:9

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

jasongrout · 2011-11-05T21:09:13Z

comment:10

Good point, and good call on the discussion.

At the very least, I guess the includes of bitset.* should be removed at some point...

nathanncohen · 2011-11-05T21:11:43Z

comment:11

That's for sure : updated :-)

Nathann

dcoudert · 2011-11-05T21:57:00Z

Reviewer: David Coudert

dcoudert · 2011-11-05T21:57:00Z

comment:12

Very nice patch Nathann !

I have some comments / improvements propositions that could be discussed

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:

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:

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"

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...

nathanncohen · 2011-11-05T23:01:19Z

comment:13

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

dcoudert · 2011-11-06T00:00:33Z

comment:14

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$

nathanncohen · 2011-11-06T15:50:50Z

comment:15

Right ! Fixed :-)

Nathann

dcoudert · 2011-11-06T16:53:57Z

comment:16

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.

nathanncohen · 2011-11-06T17:04:10Z

comment:17

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

nathanncohen · 2011-11-06T17:07:40Z

comment:18

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

dcoudert · 2011-11-06T17:15:46Z

comment:19

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.

nathanncohen · 2011-11-06T17:34:59Z

comment:20

Updated !

Now that I think about it, perhaps one trick would be to rm -fr the folder SAGE_ROOT/devel/sage-/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

nathanncohen · 2011-11-06T17:35:18Z

Attachment: trac_11994.patch.gz

dcoudert · 2011-11-07T00:15:00Z

comment:21

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 !

nathanncohen · 2011-11-07T07:50:11Z

comment:22

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

jdemeyer · 2011-11-10T13:30:29Z

Merged: sage-4.8.alpha2

nathanncohen mannequin added this to the sage-4.8 milestone Nov 5, 2011

nathanncohen mannequin added c: graph theory labels Nov 5, 2011

nathanncohen mannequin assigned jasongrout, nathanncohen and rlmill Nov 5, 2011

nathanncohen mannequin added the s: needs review label Nov 5, 2011

dcoudert added s: needs work and removed s: needs review labels Nov 5, 2011

nathanncohen mannequin added s: needs review and removed s: needs work labels Nov 5, 2011

dcoudert added s: needs work and removed s: needs review labels Nov 6, 2011

nathanncohen mannequin added s: needs review and removed s: needs work labels Nov 6, 2011

dcoudert added s: needs work and removed s: needs review labels Nov 6, 2011

dcoudert added s: needs review and removed s: needs work labels Nov 6, 2011

dcoudert added s: positive review and removed s: needs review labels Nov 7, 2011

jdemeyer removed the s: positive review label Nov 10, 2011

jdemeyer closed this as completed Nov 10, 2011

nathanncohen mannequin mentioned this issue Nov 14, 2011

Convex Hulls, Hull number in graphs #11279

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Vertex separation and pathwidth in Sage #11994

Vertex separation and pathwidth in Sage #11994

nathanncohen mannequin commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

dcoudert commented Nov 5, 2011

dcoudert commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

dcoudert commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

dcoudert commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

dcoudert commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

dcoudert commented Nov 7, 2011

nathanncohen mannequin commented Nov 7, 2011

jdemeyer commented Nov 10, 2011

Vertex separation and pathwidth in Sage #11994

Vertex separation and pathwidth in Sage #11994

Comments

nathanncohen mannequin commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

jasongrout commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

dcoudert commented Nov 5, 2011

dcoudert commented Nov 5, 2011

nathanncohen mannequin commented Nov 5, 2011

dcoudert commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

dcoudert commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

dcoudert commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

nathanncohen mannequin commented Nov 6, 2011

dcoudert commented Nov 7, 2011

nathanncohen mannequin commented Nov 7, 2011

jdemeyer commented Nov 10, 2011