Opened 9 years ago

Closed 9 years ago

Last modified 17 months ago

#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 nthiery)

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:

The code needs to be standardized once the choice is done.

Attachments (2)

transitive_ideal-6000-submitted.patch (14.5 KB) - added by nthiery 9 years ago.
trac_6000_reviewer.patch (6.9 KB) - added by rbeezer 9 years ago.
Apply on top of main patch

Download all attachments as: .zip

Change History (8)

Changed 9 years ago by nthiery

comment:1 Changed 9 years ago by nthiery

  • 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 9 years ago by nthiery

  • Status changed from new to assigned

Changed 9 years ago by rbeezer

Apply on top of main patch

comment:3 Changed 9 years ago by rbeezer

  • 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 9 years ago by mhansen

  • Resolution set to fixed
  • Status changed from assigned to closed

Merged in 4.0.1.alpha0.

comment:5 Changed 9 years ago by mhansen

  • Authors set to Nicolas Thiery
  • Merged in set to 4.0.1.alpha0
  • Reviewers set to Rob Beezer

comment:6 Changed 17 months ago by chapoton

  • Authors changed from Nicolas Thiery to Nicolas M. Thiéry
  • Report Upstream set to N/A
Note: See TracTickets for help on using tickets.