#15669 closed defect (fixed)
Errors with graph complement
Reported by:  Travis Scrimshaw  Owned by:  Travis Scrimshaw 

Priority:  major  Milestone:  sage6.2 
Component:  graph theory  Keywords:  
Cc:  Nathann Cohen  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  public/graphs/complement15669 (Commits, GitHub, GitLab)  Commit:  c393b585073dbd253314e13f3ffed01c6b8bd892 
Dependencies:  #15681  Stopgaps: 
Description (last modified by )
We can't take the complement of an immutable graph:
sage: Gamma = graphs.PathGraph(5).copy(immutable=True) sage: Gamma.complement() NotImplementedError
which is because copy(Gamma)
doesn't return a mutable copy.
Change History (27)
comment:1 followup: 2 Changed 9 years ago by
comment:2 followup: 3 Changed 9 years ago by
Authors:  → Travis Scrimshaw 

Branch:  → public/graphs/complement15699 
Commit:  → e2a498c3c7adc71adcadd76b0bc09ea9a6efe77c 
Description:  modified (diff) 
Status:  new → needs_review 
Replying to ncohen:
Well, I guess you can fix this one yourself ! You should just add a
immutable=True
to the call ofcopy
in this method.
Done and NR. Although making an immutable copy destroys the name of the graph, so a slightly different question is do we want that behavior.
Besides, your second example of code is not really a bug.
GC
is what it should be, but if you plot the complement of a graph with the same layout as for the original graph, it so happens that the edges are all horizontal too. You can add alayout="spring"
toplot()
to emphasize it.
Ah, I see. I also understand why you want to keep the same layout as the original graph too.
Thanks,
Travis
New commits:
5b42e19  Fixed complement for immutable graphs.

e2a498c  Fixed doctest output.

comment:3 followup: 4 Changed 9 years ago by
Hello !
Done and NR. Although making an immutable copy destroys the name of the graph, so a slightly different question is do we want that behavior.
O_o
Destroys the name of the graph ? Why ? Well if it does I guess it's a bug, isn't it ? O_o
Besides : shouldn't the complement of an immutable graph be immutable ?
There are so many functions that will react oddly to immutable graphs....
Ah, I see. I also understand why you want to keep the same layout as the original graph too.
Yep. It's just unfortunate for this graph ^^;
Nathann
comment:4 followup: 5 Changed 9 years ago by
Replying to ncohen:
Destroys the name of the graph ? Why ? Well if it does I guess it's a bug, isn't it ?
O_o
I agree that it is a bug:
sage: G = graphs.PathGraph(5) sage: G Path Graph: Graph on 5 vertices sage: G.copy() Path Graph: Graph on 5 vertices sage: G.copy(immutable=True) Graph on 5 vertices
Besides : shouldn't the complement of an immutable graph be immutable ?
What's the "canonical" way to check if a graph G
is immutable? hasattr(G, '_immutable') and G._immutable
?
There are so many functions that will react oddly to immutable graphs....
We'll just keep fixing them as we come across them I guess.
Best,
Travis
comment:5 Changed 9 years ago by
Yoooooooo !
What's the "canonical" way to check if a graph
G
is immutable?hasattr(G, '_immutable') and G._immutable
?
Hmmmmmmm.... Well, we have been using if hasattr(G, '_immutable', False):
several times now, even if I don't like it. But my main reason for not liking it is that the Poset backend have this variable set while they are not immutable, and #15623 will fix it anyway... So perhaps we can do that indeed. Until there is a generic way to test if something is immutable :)
We'll just keep fixing them as we come across them I guess.
Yepyepyep :/
But the graph products. The unions. The subgraphs. The orientations... pffffff :/
Nathann
comment:6 Changed 9 years ago by
Status:  needs_review → needs_work 

comment:7 followup: 8 Changed 9 years ago by
Okay, the names issue is actually something with the graph constructor:
sage: P = graphs.PetersenGraph() sage: P Petersen graph: Graph on 10 vertices sage: Graph(P) Petersen graph: Graph on 10 vertices sage: Graph(P, immutable=False) Petersen graph: Graph on 10 vertices sage: Graph(P, immutable=True) Graph on 10 vertices sage: Graph(P, immutable=True, name="Petersen graph") # This is the bad one Graph on 10 vertices sage: Graph(_, immutable=False, name="Petersen graph") Petersen graph: Graph on 10 vertices
Nathann, you're likely to know best how to fix that, do you think you could do it?
comment:8 Changed 9 years ago by
Yoooooooooo !
Nathann, you're likely to know best how to fix that, do you think you could do it?
Oh sorry, I thought that you would only deal with this copy()
function (returning an immutable graph when the input was immutable too) and leave this name thing to me. Do you think that this behaviour for copy()
should not be implemented before this name thing is fixed ?
Nathann
comment:9 Changed 9 years ago by
The copy()
not preserving the name is the problem above. This leads to a (somewhat) bad doctest output here. I will be changing complement()
to return an immutable graph if given an immutable graph.
comment:11 Changed 9 years ago by
Commit:  e2a498c3c7adc71adcadd76b0bc09ea9a6efe77c → 388d034ee0116bfc2d8991ecc2ace5fe4d6b6b00 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
0f57805  trac #15622: Immutable graphs must not be relabeled

