Extraction Gym
A suite of benchmarks to test e-graph extraction algorithms.
Add your algorithm in src/extract and then add a line in src/main.rs. To run, type make.
Data
Please add data! It's just a csv with the following schema:
eclass:str, cost:float, node_name:str, eclass_children:str*
There is a special ## directive to specify the root(s) of the e-graph. You can have multiple of these on separate lines.
Make sure all ids (including roots) are canonical!
Example
Here's an e-graph with f(g(x)) = h(y, x), and everything has cost 1 except for h which has cost 7.5:
## root: 2
0, 1, x
1, 1, g, 0
2, 1, f, 1
# this is a comment, starting the second "term"
3, 1, y
2, 7.5, h, 3, 0
Snippet
Here's a snippet that you can base your csv printing code on if you want. Make sure to also print the ## root: directive to specify the roots!
>();
ids.sort();
for id in ids {
for node in &egraph[id].nodes {
let cost = 1;
write!(w, "{},{},{}", id, cost, node)?;
for child in node.children() {
write!(w, ",{}", child)?;
}
writeln!(w)?;
}
}
Ok(())
}">
pub fn write_to_csv<L, A>(egraph: &EGraph<L, A>, w: &mut impl std::io::Write) -> std::io::Result<()> where L: Language + std::fmt::Display, A: Analysis<L>, { writeln!(w, "# generated by egg {}", env!("CARGO_PKG_VERSION"))?; let mut ids = egraph.classes().map(|c| c.id).collect::<Vec<_>>(); ids.sort(); for id in ids { for node in &egraph[id].nodes { let cost = 1; write!(w, "{},{},{}", id, cost, node)?; for child in node.children() { write!(w, ",{}", child)?; } writeln!(w)?; } } Ok(()) }
2 Oct 24, 2021
367 Jan 8, 2023
222 Jan 1, 2023
1.9k Jan 9, 2023
40 Dec 18, 2022
1 Nov 25, 2021
5 Sep 6, 2023
4 Nov 29, 2022
4 Dec 22, 2022
18 Aug 3, 2023
549 Dec 26, 2022
16 Feb 28, 2022
943 Jan 4, 2023
3 Nov 9, 2021
157 Dec 8, 2022
3 Nov 25, 2021
33 Dec 19, 2022
24 Feb 9, 2023
42 Apr 16, 2023
4 Sep 15, 2021
25 Apr 29, 2022
95 Jan 1, 2023
15 Dec 15, 2022
50 Feb 11, 2023
3 Nov 20, 2023
175 Dec 4, 2022
8 Jan 3, 2024
13 Apr 7, 2023