Opened 6 years ago

Closed 6 years ago

#13546 closed defect (fixed)

Bug in is_perfect

Reported by: azi Owned by: jason, ncohen, rlm
Priority: critical Milestone: sage-5.7
Component: graph theory Keywords: is_perfect, graph theory
Cc: rbeezer Merged in: sage-5.7.beta4
Authors: Nathann Cohen Reviewers: Jernej Azarija, Sébastien Labbé
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8952 Stopgaps:

Description (last modified by ncohen)

The method for recognizing perfect graphs if flawed. Consider the following sage function:

def f(n):
    c= 0
    for g in graphs.nauty_geng(str(n)):
        if g.is_perfect():
            c+=1
    return c

one can readily see that f(7) = 607 and f(8) = 8899 which is, (according to oeis http://oeis.org/A052431) incorrect. What should be true is that f(7) = 906 and f(7) = 8887.

I propose to rewrite a correct algorithm perhaps using the polynomial algorithm (www.comp.leeds.ac.uk/vuskovi/FOCS03final.ps).

Apply :

Attachments (1)

trac_13546.2.patch (6.2 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (39)

comment:1 Changed 6 years ago by ncohen

Hmmmmmmmmm O_o;;;

sage: def f(n):
....:         c= 0
....:     for g in graphs.nauty_geng(str(n)):
....:             if g.is_perfect():
....:                 c+=1
....:     return c
....: 
sage: f(7)
907

comment:2 Changed 6 years ago by azi

Yes and the interesting part is that you get more perfect graphs on 7 nodes and less graph of order 8.

comment:3 Changed 6 years ago by azi

I have modified is perfect in the following way:

        ret = self.is_odd_hole_free(certificate = certificate)
     
        if ret == False or (certificate and ret != None):
            return ret
     
        self_complement = self.complement()
     
        ret = self.is_odd_hole_free(certificate = certificate)
     
        if ret == False or (certificate and ret != None):
            return ret
    
        return True 

The error is still there so I suppose there is a bug in is_odd_hole_free. I will try to spot the bug there and make a temporary patch

comment:4 Changed 6 years ago by ncohen

Ahahaahah... Stupid bug :-)

Ok, it is now fixed by the following patch. Here's what it does :

  • It tests if the graph's complement is bipartite. Just a potential speed improvement.
  • Returns a result immediately if the girth is odd and > 3, and not only if it is equal to 5

And ... more importantly :-D

  • replaces an occurrence of self which should have been self_complement from the beginning :-DDDDDDD

Nathann

comment:5 Changed 6 years ago by ncohen

(but of course if you feel like implementing the polynomial algorithm, this is still a very interesting (not to mention courageous) thing to do :-D

Nathann

comment:6 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:7 Changed 6 years ago by azi

What about the is_odd_hole_free function? isn't it better if is_perfect directly calls it? Otherwise we have duplicated code?

comment:8 Changed 6 years ago by ncohen

Well, I thought while writing this code that it was better to check all odd holes and antiholes from small sizes to larger ones, than to test first ALL HOLES (all sizes) then all antiholes (all sizes).

That's the difference between this code and yours. Probably that's just a matter of taste after all O_o. What do you think ?

Nathann

comment:9 Changed 6 years ago by azi

I completely agree with you. This is just a minor stylistic difference.

I am still inclined towards "the less duplicated solution" especially since the algorithm has exponential complexity and when it "dies" it dies.

comment:10 Changed 6 years ago by ncohen

  • Dependencies set to 8952

Ok.. Well, here is a new patch that depends on 8952. The other difference between your code and the current one is that your code cannot use the "girth" computation to avoid looking for useless cycles. I updated 8952 so that is_odd_hole_free first computes the graph's odd_girth before anything, and then begins to check the existence of odd cycles.

And I can now update this patch. I was not too keen on replacing the code at first, but I have to admit that it is muuuuuuch cleaner like that. You're right ! ;-)

Nathann

comment:11 Changed 6 years ago by dcoudert

  • Dependencies changed from 8952 to #8952

comment:12 Changed 6 years ago by slabbe

  • Reviewers set to Sébastien Labbé
  • Status changed from needs_review to needs_work

Trying to understand the bug... with sage-5.6.rc0 I get:

sage: time s_907 = set(g.sparse6_string() for g in graphs.nauty_geng('7') if g.is_perfect())
Time: CPU 29.02 s, Wall: 29.74 s
sage: len(s_907)
907
save(s_907, '907_perfect_graph.sobj') 

With sage-5.6.rc0 + the patch:

sage: time s_906 = set(g.sparse6_string() for g in graphs.nauty_geng('7') if g.is_perfect())
Time: CPU 25.30 s, Wall: 26.32 s
sage: len(s_906)
906
sage: s_907 = load('907_perfect_graph.sobj')
sage: s_906.issubset(s_907)
True
sage: len(s_907.difference(s_906))
1
sage: a = s_907.difference(s_906).pop()
sage: a
':FgGE@I@GxGs'
sage: Graph(a)
Looped multi-graph on 7 vertices
sage: Graph(a).show()

With sage-5.6.rc0 and no patch applied:

sage: for g in graphs.nauty_geng('7'):
....:     if g.sparse6_string() == ':FgGE@I@GxGs':
....:         break
....:         
sage: g
Graph on 7 vertices
sage: g.to_dictionary()
{0: [2, 3, 4, 5], 1: [3, 4, 5, 6], 2: [0, 4, 5, 6], 3: [0, 1, 5, 6], 4: [0, 1, 2, 6], 5: [0, 1, 2, 3], 6: [1, 2, 3, 4]}

Starting from scratch. With sage-5.6.rc0, I get True with this graph:

sage: g = Graph({0: [2, 3, 4, 5], 1: [3, 4, 5, 6], 2: [0, 4, 5, 6], 3: [0, 1, 5, 6], 4: [0, 1, 2, 6], 5: [0, 1, 2, 3], 6: [1, 2, 3, 4]})
sage: g.is_perfect()
True

Strangely, I get a runtime error if I reconstruct the graph from the sparse string:

sage: Graph(':FgGE@I@GxGs').is_perfect()
Traceback (most recent call last):
...
RuntimeError: Segmentation fault

I don't know what this sparse string is doing... It does not seem to be injective for instance... Anyway.

With sage-5.6.rc0 + the patch, everything is fine:

sage: Graph(':FgGE@I@GxGs').is_perfect()
False
sage: g = Graph({0: [2, 3, 4, 5], 1: [3, 4, 5, 6], 2: [0, 4, 5, 6], 3: [0, 1, 5, 6], 4: [0, 1, 2, 6], 5: [0, 1, 2, 3], 6: [1, 2, 3, 4]})
sage: g.is_perfect()
False

Can we add this previous doctest in the patch? because there is no doctest in the patch in its actual version. It would have to be an optional one since it depends on the optional package nauty....

There is something I still do not understand (related to sparse string). is_perfect does not seem to be preserve under the passage to the sparse6_string... Only 818 of the graph are still perfect after the recovery... All this would be more easy if graphs were hashable... Anyways...

age: time s = set(g.sparse6_string() for g in graphs.nauty_geng('7') if g.is_perfect())
Time: CPU 24.94 s, Wall: 24.99 s
sage: L = [Graph(g).is_perfect() for g in s]
sage: all(L)
False
sage: import collections
sage: collections.Counter(L)
Counter({False: 818, True: 88})

comment:13 Changed 6 years ago by ncohen

  • Status changed from needs_work to needs_review

Updated ! :-)

Nathann

comment:14 Changed 6 years ago by slabbe

  • Authors changed from Jernej Azarija to Nathann Cohen
  • Reviewers changed from Sébastien Labbé to Jernej Azarija, Sébastien Labbé

All test passed on sage/graphs/generic_graph.py. Documentation builds fine. Doctests which were broken before were added in the latest patch. To me it is a positive review. I let Jernej Azarija say a last word on it.

comment:15 Changed 6 years ago by azi

Jernej told me he has a question!

What is the purpose of removing loops and multiple edges from the complement? Given a simple graph, does't sage produce a simple complement?

comment:16 Changed 6 years ago by ncohen

Well... Because Sebastien told me yesterday that "there was a bug" when he typed Graph(mygraph.sparse6_string()).is_perfect, and the reason is that when you build a graph from a sparse6 string, the graph (even tough it does not have loops nor multiple edges) *allows them*. And when you compute the complement of that graph, you get multiple edges and loops, which was a problem.

Well. It's up to you, really. I don't care either way. And I hate labels, multiple edges, and loops :-P

Nathann

comment:17 Changed 6 years ago by azi

I see!

Well this looks more like a bug of the Graph constructor handling sparse6/graph6 strings. The named formats are used for simple graphs hence it is pointless to have them return non-simple graphs?

comment:18 Changed 6 years ago by ncohen

Oh ! They can't store graphs with multiples labels, nor loops ? Then I'd be glad to make them simple graphs by default :-D

Nathann

comment:19 Changed 6 years ago by ncohen

Well, unfortunately sparse6 string supports multiple edges :-P

Nathann

comment:20 follow-up: Changed 6 years ago by azi

Hello!

Since someone may be using this thing on simple and non-simple graphs and expect the non-simple case to yield something different than we currently do (automatically false?) I propose to either

  • Document that non-simple graphs are going to be treated as simple
  • Simply test at the beginning if the graph is simple and return an exception if it is not.

I like this last option better since the notion of a perfect graph is defined for simple graphs so if the user is sending something that is non-simple it is his problem to handle that!

comment:21 in reply to: ↑ 20 Changed 6 years ago by ncohen

Hello !!

Since someone may be using this thing on simple and non-simple graphs and expect the non-simple case to yield something different than we currently do

No way. If somebody calls this method, he/she wants to test a simple graph. No other way. If they expect anything by giving non-simple digraphs, it would be getting incoherent results.

  • Document that non-simple graphs are going to be treated as simple

Perfect graphs are only defined for simple graphs.

  • Simply test at the beginning if the graph is simple and return an exception if it is not.

I like this last option better since the notion of a perfect graph is defined for simple graphs so if the user is sending something that is non-simple it is his problem to handle that!

The point is that in the situation of sparse6 strings, the graph given is simple but *allows* loops and multiple edges.

Nathann

comment:22 Changed 6 years ago by ncohen

Patch updated to filter non-simple graphs !

Nathann

comment:23 follow-up: Changed 6 years ago by azi

Eeeh... I should refrain from posting things late at night - I am writing confusing stuff...

Anyhow. I am aware of the sparse6 issue but in my opinion that is an issue of how we currently handle sparse6 strings! So if we enforce the simplicity rule in is_perfect then at some point someone will perhaps get annoyed and want an option of the form

Graph('sparse6_string',force_simplicity=True)

instead of Sage having to guess if the user sent a sparse6 graph that was converted to a non-simple graph etc... Or perhaps the Graph() constructor could check if the resulting graph is simple and automatically flag it as such.

Thank you for taking my comment into relevance!

As far as I see, the patch need not remove loops and multiple edges from the complement now?

comment:24 in reply to: ↑ 23 Changed 6 years ago by ncohen

Anyhow. I am aware of the sparse6 issue but in my opinion that is an issue of how we currently handle sparse6 strings! So if we enforce the simplicity rule in is_perfect then at some point someone will perhaps get annoyed and want an option of the form

Right now there is no problem with sparse6 strings, because the functions does not check whether the graph ALLOWS loops and multiple edges, but whether it HAS some. So the exception is not raised for sparse6 string, and is only raised if there is a loop in the graph, or multiple edges.

As far as I see, the patch need not remove loops and multiple edges from the complement now?

It is still needed, for instance for graphs coming from sparse6, because even though they contain no multiple edges and loops they allow it. So the complement will have multiple edges.

Actually, the problem is probably that taking the complement of a graph that allows loops will add loops and multiple edges to the graph, and I don't really think that's a good behaviour.

Nathann

comment:25 follow-up: Changed 6 years ago by azi

I see !

Well if a graph *allows* multiple edges and loops isn't it then by definition a non-simple graph?

Things see, pretty messy to me if this is not so :-)

