solver

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Apr 28, 2022 License: MIT Imports: 15 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	NoAction      = 0
	Solved        = iota
	NoSolution    = iota
	Going         = iota
	ActionRemoved = iota
	ActionAdded   = iota

	DoNoop = false

	ActionDomains = 3 // Bump it if you increase the number of actions

	DefaultMaxAttempts     = 9000
	DefaultLearningRate    = 0.7
	DefaultDiscount        = 1.0
	DefaultInitialObserved = 999999

	QLearningResolverType = "qlearning"
)

Variables

View Source 
var AvailableResolvers = strings.Join([]string{QLearningResolverType}, " ")

Functions

func DecodeModel 

func DecodeModel(model map[string]bool, db types.PackageDatabase) (types.PackagesAssertions, error)

DecodeModel decodes a model from the SAT solver to package assertions (types.PackageAssert)

func NewQLearningResolver 

func NewQLearningResolver(LearningRate, Discount float32, MaxAttempts, initialObservedDelta int) types.PackageResolver

Defaults LearningRate 0.7, Discount 1.0

func NewResolver 

func NewResolver(t types.SolverOptions, installed types.PackageDatabase, definitiondb types.PackageDatabase, solverdb types.PackageDatabase, re types.PackageResolver) types.PackageSolver

NewResolver accepts as argument two lists of packages, the first is the initial set, the second represent all the known packages. Using constructors as in the future we foresee warmups for hot-restore solver cache

func NewSolver 

func NewSolver(t types.SolverOptions, installed types.PackageDatabase, definitiondb types.PackageDatabase, solverdb types.PackageDatabase) types.PackageSolver

NewSolver accepts as argument two lists of packages, the first is the initial set, the second represent all the known packages.

func NewSolverFromOptions 

func NewSolverFromOptions(t types.BhojpurSolverOptions) types.PackageResolver

func SimpleQLearningSolver 

func SimpleQLearningSolver() types.PackageResolver

Types

type ActionType 

type ActionType int

type Choice 

type Choice struct {
	Package string     `json:"pack"`
	Action  ActionType `json:"action"`
}

Choice implements qlearning.Action for a package choice for removal from wanted targets

func ChoiceFromString 

func ChoiceFromString(s string) (*Choice, error)

func (*Choice) Apply 

func (choice *Choice) Apply(state qlearning.State) qlearning.State

Apply updates the state of the solver for the package choice.

func (*Choice) String 

func (choice *Choice) String() string

String returns the character for the current action.

type Explainer 

type Explainer struct{}

func (*Explainer) Solve 

func (*Explainer) Solve(f bf.Formula, s types.PackageSolver) (types.PackagesAssertions, error)

Solve tries to find the MUS (minimum unsat) formula from the original problem. it returns an error with the decoded dimacs

type QLearningResolver 

type QLearningResolver struct {
	Attempts int

	ToAttempt int

	Attempted map[string]bool

	Solver  types.PackageSolver
	Formula bf.Formula

	Targets types.Packages
	Current types.Packages

	Agent *qlearning.SimpleAgent
	// contains filtered or unexported fields
}

func (*QLearningResolver) Choose 

func (resolver *QLearningResolver) Choose(c Choice) bool

Choose applies a pack attempt, returning true if the formula returns sat.

Choose updates the resolver's state.

func (*QLearningResolver) IsComplete 

func (resolver *QLearningResolver) IsComplete() int

Returns the current state.

func (*QLearningResolver) Log 

func (resolver *QLearningResolver) Log(msg string, args ...interface{})

Log is a wrapper of fmt.Printf. If Game.debug is true, Log will print to stdout.

func (*QLearningResolver) Next 

func (resolver *QLearningResolver) Next() []qlearning.Action

Next creates a new slice of qlearning.Action instances. A possible action is created for each package that could be removed from the formula's target

func (*QLearningResolver) Reward 

func (resolver *QLearningResolver) Reward(action *qlearning.StateAction) float32

Reward returns a score for a given qlearning.StateAction. Reward is a member of the qlearning.Rewarder interface. If the choice will make sat the formula, a positive score is returned. Otherwise, a static -1000 is returned.

func (*QLearningResolver) Solve 

