Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

[Nathann Cohen]

Hello Paulo !

You did, and thank you for that !

The trouble is that the bug does not come from Sage, but rather from the piece of code we call to solve the problem. In sage/graph/modular_decomposition/src/ there is a dm.c file that contains the "smart" code, and contains a line at the top of the file :

#define DEBUG 0

I set it to 1, so that the C code can tell us by itself what is actually happening before Sage does anything, and I get as output on your instance (translated from french) :

Final Tree:

 Prime

  +--3

  +--1

  +--5

  +--2

  +--4

Well.. It just means that I have to forward the bug you found to the software's author :-)

I just create a trac ticket about that :

http://trac.sagemath.org/sage_trac/ticket/13744

Nathann

On Wednesday, November 21, 2012 4:07:46 PM UTC+1, Paulo Seijas wrote:

Hi,

I think I have found a serious bug on Graph.modular_decomposition. Clearly, a graph is prime if and only if its complement is so. Nevertheless:

sage: P = Graph('Dl_')
sage: P.is_prime()
True
sage: P.complement().is_prime()
False

This behaviour seems to derive from Graph.modular_decomposition. Look:

sage: P.modular_decomposition()
('Prime', [2, 0, 4, 1, 3])
sage: P.complement().modular_decomposition()
('Prime', [('Serie', [3, 1]), 4, 0, 2])

This is not the only example where you can observe this behavior. To generate easily many examples try, for instance:

sage: for g in graphs(7):
....:     if g.is_prime() and not g.complement().is_prime():
....:         g.graph6_string()
....:        
'Fl_K?'
'FlGK?'
'FlSK?'
'FnsK?'
'Fl[K?'
'FheL?'
'FlUL?'
'F|UL?'
'Fl]L?'
'FlsKG'
'FlUKG'
'FluKG'
'FnV[G'
'FlT[G'
'F|tkG'
'Fl]KG'
'Fl[KW'
'Fn|KG'
'Fn|kG'
'F|LLG'
'FnnLG'
'Flg[?'
'F|g[?'
'Fli[?'
'Flg{?'
'Fn{[?'
'Fn}[?'
'FzN{?'
'F~H[?'

Best regards,
Paulo

[Paulo Seijas]

Hello Nathann,

You're absolutely right! The problem is due to sage/graph/modular_decomposition/src/dm.c. I've managed to compile it in C, coded the graph P and got:

 Premier

  +--3
  +--1
  +--5
  +--2
  +--4

So, I downloaded the most current version of the source code from http://www.liafa.jussieu.fr/~fm/algos/dm.tar, compiled it and run the exact same code codifying the graph P. This time I got the right answer:

 Premier
  +--2
  +--0
  +--4
  +-Parallele
  |  +--1
  |  +--3

So, the bug seem to be fixed in the most current version from Fabien's webpage.

Introducing some changes into the file dm.c by hand seem to be not enough to make sage recompile it and change the behaviour of the command "P.modular_decomposition()" afterwards. Could you please tell how could I sage know that it must recompile dm.c after I modify it?

Best,
Paulo

[Nathann Cohen]

Hellooooooooo !!

> So, I downloaded the most current version of the source code from
> http://www.liafa.jussieu.fr/~fm/algos/dm.tar, compiled it and run the exact
> same code codifying the graph P. This time I got the right answer:

Hmmmmmmmm O_O

So either Fabien modified it since I wrote to him about the bug you reported, or he updated it without me knowing since the last time... Well, looks like we have an easy way out then ! I will just have to create a patch that replaces the current file, and we'll be done ;-)

> Introducing some changes into the file dm.c by hand seem to be not enough
> to make sage recompile it and change the behaviour of the command
> "P.modular_decomposition()" afterwards. Could you please tell how could I
> sage know that it must recompile dm.c after I modify it?

Oh. Well, perhaps you need to do something like "touch modular_decomposition.pyx" when you are in the sage/graphs/modular_decomposition folder. Then run "sage -b". modular_decomposition.pyx is the actual Sage code, that depends on the .c file you modified. It should be enough. Tell me how it goes !! I will keep this thread updated about the fix.

Nathann

[Paulo Seijas]

Hello Nathann,

Oh. Well, perhaps you need to do something like "touch modular_decomposition.pyx" when you are in the sage/graphs/modular_decomposition folder. Then run "sage -b". modular_decomposition.pyx is the actual Sage code, that depends on the .c file you modified. It should be enough. Tell me how it goes !! I will keep this thread updated about the fix.