Last edited 6 years ago by azi (previous) (diff)

comment:26 in reply to: ↑ 25 Changed 6 years ago by ncohen

Well if a graph *allows* multiple edges and loops isn't it then by definition a non-simple graph?

Well, you will not find any math book telling you when a Sage graph is simple or not, so the usual definition is "does it have a loop or an edge" ?

Nathann

comment:27 Changed 6 years ago by azi

Yeah but IMO this is not natural and consistent.

Somehow it would imply that a DiGraph? with 1 vertex (and any arc-less DiGraph? for that matter) is in fact a Graph and hence that all generic methods for graphs should apply?

Hopefully my remarks do not sound like being too pedantic or impolite or something! I would just like to get a clear picture of why this needs be so

comment:28 Changed 6 years ago by ncohen

The question is this : if you have a graph and add the same edge twice, do you necessarily want your graph to have it twice or did you just add it twice by mistake ? Currently, in Sage :

sage: g = Graph()
sage: g.add_edge(0,1)
sage: g.add_edge(0,1)
sage: g.add_edge(0,1)
sage: g.size()
1
sage: g.edges()
[(0, 1, None)]

If we were to change this way of doing, then that graph would have multiple edges, while at the moment you would have to insist on allowing multiple edges if you want.

Nathann

comment:29 follow-up: Changed 6 years ago by azi

