Dear Sage and Sage-combinat developers,
Patch of the day:
#6000 ([with patch, needs review] Sets enumerated by exploring a search space
with a (lazy) tree or graph structure
That's rather trivial code (searches in a graph), but has lots of
applications, and I ended up written it again too many times in my
life. So, this is an attempt at not doing it once again. It's used
extensively in upcoming patches to enumerate elements in a submonoid,
an ideal of a poset, a descent classes in a Coxeter group, a crystal,
etc.
We had the analog in MuPAD-Combinat and used it a lot, but never came
up with a good interface.
So, it needs a review, and more importantly feed back!
Best,
Nicolas
------------------------------------------------------------------------------
This patches extend the sage.combinat.backtrack library with other
generic tools for constructing large sets whose elements can be
enumerated by exploring a search space with a (lazy) tree or graph
structure.
- SearchForest:
Depth first search through a tree descrived by a `child` function
- GenericBacktracker: (was readilly there)
Depth first search through a tree descrived by a `child` function, with
branch pruning, ...
- TransitiveIdeal:
Depth first search through a graph described by a `neighbours` relation
- TransitiveIdealGraded:
Breath first search through a graph described by a `neighbours` relation
Todo: the names are crappy and inconsistent, because they come from
different point of views. We need to find a good naming scheme!!!
Do we want to emphasize the underlying graph/tree structure? The
branch&bound aspect? The transitive closure of a relation point of
view?
Todo: which interface do we want:
- TransitiveIdeal(relation, generators)
- TransitiveIdeal(generators, relation)
The code needs to be standardized once the choice is done.
------------------------------------------------------------------------------
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
