ebi_objects/ebi_objects/
stochastic_deterministic_finite_automaton.rs

1use crate::{
2    Activity, ActivityKey, ActivityKeyTranslator, EbiObject, Exportable, Graphable, HasActivityKey,
3    Importable, Infoable, TranslateActivityKey, json,
4    traits::{
5        graphable,
6        importable::{ImporterParameter, ImporterParameterValues, from_string},
7    },
8};
9use anyhow::{Context, Result, anyhow};
10use ebi_arithmetic::{Fraction, One, Signed};
11use ebi_derive::ActivityKey;
12use layout::topo::layout::VisualGraph;
13use serde_json::Value;
14use std::{
15    cmp::{Ordering, max},
16    collections::HashMap,
17    fmt,
18    io::BufRead,
19};
20
21#[derive(Debug, ActivityKey, Clone)]
22pub struct StochasticDeterministicFiniteAutomaton {
23    pub activity_key: ActivityKey,
24    pub initial_state: Option<usize>,
25    pub max_state: usize,
26    pub sources: Vec<usize>,          //transition -> source of arc
27    pub targets: Vec<usize>,          //transition -> target of arc
28    pub activities: Vec<Activity>,    //transition -> activity of arc (every transition is labelled)
29    pub probabilities: Vec<Fraction>, //transition -> probability of arc
30    pub terminating_probabilities: Vec<Fraction>, //state -> termination probability
31}
32
33impl StochasticDeterministicFiniteAutomaton {
34    /**
35     * Creates a new SDFA with an initial state. That is, it will have the stochastic language with the empty trace.
36     */
37    pub fn new() -> Self {
38        Self {
39            activity_key: ActivityKey::new(),
40            max_state: 0,
41            initial_state: Some(0),
42            sources: vec![],
43            targets: vec![],
44            activities: vec![],
45            probabilities: vec![],
46            terminating_probabilities: vec![Fraction::one()],
47        }
48    }
49
50    pub fn get_sources(&self) -> &Vec<usize> {
51        &self.sources
52    }
53
54    pub fn get_targets(&self) -> &Vec<usize> {
55        &self.targets
56    }
57
58    pub fn get_activities(&self) -> &Vec<Activity> {
59        &self.activities
60    }
61
62    pub fn get_probabilities(&self) -> &Vec<Fraction> {
63        &self.probabilities
64    }
65
66    pub fn set_initial_state(&mut self, state: Option<usize>) {
67        if let Some(state) = state {
68            self.ensure_states(state);
69        }
70        self.initial_state = state;
71    }
72
73    pub fn can_terminate_in_state(&self, state: usize) -> bool {
74        self.get_termination_probability(state).is_positive()
75    }
76
77    /**
78     * Returns whether a transition is not permanently disabled.
79     */
80    pub fn can_execute_transition(&self, transition: usize) -> bool {
81        self.probabilities[transition].is_positive()
82    }
83
84    fn ensure_states(&mut self, new_max_state: usize) {
85        if new_max_state > self.max_state {
86            self.terminating_probabilities
87                .extend(vec![Fraction::one(); new_max_state - self.max_state]);
88            self.max_state = new_max_state;
89
90            assert!(self.terminating_probabilities.len() == self.max_state + 1)
91        }
92    }
93
94    pub fn add_transition(
95        &mut self,
96        source: usize,
97        activity: Activity,
98        target: usize,
99        probability: Fraction,
100    ) -> Result<()> {
101        self.ensure_states(max(source, target));
102
103        let (found, from) =
104            self.binary_search(source, self.activity_key.get_id_from_activity(activity));
105        if found {
106            //edge already present
107            Err(anyhow!(
108                "tried to insert edge from {} to {}, which would violate the determinism of the SDFA",
109                source,
110                target
111            ))
112        } else {
113            self.sources.insert(from, source);
114            self.targets.insert(from, target);
115            self.activities.insert(from, activity);
116            self.terminating_probabilities[source] -= &probability;
117            self.probabilities.insert(from, probability);
118
119            if self.terminating_probabilities[source].is_negative() {
120                Err(anyhow!(
121                    "tried to insert edge from {} to {}, which brings the sum outgoing probability of the source state (1-{}) above 1",
122                    source,
123                    target,
124                    self.terminating_probabilities[source]
125                ))
126            } else {
127                Ok(())
128            }
129        }
130    }
131
132    pub fn get_number_of_transitions(&self) -> usize {
133        self.sources.len()
134    }
135
136    /**
137     * Adds the probability to the transition. Returns the target state, which may be new.
138     */
139    pub fn take_or_add_transition(
140        &mut self,
141        source_state: usize,
142        activity: Activity,
143        probability: Fraction,
144    ) -> usize {
145        self.terminating_probabilities[source_state] -= &probability;
146
147        let (found, transition) = self.binary_search(
148            source_state,
149            self.activity_key.get_id_from_activity(activity),
150        );
151        if found {
152            self.probabilities[transition] += &probability;
153            return self.targets[transition];
154        } else {
155            let target = self.add_state();
156            self.sources.insert(transition, source_state);
157            self.targets.insert(transition, target);
158            self.activities.insert(transition, activity);
159            self.probabilities.insert(transition, probability);
160            return target;
161        }
162    }
163
164    /**
165     * Scales the outgoing probabilities of the state.
166     */
167    pub fn scale_outgoing_probabilities(&mut self, state2scale: HashMap<usize, Fraction>) {
168        let mut new_terminating_probabilities =
169            vec![Fraction::one(); self.terminating_probabilities.len()];
170        for (state, _, _, outgoing_probability) in &mut self.into_iter() {
171            if let Some(factor) = state2scale.get(state) {
172                *outgoing_probability /= factor;
173            }
174            new_terminating_probabilities[*state] -= outgoing_probability;
175        }
176        self.terminating_probabilities = new_terminating_probabilities;
177    }
178
179    pub fn get_initial_state(&self) -> Option<usize> {
180        self.initial_state
181    }
182
183    pub fn get_termination_probability(&self, state: usize) -> &Fraction {
184        &self.terminating_probabilities[state]
185    }
186
187    pub fn add_state(&mut self) -> usize {
188        self.max_state += 1;
189        self.terminating_probabilities.push(Fraction::one());
190        return self.max_state;
191    }
192
193    pub fn get_max_state(&self) -> usize {
194        self.max_state
195    }
196
197    fn compare(source1: usize, activity1: usize, source2: usize, activity2: Activity) -> Ordering {
198        if source1 < source2 {
199            return Ordering::Greater;
200        } else if source1 > source2 {
201            return Ordering::Less;
202        } else if activity2 > activity1 {
203            return Ordering::Greater;
204        } else if activity2 < activity1 {
205            return Ordering::Less;
206        } else {
207            return Ordering::Equal;
208        }
209    }
210
211    pub fn binary_search(&self, source: usize, activity: usize) -> (bool, usize) {
212        if self.sources.is_empty() {
213            return (false, 0);
214        }
215
216        let mut size = self.sources.len();
217        let mut left = 0;
218        let mut right = size;
219        while left < right {
220            let mid = left + size / 2;
221
222            let cmp = Self::compare(source, activity, self.sources[mid], self.activities[mid]);
223
224            left = if cmp == Ordering::Less { mid + 1 } else { left };
225            right = if cmp == Ordering::Greater { mid } else { right };
226            if cmp == Ordering::Equal {
227                assert!(mid < self.sources.len());
228                return (true, mid);
229            }
230
231            size = right - left;
232        }
233
234        assert!(left <= self.sources.len());
235        (false, left)
236    }
237
238    pub fn set_activity_key(&mut self, activity_key: &ActivityKey) {
239        self.activity_key = activity_key.clone();
240    }
241}
242
243impl TranslateActivityKey for StochasticDeterministicFiniteAutomaton {
244    fn translate_using_activity_key(&mut self, to_activity_key: &mut ActivityKey) {
245        let translator = ActivityKeyTranslator::new(&self.activity_key, to_activity_key);
246        self.activities
247            .iter_mut()
248            .for_each(|activity| *activity = translator.translate_activity(&activity));
249        self.activity_key = to_activity_key.clone();
250    }
251}
252
253impl Importable for StochasticDeterministicFiniteAutomaton {
254    const FILE_FORMAT_SPECIFICATION_LATEX: &str = "A stochastic deterministic finite automaton is a JSON structure with the top level being an object.
255    This object contains the following key-value pairs:
256    \\begin{itemize}
257    \\item \\texttt{initialState} being the index of the initial state. This field is optional: if omitted, the SDFA has an empty stochastic language.
258    \\item \\texttt{transitions} being a list of transitions. 
259    Each transition is an object with \\texttt{from} being the source state index of the transition, 
260    \\texttt{to} being the target state index of the transition, 
261    \\texttt{label} being the activity of the transition, and
262    \\texttt{prob} being the probability of the transition (may be given as a fraction in a string or a float value. Must be $\\leq 1$). 
263    Silent transitions are not supported.
264    The file format supports deadlocks and livelocks.
265    The probability that a trace terminates in a state is 1 - the sum probability of the outgoing transitions of the state.
266    \\end{itemize}
267    For instance:
268    \\lstinputlisting[language=json, style=boxed]{../testfiles/aa-ab-ba.sdfa}";
269
270    const IMPORTER_PARAMETERS: &[ImporterParameter] = &[];
271
272    fn import_as_object(
273        reader: &mut dyn BufRead,
274        parameter_values: &ImporterParameterValues,
275    ) -> Result<EbiObject> {
276        Ok(EbiObject::StochasticDeterministicFiniteAutomaton(
277            Self::import(reader, parameter_values)?,
278        ))
279    }
280
281    fn import(reader: &mut dyn BufRead, _: &ImporterParameterValues) -> Result<Self>
282    where
283        Self: Sized,
284    {
285        let json: Value = serde_json::from_reader(reader)?;
286
287        let mut result = StochasticDeterministicFiniteAutomaton::new();
288
289        result.set_initial_state(json::read_field_number(&json, "initialState").ok());
290        let jtrans = json::read_field_list(&json, "transitions")
291            .context("failed to read list of transitions")?;
292        for (i, jtransition) in jtrans.iter().enumerate() {
293            let from = json::read_field_number(jtransition, "from")
294                .with_context(|| format!("could not read source of transition {}", i))?;
295            let to = json::read_field_number(jtransition, "to")
296                .with_context(|| format!("could not read destination of transition {}", i))?;
297            let label = json::read_field_string(jtransition, "label")
298                .with_context(|| format!("could not read label of transition {}", i))?;
299            let activity = result.activity_key.process_activity(label.as_str());
300            let probability = json::read_field_fraction(jtransition, "prob")
301                .with_context(|| format!("could not read probability on transition {}", i))?;
302
303            result.add_transition(from, activity, to, probability)?;
304        }
305
306        return Ok(result);
307    }
308}
309from_string!(StochasticDeterministicFiniteAutomaton);
310
311impl Exportable for StochasticDeterministicFiniteAutomaton {
312    fn export_from_object(object: EbiObject, f: &mut dyn std::io::Write) -> Result<()> {
313        match object {
314            EbiObject::StochasticDeterministicFiniteAutomaton(sdfa) => sdfa.export(f),
315            EbiObject::FiniteStochasticLanguage(slang) => Into::<Self>::into(slang).export(f),
316            EbiObject::EventLog(log) => Into::<Self>::into(log).export(f),
317            EbiObject::EventLogTraceAttributes(log) => Into::<Self>::into(log).export(f),
318            EbiObject::EventLogXes(log) => Into::<Self>::into(log).export(f),
319            EbiObject::EventLogCsv(log) => Into::<Self>::into(log).export(f),
320            _ => Err(anyhow!(
321                "Cannot export {} {} as an SDFA.",
322                object.get_type().get_article(),
323                object.get_type()
324            )),
325        }
326    }
327
328    fn export(&self, f: &mut dyn std::io::Write) -> Result<()> {
329        Ok(write!(f, "{}", self)?)
330    }
331}
332
333impl Infoable for StochasticDeterministicFiniteAutomaton {
334    fn info(&self, f: &mut impl std::io::Write) -> Result<()> {
335        writeln!(f, "Number of states\t{}", self.max_state)?;
336        writeln!(f, "Number of transitions\t{}", self.sources.len())?;
337        writeln!(
338            f,
339            "Number of activities\t{}",
340            self.activity_key.get_number_of_activities()
341        )?;
342
343        writeln!(f, "")?;
344        self.activity_key().info(f)?;
345
346        Ok(writeln!(f, "")?)
347    }
348}
349
350impl fmt::Display for StochasticDeterministicFiniteAutomaton {
351    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
352        writeln!(f, "{{")?;
353        if let Some(state) = self.get_initial_state() {
354            writeln!(f, "\"initialState\": {},", state)?;
355        }
356        writeln!(f, "\"transitions\": [")?;
357        for pos in 0..self.sources.len() {
358            write!(
359                f,
360                "{{\"from\":{},\"to\":{},\"label\":\"{}\",\"prob\":\"{}\"}}",
361                self.sources[pos],
362                self.targets[pos],
363                self.activity_key.get_activity_label(&self.activities[pos]),
364                self.probabilities[pos]
365            )?;
366            if pos + 1 == self.sources.len() {
367                writeln!(f, "")?;
368            } else {
369                writeln!(f, ",")?;
370            }
371        }
372        writeln!(f, "]}}")?;
373        Ok(())
374    }
375}
376
377impl Graphable for StochasticDeterministicFiniteAutomaton {
378    fn to_dot(&self) -> Result<layout::topo::layout::VisualGraph> {
379        log::info!("to_dot for StochasticDeterministicFiniteAutomaton");
380        let mut graph = VisualGraph::new(layout::core::base::Orientation::LeftToRight);
381
382        let mut places = vec![];
383        for state in 0..=self.max_state {
384            places.push(graphable::create_place(
385                &mut graph,
386                &format!("{}", self.terminating_probabilities[state]),
387            ));
388            // places.push(<dyn Dottable>::create_place(&mut graph, ""));
389        }
390
391        for pos in 0..self.sources.len() {
392            let source = places[self.sources[pos]];
393            let target = places[self.targets[pos]];
394            let probability = &self.probabilities[pos];
395            let activity = self.activity_key.get_activity_label(&self.activities[pos]);
396
397            graphable::create_edge(
398                &mut graph,
399                &source,
400                &target,
401                &format!("{}, {}", activity, probability.to_string()),
402            );
403        }
404
405        Ok(graph)
406    }
407}
408
409impl<'a> IntoIterator for &'a StochasticDeterministicFiniteAutomaton {
410    type Item = (&'a usize, &'a usize, &'a Activity, &'a Fraction);
411
412    type IntoIter = StochasticDeterministicFiniteAutomatonIterator<'a>;
413
414    fn into_iter(self) -> Self::IntoIter {
415        Self::IntoIter {
416            it_sources: self.get_sources().iter(),
417            it_targets: self.get_targets().iter(),
418            it_activities: self.get_activities().iter(),
419            it_probabilities: self.get_probabilities().iter(),
420        }
421    }
422}
423
424pub struct StochasticDeterministicFiniteAutomatonIterator<'a> {
425    it_sources: std::slice::Iter<'a, usize>,
426    it_targets: std::slice::Iter<'a, usize>,
427    it_activities: std::slice::Iter<'a, Activity>,
428    it_probabilities: std::slice::Iter<'a, Fraction>,
429}
430
431impl<'a> Iterator for StochasticDeterministicFiniteAutomatonIterator<'a> {
432    type Item = (&'a usize, &'a usize, &'a Activity, &'a Fraction);
433
434    fn next(&mut self) -> Option<Self::Item> {
435        if let Some(source) = self.it_sources.next() {
436            let target = self.it_targets.next().unwrap();
437            let activity = self.it_activities.next().unwrap();
438            let probability = self.it_probabilities.next().unwrap();
439            let result = Some((source, target, activity, probability));
440            result
441        } else {
442            None
443        }
444    }
445}
446
447impl<'a> IntoIterator for &'a mut StochasticDeterministicFiniteAutomaton {
448    type Item = (&'a usize, &'a usize, &'a Activity, &'a mut Fraction);
449
450    type IntoIter = StochasticDeterministicFiniteAutomatonMutIterator<'a>;
451
452    fn into_iter(self) -> Self::IntoIter {
453        Self::IntoIter {
454            it_sources: self.sources.iter(),
455            it_targets: self.targets.iter(),
456            it_activities: self.activities.iter(),
457            it_probabilities: self.probabilities.iter_mut(),
458        }
459    }
460}
461
462pub struct StochasticDeterministicFiniteAutomatonMutIterator<'a> {
463    it_sources: std::slice::Iter<'a, usize>,
464    it_targets: std::slice::Iter<'a, usize>,
465    it_activities: std::slice::Iter<'a, Activity>,
466    it_probabilities: std::slice::IterMut<'a, Fraction>,
467}
468
469impl<'a> Iterator for StochasticDeterministicFiniteAutomatonMutIterator<'a> {
470    type Item = (&'a usize, &'a usize, &'a Activity, &'a mut Fraction);
471
472    fn next(&mut self) -> Option<Self::Item> {
473        if let Some(source) = self.it_sources.next() {
474            let target = self.it_targets.next().unwrap();
475            let activity = self.it_activities.next().unwrap();
476            let probability = self.it_probabilities.next().unwrap();
477            let result = Some((source, target, activity, probability));
478            result
479        } else {
480            None
481        }
482    }
483}
ebi_objects/ebi_objects/stochastic_deterministic_finite_automaton.rs

ebi_objects/ebi_objects/
stochastic_deterministic_finite_automaton.rs