Yes!

What confuses me is this. Suppose I allow multiple edges from a graph G why is it then not treated as being non-simple.

What about the remark on handling sparse6 strings? If a sparse6 string represents a simple graph there is no need to return a graph allowing multiple edges?

comment:30 in reply to: ↑ 29 Changed 6 years ago by ncohen

Yo !

What confuses me is this. Suppose I allow multiple edges from a graph G why is it then not treated as being non-simple.

There's nothing called "simple" graph is Sage. What we have is 4 methods : has_loops, allows_loops, has_multiple_edges, allows_multiple_edges. I don't know why that's how it got written, but that's how it is. We can change that of course, and even define a is_simple function. But well, that's how it is.

What about the remark on handling sparse6 strings? If a sparse6 string represents a simple graph there is no need to return a graph allowing multiple edges?

It means that whether a graph allows loops depends on whether the sparse6 string you feed it with allows it. So if you store 1000 sparse6 string and load them all, some of the graphs you get will allow multiple edges and loops, some others will not. I think that this would be dirty.

What could be done is this :

Graph(my_string, allow_loops = True, allow_multiple_edges = True)

returs graphs allowing loops and multiple edges.

Graph(my_string, allow_loops = False)

raises an exception if the string does not correspond to a non-simple graph.

The point is that you wouldn't create graphs allowing loops and multiple edges by mistake.

