Expand description
goatd — Greatest Of All Tree Decompositions: tree decompositions of graphs.
A Graph goes in and a TreeDecomposition comes out.
elimination provides min-fill, min-degree, and nested-dissection orders.
flowcutter provides the vendored FlowCutter decomposer and a Rust
separator search. portfolio combines constructions, and
decomposition contains the result type and its separator-based
refinement. partition exposes
the multilevel graph and hypergraph bisectors used by those constructions.
Graph::from_gr and TreeDecomposition::to_td handle the PACE formats.
TreeDecomposition::validate checks a result against its graph. The
library is single-threaded. meter::arm makes duration budgets advance by
charged graph work instead of wall time when repeatable stopping points are
needed.
use goatd::Graph;
use goatd::elimination::{Order, decompose};
// The 4-cycle with one chord: treewidth 2.
let graph = Graph::new(4, [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]);
let td = decompose(&graph, Order::MinFill, 0, None)?;
assert_eq!(td.treewidth(), 2);
let text = td.to_td();
assert!(text.starts_with("s td "));Re-exports§
pub use decomposition::TdBag;pub use decomposition::TreeDecomposition;
Modules§
- decomposition
- Tree-decomposition data, validation, projection, and refinement.
- elimination
- Elimination-order tree decompositions: safe-reduction preprocessing, then a greedy or nested-dissection elimination order, then the bag tree that order induces.
- flowcutter
- FlowCutter tree-decomposition construction and separator search.
- meter
- A work-based clock for repeatable budget decisions.
- partition
- Multilevel two-way partitioning for graphs and hypergraphs.
- portfolio
- Run several decomposition constructions and keep the candidates they produce.
Structs§
- Graph
- An undirected graph as an edge list.
Enums§
- Error
- An invalid input, malformed PACE file, invalid decomposition, oversized problem, or failed FlowCutter construction.