# Changes between Initial Version and Version 6 of Ticket #13917

Ignore:
Timestamp:
06/01/13 16:20:55 (8 years ago)
Comment:

0) I found your patch useful!

0') I thought that in your timing most of the time was lost in the creation of the list and the for loop... but no: it is not much faster to enumerate all independent set rather than counting them with the method cardinality (I update the example in the description). So, I am as well surprised by `Python/Cython`.

Todo

1) I am not sure the following is what we want

```sage: I = independent_sets.IndependentSets(graphs.PetersenGraph())
sage: i1 = iter(I); sage: i2 = iter(I)
sage: i1.next()
[0]
sage: i2.next()
[0, 2]
sage: i1.next()
[0, 2, 6]
sage: i2.next()
[0, 2, 8]
```

In other words an iterator is an iterator and nothing else. If you want to design the set of independent sets it should be an object different from the iterator. It would be better to have a Python class `IndependentSets` desinged to modelize the set of independent sets (it should inherit from `Parent` :P) and a Cython iterator `IndependentSetIterator`. What do you think?

2) Could you provide a method to graph (independent_set_iterator or/and independent_sets)?

3) The flag count_only allows to count the number of independent set in only one call to `__next__` (if you do replace "return []" by "if not self.count_only: return []"). Your solution is a bit hackish and moreover the "for i in self: pass" needs to catch the `StopIteration`.

Possible improvements

1) With the current implementation it would be easy to provide the number of independent set of each cardinality and to iterate through the set of independent set of given cardinality.

Documentation

1) The complement of an independent set is a dominating set, right (not a clique) ? If so, please change the documentation accordingly.

2) wikipedia links might be useful :wikipedia:Independent_set_(graph_theory), :wikipedia:Dominating_set, :wikipedia:Clique_graph

Unmodified
Removed
Modified
• ## Ticket #13917

• Property Status changed from `new` to `needs_work`
• Property Reviewers changed from to `ahmorales`
• Property Work issues changed from to `design, documentation`