func (resolver *QLearningResolver) Solve(f bf.Formula, s types.PackageSolver) (types.PackagesAssertions, error)

func (*QLearningResolver) String 

func (resolver *QLearningResolver) String() string

String returns a consistent hash for the current env state to be used in a qlearning.Agent.

func (*QLearningResolver) Try 

func (resolver *QLearningResolver) Try(c Choice) error

type Solver 

type Solver struct {
	DefinitionDatabase types.PackageDatabase
	SolverDatabase     types.PackageDatabase
	Wanted             types.Packages
	InstalledDatabase  types.PackageDatabase

	Resolver types.PackageResolver
}

Solver is the default solver for Bhojpur ISO

func (*Solver) BuildFormula 

func (s *Solver) BuildFormula() (bf.Formula, error)

BuildFormula builds the main solving formula that is evaluated by the sat solver.

func (*Solver) BuildInstalled 

func (s *Solver) BuildInstalled() (bf.Formula, error)

func (*Solver) BuildPartialWorld 

func (s *Solver) BuildPartialWorld(includeInstalled bool) (bf.Formula, error)

BuildWorld builds the formula which olds the requirements from the package definitions which are available (global state)

func (*Solver) BuildWorld 

func (s *Solver) BuildWorld(includeInstalled bool) (bf.Formula, error)

BuildWorld builds the formula which olds the requirements from the package definitions which are available (global state)

func (*Solver) Conflicts 

func (s *Solver) Conflicts(pack *types.Package, lsp types.Packages) (bool, error)

Conflicts acts like ConflictsWith, but uses package's reverse dependencies to determine if it conflicts with the given set

func (*Solver) ConflictsWith 

func (s *Solver) ConflictsWith(pack *types.Package, lsp types.Packages) (bool, error)

ConflictsWith return true if a package is part of the requirement set of a list of package return false otherwise (and thus it is NOT relevant to the given list)

func (*Solver) ConflictsWithInstalled 

func (s *Solver) ConflictsWithInstalled(p *types.Package) (bool, error)

func (*Solver) Install 

func (s *Solver) Install(c types.Packages) (types.PackagesAssertions, error)

Install returns the assertions necessary in order to install the packages in a system. It calculates the best result possible, trying to maximize new packages.

func (*Solver) Installed 

func (s *Solver) Installed() types.Packages

func (*Solver) RelaxedInstall 

func (s *Solver) RelaxedInstall(c types.Packages) (types.PackagesAssertions, error)

Install given a list of packages, returns package assertions to indicate the packages that must be installed in the system in order to statisfy all the constraints

func (*Solver) SetDefinitionDatabase 

func (s *Solver) SetDefinitionDatabase(db types.PackageDatabase)

func (*Solver) SetResolver 

func (s *Solver) SetResolver(r types.PackageResolver)

SetResolver is a setter for the unsat resolver backend

func (*Solver) Solve 

func (s *Solver) Solve() (types.PackagesAssertions, error)

Solve builds the formula given the current state and returns package assertions

func (*Solver) Uninstall 

func (s *Solver) Uninstall(checkconflicts, full bool, packs ...*types.Package) (types.Packages, error)

Uninstall takes a candidate package and return a list of packages that would be removed in order to purge the candidate. Returns error if unsat.

func (*Solver) UninstallUniverse 

func (s *Solver) UninstallUniverse(toremove types.Packages) (types.Packages, error)

UninstallUniverse takes a list of candidate package and return a list of packages that would be removed in order to purge the candidate. Uses the solver to check constraints and nothing else

It can be compared to the counterpart Uninstall as this method acts like a uninstall --full it removes all the packages and its deps. taking also in consideration other packages that might have revdeps

func (*Solver) Upgrade 

func (s *Solver) Upgrade(checkconflicts, full bool) (types.Packages, types.PackagesAssertions, error)

func (*Solver) UpgradeUniverse 

func (s *Solver) UpgradeUniverse(dropremoved bool) (types.Packages, types.PackagesAssertions, error)

UpgradeUniverse mark packages for removal and returns a solution. It considers the Universe db as authoritative See also on the subject: https://arxiv.org/pdf/1007.1021.pdf

func (*Solver) World 

func (s *Solver) World() types.Packages

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.