IndependentSets class

[nathanncohen]

I'm rather disappointed by this patch. Or I'm pleasantly surprised by Python, I don't know. I expected a much better speedup.

sage: g = graphs.RandomGNP(50,.7)
sage: import networkx
sage: gn = g.networkx_graph()
sage: %timeit list(networkx.find_cliques(gn))
10 loops, best of 3: 48.8 ms per loop
sage: from sage.graphs.independent_sets import IndependentSets
sage: %timeit list(IndependentSets(g,complement=True, maximal = True))
10 loops, best of 3: 20.8 ms per loop
sage: %timeit IndependentSets(g,complement=True, maximal = True).cardinality()
100 loops, best of 3: 19 ms per loop

Either way, this patch implements a sage.graphs.independent_set module that can list/count (possibly maximal) independent sets. While right now we can only compute the maximal ones.

Nathann

Depends on #14589

CC: @videlec

Component: graph theory

Author: Nathann Cohen

Branch/Commit: 635c88d

Reviewer: Vincent Delecroix

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

[sagetrac-ahmorales]

comment:2

I think this patch is useful. I was looking for something to count independents sets of a given size since they index certain triangulations of polytopes coming from flows on graphs (#14654).

[sagetrac-ahmorales]

Reviewer: ahmorales

[nathanncohen]

Attachment: trac_13917.patch.gz

[videlec]

comment:5

Hi,

People from statistical physics are interested in finer quantities than the number of independent configurations (independent sets are related to particule interactions). In their case each configuration is counted with a weight of the form $\prod_{v \in I} \lambda(v)$ where $\lambda: V \rightarrow \mathbb{R}_+$ is a function on the vertices. Considering the case of $\lambda$ being constant, the code could even return the polynomial $f(\lambda)$ whose coefficient for $\lambda^k$ is the number of independent set with $k$ vertices (or equivalently the list of number of independent set of given size). Perhaps this polynomial has a name in graph theory ?

I let the serious comments to the reviewer.

Vincent

[videlec]

Work Issues: design, documentation

[videlec]

comment:6

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

[nathanncohen]

comment:7

Yoooooooooooo !!

0. I found your patch useful!

Cool !

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.

Yep O_o

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

Ok. So what you want is an empty class that does nothing, which calls another class that does all the job ? It cannot be just an independent iterator, for I also want to compute the number of cliques without having to compute all the lists of elements at Python level.

In other words an iterator is an iterator and nothing else.

Says the dogma.

If you want to design the set of independent sets it should be an object different from the iterator.

Says the dogma.

It would be better to have a Python class IndependentSets desinged to modelize the set of independent sets

And what on earth would it do that is not a feature of the iterator ?

(it should inherit from Parent :P)

Over my dead body.

and a Cython iterator IndependentSetIterator. What do you think?

I will not create an empty class if I can avoid it.

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

Actually I avoided it on purpose. I felt like this thing was not interesting for everybody, and that it should belong to a module one would load when needed, rather than add a new function to Graph.... What do you think ? It's not like one wants to enumerate independent sets every other day.

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.

I will rewrite this part using $14589 as a dependency. It's a bit stupid to deal with <64 vertices graphs only.

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.

And it already is :

n_sets = [0]*g.order()
for s in IndependentSets(g):
    n_sets[len(s)] += 1

What do you want ? Ugly "if" everywhere in the main loop to filter this before returning them ?...

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

The complement of an independent set is a vertex cover (and very often a dominating set too, unless the graph has isolated vertices), but an independent set of the is a clique. Was that the problem ?

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

Right, right. I will add them to the next version of this patch.

Nathann

[videlec]

comment:8

Replying to @nathanncohen:

Hey!

(it should inherit from Parent :P)

Over my dead body.

(-: you should love your parents :-)

and a Cython iterator IndependentSetIterator. What do you think?

I will not create an empty class if I can avoid it.

And what about

sage: from sage.graphs.independent_sets import IndependentSets
sage: I = IndependentSets(g,complement=True, maximal = True)
sage: I.next()
[0, 1, 2, 9, 19, 35, 40, 43, 47]
sage: I.cardinality()
4457
sage: I.next()
Traceback (most recent call last):
...
StopIteration:

Your class is in between:

• an iterator
• an object that modelises the set of independent sets (the methods cardinality and __contains__)
  Doing both purposes at the same time implies many unsatisfactory behaviors. What I suggest is an iterator that iterates and a class that answers to __contains__ and cardinality. But this is not satisfactory either because you still have to hack the iterator to get the cardinality.

It might be your choice to have a multiple purposes class. If so, specify it in the documentation as : "you can either use the class to iterate (though only once) or compute the cardinality, but do not think that you can do both in a clean way".

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

Actually I avoided it on purpose. I felt like this thing was not interesting for everybody, and that it should belong to a module one would load when needed, rather than add a new function to Graph.... What do you think ? It's not like one wants to enumerate independent sets every other day.

I agree!

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.

I will rewrite this part using $14589 as a dependency. It's a bit stupid to deal with <64 vertices graphs only.

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.

And it already is :

n_sets = [0]*g.order()
for s in IndependentSets(g):
    n_sets[len(s)] += 1

What do you want ? Ugly "if" everywhere in the main loop to filter this before returning them ?...

No. What I meant is to consider a more general attribute .count of type int[64] which contains the number of independent set of each cardinality. But your solution is satisfactory and you can keep the implementation as it is. Could you add your clever solution to the documentation?

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

The complement of an independent set is a vertex cover (and very often a dominating set too, unless the graph has isolated vertices), but an independent set of the is a clique. Was that the problem ?

My mistake.

[nathanncohen]

comment:9

(new patch that works with >64 vertices, based on top of 14589. And even slower than the first one >_<)

Nathann

[nathanncohen]

Dependencies: #14589

[nathanncohen]

comment:11

Newwwwwwww patch !!!!

• It now deals with graphs of arbitrary size (using the binary matrices from binary matrices, dense graphs, and faster is_strongly_regular #14589)

• I spent quite some time complaining to myself (and to Florent) about creating an empty IndependentSets class which would call an IndependentSetsIterator class. He also agreed with you Vincent, and even though I did not like this problem with double loops either, I still refused to write an empty class.

  Because I hate empty classes.

  Turns out that there is a nice way out, that I stupidly did not notice : instead of writing a .next() method, I moved the code to .__iter__(), and replaced the return by yield. And many global variables are now local to .__iter__(), and everything goes well under the sun :-P

  sage: g = graphs.PetersenGraph()
  sage: from sage.graphs.independent_sets import IndependentSets                                        
  sage: IS = IndependentSets(g)
  sage: IS2 = [(x,y) for x in IS for y in IS]
  sage: len(IS2)
  5776
  sage: IS.cardinality()**2
  5776
  

• I added a comment about the difference in speed between this implementation and NetworkX

• Annnnnnd I added some links toward Wikipedia.

Tell me if you like it :-)

Nathann

[nathanncohen]

Attachment: trac_13917-v2.patch.gz

[videlec]

Changed work issues from design, documentation to none

[videlec]

comment:12

Attachment: trac_13917-v2-more_doc.patch.gz

You are a clever guy as you found a solution that satisfy both of us!

Some new comments

0. Nobody would access the documentation in __iter__ or __contains__. I modified the documentation accordingly.

1. you should move bitset_are_disjoint to sage.misc.bitset as somebody else may want to use it.

2. your example to iterate over the independent set of given cardinality is nice to learn Python but not to learn a good algorithm... If I want the independent sets of cardinality 1 of a grid graph 12x12 it will take an hour just to obtain my 144 independent sets.

sage: G = graphs.CubeGraph(5)
sage: I = IndependentSets(G)
sage: [0,1,2,3] in I
BOOOOOOOOOOOOOOOOOOOOOOOOOOOOM!!!

sage: IndependentSets(graphs.EmptyGraph())
REBOOOOOOOOOOOOOOOOOOOOOOOOOOM!!

[nathanncohen]

Commit: 1be18a5

[nathanncohen]

comment:24

(now with a git branch)

---

New commits:

cc8d994	trac #13917: IndependentSets class
d01cefb	trac #13917: add more documentation
1be18a5	trac #13917: doctests

[nathanncohen]

Branch: u/ncohen/13917

[sagetrac-git]

Changed commit from 1be18a5 to 2e15c7d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2e15c7d

trac #13917: A couple of mistakes

[videlec]

Changed reviewer from ahmorales to ahmorales, Vincent Delecroix

[videlec]

comment:26

• I do not like line 168 of independent_sets.py and expecially G.__class__(n) It looks offuscated to me... I replaced it with Graph(n). I am not sure this is the same so please double check.
• I changed the 0 to a 4 in line 114.
• Regarding comment:6 of me (Possible improvements), note that comment:2 of ahmorales advocates for having the iterator for independent sets of fixed size ! So I added it into a TODO section.

See u/vdelecroix/13917 and this is good to go (after your check of point 1 above).

[nathanncohen]

comment:27

Helloooooooooooooooooooooo !!!

I think that this 0 was meant to be a 10 or something. Anyway thank you for changing it.

About G.__class__ : no idea why it was written this way. The only point of this is to create a Graph when G is a Graph and a DiGraph when G is a DiGraph, but really, there, it served no purpose at all.

About the TODO section. HMmmm... I don't like this much, because to me it is not a "todo" at all. It is just ideas for improvement. It is not something that must be done, it is just ideas.... "Possible improvements" would fit better I think. Well. 'tsup to you :-)

