Struct egg::LpExtractor
source · pub struct LpExtractor<'a, L: Language, N: Analysis<L>> { /* private fields */ }
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 |
On macOS, you might also need the following in your .zshrc
file:
export LIBRARY_PATH=$LIBRARY_PATH:$(brew --prefix)/lib
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
.
Auto Trait Implementations§
impl<'a, L, N> RefUnwindSafe for LpExtractor<'a, L, N>where L: RefUnwindSafe, N: RefUnwindSafe, <N as Analysis<L>>::Data: RefUnwindSafe, <L as DiscriminantKind>::Discriminant: RefUnwindSafe,
impl<'a, L, N> Send for LpExtractor<'a, L, N>where L: Sync, N: Sync, <N as Analysis<L>>::Data: Sync,
impl<'a, L, N> Sync for LpExtractor<'a, L, N>where L: Sync, N: Sync, <N as Analysis<L>>::Data: Sync,
impl<'a, L, N> Unpin for LpExtractor<'a, L, N>
impl<'a, L, N> UnwindSafe for LpExtractor<'a, L, N>where L: RefUnwindSafe, N: RefUnwindSafe, <N as Analysis<L>>::Data: RefUnwindSafe, <L as DiscriminantKind>::Discriminant: RefUnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more