Changes between Initial Version and Version 6 of Ticket #13917


Ignore:
Timestamp:
06/01/13 16:20:55 (8 years ago)
Author:
vdelecroix
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

Legend:

Unmodified
Added
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
    • Property Cc vdelecroix added
  • Ticket #13917 – Description

    initial v6  
    22
    33{{{
    4 sage: g = graphs.RandomGNP(50,.7)                   
    5 sage: import networkx                     
    6 sage: gn = g.networkx_graph()                     
     4sage: g = graphs.RandomGNP(50,.7)
     5sage: import networkx
     6sage: gn = g.networkx_graph()
    77sage: %timeit list(networkx.find_cliques(gn))
    8 5 loops, best of 3: 79.8 ms per loop
     810 loops, best of 3: 59.9 ms per loop
     9sage: from sage.graphs.independent_sets import IndependentSets
    910sage: %timeit list(IndependentSets(g,complement=True, maximal = True))
    10 25 loops, best of 3: 26.4 ms per loop
     11100 loops, best of 3: 19.7 ms per loop
     12sage: %timeit IndependentSets(g,complement=True, maximal = True).cardinality()
     13100 loops, best of 3: 17.6 ms per loop
    1114}}}
    1215