iter

package
v0.4.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 11, 2024 License: MIT Imports: 8 Imported by: 1

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

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 (s BasicStrategy) ReduceSplitVars(variables *f.VarSet, _ int) *f.VarSet

func (BasicStrategy) SplitVarsForRecursionDepth

func (s BasicStrategy) SplitVarsForRecursionDepth(
	variables *f.VarSet, solver *sat.Solver, recursionDepth int,
) *f.VarSet

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

type Config struct {
	Handler  Handler
	Strategy Strategy
}

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.

func (*FixedVarProvider) Vars

func (p *FixedVarProvider) Vars(_ *sat.Solver, _ *f.VarSet) *f.VarSet

Vars returns the split variables for the given solver and subset of 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.

func (*LeastCommonVarProvider) Vars

func (p *LeastCommonVarProvider) Vars(solver *sat.Solver, variables *f.VarSet) *f.VarSet

Vars returns the split variables for the given solver and subset of variables.

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.

func (*MostCommonVarProvider) Vars

func (p *MostCommonVarProvider) Vars(solver *sat.Solver, variables *f.VarSet) *f.VarSet

Vars returns the split variables for the given solver and subset of variables.

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 (s NoSplitStrategy) ReduceSplitVars(_ *f.VarSet, _ int) *f.VarSet

func (NoSplitStrategy) SplitVarsForRecursionDepth

func (s NoSplitStrategy) SplitVarsForRecursionDepth(
	_ *f.VarSet, _ *sat.Solver, _ int,
) *f.VarSet

type SplitProvider

type SplitProvider interface {
	Vars(solver *sat.Solver, variables *f.VarSet) *f.VarSet
}

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

type TimeoutHandler struct {
	handler.Timeout
	// contains filtered or unexported fields
}

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL