Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-08 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-08 Thread Dima Pasechnik


On Friday, 8 May 2015 09:27:57 UTC+1, Nathann Cohen wrote:

 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. 

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

 


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

 Nathann 


-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-08 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-08 Thread Dima Pasechnik


On Friday, 8 May 2015 14:06:58 UTC+1, Nathann Cohen wrote:

  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? 


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


 Nathann 


-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-08 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-08 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-08 Thread Dima Pasechnik


On Friday, 8 May 2015 10:13:26 UTC+1, Nathann Cohen wrote:

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


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


 Nathann 


-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-03 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-02 Thread 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

On Saturday, November 24, 2012 at 12:00:21 AM UTC-3, Nathann Cohen wrote:

 The ticket is now waiting to be reviewed :-) 

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

 Nathann 


-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-02 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2015-05-02 Thread 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

On Saturday, May 2, 2015 at 12:33:11 PM UTC-3, Nathann Cohen wrote:

 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 


-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.


[sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2012-11-23 Thread 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

On Thursday, November 22, 2012 12:04:56 PM UTC-3, Nathann Cohen wrote:

 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



-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to 
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2012-11-23 Thread Nathann Cohen
Hello !!

 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:

H 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to 
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2012-11-23 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to 
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2012-11-23 Thread Nathann Cohen
Hell !!

 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 fn !

Nathann

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to 
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




Re: [sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2012-11-23 Thread Nathann Cohen
The ticket is now waiting to be reviewed :-)

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

Nathann

-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to 
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.




[sage-support] Re: Serious bug in Graph.modular_decomposition (which propagates to Graph.is_prime)

2012-11-22 Thread 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



-- 
You received this message because you are subscribed to the Google Groups 
sage-support group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to 
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.