Struct egg::LpExtractor
source · Available on crate feature
lp
only.Expand description
A structure to perform extraction using integer linear programming.
This uses the cbc
solver.
You must have it installed on your machine to use this feature.
You can install it using:
OS | Command |
---|---|
Fedora / Red Hat | sudo dnf install coin-or-Cbc-devel |
Ubuntu / Debian | sudo apt-get install coinor-libcbc-dev |
macOS | brew install cbc |
Example
use egg::*;
let mut egraph = EGraph::<SymbolLang, ()>::default();
let f = egraph.add_expr(&"(f x x x)".parse().unwrap());
let g = egraph.add_expr(&"(g (g x))".parse().unwrap());
egraph.union(f, g);
egraph.rebuild();
let best = Extractor::new(&egraph, AstSize).find_best(f).1;
let lp_best = LpExtractor::new(&egraph, AstSize).solve(f);
// In regular extraction, cost is measures on the tree.
assert_eq!(best.to_string(), "(g (g x))");
// Using ILP only counts common sub-expressions once,
// so it can lead to a smaller DAG expression.
assert_eq!(lp_best.to_string(), "(f x x x)");
assert_eq!(lp_best.as_ref().len(), 2);
Implementations§
source§impl<'a, L, N> LpExtractor<'a, L, N>where
L: Language,
N: Analysis<L>,
impl<'a, L, N> LpExtractor<'a, L, N>where
L: Language,
N: Analysis<L>,
sourcepub fn new<CF>(egraph: &'a EGraph<L, N>, cost_function: CF) -> Selfwhere
CF: LpCostFunction<L, N>,
pub fn new<CF>(egraph: &'a EGraph<L, N>, cost_function: CF) -> Selfwhere
CF: LpCostFunction<L, N>,
Create an LpExtractor
using costs from the given LpCostFunction
.
See those docs for details.
sourcepub fn solve(&mut self, root: Id) -> RecExpr<L>
pub fn solve(&mut self, root: Id) -> RecExpr<L>
Extract a single rooted term.
This is just a shortcut for LpExtractor::solve_multiple
.