#15669 closed defect (fixed)
Errors with graph complement
Reported by: | tscrim | Owned by: | tscrim |
---|---|---|---|
Priority: | major | Milestone: | sage-6.2 |
Component: | graph theory | Keywords: | |
Cc: | ncohen | Merged in: | |
Authors: | Travis Scrimshaw | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | public/graphs/complement-15669 (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 follow-up: ↓ 2 Changed 7 years ago by
comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 7 years ago by
- Branch set to public/graphs/complement-15699
- Commit set to e2a498c3c7adc71adcadd76b0bc09ea9a6efe77c
- Description modified (diff)
- Status changed from new to 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 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 7 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 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 7 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 in reply to: ↑ 4 Changed 7 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 7 years ago by
- Status changed from needs_review to needs_work
comment:7 follow-up: ↓ 8 Changed 7 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 in reply to: ↑ 7 Changed 7 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 7 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:10 Changed 7 years ago by
Okay, done in #15681 !
Nathann
comment:11 Changed 7 years ago by
- Commit changed from e2a498c3c7adc71adcadd76b0bc09ea9a6efe77c to 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 7 years ago by
- Status changed from needs_work to needs_review
Okay, immutable graph complements now return immutable graphs with the correct name.
comment:13 Changed 7 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 7 years ago by
- Dependencies set to #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 7 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
comment:16 Changed 7 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 7 years ago by
- Commit changed from 388d034ee0116bfc2d8991ecc2ace5fe4d6b6b00 to 429f6e82e589e2491efff17f297d020bbbbb67e4
- Status changed from positive_review to 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/complement-15699' of trac.sagemath.org:sage into public/graphs/complement-15669
|
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/complement-15669
|
429f6e8 | Changed hasattr to getattr.
|
comment:18 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:19 Changed 7 years ago by
I just realized the ticket number is wrong... whoops :p
comment:20 Changed 7 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 7 years ago by
Can't we just remove the last 3 commits ? They undo what they do O_o
Nathann
comment:22 Changed 7 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:23 Changed 7 years ago by
O_o
Okayokay O_o
Nathann
comment:24 Changed 7 years ago by
- Branch changed from public/graphs/complement-15699 to public/graphs/complement-15669
- Commit changed from 429f6e82e589e2491efff17f297d020bbbbb67e4 to c393b585073dbd253314e13f3ffed01c6b8bd892
Rebased branch.
New commits:
dae53af | Merge branch 'develop' into ticket/15623
|
c5b6d59 | Re-insert 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/complement-15699' of trac.sagemath.org:sage into public/graphs/complement-15669
|
comment:25 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:26 Changed 7 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
comment:27 Changed 2 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