arcweight 0.3.0

//! Algorithms for weighted finite-state transducers.
//!
//! This module provides a comprehensive suite of algorithms for manipulating and
//! analyzing weighted finite-state transducers (WFSTs). The implementations follow
//! the theoretical framework established by Mohri et al. and are optimized for
//! practical speech recognition, natural language processing, and pattern matching
//! applications.
//!
//! # Overview
//!
//! Algorithms are organized into functional categories:
//!
//! | Category | Algorithms | Typical Use Case |
//! |----------|-----------|------------------|
//! | Composition | [`compose()`], [`intersect()`], [`difference()`] | Combining transducers |
//! | Optimization | [`determinize()`], [`minimize()`], [`remove_epsilons`] | Reducing FST size |
//! | Path Finding | [`shortest_path()`], [`shortest_distance()`] | Decoding, scoring |
//! | Transformation | [`reverse()`], [`project_input`], [`project_output`] | FST manipulation |
//! | Construction | [`union()`], [`concat()`], [`closure()`] | Building FSTs |
//!
//! # Complexity Summary
//!
//! | Algorithm | Time | Space | Requirements |
//! |-----------|------|-------|--------------|
//! | [`compose`](crate::algorithms::compose()) | $`O(V_1 V_2 E_1 E_2)`$ | $`O(V_1 V_2)`$ | — |
//! | [`determinize`](crate::algorithms::determinize()) | $`O(2^V)`$ worst | $`O(2^V)`$ | [`DivisibleSemiring`] |
//! | [`minimize`](crate::algorithms::minimize()) | $`O(2^V)`$ worst | $`O(2^V)`$ | [`DivisibleSemiring`] |
//! | [`minimize_hopcroft`](crate::algorithms::minimize_hopcroft()) | $`O(V \log V)`$ | $`O(V + E)`$ | Deterministic input |
//! | [`shortest_path`](crate::algorithms::shortest_path()) | $`O(k V (E + V \log V))`$ | $`O(k V)`$ | [`NaturallyOrderedSemiring`] |
//! | [`shortest_distance`](crate::algorithms::shortest_distance()) | $`O(V + E)`$ acyclic | $`O(V)`$ | — |
//! | [`remove_epsilons`](crate::algorithms::remove_epsilons()) | $`O(V^2 + V E)`$ | $`O(V^2)`$ | [`StarSemiring`] |
//!
//! [`DivisibleSemiring`]: crate::semiring::DivisibleSemiring
//! [`NaturallyOrderedSemiring`]: crate::semiring::NaturallyOrderedSemiring
//! [`StarSemiring`]: crate::semiring::StarSemiring
//!
//! # Core Operations
//!
//! ## Composition
//!
//! - [`compose()`] - Compose two FSTs: $`T_1 \circ T_2`$
//! - [`compose_default()`] - Composition with standard label matching
//! - [`compose_sorted()`] - Optimized composition using sorted arcs
//! - [`compose_with_lookahead()`] - Composition with lookahead filtering
//! - [`intersect()`] - Intersection of acceptor languages
//! - [`difference()`] - Language difference $`L(A_1) - L(A_2)`$
//!
//! ## Optimization
//!
//! - [`determinize()`] - Convert NFST to DFST via weighted subset construction
//! - [`minimize()`] - State minimization using Brzozowski's algorithm
//! - [`minimize_hopcroft()`] - $`O(n \log n)`$ minimization via partition refinement
//! - [`remove_epsilons()`] - Eliminate epsilon transitions
//! - [`connect()`] - Remove non-accessible and non-coaccessible states
//! - [`prune()`] - Weight-based arc and state pruning
//!
//! ## Path Algorithms
//!
//! - [`shortest_path()`] - Find k-shortest paths using Yen's algorithm
//! - [`shortest_distance()`] - Compute sum of path weights to each state
//! - [`shortest_distance_acyclic()`] - $`O(V+E)`$ algorithm for DAGs
//! - [`randgen()`] - Stochastic path generation
//!
//! ## Rational Operations
//!
//! - [`concat()`] - Concatenation: $`L_1 \cdot L_2`$
//! - [`union()`] - Union: $`L_1 \cup L_2`$
//! - [`closure()`] - Kleene star: $`L^*`$
//! - [`closure_plus()`] - Kleene plus: $`L^+`$
//!
//! ## Transformation
//!
//! - [`reverse()`] - Reverse arc directions and swap initial/final states
//! - [`project_input()`], [`project_output()`] - Project transducer to acceptor
//! - [`synchronize()`] - Synchronize input/output label timing
//! - [`push_weights()`], [`push_labels()`] - Push toward initial/final states
//! - [`reweight()`] - Reweight using potential function
//!
//! ## Utility
//!
//! - [`topsort()`] - Topological sort of states
//! - [`state_sort()`] - Sort states by BFS/DFS/topological order
//! - [`replace()`] - Replace labels with sub-FSTs
//! - [`condense()`] - Contract strongly connected components
//! - [`partition()`] - Partition states into equivalence classes
//! - [`weight_convert()`] - Convert between semiring types
//! - [`isomorphic()`] - Test FST structural equivalence
//!
//! # Usage Examples
//!
//! ## Basic Pipeline
//!
//! ```
//! use arcweight::prelude::*;
//!
//! // Create a simple FST
//! let mut fst = VectorFst::<TropicalWeight>::new();
//! let s0 = fst.add_state();
//! let s1 = fst.add_state();
//! fst.set_start(s0);
//! fst.set_final(s1, TropicalWeight::one());
//! fst.add_arc(s0, Arc::new(1, 2, TropicalWeight::new(0.5), s1));
//!
//! // Typical optimization pipeline
//! let connected: VectorFst<TropicalWeight> = connect(&fst)?;
//! let deterministic: VectorFst<TropicalWeight> = determinize(&connected)?;
//! let minimal: VectorFst<TropicalWeight> = minimize(&deterministic)?;
//! # Ok::<(), arcweight::Error>(())
//! ```
//!
//! ## Speech Recognition Pipeline
//!
//! ```
//! use arcweight::prelude::*;
//!
//! // Compose grammar with lexicon (typical ASR pipeline)
//! fn build_decoder(
//!     grammar: &VectorFst<TropicalWeight>,
//!     lexicon: &VectorFst<TropicalWeight>,
//! ) -> Result<VectorFst<TropicalWeight>> {
//!     // G ∘ L composition
//!     let gl: VectorFst<TropicalWeight> = compose_default(grammar, lexicon)?;
//!
//!     // Optimize for runtime
//!     let det: VectorFst<TropicalWeight> = determinize(&gl)?;
//!     let min: VectorFst<TropicalWeight> = minimize(&det)?;
//!
//!     Ok(min)
//! }
//! # let mut g = VectorFst::<TropicalWeight>::new();
//! # let s = g.add_state(); g.set_start(s); g.set_final(s, TropicalWeight::one());
//! # let mut l = VectorFst::<TropicalWeight>::new();
//! # let s = l.add_state(); l.set_start(s); l.set_final(s, TropicalWeight::one());
//! # build_decoder(&g, &l)?;
//! # Ok::<(), arcweight::Error>(())
//! ```
//!
//! # References
//!
//! The algorithms in this module are based on the following foundational works:
//!
//! \[1\] Mohri, M., Pereira, F., and Riley, M. 2002. Weighted finite-state transducers
//!     in speech recognition. *Computer Speech & Language* 16, 1 (January 2002), 69-88.
//!     DOI: <https://doi.org/10.1006/csla.2001.0184>
//!
//! \[2\] Mohri, M. 2009. Weighted automata algorithms. In *Handbook of Weighted Automata*,
//!     M. Droste, W. Kuich, and H. Vogler, Eds. Springer, 213-254.
//!     DOI: <https://doi.org/10.1007/978-3-642-01492-5_6>
//!
//! \[3\] Allauzen, C., Riley, M., Schalkwyk, J., Skut, W., and Mohri, M. 2007.
//!     OpenFst: A general and efficient weighted finite-state transducer library.
//!     In *Proceedings of the 12th International Conference on Implementation and
//!     Application of Automata (CIAA 2007)*, 11-23.
//!     DOI: <https://doi.org/10.1007/978-3-540-76336-9_3>

