Struct LpExtractor 

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

Available on crate feature lp only.

A structure to perform extraction using integer linear programming.

This uses the good_lp to support multiple solving backends. The default backend is cbc. You must have it installed on your machine or choose a different backend (see below). You can install cbc 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.len(), 2);

Configuring the LP backend

Enable the corresponding good_lp feature in your own crate. For example, in your Cargo.toml:

[dependencies]
egg = { version = "0.10", features = ["lp"] }
good_lp = { version = "1", features = ["coin_cbc"] } # or highs, microlp, etc.

See the (good_lp documentation)[https://docs.rs/good_lp/1/good_lp/solvers/index.html]

At run time, select the solver by calling Self::solve_with, Self::solve_multiple_with, Self::solve_with_timeout, or Self::solve_multiple_with_timeout and passing one of the enabled good_lp solver implementations.

• Example (CBC):

use good_lp::coin_cbc;
let rec = LpExtractor::new(egraph, AstSize)
  .solve_with(root, coin_cbc);

• Example (HiGHS):

  use good_lp::highs;
  let rec = LpExtractor::new(egraph, AstSize)
      .solve_with(root, highs);

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 solve(&mut self, root: Id) -> RecExpr<L>

Extract a single rooted term.

This is just a shortcut for LpExtractor::solve_multiple.

pub fn solve_with<S: Solver>(&mut self, root: Id, solver: S) -> RecExpr<L>

Extract a single rooted term with an explicit solver backend.

pub fn solve_with_timeout<S: Solver>( &mut self, root: Id, solver: S, timeout: f64, ) -> RecExpr<L>

where <S as Solver>::Model: WithTimeLimit,

Extract a single rooted term with an explicit solver backend and time limit.

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

Extract (potentially multiple) roots

pub fn solve_multiple_with<S: Solver>( &mut self, roots: &[Id], solver: S, ) -> (RecExpr<L>, Vec<Id>)

Like [solve_multiple], but lets the caller provide a good_lp solver backend. Example: solve_multiple_with(roots, good_lp::highs).

pub fn solve_multiple_with_timeout<S: Solver>( &mut self, roots: &[Id], solver: S, timeout: f64, ) -> (RecExpr<L>, Vec<Id>)

where <S as Solver>::Model: WithTimeLimit,

Like [solve_multiple_with], but lets the caller provide a time limit for the ‘good_lp’ solver in seconds. Example: solve_multiple_with_timeout(roots, good_lp::highs, 600.0).