Opened 9 years ago

Closed 7 years ago

#8458 closed defect (fixed)

iterator for graphs() doesn't return independent graphs

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

Description (last modified by ncohen)

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 brunellus 7 years ago.
trac_8458_independent_graphs.2.patch (3.4 KB) - added by brunellus 7 years ago.
trac_8458.patch (3.6 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 9 years ago by rlm

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 9 years ago by jason

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 7 years ago by brunellus

  • Cc brunellus added

Changed 7 years ago by brunellus

comment:4 Changed 7 years ago by brunellus

  • Status changed from new to needs_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 7 years ago by ncohen

  • Status changed from needs_review to needs_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 7 years ago by ncohen

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 follow-up: Changed 7 years ago by jason

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

comment:8 in reply to: ↑ 7 Changed 7 years ago by ncohen

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

>_<

Of course... Much more natural :-D

Thanks !!

Nathann

Changed 7 years ago by brunellus

comment:9 Changed 7 years ago by brunellus

  • Status changed from needs_info to needs_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 7 years ago by ncohen

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

  • Status changed from needs_review to needs_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 7 years ago by ncohen

  • Description modified (diff)
  • Reviewers set to Nathann Cohen
  • Status changed from needs_work to needs_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 7 years ago by ncohen

comment:13 Changed 7 years ago by brunellus

  • Status changed from needs_review to positive_review

Thank you. :-)

comment:14 Changed 7 years ago by jdemeyer

  • Authors set to Lukáš Lánský

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

comment:15 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.