mod arc_sort;
mod arc_sum;
mod arc_unique;
mod closure;
mod compose;
mod compose_lookahead;
mod concat;
mod condense;
mod connect;
mod decode;
mod determinize;
mod difference;
mod encode;
mod intersect;
mod isomorphic;
mod minimize;
mod minimize_hopcroft;
mod partition;
mod project;
mod prune;
mod push;
mod randgen;
mod replace;
mod reverse;
mod reweight;
mod rmepsilon;
mod shortest_distance;
mod shortest_distance_acyclic;
mod shortest_path;
mod state_sort;
mod streaming;
mod synchronize;
mod topsort;
mod union;
mod weight_convert;

pub use arc_sort::{arc_sort, ArcSortType};
pub use arc_sum::arc_sum;
pub use arc_unique::arc_unique;
pub use closure::{closure, closure_plus};
pub use compose::{compose, compose_default, compose_sorted, ComposeFilter, DefaultComposeFilter};
pub use compose_lookahead::{
    compose_with_lookahead, LabelLookaheadFilter, LabelPairLookaheadFilter, LookaheadComposeFilter,
    MatcherLookaheadFilter,
};
pub use concat::concat;
pub use condense::condense;
pub use connect::connect;
pub use decode::{decode_linear_fst, decode_linear_fst_input, decode_linear_fst_output};
pub use determinize::determinize;
pub use difference::difference;
pub use encode::{decode, encode, EncodeTable};
pub use intersect::intersect;
pub use isomorphic::isomorphic;
pub use minimize::minimize;
pub use minimize_hopcroft::minimize_hopcroft;
pub mod parallel;
pub use partition::partition;
pub use project::{project_input, project_output};
pub use prune::{prune, PruneConfig};
pub use push::{push, push_labels, push_weights, PushConfig};
pub use randgen::{randgen, RandGenConfig};
pub use replace::{replace, ReplaceConfig, ReplaceFst};
pub use reverse::reverse;
pub use reweight::{reweight, ReweightType};
pub use rmepsilon::remove_epsilons;
pub use shortest_distance::shortest_distance;
pub use shortest_distance_acyclic::{
    is_acyclic, shortest_distance_acyclic, shortest_distance_acyclic_reverse,
    shortest_distance_auto,
};
pub use shortest_path::{shortest_path, shortest_path_single, ShortestPathConfig};
pub use state_sort::{state_sort, StateSortType};
pub use streaming::{compose_bounded, StreamingShortestPath};
pub use synchronize::synchronize;
pub use topsort::topsort;
pub use union::union;
pub use weight_convert::weight_convert;