b6ed038  trac #15623: Immutable graph backend for Posets

ee8c395  Trac 15623: Let to_graph return an immutable graph

dcb8a0b  trac #15623: rebase on 6.1.beta4

529f785  trac #15622: More informative exception message

2245c02  Trac 15622: Review commit, fixing a misspelled doctest

60ad575  trac #15622: Rebase on 6.1.beta3

6398780  trac #15622: bugfix before #15623 gets merged

3531566  trac #15623: Rebase on updated #15622

95cecd1  trac #15623: Removing the hack from #15622, update a variable's name

comment:12 Changed 9 years ago by
Status:  needs_work → needs_review 

Okay, immutable graph complements now return immutable graphs with the correct name.
comment:13 Changed 9 years ago by
I may have mentionned a couple of times that seeing the commits of the ticket's dependencies was a pain. So let's say it another time : it is a pain.
Nathann
comment:14 Changed 9 years ago by
Dependencies:  → #15681 

Okay, good to go !
I set it to positive review and add the dependency with #15681. A request, though : could you add the ticket number to the commit message ? This helps a lot with tickets like that. If all the other commits did not contain the number, there would be no way to know what belong to this ticket easily Y_Y
Thaaaaaaaaaanks for this ticket ! ;)
Nathann
comment:15 Changed 9 years ago by
Reviewers:  → Nathann Cohen 

Status:  needs_review → positive_review 
comment:16 Changed 9 years ago by
I thought I added the dependency...*shrugs* I'll take the commit message under advisement. Thank you for doing the review.
comment:17 Changed 9 years ago by
Commit:  388d034ee0116bfc2d8991ecc2ace5fe4d6b6b00 → 429f6e82e589e2491efff17f297d020bbbbb67e4 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
a0d6510  Merge branch 'public/graphs/complement15699' of trac.sagemath.org:sage into public/graphs/complement15669

86ed772  trac #15699: fix hasattr in generic_graph.py.

46cfc90  trac #15681: A doctest for the bugfix

5620ec5  trac #15681: Rebase on6.1.beta5

7e9d208  trac #15681: New doctest for name() on immutable graphs

b0661b1  Merge branch 'u/ncohen/15681' of trac.sagemath.org:sage into public/graphs/complement15669

429f6e8  Changed hasattr to getattr.

comment:18 Changed 9 years ago by
Status:  needs_review → positive_review 

comment:20 Changed 9 years ago by
I don't get it O_o
Why did you change this hasattr line, and why did you add to the branch ? O_o
Nathann
comment:21 Changed 9 years ago by
Can't we just remove the last 3 commits ? They undo what they do O_o
Nathann
comment:22 Changed 9 years ago by
hasattr(obj, attr_str)
is the format which only checks if the attribute is there, but we want to actually retrieve the attribute if possible and if not, then return False
which would be getattr(obj, attr_str, [default_value])
in the form of getattr(self, "_immutable", False)
. The second to last is important because the latest of #15681 removed the conflict with develop
, and the third to last comes along for the ride.
comment:24 Changed 9 years ago by
Branch:  public/graphs/complement15699 → public/graphs/complement15669 

Commit:  429f6e82e589e2491efff17f297d020bbbbb67e4 → c393b585073dbd253314e13f3ffed01c6b8bd892 
Rebased branch.
New commits:
dae53af  Merge branch 'develop' into ticket/15623

c5b6d59  Reinsert a bit of code that had been erroneously deleted in the previous merge commit

81fc8a4  Merge branch 'u/ncohen/15681' of trac.sagemath.org:sage into u/tscrim/15681

c393b58  Merge branch 'public/graphs/complement15699' of trac.sagemath.org:sage into public/graphs/complement15669

comment:25 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:26 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
comment:27 Changed 4 years ago by
The trac reference in the doctest added in this ticket had a typo. See #27338 for a fix.
Hello Travis !
Well, I guess you can fix this one yourself ! You should just add a
immutable=True
to the call ofcopy
in this method. Besides, your second example of code is not really a bug.GC
is what it should be, but if you plot the complement of a graph with the same layout as for the original graph, it so happens that the edges are all horizontal too. You can add alayout="spring"
toplot()
to emphasize it.Nathann