#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:
---------------------------------+------------------------------------------
Changes (by ncohen):
* status: needs_info => needs_review
Comment:
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 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.
> on rc1 it works fine...
I fixed the segfault on empty graphs, and they are now supported too by
this class. This way nothing bad happens when it is called from
Graph.cliques_maximal.
Patch updated ! `;-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:17>
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.
