Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#11754 closed enhancement (fixed)

Computation of rank-decompositions in Sage

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: lsampaio, mvngu Merged in: sage-5.0.beta6
Authors: Nathann Cohen Reviewers: David Coudert, Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

Hello everybody !

This patch is an interface between Sage and the software RW, written by Philipp Klaus Krause [1]. It is written in C, and freshly licensed under the GPL2. It is a highly enumerative code that uses a lot of memory, but is still so far the best practical way to obtain optimal decompositions.

This patch creates the module sage.graphs.graph_decompositions and the rankwidth-related files. As it requires some documentation, some words are added on what a rank-decomposition is and where the code is coming from. Doing that, I also added sage.graphs.modular_decompositions to the documentation.

(As I created a module graph_decompositions, it would make sense to move te modular_decomposition there. It thought it best to do it in a distinct patch, this one being large enough already)

Oh. By the way, most of the patch actually contains the copy of the files written by Philipp Klaus Krause.

Nathann

http://pholia.tdi.informatik.uni-frankfurt.de/~philipp/software/rw.shtml

APPLY:

Attachments (7)

trac_11754_warning.patch (1.4 KB) - added by ncohen 7 years ago.
trac_11754_fix_compilation_error_and_a_segfault.patch (2.3 KB) - added by dcoudert 7 years ago.
complement patch to fix compilation errors and segfaults
trac_11754.patch (33.7 KB) - added by ncohen 7 years ago.
trac_11754-ifndef.patch (898 bytes) - added by ncohen 7 years ago.
trac_11754-ifndef-rev.patch (1.4 KB) - added by dcoudert 7 years ago.
trac_11754-RM.patch (1.6 KB) - added by ncohen 7 years ago.
11754_manifest.patch (697 bytes) - added by jdemeyer 7 years ago.

Download all attachments as: .zip

Change History (62)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_work

Nathann,

I tried to install the patch with sage-4.8.alpha5 and it's not possible anymore. Could you update the patch ?

Best, D.

compote:/path-to-sage/sage-4.8.alpha5/devel/sage-myclone> hg qimport ~/Soft/sage-patchs/trac_11754.patchadding trac_11754.patch to series file
compote:/path-to-sage/sage-4.8.alpha5/devel/sage-myclone> hg qpush
applying trac_11754.patch
patching file doc/en/reference/graphs.rst
Hunk #1 FAILED at 46
1 out of 1 hunks FAILED -- saving rejects to file doc/en/reference/graphs.rst.rej
file sage/graphs/graph_decompositions/__init__.py already exists
1 out of 1 hunks FAILED -- saving rejects to file sage/graphs/graph_decompositions/__init__.py.rej
patching file setup.py
Hunk #1 FAILED at 929
1 out of 1 hunks FAILED -- saving rejects to file setup.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_11754.patch
compote:/path-to-sage/sage-4.8.alpha5/devel/sage-myclone> 

comment:3 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

I thought it would be much worse ! Just obvious conflicts with the vertex_separation stuff... Patch updated ! :-)

Nathann

comment:4 Changed 8 years ago by dcoudert

I can now install the patch correctly. It works on my computer for graphs with 20 nodes and seems OK for 25 nodes (I stopped computation since its quite long), but not for graphs with 30 nodes (see error message bellow). I assume I don't have enough memory on my computer, but the error message is not explicit enough. Is it possible to test if enough memory is available to run the algorithm as you did for vertex separation and pathwidth ? Thanks, David.

sage: G = graphs.RandomGNM(30,200)
sage: x,H = G.rank_decomposition()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)

/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
   2999 
   3000         from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001         return rank_decomposition(self, verbose = verbose)
   3002 
   3003     ### Matching

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:815)()

RuntimeError: Segmentation fault

comment:5 Changed 8 years ago by ncohen

HMmmmmmm.... In the part of the code I wrote the memory allocations are checked, and it would be bad if it came from the original source code. We try not to put our hands in this kind of code, in order to avoid any troubles when the original source codes get updated (we would have to do all our modifications again on the updated version). What we usually do in these cases is report the bug upstream and wait for them to fix it.

The thing is that I was not able to reproduce your bug on my computer. It begins to eat a lot of memory but no segfault, so I do not really know how to debug it ^^;

