#13917: IndependentSets class
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: ahmorales
Authors: Nathann Cohen | Merged in:
Dependencies: #14589 | Stopgaps:
---------------------------------+------------------------------------------
Comment (by vdelecroix):
Replying to [comment:17 ncohen]:
> Hellooooooooooo !!
>
> > The set of independent sets has an acylcic oriented graph structure
(two ind. set are neighbors if you pass from one to the other by removing
or adding a vertex). What you do in your algorithm is that, by considering
an order on the vertices, you can easily build a tree out of this acyclic
graph. So, in principle, it would possible to explore the graph with much
less backtracking... I wonder if this is along those lines that something
clever is done in networkx...
>
> Hmmmmm... I don't get it `O_o`
>
> If you do nothing but talk of the exploration tree then I do not see how
you can beat this implementation : it goes through this tree and only
remembers the name of the current node... I don't see it getting much
cheaper `O_o`
I just read [ftp://ftp-sop.inria.fr/abs/fcazals/papers/ncliques.pdf Cazals
Karande 2008] and in the algorithm they expose: they deal with smaller and
smaller graphs at each step and this is what makes the networkx
implementation faster. It starts from the stupid remark: I have a
candidate u to add to my ind. set, if I add it then I should remove its
neighbors from the graph.
Basically, at each step, you store three sets: R (current indep. set), P
(vertices away from R), X (vertices away from R but yet used) and you
assume that P u X are all neighbors of R. Then for each vertex in P you
add it to R, then update P and R, explore from there and then add the
vertex to X. When X is empty, then you get an independent set, when P and
X are empty you get a maximal independent set.
> > > I can do it. I don't mind.
>
> Hmmm... Turns out that when looking at the code again, it required to
store a variable containing the current number of elements in the set, and
add +=1 and -=1 in several places... Soooooo if you don't need it I would
prefer not to implement this here. I added a message saying that the
iterator trick is not computationally smart.
Ok.
> Patch updated ! `;-)`
Ok
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:19>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
