Struct egg::LpExtractor

pub struct LpExtractor<'a, L: Language, N: Analysis<L>> { /* private fields */ }

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

impl<'a, L, N> LpExtractor<'a, L, N> where
    L: Language,
    N: Analysis<L>, 

pub fn new<CF>(egraph: &'a EGraph<L, N>, cost_function: CF) -> Self where
    CF: LpCostFunction<L, N>, 

Create an LpExtractor using costs from the given LpCostFunction. See those docs for details.

pub fn timeout(&mut self, seconds: f64) -> &mut Self

Set the cbc timeout in seconds.

pub fn solve(&mut self, root: Id) -> RecExpr<L>

Extract a single rooted term.

This is just a shortcut for LpExtractor::solve_multiple.

pub fn solve_multiple(&mut self, roots: &[Id]) -> (RecExpr<L>, Vec<Id>)

Extract (potentially multiple) roots