Are you testing this code on your mac ? I hope it is not one of those integer initializations again :-P

Nathann

comment:6 Changed 8 years ago by dcoudert

The test has been done on a standard PC (32 bits) with 4G of RAM and running linux. Nothing special. The error is almost instantaneous.

Some simple tests.

sage: G = graphs.PetersenGraph()
sage: G.rank_decomposition()
(3, Graph on 19 vertices)
sage: G = graphs.RandomGNM(20,200)
sage: G.rank_decomposition()
(1, Graph on 39 vertices)

Testing with 32 nodes => the patch is working for 31 vertices only !

sage: G = graphs.RandomGNM(32,200)
sage: G.connected_components_number()
1
sage: G.rank_decomposition()
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)

/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
   2999 
   3000         from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001         return rank_decomposition(self, verbose = verbose)
   3002 
   3003     ### Matching

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:677)()

Exception: The rank decomposition cannot be computed on graphs of more than 32 vertices.

The patch contains some test regarding memory requirement

sage: G = graphs.RandomGNM(29,200)
sage: G.connected_components_number()
1
sage: G.rank_decomposition()
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)

/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
   2999 
   3000         from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001         return rank_decomposition(self, verbose = verbose)
   3002 
   3003     ### Matching

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:730)()

Exception: There has been a mistake while converting the Sage graph to a C structure. The memory is probably insufficient (2^(n+1) is a *LOT*).

But the test is not always working, perhaps because I'm on a 32 bits computer...

sage: G = graphs.RandomGNM(30,200)
sage: G.connected_components_number()
1
sage: G.rank_decomposition()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)

/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
   2999 
   3000         from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001         return rank_decomposition(self, verbose = verbose)
   3002 
   3003     ### Matching

/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:815)()

RuntimeError: Segmentation fault

I also have a segfault when running on an empty graph. A simple test is certainly missing.

sage: G= Graph()
sage: G.rank_decomposition()
/path-to-sage/sage-4.8.alpha5/local/lib/libcsage.so(print_backtrace+0x3b)[0x4f7967]
/path-to-sage/sage-4.8.alpha5/local/lib/libcsage.so(sigdie+0x17)[0x4f79a7]
...
...
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
local/bin/sage-sage: line 305:  4884 Segmentation fault      (core dumped) sage-ipython "$@" -i

Hope it helps fixing the problems.

Best,

David.

comment:7 Changed 8 years ago by ncohen

Hellooooooo David !!

I just updated the patch so that the case n == 0 is checked. This being said, there is nothing I can do with the segfault you meet as I have not been able to reproduce it. I read my code several times and try to pay attention to those memory errors, all the malloc are checked, etc... I am beginning to think the error may be in the original C code and perhaps it is not too hard to spot by adding "printf("Hello\n");" at some different places until we know where the error is coming from. After this, I can forward the problem to the author and ask for a patch (and I don't expect this to take too much time either).

The thing is that I really can not debug this without being able to reproduce the bug. I tried maaaaaaany times t create a random graph and give it a try but it never happened. Did you tell me that the error occurred right when the function was called ? And do you know if it happens "often" ? How many random graphs do you try before it segfaults ?

Nathann

comment:8 Changed 8 years ago by dcoudert

I just tried the new version of the patch.

It is now OK for empty graphs

sage: G = Graph()
sage: G.rank_decomposition()
(0, Graph on 0 vertices)

I don't know what is the expected result for non-connected graphs. I have the following result:

sage: G = graphs.RandomGNM(10,1)
sage: G.connected_components_number()
9
sage: G.rank_decomposition()
(1, Graph on 19 vertices)

Now, concerning large graphs:

  • The exception message for N==32 could be slightly improve. The current message is "

Exception: The rank decomposition cannot be computed on graphs of more than 32 vertices.", but is it >32 or >=32 ?

  • N == 31 AND N == 29: I got the correct message: "Exception: There has been a mistake while converting the Sage graph to a C structure. The memory is probably insufficient (2(n+1) is a *LOT*)."
  • N == 30: I have a segfault immediatly, that is for the first 30 vertices graph I'm trying:
    sage: G = graphs.RandomGNM(30,500)
    sage: G.rank_decomposition()
    ---------------------------------------------------------------------------
    RuntimeError                              Traceback (most recent call last)
    
    /path-to-sage/sage-4.8.alpha5/devel/sage-blop/sage/<ipython console> in <module>()
    
    /path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
       2999 
       3000         from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
    -> 3001         return rank_decomposition(self, verbose = verbose)
       3002 
       3003     ### Matching
    
    /path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:863)()
    
    RuntimeError: Segmentation fault
    
    

