Skip to main content

compute_properties

arcweight::properties

Function compute_properties 

Source 
pub fn compute_properties<W: Semiring, F: Fst<W>>(fst: &F) -> FstProperties
Expand description

Compute FST properties through structural analysis

Analyzes the FST structure to determine which properties hold, including epsilon patterns, determinism, connectivity, and weight characteristics. Properties are computed once and can be cached for efficient access.

§Algorithm

  • Time Complexity: O(|V| + |E|) where V = states, E = arcs
  • Space Complexity: O(|V|) for visited state tracking
  • Analysis: Single pass through all states and arcs with graph traversal

§Properties Computed

§Always Computed

  • Epsilon transition patterns
  • Acceptor vs transducer classification
  • Weight presence (weighted vs unweighted)
  • Connectivity (accessible, coaccessible)
  • Topology (cyclic vs acyclic)
  • String property (linear vs branching)

§Not Currently Computed

  • Input/output determinism (requires more complex analysis)
  • Functional property (requires path analysis)
  • Arc sorting properties (requires per-state sorting checks)

§Examples

use arcweight::prelude::*;

// Analyze a simple acceptor FST
let mut fst = VectorFst::<BooleanWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
fst.set_start(s0);
fst.set_final(s1, BooleanWeight::one());
fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, BooleanWeight::one(), s1));

let props = compute_properties(&fst);

// Check computed properties
assert!(props.has_property(PropertyFlags::ACCEPTOR));
assert!(props.has_property(PropertyFlags::UNWEIGHTED));
assert!(props.has_property(PropertyFlags::ACYCLIC));
assert!(props.has_property(PropertyFlags::NO_EPSILONS));
assert!(props.has_property(PropertyFlags::STRING));

§Property-Based Optimization

use arcweight::prelude::*;

fn optimize_based_on_properties<W: StarSemiring + std::hash::Hash + Eq + Ord>(
    fst: &VectorFst<W>
) -> Result<VectorFst<W>> {
    let props = compute_properties(fst);
     
    // Skip operations based on properties
    let mut result = fst.clone();
     
    if !props.has_property(PropertyFlags::ACCESSIBLE) {
        result = connect(&result)?; // Remove unreachable states
    }
     
    if props.has_property(PropertyFlags::NO_EPSILONS) {
        // Skip epsilon removal
        println!("No epsilons detected, skipping removal");
    } else {
        result = remove_epsilons(&result)?;
    }
     
    if props.has_property(PropertyFlags::ACYCLIC) {
        // Use topological sort for acyclic FSTs
        result = topsort(&result)?;
    }
     
    Ok(result)
}

// Example usage  
let mut fst = VectorFst::<BooleanWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
fst.set_start(s0);
fst.set_final(s1, BooleanWeight::one());
fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, BooleanWeight::one(), s1));

let optimized = optimize_based_on_properties(&fst).unwrap();
assert!(optimized.num_states() > 0);

§Performance Considerations

  • Caching: Properties should be computed once and cached in the FST
  • Incremental: Modifying FSTs should invalidate affected properties
  • Selective: Only compute expensive properties when needed
  • Lazy: Some properties can be computed on-demand

§Errors

This function does not return errors in the current implementation, but future versions may return errors if:

  • The input FST structure is corrupted or invalid
  • Memory allocation fails during property computation
  • Complex property analysis encounters unsupported FST patterns

§See Also