Errors with graph complement #15669

tscrim · 2014-01-13T16:18:55Z

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.

Depends on #15681

CC: @nathanncohen

Component: graph theory

Author: Travis Scrimshaw

Branch/Commit: public/graphs/complement-15669 @ c393b58

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/15669

The text was updated successfully, but these errors were encountered:

nathanncohen · 2014-01-13T16:32:02Z

comment:1

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

tscrim · 2014-01-13T16:50:25Z

comment:2

Replying to @nathanncohen:

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.`

tscrim · 2014-01-13T16:50:25Z

Branch: public/graphs/complement-15699

tscrim · 2014-01-13T16:50:25Z

Author: Travis Scrimshaw

tscrim · 2014-01-13T16:50:25Z

Commit: e2a498c

nathanncohen · 2014-01-13T16:53:29Z

comment:3

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

tscrim · 2014-01-13T17:29:51Z

comment:4

Replying to @nathanncohen:

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

nathanncohen · 2014-01-13T17:34:56Z

comment:5

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

tscrim · 2014-01-14T18:35:49Z

comment:7

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?

nathanncohen · 2014-01-14T18:38:32Z

comment:8

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

tscrim · 2014-01-14T20:58:42Z

comment:9

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.

nathanncohen · 2014-01-15T10:28:05Z

comment:10

Okay, done in #15681 !

Nathann

sagetrac-git · 2014-01-15T17:22:58Z

Changed commit from e2a498c to 388d034

sagetrac-git · 2014-01-15T17:22:58Z

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`

tscrim · 2014-01-15T17:24:14Z

comment:12

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

nathanncohen · 2014-01-15T17:25:05Z

comment:13

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

nathanncohen · 2014-01-15T17:32:25Z

comment:14

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

nathanncohen · 2014-01-15T17:32:25Z

Dependencies: #15681

nathanncohen · 2014-01-15T17:32:36Z

Reviewer: Nathann Cohen

tscrim · 2014-01-15T17:52:40Z

comment:16

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

sagetrac-git · 2014-01-16T18:12:15Z

Changed commit from 388d034 to 429f6e8

sagetrac-git · 2014-01-16T18:12:15Z

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.`

tscrim · 2014-01-16T18:14:59Z

comment:19

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

nathanncohen · 2014-01-16T18:18:14Z

comment:20

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

nathanncohen · 2014-01-16T18:21:31Z

comment:21

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

Nathann

tscrim · 2014-01-17T00:41:44Z

comment:22

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.

nathanncohen · 2014-01-17T08:19:14Z

comment:23

O_o

Okayokay O_o

Nathann

tscrim · 2014-01-30T15:09:32Z

Changed commit from 429f6e8 to c393b58

tscrim · 2014-01-30T15:09:32Z

Changed branch from public/graphs/complement-15699 to public/graphs/complement-15669

tscrim · 2014-01-30T15:09:32Z

comment:24

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`

sagetrac-sage-snail · 2019-02-22T02:09:37Z

comment:27

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

tscrim added this to the sage-6.1 milestone Jan 13, 2014

tscrim added c: graph theory labels Jan 13, 2014

tscrim self-assigned this Jan 13, 2014

This comment has been minimized.

Sign in to view

tscrim added the s: needs review label Jan 13, 2014

nathanncohen mannequin added s: needs work and removed s: needs review labels Jan 14, 2014

tscrim added s: needs review and removed s: needs work labels Jan 15, 2014

nathanncohen mannequin added s: positive review and removed s: needs review labels Jan 15, 2014

sagetrac-git mannequin added s: needs review and removed s: positive review labels Jan 16, 2014

tscrim added s: positive review and removed s: needs review labels Jan 16, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

vbraun removed the s: positive review label Feb 1, 2014

vbraun closed this as completed in a6b945d Feb 1, 2014

tscrim mentioned this issue Jun 19, 2014

Implement right-angled Artin groups #15137

Closed

nathanncohen mannequin mentioned this issue Feb 1, 2014

Name of immutable graphs #15681

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Errors with graph complement #15669

Errors with graph complement #15669

tscrim commented Jan 13, 2014

nathanncohen mannequin commented Jan 13, 2014

tscrim commented Jan 13, 2014

tscrim commented Jan 13, 2014

This comment has been minimized.

tscrim commented Jan 13, 2014

tscrim commented Jan 13, 2014

nathanncohen mannequin commented Jan 13, 2014

tscrim commented Jan 13, 2014

nathanncohen mannequin commented Jan 13, 2014

tscrim commented Jan 14, 2014

nathanncohen mannequin commented Jan 14, 2014

tscrim commented Jan 14, 2014

nathanncohen mannequin commented Jan 15, 2014

sagetrac-git mannequin commented Jan 15, 2014

sagetrac-git mannequin commented Jan 15, 2014

tscrim commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

tscrim commented Jan 15, 2014

sagetrac-git mannequin commented Jan 16, 2014

sagetrac-git mannequin commented Jan 16, 2014

tscrim commented Jan 16, 2014

nathanncohen mannequin commented Jan 16, 2014

nathanncohen mannequin commented Jan 16, 2014

tscrim commented Jan 17, 2014

nathanncohen mannequin commented Jan 17, 2014

tscrim commented Jan 30, 2014

tscrim commented Jan 30, 2014

tscrim commented Jan 30, 2014

sagetrac-sage-snail mannequin commented Feb 22, 2019

Errors with graph complement #15669

Errors with graph complement #15669

Comments

tscrim commented Jan 13, 2014

nathanncohen mannequin commented Jan 13, 2014

tscrim commented Jan 13, 2014

tscrim commented Jan 13, 2014

This comment has been minimized.

tscrim commented Jan 13, 2014

tscrim commented Jan 13, 2014

nathanncohen mannequin commented Jan 13, 2014

tscrim commented Jan 13, 2014

nathanncohen mannequin commented Jan 13, 2014

tscrim commented Jan 14, 2014

nathanncohen mannequin commented Jan 14, 2014

tscrim commented Jan 14, 2014

nathanncohen mannequin commented Jan 15, 2014

sagetrac-git mannequin commented Jan 15, 2014

sagetrac-git mannequin commented Jan 15, 2014

tscrim commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

nathanncohen mannequin commented Jan 15, 2014

tscrim commented Jan 15, 2014

sagetrac-git mannequin commented Jan 16, 2014

sagetrac-git mannequin commented Jan 16, 2014

tscrim commented Jan 16, 2014

nathanncohen mannequin commented Jan 16, 2014

nathanncohen mannequin commented Jan 16, 2014

tscrim commented Jan 17, 2014

nathanncohen mannequin commented Jan 17, 2014

tscrim commented Jan 30, 2014

tscrim commented Jan 30, 2014

tscrim commented Jan 30, 2014

sagetrac-sage-snail mannequin commented Feb 22, 2019