I tried with other 30 vertices graphs: G = graphs.GridGraph?([5,6]), G = graphs.RandomTree(30), G = graphs.CompleteGraph?(30), ... and I have exactly the same segfault.

The problem comes from the "if sage_graph_to_matrix(G)" in which you use the " int init_rw_dec(uint_fast8_t n) " function that uses the "int init_rw(uint_fast8_t n)" function. Most probably, the computation exceeds the type capacity and we get a wrong result. So, to be on the safe side, I suggest to add a test in the sage_graph_to_matrix function to test if memory allocation is possible. Or, as you have suggested, you can ask for a patch from the original author.

Best, D.

comment:9 Changed 8 years ago by ncohen

Helloooooo !!!

Patch updated to make the 32 limit clearer :-)

About the segfault : the point is that there is nothing I could "check" to return an exception to avoid the segault unless I know where it comes from. The function you mention contains a total of 5 lines which can produce no segfault, and exclusively consist in memory allocations and checking the memory has been allocated

int init_rw(uint_fast8_t n)
{
 	num_vertices = n;
	adjacency_matrix = malloc(sizeof(subset_t) * n);
	slots = malloc(sizeof(uint_fast8_t) * (1ul << n));
	cslots = 0;
	return((adjacency_matrix && slots) ? 0 : -1);
}

If anything goes wrong, the function return -1 instead of 0. And this function (which is defined in the original C code) is called as you said, by a "if" that is precisely there to ensure the memory allocation went smoothly. If it did not, it also returns and error and the function above (rank_decomposition) raises the exception. I mean, there is no memory allocation that I could check and that is not checked already O_o

Nathann

comment:10 Changed 8 years ago by dcoudert

I added some printf to track the segfault. It occurs in the calculate_level function for ss=1 and i=17. More precisely, the segfault is with the instruction cslots[1 << i] = 0x0;.

void calculate_level(uint_fast8_t ss)
{
        uint_fast8_t i;

        subset_size = ss;

        if(subset_size == 0)
                slots[0] = 0;
        else if(subset_size == 1)
                for(i = 0; i < num_vertices; i++)
                { 
                  printf("ss=%d, i=%d\n",ss,i);
                        slots[1 << i] = cut_rank(1 << i);
                  printf("after cut_rank\n");
                        cslots[1 << i] = 0x0;
                  printf("after cslots\n");
                }
        else
        {
                subset_t i;
                const subset_t end = binomial_coefficient(num_vertices, subset_size);
                for(i = 0; i < end; i++)
                        fill_slot(i);
        }
}

This is definitely a memory allocation problem.

D.

comment:11 Changed 8 years ago by ncohen

Ahah !! i=17 ! Now that's something ! I prefer when it is something around a power of two, it makes more sense :-)

Well, for instance I wondered what the result of

1 << (uint_fast8) 17

is in C. Is 1 automatically set to type uint_fast8 ? In this case the result is zero. Is it automatically set to integer ? In this case the result is 217. Anyway this should not make much of a difference, as accessing cslots[0] is not big deal -- it is the safest of them all to access ! Oddly the allocation part seems totally safe

cslots = malloc(sizeof(subset_t) * (1ul << n));

Nathann

comment:12 Changed 7 years ago by dcoudert

I tried with a fresh install of 5.0.beta1 and I still have the problem with 30 :(

D.

comment:13 Changed 7 years ago by ncohen

Ok... I gave it another try and really have no idea where this could come from. As the only thing I can guess is that the problem actually come from the original source code, what would you think of merging this patch anyway, with a warning in the documentation (also to ask people experiencing the same bug, if any, to give us information on their hardware), and continue to discuss it with the author ?

The way we are going now, this patch will just be forgotten even though it can actually solve the problem except on your architecture for some mysterious reason O_o

Nathann

comment:14 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

I agree with this proposal, so I give a positive review.

Honestly, I think most of us will never try use the algorithm for N=30 due to very huge computation time ;-)

