arcweight 0.3.0

//! FST intersection algorithm.
//!
//! Computes the intersection of two weighted finite-state acceptors, creating
//! an acceptor that recognizes exactly the strings accepted by both input acceptors.
//!
//! For acceptors $`A_1`$ and $`A_2`$:
//! $`L(A_1 \cap A_2) = L(A_1) \cap L(A_2) = \{w : w \in L(A_1) \text{ and } w \in L(A_2)\}`$
//!
//! Weights combine via semiring multiplication for matching paths:
//! $(A_1 \cap A_2)(x) = A_1(x) \otimes A_2(x)$.
//!
//! # Implementation Note
//!
//! For acceptors (FSTs where input labels equal output labels), intersection is
//! equivalent to composition. This module implements intersection via composition.
//!
//! # Complexity
//!
//! - **Time:** $`O(|V_1| \times |V_2| \times |E_1| \times |E_2|)`$ worst case
//! - **Space:** $`O(|V_1| \times |V_2|)`$ for the state cross product
//!
//! # References
//!
//! - John E. Hopcroft and Jeffrey D. Ullman. 1979. *Introduction to Automata Theory,
//!   Languages, and Computation*. Addison-Wesley, Reading, MA.
//! - Mehryar Mohri, Fernando Pereira, and Michael Riley. 2002. Weighted finite-state
//!   transducers in speech recognition. *Computer Speech & Language* 16, 1 (2002),
//!   69-88.

use crate::algorithms::compose_default;
use crate::fst::{Fst, MutableFst};
use crate::semiring::Semiring;
use crate::Result;