I will upload a small commit in a second, because the second check_matching which is defined in the code is not about matchings at all. Annnnd then you can decide what this patch becomes.

Have fuuuuuuuun and thank you again :-)

Nathann

[sagetrac-git]

Changed commit from 2e15c7d to 5aeaccf

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

86bc3fd	documentation improvement
825f8f6	Todo section
5aeaccf	trac #13917: A misnamed function

[videlec]

comment:29

In my last commit, I removed the TODO and put the comment in the NOTE.

---

New commits:

09052a0

remove the TODO and put the comment in NOTE

[videlec]

Changed reviewer from ahmorales, Vincent Delecroix to Vincent Delecroix

[videlec]

Changed commit from 5aeaccf to 09052a0

[videlec]

Changed branch from u/ncohen/13917 to u/vdelecroix/13917

[nathanncohen]

comment:30

Wouhouuuuuu !! :-)

Nathann

[vbraun]

comment:31

Doctest failure

sage -t --long src/sage/graphs/graph.py
**********************************************************************
File "src/sage/graphs/graph.py", line 4910, in sage.graphs.graph.Graph.cliques_maximal
Failed example:
    C.cliques_maximal()
Expected:
    [[0, 4], [4, 1, 2, 3]]
Got:
    [[0, 4], [1, 2, 3, 4]]
**********************************************************************

[nathanncohen]

Changed branch from u/vdelecroix/13917 to public/13917

[nathanncohen]

Changed commit from 09052a0 to 635c88d

[nathanncohen]

New commits:

635c88d

trac #13917: Broken doctest

[vbraun]

Changed branch from public/13917 to 635c88d