comment:15 Changed 7 years ago by ncohen

Argggg !!! A bit too fast !! The warning was not in the patch when I said that ! Could you check this other patch too ? It contains the message I mentionned and also fixes a warning when building the documentation.

Sorryyyyyyyyyyyyyyyyyy !!

Nathann

Changed 7 years ago by ncohen

comment:16 Changed 7 years ago by dcoudert

I tried the warning patch as well, and the documentation is properly generated with a clear message (pink warning box).

I give a positive review.

D.

comment:17 Changed 7 years ago by ncohen

Thaaaaaaaaaanks ! :-)

I'm trying to write some proof in geometry, and I'm having a lot of fun. Hopefully it is not a final one, but just for my new bosses... It's as clear as a cops-and-robbers proof :-P

Nathann

comment:18 Changed 7 years ago by ncohen

  • Description modified (diff)

Oops. Forgot to add the list of patches that should be applied to the ticket.

comment:19 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

The commit message of trac_11754.patch should be changed.

comment:20 Changed 7 years ago by ncohen

  • Status changed from needs_work to positive_review

Ooops ^^;

Nathann

comment:21 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

I get Cython compilation failures:

In file included from sage/graphs/graph_decompositions/rankwidth/rw.c:22,
                 from sage/graphs/graph_decompositions/rankwidth.c:236:
sage/graphs/graph_decompositions/rankwidth/rw.h:28: error: redefinition of typedef 'subset_t'
sage/graphs/graph_decompositions/rankwidth/rw.h:28: error: previous declaration of 'subset_t' was here

comment:22 Changed 7 years ago by ncohen

Weird O_o. I've got no problem on my computer. Are you using beta1, or has something important changed since ?

Nathann

comment:23 Changed 7 years ago by dcoudert

I tried on several computers, and I have the same compilation error on one of them (namely musclotte).

  • Intel(R) Xeon(R) CPU W5580 @ 3.20GHz
  • 64bits
  • gcc (GCC) 4.4.3 20100127 (Red Hat 4.4.3-4)
  • Sage Version 4.8, Release Date: 2012-01-20

Let me know if I can help solving the problem.

D.

comment:24 Changed 7 years ago by jdemeyer

Probably it depends on the gcc version. My report was with the default gcc on sage.math, which is gcc-4.2.4.

comment:25 Changed 7 years ago by ncohen

Hmmmm... Considering the bug, this is probably the problem. Mine is 4.6.2.

Nathann

comment:26 Changed 7 years ago by dcoudert

The other computer on which I don't have compilation error is with gcc (GCC) 4.6.1 20110908 (Red Hat 4.6.1-9).

Unfortunately, we cannot rely on gcc version to solve the problem.

Nathann, may be you can add a test around the definition of type subset_t to avoid redefinition, something like (not sure of the syntax but I know it can be done)

#ifndef _GUARD_SUBSET_T_DEFINITION_
	
typedef uint_least32_t subset_t;

#define _GUARD_SUBSET_T_DEFINITION_ 

#endif

D.

comment:27 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_review

Hellooooooo !!!

Could you please try this new patch ? And could you give the 30-vertices segfault another try too ? :-)

Nathann

comment:28 Changed 7 years ago by jdemeyer

Considering rw.c is part of Sage, there is no need for the file COPYING.

comment:29 Changed 7 years ago by ncohen

Updated !

Nathann

comment:30 Changed 7 years ago by dcoudert

Not good with 30-vertices on my 32bits / sage.5.beta1 / gcc 4.6.1 computer

sage: G = graphs.RandomTree(30)
sage: G.rank_decomposition()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)

/path-to-sage/sage-5.0.beta1/devel/sage-myclone/sage/graphs/<ipython console> in <module>()

/path-to-sage/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in rank_decomposition(self, verbose)
   2999 
   3000         from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
-> 3001         return rank_decomposition(self, verbose = verbose)
   3002 
   3003     ### Matching

/path-to-sage/sage-5.0.beta1/local/lib/python2.7/site-packages/sage/graphs/graph_decompositions/rankwidth.so in sage.graphs.graph_decompositions.rankwidth.rank_decomposition (sage/graphs/graph_decompositions/rankwidth.c:863)()