Indeed it worked!
I've just:
1) Replaced the the files: dm.c, dm_english.c and random.c from Fabien's tar to devel/sage-main/sage/graphs/modular_decomposition/src taking care of commenting the line "#include "dm_english.h" in dm.c.
2) "touch modular_decomposition.pyx"
3) "sage -b" (for this I had to install the g++ package)
Now I can report that the bug I have reported is solved. Look:

sage: P = Graph('Dl_')
sage: P.is_prime()

False
sage: P.complement().is_prime() 
False
sage: P.modular_decomposition()
('Prime', [2, 0, 4, ('Parallel', [1, 3])])

sage: P.complement().modular_decomposition()
('Prime', [('Serie', [3, 1]), 4, 0, 2])

sage: for g in graphs(7):
....:     if g.is_prime() and not g.complement().is_prime():
....:         g.graph6_string()
....:        

sage:

Thank you very much Nathann!
Paulo

[Nathann Cohen]

Helloooooooo !!

> Indeed it worked!

Good !

> Now I can report that the bug I have reported is solved.

Well.. It is solved on your (unique) version of Sage :-P

I haven't written the patch yet. I wait for an answer from the code's author, and then it will be ready to be reviewed :-)

> Thank you very much Nathann!

Well, thank you for reporting the bug ! ;-)

Have fuuuuuuuuuuuuuuuuuuuun !

Nathann

[Nathann Cohen]

The ticket is now waiting to be reviewed :-)

http://trac.sagemath.org/sage_trac/ticket/13744

Nathann

[Paulo Seijas]

Dear Nathann,

I have just installed sage 6.6 and found out that the bug is still there and that I am not able to apply the same workaround as before. I used to replace dm.c and random.c, apply touch to modular_decomposition.pyx and do sage -b. That used to be enough. But I do not know how to reproduce this workaround in version 6.6.

I did the following. I installed sage 6.6 by uncompressing sage-6.6-x86_64-Linux-Ubuntu_14.04_x86_64.tar.gz. Since sage complained that modular_decomposition package was not installed, I proceeded to install the package using "sage -i modular_decomposition" plus "sage -b". Now the package is installed, but modular_decomposition behaves as it did when I frst started this post (except that it nows displays a warning claiming that it is known to return wrong results).

I would like to know if there is any workaround for solving this issue for version 6.6. Unfortunately, there is no dm.c and no random.c in the sage 6.6 directory structure so as to replace them and so I do not know how to proceed.

Thank you for your help.

Best,
Paulo

[Nathann Cohen]

Hello !

> I would like to know if there is any workaround for solving this issue for
> version 6.6. Unfortunately, there is no dm.c and no random.c in the sage 6.6
> directory structure so as to replace them and so I do not know how to
> proceed.

Sigh... Modular decomposition. A story of many disappointments.

No, right now you will not find those two files in Sage's source code.
They are, however, contained in the optional package that is
downloaded when you run "sage -i modular_decomposition", and all that
is done on them is compile them into a shared library named
libmodulardecomposition (if I remember correctly. Not of my own
computer at the moment) located in SAGE_ROOT/local/lib/. If you
compile this shared library from the new sources, there should not be
any problem. If you do not know how, open the archive and look at
"spkg-install", it contains the lines that do that.

I feel a bit guilty telling you how to make it work on your computer;
for we have a REAL problem with this package. What we need is to get
the original authors to solve it.

1) The old version of the sources (those that we ship) returns wrong
results. For instance on yours, as you were the one who reported it
first.

2) The new version of the sources apparently returns correct results
on your architecture (and on mine), but .... not on all of them. Look
at this ticket I opened when you first reported it:
http://trac.sagemath.org/ticket/13744

As you can see, the "new" version still triggers segfaults or wrong
results on some machines that we use to test Sage. Thus, my attempts
at upgrading Sage's version of the code were (rather legitimately)
refused.

I am stuck with those files, and I do not like this situation (at
all). We ship something which returns wrong results, the problem is
fixed by updating to a new version which returns wrong results too or
even segfaults, and of course I get absolutely no answer from the
authors, whom I reminded regularly of the problem.

To be honest, I feel like removing this from Sage. That was part of
the reason behind that more recent change, which made it an optional
package.

Really, the best you could do to help us is send an email to the
authors. Tell them about your problem, and how cool it would be if it
worked, as this situation is bad advertisement for everybody.
Computing modular decompositions is cool and everything, but we can't
just keep buggy code in Sage, even if we raise a warning whenever it
is used :-/

