Opened 8 years ago
Closed 7 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 )
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)
Change History (39)
comment:1 Changed 7 years ago by
comment:2 Changed 7 years ago by
Yes and the interesting part is that you get more perfect graphs on 7 nodes and less graph of order 8.
comment:3 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
(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 7 years ago by
- Status changed from new to needs_review
comment:7 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
- 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 7 years ago by
- Dependencies changed from 8952 to #8952
comment:12 Changed 7 years ago by
- 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 7 years ago by
- Status changed from needs_work to needs_review
Updated ! :-)
Nathann
comment:14 Changed 7 years ago by
- 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 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
Well, unfortunately sparse6 string supports multiple edges :-P
Nathann
comment:20 follow-up: ↓ 21 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
Patch updated to filter non-simple graphs !
Nathann
comment:23 follow-up: ↓ 24 Changed 7 years ago by
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 7 years ago by
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: ↓ 26 Changed 7 years ago by
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 :-)
comment:26 in reply to: ↑ 25 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
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: ↓ 30 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
- 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 7 years ago by
What would you thing of modifying the constructor as I said above ?
Thanks for the review !
Nathann
comment:33 Changed 7 years ago by
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 7 years ago by
- Status changed from positive_review to needs_work
This needs to be rebased to sage-5.7.beta2.
comment:35 Changed 7 years ago by
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 7 years ago by
Apply trac_13546.2.patch
Changed 7 years ago by
comment:37 Changed 7 years ago by
- 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 7 years ago by
- Merged in set to sage-5.7.beta4
- Resolution set to fixed
- Status changed from positive_review to closed
Hmmmmmmmmm
O_o;;;