RuntimeError: Segmentation fault

and still compilation errors on the other computer :(

comment:31 Changed 7 years ago by ncohen

Hmmm... Is there any way to use musclotte from outside of the INRIA network. It is pretty hard to debug a code that runs on your computer :-p

Nathann

comment:32 Changed 7 years ago by ncohen

What about this new patch ? After this, I really have no idea of what to try :-p

Nathann

comment:33 Changed 7 years ago by dcoudert

no change :( I will check the code asap. D.

comment:34 Changed 7 years ago by dcoudert

  • Status changed from needs_review to needs_work

Good news, I have identified the cause of my segfault !

In function init_rw_dec, with N=30, I have sizeof(subset_t) * (1ul << n) == 0 !!! Consequently, the malloc function returns a pointer. This is a stupid numerical problem. We have sizeof(subset_t)==4 and (1ul<<30)==1073741824. But at least on my computer, it happens that 4294967296==0 mod(2^32)...

So you should add a test like this just after the malloc:

if((sizeof(subset_t) * (1ul << n)==0) && (n>0) && cslots) return(-1);

A similar test in function init_rw could be safer.

No news concerning the compilation error.

Best, D.

Changed 7 years ago by dcoudert

complement patch to fix compilation errors and segfaults

comment:35 Changed 7 years ago by dcoudert

  • Status changed from needs_work to needs_review

This complementary patch solves:

  • compilation errors discussed in this ticket on some versions of gcc
  • segfault with N=30 discussed in this ticket.

Applying all attached files, I'm satisfied with this patch. What about you ?

comment:36 Changed 7 years ago by ncohen

Hellooooooooooooo !!

Well... ^^;

The problem with this is that we usually avoid touching the source code we add to Sage, so that there is no problem when we have to update it... I've been personally yelled at once or twice for doing just that ^^;

I can forward the first fix to the author, for it is a bug of his own software, as for the second bug....

Well, perhaps "just this" could be ok for Sage (Jeroen, are you still reading what's happening here ) ? :-p

Nathann

comment:37 Changed 7 years ago by dcoudert

OK, so please ask the author to perform the proposed modification in the rw.c file.

Furthermore, tell the author of rw.h to add at the beginning of the file the #ifndef _SOME_FLAG_ followed by #define _SOME_FLAG_ 1, then the content of the actual rw.h file, and to end the file with the #endif command. This is standard way of writing .h files.

Best,

D.

comment:38 Changed 7 years ago by ncohen

  • Description modified (diff)

Ok, in the end it's not really fair that Philipp should change his code to make ours work. I just added this "ifndef" preprocessor instruction in the rw.h file, and I guess it will not be the end of the world to remember if we have to update the code at some point (which I'd probably do myself anyway :-p).

Please tell me if it works on your computer, and let's roll :-)

Nathann

comment:39 Changed 7 years ago by ncohen

(I also updated the original source code, just in case)

Nathann

Changed 7 years ago by ncohen

Changed 7 years ago by ncohen

comment:40 follow-up: Changed 7 years ago by dcoudert

  • Description modified (diff)

Nathann,

I have added a review patch because 1) the test in rw.h was not correct. We have to define a tag. 2) the test in rw.c was also incorrect due to missing braces.

Now compilation is correct on both my 32 bits and 64 bits computers. The execution is correct, in particular it returns the correct error message when memory is insufficient. Tests are OK, and documentation was already OK.

For me the patch is now good to go.

D.

comment:41 in reply to: ↑ 40 Changed 7 years ago by ncohen

Hellooooo !!!

I have added a review patch because 1) the test in rw.h was not correct. We have to define a tag. 2) the test in rw.c was also incorrect due to missing braces.

Hmm... That should be fixed in *his* code. I will email him about it O_o

Now compilation is correct on both my 32 bits and 64 bits computers. The execution is correct, in particular it returns the correct error message when memory is insufficient. Tests are OK, and documentation was already OK.

One last mail exchange with him, and I'll be glad to see this patch merged ! :-p

Nathann

comment:42 Changed 7 years ago by dcoudert