Nathann

[Paulo Seijas]

Hi Nathann,

Thank you very much. With your help I was able to compile the library from the "new" sources and it is working properly now, although just for me of course. I understand your disappointment because of not being able to solve the issue for everybody.

I am willing to write to the author of the C code but I do not know what exactly to ask him to do. The main problem is that the code works right in some architectures (at least in ours and in the one of the author I guess). So what is needed the most is active involvement from some other Sage user interested in having the modular_decomposition package to work in a different architecture so as detect what should be modified in the C code to make it work in that architecture too. Is there someone out there?

I really appreciate your effort to make modular decomposition available in Sage because for some of us this is very useful. I think that keeping modular_decomposition as an optional package should be useful for testing purposes in different architectures until the portability problem with the source code is identified and solved.

Thanks,
Paulo

[Nathann Cohen]

Hello !

> Thank you very much. With your help I was able to compile the library from
> the "new" sources and it is working properly now, although just for me of
> course.

"Good" :-P

> I understand your disappointment because of not being able to solve
> the issue for everybody.
>
> I am willing to write to the author of the C code but I do not know what
> exactly to ask him to do. The main problem is that the code works right in
> some architectures (at least in ours and in the one of the author I guess).

Well... Probably that it would be cool if they could try to test and
debug it under Mac OS X (seems like it aways fails on this
architecture), for there are known bugs and that their code returns
wrong results on this platform. I don't exactly know how to make them
understand that this is important O_o

> So what is needed the most is active involvement from some other Sage user
> interested in having the modular_decomposition package to work in a
> different architecture so as detect what should be modified in the C code to
> make it work in that architecture too. Is there someone out there?

Someone with a mac. Someone who preferably knows french, as the all
comments are in french.

> I really appreciate your effort to make modular decomposition available in
> Sage because for some of us this is very useful. I think that keeping
> modular_decomposition as an optional package should be useful for testing
> purposes in different architectures until the portability problem with the
> source code is identified and solved.

I have to day that I am a bit pessimistic. The code has been in Sage's
source tree for years already :-/

Nathann

[Nathann Cohen]

Small update on the 'modular decomposition story'.

Today I ran valgrind on the code, and ended up finding where the error
comes from. Around line 972 of dm.c, one can find:

for(v = n-1; v>=0; v--)
if(ds[v-1] != -1){
L2[v]=v;
while( pile[sommet] < ds[v-1])
L2[pile[sommet--]]=v;
}

Now, because v can be equal to 0 in the loop, ds[v-1] is actually
ds[-1] and leads, unsurprisingly, to a wrong area of the memory.
Valgrind reports it like that:

==23980== 1 errors in context 3 of 4:
==23980== Invalid read of size 4
==23980== at 0x40269D: algo2 (dm.c:972)

Thus it is rather obvious where the error comes from (there are some
other occurrences of the same problem). I was about to write an email
to the authors, when I noticed that..... I had already sent an email
with the very same information, i.e. line number+explanation+short
tutorial on valgrind, and that was... one year ago. On the 6th of
April 2014, to be specific.

So that is not a problem of having to debug under mac OS X.

Nathann

[Dima Pasechnik]

Was it about the same version of their code?

Maybe we should tell the code authors that we will have to remove it from Sage if they will not fix the bug?
(and not have certainly wrong code in Sage?)

 

[Nathann Cohen]

> Was it about the same version of their code?

I cannot swear that they have not changed a single character of their
code in the meantime. What I can tell for sure is that the same error
still exists at the same line of their file, on the copy I downloaded
this morning.

> Maybe we should tell the code authors that we will have to remove it from
> Sage if they will not fix the bug?
> (and not have certainly wrong code in Sage?)

Maybe ... Just thinking that they might ignore that email too... >_<

Nathann

[Dima Pasechnik]

maybe we should just keep posting strong-worded statements about quality of that code,
perhaps in French ;-)
 

Nathann

[Nathann Cohen]

> maybe we should just keep posting strong-worded statements about quality of
> that code,
> perhaps in French ;-)

I prefer your technique. You are waiting for me to do something about it, right?

Nathann

[Dima Pasechnik]

I trust that you know the proper order of these powerful French words starting from p and m better than me.  ;-)

Nathann

[Nathann Cohen]

> I trust that you know the proper order of these powerful French words
> starting from p and m better than me. ;-)

I sent them an email asking if anything had been done about this bug,
and saying that we would remove the code otherwise.

Nathann