Function rustfst::algorithms::all_pairs_shortest_distance
source · pub fn all_pairs_shortest_distance<F>(fst: &F) -> Result<Vec<Vec<F::W>>, Error>where
F: Fst + ExpandedFst,
F::W: StarSemiring,
Expand description
This operation computes the shortest distance from each state to every other states.
The shortest distance from p
to q
is the ⊕-sum of the weights
of all the paths between p
and q
.
Example
use rustfst::semirings::{Semiring, IntegerWeight};
use rustfst::fst_impls::VectorFst;
use rustfst::fst_traits::MutableFst;
use rustfst::algorithms::all_pairs_shortest_distance;
use rustfst::arc::Arc;
let mut fst = VectorFst::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
let s2 = fst.add_state();
fst.add_arc(&s0, Arc::new(32, 23, IntegerWeight::new(18), s1));
fst.add_arc(&s0, Arc::new(32, 23, IntegerWeight::new(21), s2));
fst.add_arc(&s1, Arc::new(32, 23, IntegerWeight::new(55), s2));
let dists = all_pairs_shortest_distance(&fst).unwrap();
assert_eq!(dists, vec![
vec![IntegerWeight::one(), IntegerWeight::new(18), IntegerWeight::new(18*55 + 21)],
vec![IntegerWeight::zero(), IntegerWeight::one(), IntegerWeight::new(55)],
vec![IntegerWeight::zero(), IntegerWeight::zero(), IntegerWeight::one()],
]);