Opened 6 years ago

Closed 6 years ago

Last modified 7 months ago

#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) Commit: c393b585073dbd253314e13f3ffed01c6b8bd892
Dependencies: #15681 Stopgaps:

Description (last modified by tscrim)

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: Changed 6 years ago by ncohen

Hello Travis !

Well, I guess you can fix this one yourself ! You should just add a immutable=True to the call of copy 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 a layout="spring" to plot() to emphasize it.

Nathann

comment:2 in reply to: ↑ 1 ; follow-up: Changed 6 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • 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 of copy 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 a layout="spring" to plot() 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:

5b42e19Fixed complement for immutable graphs.
e2a498cFixed doctest output.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 6 years ago by ncohen

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: Changed 6 years ago by tscrim

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 6 years ago by ncohen

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 6 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:7 follow-up: Changed 6 years ago by tscrim

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 6 years ago by ncohen

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 6 years ago by tscrim

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 6 years ago by ncohen

Okay, done in #15681 !

Nathann

comment:11 Changed 6 years ago by git

  • Commit changed from e2a498c3c7adc71adcadd76b0bc09ea9a6efe77c to 388d034ee0116bfc2d8991ecc2ace5fe4d6b6b00

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

0f57805trac #15622: Immutable graphs must not be relabeled
b6ed038trac #15623: Immutable graph backend for Posets
ee8c395Trac 15623: Let to_graph return an immutable graph
dcb8a0btrac #15623: rebase on 6.1.beta4
529f785trac #15622: More informative exception message
2245c02Trac 15622: Review commit, fixing a misspelled doctest
60ad575trac #15622: Rebase on 6.1.beta3
6398780trac #15622: bugfix before #15623 gets merged
3531566trac #15623: Rebase on updated #15622
95cecd1trac #15623: Removing the hack from #15622, update a variable's name

comment:12 Changed 6 years ago by tscrim

  • Status changed from needs_work to needs_review

Okay, immutable graph complements now return immutable graphs with the correct name.

comment:13 Changed 6 years ago by ncohen

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 6 years ago by ncohen

  • 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 6 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

comment:16 Changed 6 years ago by tscrim

I thought I added the dependency...*shrugs* I'll take the commit message under advisement. Thank you for doing the review.

comment:17 Changed 6 years ago by git

  • 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:

a0d6510Merge branch 'public/graphs/complement-15699' of trac.sagemath.org:sage into public/graphs/complement-15669
86ed772trac #15699: fix hasattr in generic_graph.py.
46cfc90trac #15681: A doctest for the bugfix
5620ec5trac #15681: Rebase on6.1.beta5
7e9d208trac #15681: New doctest for name() on immutable graphs
b0661b1Merge branch 'u/ncohen/15681' of trac.sagemath.org:sage into public/graphs/complement-15669
429f6e8Changed hasattr to getattr.

comment:18 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:19 Changed 6 years ago by tscrim

I just realized the ticket number is wrong... whoops :p

comment:20 Changed 6 years ago by ncohen

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 6 years ago by ncohen

Can't we just remove the last 3 commits ? They undo what they do O_o

Nathann

comment:22 Changed 6 years ago by tscrim

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 6 years ago by ncohen

O_o

Okayokay O_o

Nathann

comment:24 Changed 6 years ago by tscrim

  • Branch changed from public/graphs/complement-15699 to public/graphs/complement-15669
  • Commit changed from 429f6e82e589e2491efff17f297d020bbbbb67e4 to c393b585073dbd253314e13f3ffed01c6b8bd892

Rebased branch.


New commits:

dae53afMerge branch 'develop' into ticket/15623
c5b6d59Re-insert a bit of code that had been erroneously deleted in the previous merge commit
81fc8a4Merge branch 'u/ncohen/15681' of trac.sagemath.org:sage into u/tscrim/15681
c393b58Merge branch 'public/graphs/complement-15699' of trac.sagemath.org:sage into public/graphs/complement-15669

comment:25 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:26 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:27 Changed 7 months ago by sage_snail

The trac reference in the doctest added in this ticket had a typo. See #27338 for a fix.

Note: See TracTickets for help on using tickets.