Nathann

comment:31 Changed 6 years ago by azi

  • Status changed from needs_review to positive_review

Hello!

Thanks for the clarifications.

What I don't like is this. The "looped" here implies as if the graph is non-simple.

sage: G = graphs.PetersenGraph()  
sage: G
Petersen graph: Graph on 10 vertices
sage: Graph(G.sparse6_string())   
Looped multi-graph on 10 vertices

I see that this is not an issue with is_perfect hence I'll flag this ticket with a positive review. But I really don't like the current way we are handling multigraphs as it introduces messy situations and I would really like to get a clear distinctions for this.

comment:32 Changed 6 years ago by ncohen

What would you thing of modifying the constructor as I said above ?

Thanks for the review !

Nathann

comment:33 Changed 6 years ago by azi

This would definitely solve part of the problem but I am not sure how elegant it'd be. I am afraid this would increase the complexity of all these constructors while not solving the problem at the root - which somehow I think is related to a design issue handling simple and non-simple graphs together!

comment:34 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This needs to be rebased to sage-5.7.beta2.

comment:35 Changed 6 years ago by ncohen

Well, because of that segfault with Sage I can't run tests, be it on my office's computer or on my laptop :-/

Nathann

comment:36 Changed 6 years ago by ncohen

Apply trac_13546.2.patch

Changed 6 years ago by ncohen

comment:37 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to positive_review

Good to go ! I had to ask David to check it on his computer as Sage segfaults on mine on exit, which prevents me from running tests :-/

Nathann

comment:38 Changed 6 years ago by jdemeyer

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