/// Computes the intersection of two finite-state acceptors.
///
/// Creates a new acceptor that recognizes exactly the strings accepted by
/// both input acceptors:
/// $`L(A_1 \cap A_2) = \{w : w \in L(A_1) \text{ and } w \in L(A_2)\}`$
///
/// Weights combine via semiring multiplication:
/// $(A_1 \cap A_2)(x) = A_1(x) \otimes A_2(x)$.
///
/// # Arguments
///
/// * `fst1` - The first acceptor
/// * `fst2` - The second acceptor
///
/// # Type Parameters
///
/// * `W` - Weight type implementing [`Semiring`]
/// * `F1` - First FST type implementing [`Fst<W>`]
/// * `F2` - Second FST type implementing [`Fst<W>`]
/// * `M` - Output FST type implementing [`MutableFst<W>`] and [`Default`]
///
/// # Returns
///
/// A new acceptor recognizing the intersection of the two input languages.
///
/// # Errors
///
/// Returns [`Error::Algorithm`](crate::Error::Algorithm) if either input FST
/// is invalid or has no start state.
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
/// use arcweight::algorithms::intersect;
///
/// // Acceptor 1: accepts "ab"
/// let mut acc1 = VectorFst::<TropicalWeight>::new();
/// let s0 = acc1.add_state();
/// let s1 = acc1.add_state();
/// let s2 = acc1.add_state();
/// acc1.set_start(s0);
/// acc1.set_final(s2, TropicalWeight::one());
/// acc1.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s1));
/// acc1.add_arc(s1, Arc::new('b' as u32, 'b' as u32, TropicalWeight::one(), s2));
///
/// // Acceptor 2: also accepts "ab"
/// let mut acc2 = VectorFst::<TropicalWeight>::new();
/// let s0 = acc2.add_state();
/// let s1 = acc2.add_state();
/// let s2 = acc2.add_state();
/// acc2.set_start(s0);
/// acc2.set_final(s2, TropicalWeight::one());
/// acc2.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s1));
/// acc2.add_arc(s1, Arc::new('b' as u32, 'b' as u32, TropicalWeight::one(), s2));
///
/// // Intersection accepts "ab"
/// let result: VectorFst<TropicalWeight> = intersect(&acc1, &acc2)?;
/// assert!(result.start().is_some());
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # References
///
/// - Mehryar Mohri, Fernando Pereira, and Michael Riley. 2002. Weighted finite-state
///   transducers in speech recognition. *Computer Speech & Language* 16, 1 (2002),
///   69-88.
///
/// [`Semiring`]: crate::semiring::Semiring
pub fn intersect<W, F1, F2, M>(fst1: &F1, fst2: &F2) -> Result<M>
where
    W: Semiring,
    F1: Fst<W>,
    F2: Fst<W>,
    M: MutableFst<W> + Default,
{
    // intersection is composition for acceptors
    compose_default(fst1, fst2)
}

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

    #[test]
    fn test_intersect_simple() {
        // Create two acceptors that share common strings
        let mut acc1 = VectorFst::<BooleanWeight>::new();
        let s0 = acc1.add_state();
        let s1 = acc1.add_state();
        acc1.set_start(s0);
        acc1.set_final(s1, BooleanWeight::one());
        acc1.add_arc(s0, Arc::new(1, 1, BooleanWeight::one(), s1)); // Accepts "1"

        let mut acc2 = VectorFst::<BooleanWeight>::new();
        let s0 = acc2.add_state();
        let s1 = acc2.add_state();
        acc2.set_start(s0);
        acc2.set_final(s1, BooleanWeight::one());
        acc2.add_arc(s0, Arc::new(1, 1, BooleanWeight::one(), s1)); // Also accepts "1"

        let intersection: VectorFst<BooleanWeight> = intersect(&acc1, &acc2).unwrap();

        // Should have states and start state
        assert!(intersection.num_states() > 0);
        assert!(intersection.start().is_some());
    }

    #[test]
    fn test_intersect_disjoint() {
        // Create two acceptors with no common strings
        let mut acc1 = VectorFst::<BooleanWeight>::new();
        let s0 = acc1.add_state();
        let s1 = acc1.add_state();
        acc1.set_start(s0);
        acc1.set_final(s1, BooleanWeight::one());
        acc1.add_arc(s0, Arc::new(1, 1, BooleanWeight::one(), s1)); // Accepts "1"

        let mut acc2 = VectorFst::<BooleanWeight>::new();
        let s0 = acc2.add_state();
        let s1 = acc2.add_state();
        acc2.set_start(s0);
        acc2.set_final(s1, BooleanWeight::one());
        acc2.add_arc(s0, Arc::new(2, 2, BooleanWeight::one(), s1)); // Accepts "2"

        let intersection: VectorFst<BooleanWeight> = intersect(&acc1, &acc2).unwrap();

        // Should succeed but may have no accepting paths
        assert!(intersection.start().is_some());
    }

    #[test]
    fn test_intersect_weighted() {
        // Test intersection with tropical weights
        let mut acc1 = VectorFst::<TropicalWeight>::new();
        let s0 = acc1.add_state();
        let s1 = acc1.add_state();
        acc1.set_start(s0);
        acc1.set_final(s1, TropicalWeight::new(1.0));
        acc1.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(0.5), s1));

        let mut acc2 = VectorFst::<TropicalWeight>::new();
        let s0 = acc2.add_state();
        let s1 = acc2.add_state();
        acc2.set_start(s0);
        acc2.set_final(s1, TropicalWeight::new(2.0));
        acc2.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(1.5), s1));

        let intersection: VectorFst<TropicalWeight> = intersect(&acc1, &acc2).unwrap();

        // Should combine weights appropriately (tropical addition)
        assert!(intersection.start().is_some());
        assert!(intersection.num_states() > 0);
    }

    #[test]
    fn test_intersect_empty_fsts() {
        let acc1 = VectorFst::<BooleanWeight>::new();
        let acc2 = VectorFst::<BooleanWeight>::new();

        // Empty FSTs should return error (no start state)
        let result = intersect::<
            BooleanWeight,
            VectorFst<BooleanWeight>,
            VectorFst<BooleanWeight>,
            VectorFst<BooleanWeight>,
        >(&acc1, &acc2);
        assert!(result.is_err());
    }

    #[test]
    fn test_intersect_single_state() {
        // Test intersection of single-state acceptors
        let mut acc1 = VectorFst::<BooleanWeight>::new();
        let s0 = acc1.add_state();
        acc1.set_start(s0);
        acc1.set_final(s0, BooleanWeight::one());

        let mut acc2 = VectorFst::<BooleanWeight>::new();
        let s0 = acc2.add_state();
        acc2.set_start(s0);
        acc2.set_final(s0, BooleanWeight::one());

        let intersection: VectorFst<BooleanWeight> = intersect(&acc1, &acc2).unwrap();

        // Both accept empty string, so intersection should too
        assert!(intersection.start().is_some());
    }

    #[test]
    fn test_intersect_multiple_paths() {
        // Create acceptors with multiple paths
        let mut acc1 = VectorFst::<BooleanWeight>::new();
        let s0 = acc1.add_state();
        let s1 = acc1.add_state();
        let s2 = acc1.add_state();
        acc1.set_start(s0);
        acc1.set_final(s1, BooleanWeight::one());
        acc1.set_final(s2, BooleanWeight::one());
        acc1.add_arc(s0, Arc::new(1, 1, BooleanWeight::one(), s1)); // Path: 1
        acc1.add_arc(s0, Arc::new(2, 2, BooleanWeight::one(), s2)); // Path: 2

        let mut acc2 = VectorFst::<BooleanWeight>::new();
        let s0 = acc2.add_state();
        let s1 = acc2.add_state();
        acc2.set_start(s0);
        acc2.set_final(s1, BooleanWeight::one());
        acc2.add_arc(s0, Arc::new(1, 1, BooleanWeight::one(), s1)); // Only accepts 1

        let intersection: VectorFst<BooleanWeight> = intersect(&acc1, &acc2).unwrap();

        // Should intersect correctly
        assert!(intersection.start().is_some());
    }
}