Opened 13 years ago

Closed 11 years ago

#8458 closed defect (fixed)

iterator for graphs() doesn't return independent graphs

Reported by: Minh Van Nguyen Owned by: Robert Miller
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: Lukáš Lánský Merged in: sage-5.0.beta3
Authors: Lukáš Lánský Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Nathann Cohen)

From sage-support:

So, what you are saying is that the iterator for graphs() does not
return independent graphs which can be changed without affecting the
others.
That does explain what I am seeing and is consistent with Pat
LeSmith's suggested workaround.

Should this property of the iterators to the generated graphs be
documented?

So, I think I will try making a copy of just the graphs I want to
change or use the list() trick. 

Apply:

trac_8458.patch

Attachments (3)

trac_8458_independent_graphs.patch (3.5 KB) - added by Lukáš Lánský 11 years ago.
trac_8458_independent_graphs.2.patch (3.4 KB) - added by Lukáš Lánský 11 years ago.
trac_8458.patch (3.6 KB) - added by Nathann Cohen 11 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 13 years ago by Robert Miller

This is an unintended consequence of the fact that when the graphs(n) iterator yields a graph, it does not first make a copy. The method of generating graphs is to add on to previously generated graphs in a well-chosen way, and I did not think to make a copy of the graph before having the iterator yield it.

This shouldn't just be documented, but in fact I think this should be an option to graphs(n). If someone will not modify the graphs in the loop, they can get the speed advantage of not making copies, and someone else who wants to modify them can have the iterator make copies on the fly.

comment:2 Changed 13 years ago by Jason Grout

I agree with rlm. I think the default should be to return a copy of the graph, with an optional argument to return the actual graph.

comment:3 Changed 11 years ago by Lukáš Lánský

Cc: Lukáš Lánský added

Changed 11 years ago by Lukáš Lánský

comment:4 Changed 11 years ago by Lukáš Lánský

Status: newneeds_review

I corrected the main generator. There are several specialized (e.g. tree generator) but I don't think the same problem arises in any of them. Do you agree?

comment:5 Changed 11 years ago by Nathann Cohen

Status: needs_reviewneeds_info

Helloooooo !!!

This is a good patch, but I do not think the documentation is very clear. What would you think of changing the new argument's name to "return_copies" or "graph_copy" ? To be honest I took me 2 minutes to understand that this message's title did not mean "The independent graph is not returned by graphs(n)" :-p

Either way, with a name like "independent" it is not very clear that there may be performances issues hidden in this argument.

Here's what I would write. Of course, it's just my advice, so take or leave whatever you want :

- ``copy_graphs`` (boolean) -- If set to ``True`` (default) this method makes copies of the graphs before returning them. If set to ``False`` the method returns the graph it is working on. The second alternative is faster, but modifying any of the graph instances returned by the method may break the function's behaviour, as it is using these graphs to compute the next ones : only use ``copy_graph = False`` when you stick to *reading* the graphs returned.

Please tell me what you think :-)

Nathann

comment:6 Changed 11 years ago by Nathann Cohen

Arg.... It's all written on one line. Stupid me. Here it is :

- ``copy_graphs`` (boolean) -- If set to ``True`` (default)
   this method makes copies of the graphs before returning 
   them. If set to ``False`` the method returns the graph it
   is working on. The second alternative is faster, but modifying
   any of the graph instances returned by the method may break
   the function's behaviour, as it is using these graphs to 
   compute the next ones : only use ``copy_graph = False`` when
   you stick to *reading* the graphs returned.

comment:7 Changed 11 years ago by Jason Grout

Can I suggest copy=True, which is shorter and just as clear in the context?

comment:8 in reply to:  7 Changed 11 years ago by Nathann Cohen

Can I suggest copy=True, which is shorter and just as clear in the context?

>_<

Of course... Much more natural :-D

Thanks !!

Nathann

Changed 11 years ago by Lukáš Lánský

comment:9 Changed 11 years ago by Lukáš Lánský

Status: needs_infoneeds_review

If you think that "copy" is better, I don't mind. I thought that a consumer of the library doesn't care about what is the way we create the graphs (that we copy them), so the relevant property of the output is rather independence. The proposed description is also good.

comment:10 Changed 11 years ago by Nathann Cohen

Hellooooooo !!!

Well, with a keyword like "independent" the user needs to read the documentation to understand what it precisely means. And with "copy" he also knows that there is some complexity question hidden in there :-)

comment:11 Changed 11 years ago by Nathann Cohen

Status: needs_reviewneeds_work

(for me the patch is ok, but it does not apply on 5.0-beta1. I just reinstalled it, so it seems genuine :-))

Nathann

comment:12 Changed 11 years ago by Nathann Cohen

Description: modified (diff)
Reviewers: Nathann Cohen
Status: needs_workneeds_review

Well, I do not like to set tickets back to "needs work" in such cases... Here is the same patch rebased on beta1. If it's fine with you too, you can set the ticket to positive_review :-)

Nathann

Changed 11 years ago by Nathann Cohen

Attachment: trac_8458.patch added

comment:13 Changed 11 years ago by Lukáš Lánský

Status: needs_reviewpositive_review

Thank you. :-)

comment:14 Changed 11 years ago by Jeroen Demeyer

Authors: Lukáš Lánský

Lukáš: in the future try to remember to add yourself as Author.

comment:15 Changed 11 years ago by Jeroen Demeyer

Merged in: sage-5.0.beta3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.