#6000 closed enhancement (fixed)
[with patch, positive review] Sets enumerated by exploring a search space with a (lazy) tree or graph structure
Reported by: | nthiery | Owned by: | nthiery |
---|---|---|---|
Priority: | major | Milestone: | sage-4.0.1 |
Component: | combinatorics | Keywords: | enumerate sets, depth first search, ideal of a relation |
Cc: | sage-combinat | Merged in: | 4.0.1.alpha0 |
Authors: | Nicolas M. Thiéry | Reviewers: | Rob Beezer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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.
Attachments (2)
Change History (8)
Changed 13 years ago by
comment:1 Changed 13 years ago by
- Description modified (diff)
- Summary changed from Sets enumerated by exploring a search space with a (lazy) tree or graph structure to [with patch, needs review] Sets enumerated by exploring a search space with a (lazy) tree or graph structure
comment:2 Changed 13 years ago by
- Status changed from new to assigned
Changed 13 years ago by
comment:3 Changed 13 years ago by
- Summary changed from [with patch, needs review] Sets enumerated by exploring a search space with a (lazy) tree or graph structure to [with patch, positive review] Sets enumerated by exploring a search space with a (lazy) tree or graph structure
Passes tests: ./sage -t devel/sage-backtrack/sage/combinat/
Reviewer patch adds two doctests, and some general cleanup, so apply on top of the main patch.
In the case of a search tree (not a graph), options for "leaves only" would be useful. Then the generators could be checked for a first element when using a search tree for existence questions.
Building a single function to call these routines as variants might ease the question of names and interfaces.
Positive review.
comment:4 Changed 13 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Merged in 4.0.1.alpha0.
comment:5 Changed 13 years ago by
- Merged in set to 4.0.1.alpha0
- Reviewers set to Rob Beezer
comment:6 Changed 6 years ago by
- Report Upstream set to N/A
Apply on top of main patch