satsolver SAT Solver for package management
0.17.9
- Author:
- Michael Schroeder <mls@suse.de>
Welcome to the sat solver documentation page.
The SAT solver is a package dependency solver library which offers the following:
See History of satsolver for the SAT solver history.
Express packaga dependencies as boolean expressions. (in conjunctive normal form - CNF)
(! == boolean not)
- A requires B -> !A or B
- A conflicts B -> !A or !B (! (A and B) A obsoletes B -> A conflicts B
- A provides B -> B == A (replace all occurences of B in CNFs with A)
- Solvable:
- Representation of package with name, version, architecture, dependencies
- Repo:
- Collection of solvables, like a repository or the rpm database
- Pool:
- Collection of repositories. See more at The Pool
- The installed packages are represented as a single repo
- The installed and available packages are represented as a Pool
The solver gets initialized by passing it the complete pool (all Solvables) and a single Source (called 'system', representing the installed Solvables).
It then creates rules to flag the Solvables of 'system' as installed.
See
Code Conventions for code conventions.
http://del.icio.us/kkaempf/sat for a general overview on references about satisfiability, sat-solving and its relation to package dependencies.