Documentation
¶
Overview ¶
Package iter gathers functionality for model iteration in LogicNG.
All (potentially projected) models on a SAT solver are iterated. Iteration can be configured with different strategies. The default strategy is to recursively split the models and iterate over sub-sets. Especially for large enumerations this should yield better performance than iterating in one go.
Index ¶
- type BasicStrategy
- func (s BasicStrategy) MaxModelsForIter(_ int) int
- func (s BasicStrategy) MaxModelsForSplitAssignments(_ int) int
- func (s BasicStrategy) ReduceSplitVars(variables *f.VarSet, _ int) *f.VarSet
- func (s BasicStrategy) SplitVarsForRecursionDepth(variables *f.VarSet, solver *sat.Solver, recursionDepth int) *f.VarSet
- type Collector
- type Config
- type FixedVarProvider
- type Handler
- type LeastCommonVarProvider
- type LimitHandler
- type ModelIterator
- type MostCommonVarProvider
- type NoSplitStrategy
- type SplitProvider
- type Strategy
- type TimeoutHandler
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BasicStrategy ¶
type BasicStrategy struct { SplitProvider SplitProvider MaxModels int }
BasicStrategy represents the default strategy for the model iteration.
It takes a SplitVariableProvider and a maximum number of models.
The split variable provider is used to compute the initial split variables on recursion depth 0. Afterward (including the ReduceSplitVars the reduction of split variables), always the first half of the variables is returned.
MaxModels is always returned for both MaxModelsForIter and MaxModelsForSplitAssignments, ignoring the recursion depth.
This struct can potentially be embedded if you want to fine-tune some methods, e.g. to change the maximum number of models depending on the recursion depth or whether the models are required for iteration or for split assignments.
func DefaultStrategy ¶
func DefaultStrategy() BasicStrategy
DefaultStrategy constructs a new default model iteration strategy with the most common split provider and a maximum number of 500 models.
func NewBasicStrategy ¶
func NewBasicStrategy(splitProvider SplitProvider, maxModels int) BasicStrategy
NewBasicStrategy constructs a new default model iteration strategy with a given split provider and a maximum number of models before a split is performed. In order to guarantee termination of the iteration algorithm, this number must be > 2. If a smaller number is provided, it is automatically set to 3.
func (BasicStrategy) MaxModelsForIter ¶
func (s BasicStrategy) MaxModelsForIter(_ int) int
func (BasicStrategy) MaxModelsForSplitAssignments ¶
func (s BasicStrategy) MaxModelsForSplitAssignments(_ int) int
func (BasicStrategy) ReduceSplitVars ¶
func (BasicStrategy) SplitVarsForRecursionDepth ¶
type Collector ¶
type Collector[R any] interface { // AddModel adds a model to the iteration collector. Returns true if the // model was added successfully. AddModel(modelFromSolver []bool, solver *sat.Solver, relevantAllIndices []int32, handler Handler) bool // Commit confirms all models found since the last commit. These cannot be // rolled back anymore. Also calls the Commit method of the handler. // Returns true if the iteration should continue after the commit. Commit(handler Handler) bool // Rollback discards all models since the last commit. Also calls the // Rollback method of the handler. Returns true if the iteration should // continue after the commit. Rollback(handler Handler) bool // RollbackAndReturnModels discards all models since the last commit and // returns them. Also calls the Rollback method of the handler. RollbackAndReturnModels(solver *sat.Solver, handler Handler) []*model.Model // Result returns the committed state of the collector . Result() R }
Collector gathers functionality for model iteration collectors.
An iteration collector gathers the found models given by AddModel. Added models can potentially be discarded later via Rollback. To prevent models from being rolled back one can call Commit. With Result the result - the committed models - can be retrieved. The generic type R is result type of the model iteration function. It can be e.g. a model count, a list of models, or a BDD.
type Config ¶
Config represents a model iteration configuration including a handler and an iteration strategy.
func DefaultConfig ¶
func DefaultConfig() *Config
DefaultConfig returns the default configuration for a model iteration configuration.
func (Config) DefaultConfig ¶
func (Config) DefaultConfig() configuration.Config
DefaultConfig returns the default configuration for a model iteration configuration.
func (Config) Sort ¶
func (Config) Sort() configuration.Sort
Sort returns the configuration sort (ModelIteration).
type FixedVarProvider ¶
type FixedVarProvider struct {
// contains filtered or unexported fields
}
A FixedVarProvider always returns the same split vars.
func NewFixedVarProvider ¶
func NewFixedVarProvider(variables *f.VarSet) *FixedVarProvider
NewFixedVarProvider generates a new split variable provider which always returns the given variables.
type Handler ¶
type Handler interface { handler.Handler // SatHandler returns the embedded SAT handler. SatHandler() sat.Handler // FoundModels is called every time new models are found. The found models // are in an uncommitted state until they are confirmed by calling Commit. // It is also possible to roll back the uncommitted models by calling // Rollback. Returns true if the iteration should continue. FoundModels(numberOfModels int) bool // Commit is called every time the models are committed. Returns true if // the iteration should continue. Commit() bool // Rollback is called everytime uncommitted models are rolled back. Returns // true if the iteration should continue. Rollback() bool }
Handler describes the functionality of a model iteration handler.
type LeastCommonVarProvider ¶
type LeastCommonVarProvider struct {
// contains filtered or unexported fields
}
A LeastCommonVarProvider is a split variable provider which provides split variables which occur particularly seldom in the formulas on the solver. The variables occurring in the formulas are sorted by their occurrence. This provider returns those variables with the smallest occurrence.
func DefaultLeastCommonVarProvider ¶
func DefaultLeastCommonVarProvider() *LeastCommonVarProvider
DefaultLeastCommonVarProvider returns a new split variable provider which returns the variables with the smallest occurrence on the solver with default values.
func NewLeastCommonVarProvider ¶
func NewLeastCommonVarProvider(takeRate float64, maxVars int) *LeastCommonVarProvider
NewLeastCommonVarProvider returns a new split variable provider which returns the variables with the smallest occurrence on the solver. The take rate must be between 0 and 1 otherwise the function panics.
type LimitHandler ¶
type LimitHandler struct { handler.Computation // contains filtered or unexported fields }
A LimitHandler can be used to abort a model iteration depending on the number of found models.
func HandlerWithLimit ¶
func HandlerWithLimit(limit int) *LimitHandler
HandlerWithLimit generates a new handler which aborts a model iteration after the limit of found models is reached.
func (*LimitHandler) Commit ¶
func (l *LimitHandler) Commit() bool
Commit is called every time the models are committed. Returns true if the iteration should continue.
func (*LimitHandler) FoundModels ¶
func (l *LimitHandler) FoundModels(numberOfModels int) bool
FoundModels is called every time new models are found. The found models are in an uncommitted state until they are confirmed by calling Commit. It is also possible to roll back the uncommitted models by calling Rollback. Returns true if the iteration should continue.
func (*LimitHandler) Rollback ¶
func (l *LimitHandler) Rollback() bool
Rollback is called everytime uncommitted models are rolled back. Returns true if the iteration should continue.
func (*LimitHandler) SatHandler ¶
func (l *LimitHandler) SatHandler() sat.Handler
SatHandler returns the embedded SAT handler.
type ModelIterator ¶
type ModelIterator[R any] struct { // contains filtered or unexported fields }
A ModelIterator iterates over models on a solver.
func New ¶
func New[R any](vars, additionalVars *f.VarSet, config *Config) *ModelIterator[R]
New creates a new model iterator. It will iterate over all models projected to the given vars. The additionalVars will be included in each model, but they are not iterated over. The config can be used to influence the iteration process with a split strategy an optional handler to abort the iteration.
func (*ModelIterator[R]) Iterate ¶
func (m *ModelIterator[R]) Iterate( solver *sat.Solver, newCollector func(fac f.Factory, knownVars, dontCareVars, additionalVars *f.VarSet) Collector[R], ) (R, bool)
Iterate is the main entry point for the model iteration. It iterates over all model on the given solver. The newCollector function is used to generate a new iteration collector for the given known variables on the solver, don't care variables, and additional variables.
type MostCommonVarProvider ¶
type MostCommonVarProvider struct {
// contains filtered or unexported fields
}
A MostCommonVarProvider is a split variable provider which provides split variables which occur particularly often in the formulas on the solver. The variables occurring in the formulas are sorted by their occurrence. This provider returns those variables with the largest occurrence.
func DefaultMostCommonVarProvider ¶
func DefaultMostCommonVarProvider() *MostCommonVarProvider
DefaultMostCommonVarProvider returns a new split variable provider which returns the variables with the largest occurrence on the solver with default values.
func NewMostCommonVarProvider ¶
func NewMostCommonVarProvider(takeRate float64, maxVars int) *MostCommonVarProvider
NewMostCommonVarProvider returns a new split variable provider which returns the variables with the largest occurrence on the solver. The take rate must be between 0 and 1 otherwise the function panics.
type NoSplitStrategy ¶
type NoSplitStrategy struct{}
NoSplitStrategy is strategy for the model iteration where there are no splits.
func NewNoSplitMEStrategy ¶
func NewNoSplitMEStrategy() NoSplitStrategy
NewNoSplitMEStrategy returns a new model iteration strategy without splits.
func (NoSplitStrategy) MaxModelsForIter ¶
func (s NoSplitStrategy) MaxModelsForIter(_ int) int
func (NoSplitStrategy) MaxModelsForSplitAssignments ¶
func (s NoSplitStrategy) MaxModelsForSplitAssignments(_ int) int
func (NoSplitStrategy) ReduceSplitVars ¶
func (NoSplitStrategy) SplitVarsForRecursionDepth ¶
type SplitProvider ¶
A SplitProvider provides functionality to generate a new set of variables for model iteration functions.
type Strategy ¶
type Strategy interface { // MaxModelsForIter returns the maximum number of models to be iterated // on the given recursion depth. // // If this number of models is exceeded, the algorithm will compute new // split assignments and proceed to the next recursion step. // // This number refers to actual iterations on the solver, not to the // expanded number of models in the presence of don't care variables. MaxModelsForIter(recursionDepth int) int // MaxModelsForSplitAssignments returns the maximum number of models to be // iterated for split variables on the given recursion depth. // // This method is used to determine how many split assignments should at // most be computed and used for the next recursion step. If this limit is // exceeded, the algorithm will reduce the number of split variables using // ReduceSplitVars and then try again. MaxModelsForSplitAssignments(recursionDepth int) int // SplitVarsForRecursionDepth selects the split variables for the given // recursion depth from the given variables. // // This method is called before the algorithm makes another recursive call // to determine the initial split variables for this call. SplitVarsForRecursionDepth(variables *f.VarSet, solver *sat.Solver, recursionDepth int) *f.VarSet // ReduceSplitVars reduces the split variables for the given recursion // depth in case of MaxModelsForSplitAssignments was exceeded. ReduceSplitVars(variables *f.VarSet, recursionDepth int) *f.VarSet }
Strategy represents a strategy for fine-tuning the SAT solver based model iteration.
type TimeoutHandler ¶
A TimeoutHandler can be used to abort a model iteration depending on a timeout set beforehand.
func HandlerWithTimeout ¶
func HandlerWithTimeout(timeout handler.Timeout) *TimeoutHandler
HandlerWithTimeout generates a new timeout handler with the given timeout.
func (*TimeoutHandler) Commit ¶
func (t *TimeoutHandler) Commit() bool
Commit is called every time the models are committed. Returns true if the iteration should continue.
func (*TimeoutHandler) FoundModels ¶
func (t *TimeoutHandler) FoundModels(_ int) bool
FoundModels is called every time new models are found. The found models are in an uncommitted state until they are confirmed by calling Commit. It is also possible to roll back the uncommitted models by calling Rollback. Returns true if the iteration should continue.
func (*TimeoutHandler) Rollback ¶
func (t *TimeoutHandler) Rollback() bool
Rollback is called everytime uncommitted models are rolled back. Returns true if the iteration should continue.
func (*TimeoutHandler) SatHandler ¶
func (t *TimeoutHandler) SatHandler() sat.Handler
SatHandler returns the embedded SAT handler.