I did some more tests with sage-5.0.beta5

  1. on a 32 bits computer with 4Go of RAM, gcc (GCC) 4.6.1 20110908 (Red Hat 4.6.1-9)
    • I tried first to apply only trac_11754.patch + trac_11754_warning.patch + trac_11754-ifndef.patch
  • Install OK, tests, OK, functionality OK, but problem when n = 30: the execution starts as if mallocs were OK, but I don't have enough memory for 29 so it cannot work for 30
Now, changing the ugly (unsafe?) test in init_rw from ``if(n > MAX_VERTICES
n && !(sizeof(uint_fast8_t) * (1ul << n)))`` to ``if( ( (n > MAX_VERTICES)   (n>0) ) && !(sizeof(uint_fast8_t) * (1ul << n)) )`` solves the problem and I get the correct error message !
  1. on a 64 bits computer with 64Go of RAM, gcc (GCC) 4.4.3 20100127 (Red Hat 4.4.3-4)
    • I have an installation error when using only trac_11754.patch + trac_11754_warning.patch + trac_11754-ifndef.patch
    • When patching the ifndef test in rw.h, I solve installation problem, and then every thing seems to work. However, I have no way to control execution with N>=29 due to computation time. So I don't know what's happening when N=30 (I have large enough memory, but computation should be huge).

Altogether, I need the revision patch (as I already identified weeks ago) to have the patch properly installing and operating.

D.

comment:43 Changed 7 years ago by dcoudert

Wysiwyg problem...

So change the test from

if(n > MAX_VERTICES || n && !(sizeof(uint_fast8_t) * (1ul << n)))

To

if( ( (n > MAX_VERTICES) || (n>0) ) && !(sizeof(uint_fast8_t) * (1ul << n)) )

Honestly, which one is the fastest to read ?

comment:44 Changed 7 years ago by ncohen

Ok, the author told me he intended the priority to be different (a parenthesis around "n && !(sizeof(uint_fast8_t) * (1ul << n))", but it makes no difference anyway as we settle the case n=0 differently already.

On my machine everything runs fine with all 4 patches applied. If everything is fine on your computer too I think this patch can go. As for a possible updates in 50 years, we will still have this track ticket lying around :-)

Nathann

Changed 7 years ago by dcoudert

comment:45 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

The author is right ;-)

The previous version was also working for me because the test was true for N> 31, n <0, and N=30, but it was an accident. With the correct version, we have the same result but it is more expected.

I have updated the patch accordingly and its working fine on all my computers: compilation, tests, documentation, functionality, error messages.

For me it's good to go so I give positive review.

D.

PS: I hope the ARM guys will not experience similar problems than for vertex separation...

comment:46 Changed 7 years ago by ncohen

Well, at least not "the same ones", as the author uses the correct types. And I'll do that too from now on :-)

Thank you for the review, by the way ! This is another of the patches that have been waiting for... ages ! :-D

Nathann

comment:47 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta6
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:48 Changed 7 years ago by jdemeyer

  • Resolution fixed deleted
  • Status changed from closed to new

Re-opening this as there some problems with the MANIFEST.in. The following need to be added:

! sage/graphs/graph_decompositions/rankwidth/README
! sage/graphs/graph_decompositions/rankwidth/__init__.py

comment:49 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

Helloooo !!!

Is this patch what you need ? ^^;

Nathann

Changed 7 years ago by ncohen

comment:50 Changed 7 years ago by ncohen

  • Description modified (diff)

Changed 7 years ago by jdemeyer

comment:51 Changed 7 years ago by jdemeyer

  • Description modified (diff)
  • Reviewers changed from David Coudert to David Coudert, Jeroen Demeyer
  • Status changed from needs_review to positive_review

comment:52 Changed 7 years ago by jdemeyer

  • Description modified (diff)
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:53 Changed 7 years ago by mhansen

I think there is an issue with this code as there is a extension module sage.graphs.graph_decompositions.rankwidth as well as a package (with init.py) sage/graphs/decompositions/rankwidth/ . I think that should really be fixed as it's ambiguous which should be used.

comment:54 Changed 7 years ago by jdemeyer

To be fixed in a follow-up ticket of course.

comment:55 Changed 7 years ago by mhansen

This is now at #12684.

Note: See TracTickets for help on using tickets.