rustfst 0.5.0

Library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs).
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

use failure::Fallible;

use crate::algorithms::arc_filters::AnyArcFilter;
use crate::algorithms::dfs_visit::{dfs_visit, Visitor};
use crate::algorithms::state_sort;
use crate::fst_traits::{ExpandedFst, Fst, MutableFst};
use crate::Arc;
use crate::StateId;

pub struct TopOrderVisitor {
    pub order: Vec<StateId>,
    pub acyclic: bool,
    pub finish: Vec<StateId>,
}

impl TopOrderVisitor {
    pub fn new() -> Self {
        Self {
            order: vec![],
            acyclic: true,
            finish: vec![],
        }
    }
}

impl<'a, F: 'a + Fst> Visitor<'a, F> for TopOrderVisitor {
    fn init_visit(&mut self, _fst: &'a F) {}

    fn init_state(&mut self, _s: usize, _root: usize) -> bool {
        true
    }

    fn tree_arc(&mut self, _s: StateId, _arc: &Arc<F::W>) -> bool {
        true
    }

    fn back_arc(&mut self, _s: StateId, _arc: &Arc<F::W>) -> bool {
        self.acyclic = false;
        false
    }

    fn forward_or_cross_arc(&mut self, _s: StateId, _arc: &Arc<F::W>) -> bool {
        true
    }

    fn finish_state(&mut self, s: StateId, _parent: Option<StateId>, _arc: Option<&Arc<F::W>>) {
        self.finish.push(s)
    }

    fn finish_visit(&mut self) {
        if self.acyclic {
            self.order = vec![0; self.finish.len()];

            for s in 0..self.finish.len() {
                self.order[self.finish[self.finish.len() - s - 1]] = s;
            }
        }
    }
}

/// This operation topologically sorts its input. When sorted, all transitions are from
/// lower to higher state IDs.
///
/// # Example
///
/// ## Input
///
/// ![topsort_in](https://raw.githubusercontent.com/Garvys/rustfst-images-doc/master/images/topsort_in.svg?sanitize=true)
///
/// ## Output
///
/// ![topsort_out](https://raw.githubusercontent.com/Garvys/rustfst-images-doc/master/images/topsort_out.svg?sanitize=true)
///
pub fn top_sort<F>(fst: &mut F) -> Fallible<()>
where
    F: MutableFst + ExpandedFst,
{
    let mut visitor = TopOrderVisitor::new();
    dfs_visit(fst, &mut visitor, &AnyArcFilter {}, false);
    if visitor.acyclic {
        state_sort(fst, &visitor.order)?;
    }

    Ok(())
}