Sets enumerated by exploring a search space with a (lazy) tree or graph structure

[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:

• TransitiveIdeal(relation, generators)
• TransitiveIdeal(generators, relation)
  The code needs to be standardized once the choice is done.

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: enumerate sets, depth first search, ideal of a relation

Author: Nicolas M. Thiéry

Reviewer: Rob Beezer

Merged: 4.0.1.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/6000

[nthiery]

comment:1

Attachment: transitive_ideal-6000-submitted.patch.gz

[rbeezer]

Apply on top of main patch

[rbeezer]

comment:3

Attachment: trac_6000_reviewer.patch.gz

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.

[mwhansen]

comment:4

Merged in 4.0.1.alpha0.

[mwhansen]

Merged: 4.0.1.alpha0

[mwhansen]

Reviewer: Rob Beezer

[mwhansen]

Author: Nicolas Thiery

[fchapoton]

Changed author from Nicolas Thiery to Nicolas M. Thiéry