Errors with graph complement

[Travis Scrimshaw]

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.

[Nathann Cohen]

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

[Travis Scrimshaw]

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:

​5b42e19	Fixed complement for immutable graphs.
​e2a498c	Fixed doctest output.

[Nathann Cohen]

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

[Travis Scrimshaw]

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

[Nathann Cohen]

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

[Travis Scrimshaw]

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?

[Nathann Cohen]

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

[Travis Scrimshaw]

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.

[Nathann Cohen]

Okay, done in #15681 !

Nathann

[git]

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

[Travis Scrimshaw]

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

[Nathann Cohen]

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

[Nathann Cohen]

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

[Travis Scrimshaw]

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

[git]

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.

[Travis Scrimshaw]

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

[Nathann Cohen]

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

[Nathann Cohen]

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

Nathann

[Travis Scrimshaw]

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.

[Nathann Cohen]

O_o

Okayokay O_o

Nathann

[Travis Scrimshaw]

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

[Anne Dranowski]

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