arcweight 0.3.0

//! FST reversal algorithm.
//!
//! Constructs the reverse of a weighted finite-state transducer by reversing
//! all transitions and swapping start/final states. The reversed FST accepts
//! the reversal of each string in the original language.
//!
//! For an FST $`T`$ that accepts language $`L`$, the reversed FST $`T^R`$ accepts
//! the language $`L^R = \{w^R : w \in L\}`$ where $`w^R`$ is the reversal of string $`w`$.
//!
//! # Complexity
//!
//! - **Time:** $`O(|V| + |E|)`$ for state and arc creation
//! - **Space:** $`O(|V| + |E|)`$ for the new FST structure
//!
//! # References
//!
//! - Mehryar Mohri. 2009. Weighted automata algorithms. In *Handbook of Weighted
//!   Automata*, Manfred Droste, Werner Kuich, and Heiko Vogler (Eds.). Springer,
//!   Berlin, Heidelberg, 213-254. DOI: <https://doi.org/10.1007/978-3-642-01492-5_6>

use crate::arc::Arc;
use crate::fst::{Fst, MutableFst};
use crate::semiring::Semiring;
use crate::Result;

/// Reverses an FST by swapping direction of transitions and start/final states.
///
/// Creates the reverse automaton where all transitions are reversed, the original
/// start state becomes final, and original final states connect to a new start state.
/// The reversed FST accepts the reversal of each string in the original language.
///
/// For an FST $`T`$ that maps input strings to output strings with weights,
/// the reverse $`T^R`$ satisfies: $`T^R(x^R) = T(x)`$ where $`x^R`$ is the reversal
/// of string $`x`$.
///
/// # Type Parameters
///
/// * `W` - Weight type implementing [`Semiring`]
/// * `F` - Input FST type implementing [`Fst<W>`]
/// * `M` - Output FST type implementing [`MutableFst<W>`] and [`Default`]
///
/// # Returns
///
/// A new FST representing the reversal of the input FST.
///
/// # Errors
///
/// Returns [`Error::Algorithm`](crate::Error::Algorithm) if the input FST is invalid.
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // Create FST that accepts "ab"
/// let mut fst = VectorFst::<TropicalWeight>::new();
/// let s0 = fst.add_state();
/// let s1 = fst.add_state();
/// let s2 = fst.add_state();
///
/// fst.set_start(s0);
/// fst.set_final(s2, TropicalWeight::one());
///
/// fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s1));
/// fst.add_arc(s1, Arc::new('b' as u32, 'b' as u32, TropicalWeight::one(), s2));
///
/// // Reverse: now accepts "ba"
/// let reversed: VectorFst<TropicalWeight> = reverse(&fst)?;
///
/// // +1 state for new start that connects to original finals
/// assert_eq!(reversed.num_states(), fst.num_states() + 1);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # References
///
/// - Mehryar Mohri. 2009. Weighted automata algorithms. In *Handbook of Weighted
///   Automata*, Manfred Droste, Werner Kuich, and Heiko Vogler (Eds.). Springer,
///   Berlin, Heidelberg, 213-254.
///
/// [`Semiring`]: crate::semiring::Semiring
pub fn reverse<W, F, M>(fst: &F) -> Result<M>
where
    W: Semiring,
    F: Fst<W>,
    M: MutableFst<W> + Default,
{
    let mut result = M::default();

    // create states
    for _ in 0..fst.num_states() {
        result.add_state();
    }

    // create new start state
    let new_start = result.add_state();
    result.set_start(new_start);

    // add reversed arcs
    for state in fst.states() {
        for arc in fst.arcs(state) {
            result.add_arc(
                arc.nextstate,
                Arc::new(arc.ilabel, arc.olabel, arc.weight.clone(), state),
            );
        }

        // final states become arcs from new start
        if let Some(weight) = fst.final_weight(state) {
            result.add_arc(new_start, Arc::epsilon(weight.clone(), state));
        }
    }

    // original start becomes final
    if let Some(orig_start) = fst.start() {
        result.set_final(orig_start, W::one());
    }

    Ok(result)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::prelude::*;

    #[test]
    fn test_reverse_basic() {
        let mut fst = VectorFst::<TropicalWeight>::new();
        let s0 = fst.add_state();
        let s1 = fst.add_state();
        let s2 = fst.add_state();

        fst.set_start(s0);
        fst.set_final(s2, TropicalWeight::new(2.0));

        fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(1.0), s1));
        fst.add_arc(s1, Arc::new(2, 2, TropicalWeight::new(3.0), s2));

        let reversed: VectorFst<TropicalWeight> = reverse(&fst).unwrap();

        // Should add a new start state
        assert_eq!(reversed.num_states(), fst.num_states() + 1);
        assert!(reversed.start().is_some());

        // Original start should be final in reversed
        assert!(reversed.is_final(s0));

        // Check that arcs are reversed
        let mut found_reversed_arc = false;
        for state in reversed.states() {
            for arc in reversed.arcs(state) {
                if arc.nextstate == s1 && arc.ilabel == 2 {
                    found_reversed_arc = true;
                }
            }
        }
        assert!(found_reversed_arc);
    }
}