#13917: IndependentSets class
---------------------------------+------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
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:15 ncohen]:
A stupid comment I was doing myself:
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...
> > - You do not want to do the change, then mention, just next to the
example, that this is not necessarily a good idea
>
> I can do it. I don't mind.
>
> > - add a special filter according to the number of vertices (it is
straightforward to add constants min_num_verts and max_num_verts within
your iterator)
>
> I hope that this will not change the speed of the computations, though.
If you have the time to try, please do. I can not imagine that you will
see a difference with two test conditions. Otherwise, the first solution
is ok.
> > Your computer is better than mine ;-) What sage version are you
running ?
>
> Sage-5.10.rc0. But I don't see why mine would not see a segfault that
occurs on yours. Usually, the one who gets the segfaults is right, and the
one who does not get it is just lucky. There may be a problem somewhere.
>
> > I will compile the rc1 and see what I get (I was on 5.10.beta4).
>
on rc1 it works fine...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13917#comment:16>
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.
