ebi_objects/ebi_objects/
deterministic_finite_automaton.rs

1use crate::{
2    Activity, ActivityKey, ActivityKeyTranslator, EbiObject, Exportable, Graphable, HasActivityKey,
3    Importable, Infoable, TranslateActivityKey, dfg_format_comparison, json,
4    traits::{
5        graphable,
6        importable::{ImporterParameter, ImporterParameterValues, from_string},
7    },
8};
9#[cfg(any(test, feature = "testactivities"))]
10use ebi_activity_key::TestActivityKey;
11use ebi_arithmetic::anyhow::{Context, Error, Result, anyhow};
12use ebi_derive::ActivityKey;
13use layout::topo::layout::VisualGraph;
14use serde_json::Value;
15use std::{
16    cmp::{Ordering, max},
17    fmt::{Display, Formatter},
18    io::BufRead,
19};
20
21#[derive(Debug, ActivityKey, Clone)]
22pub struct DeterministicFiniteAutomaton {
23    pub activity_key: ActivityKey,
24    pub initial_state: Option<usize>,
25    pub sources: Vec<usize>,       //transition -> source of arc
26    pub targets: Vec<usize>,       //transition -> target of arc
27    pub activities: Vec<Activity>, //transition -> activity of arc (every transition is labelled)
28    pub final_states: Vec<bool>,
29}
30
31impl DeterministicFiniteAutomaton {
32    /**
33     * Creates a new DFA with an initial state that is not an explicit final state. As this state is a deadlock, it is an implicit final state anyway, until an outgoing transition is added.
34     */
35    pub fn new() -> Self {
36        Self {
37            activity_key: ActivityKey::new(),
38            initial_state: Some(0),
39            sources: vec![],
40            targets: vec![],
41            activities: vec![],
42            final_states: vec![false],
43        }
44    }
45
46    pub fn get_sources(&self) -> &Vec<usize> {
47        &self.sources
48    }
49
50    pub fn get_targets(&self) -> &Vec<usize> {
51        &self.targets
52    }
53
54    pub fn get_activities(&self) -> &Vec<Activity> {
55        &self.activities
56    }
57
58    pub fn set_initial_state(&mut self, state: Option<usize>) {
59        if let Some(state) = state {
60            self.ensure_states(state);
61        }
62        self.initial_state = state;
63    }
64
65    /// Ensures that a state with index `new_max_state` exists
66    fn ensure_states(&mut self, new_max_state: usize) {
67        while self.number_of_states() <= new_max_state {
68            self.add_state();
69        }
70    }
71
72    pub fn add_transition(
73        &mut self,
74        source: usize,
75        activity: Activity,
76        target: usize,
77    ) -> Result<()> {
78        self.ensure_states(max(source, target));
79
80        let (found, from) =
81            self.binary_search(source, self.activity_key.get_id_from_activity(activity));
82        if found {
83            //edge already present
84            Err(anyhow!(
85                "tried to insert an edge that would violate the determinism of the SDFA"
86            ))
87        } else {
88            self.sources.insert(from, source);
89            self.targets.insert(from, target);
90            self.activities.insert(from, activity);
91
92            Ok(())
93        }
94    }
95
96    /**
97     * Adds the probability to the transition. Returns the target state, which may be new.
98     */
99    pub fn take_or_add_transition(&mut self, source_state: usize, activity: Activity) -> usize {
100        let (found, transition) = self.binary_search(
101            source_state,
102            self.activity_key.get_id_from_activity(activity),
103        );
104        if found {
105            return self.targets[transition];
106        } else {
107            let target = self.add_state();
108            self.sources.insert(transition, source_state);
109            self.targets.insert(transition, target);
110            self.activities.insert(transition, activity);
111            return target;
112        }
113    }
114
115    pub fn can_terminate_in_state(&self, state: usize) -> bool {
116        self.final_states[state]
117    }
118
119    /**
120     * Returns whether a transition is not permanently disabled.
121     */
122    pub fn can_execute_transition(&self, _transition: usize) -> bool {
123        true
124    }
125
126    pub fn set_final_state(&mut self, state: usize, is_final: bool) {
127        self.final_states[state] = is_final
128    }
129
130    pub fn add_state(&mut self) -> usize {
131        let state = self.final_states.len();
132        self.final_states.push(false);
133        state
134    }
135
136    pub fn number_of_states(&self) -> usize {
137        self.final_states.len()
138    }
139
140    fn compare(source1: usize, activity1: usize, source2: usize, activity2: Activity) -> Ordering {
141        if source1 < source2 {
142            return Ordering::Greater;
143        } else if source1 > source2 {
144            return Ordering::Less;
145        } else if activity2 > activity1 {
146            return Ordering::Greater;
147        } else if activity2 < activity1 {
148            return Ordering::Less;
149        } else {
150            return Ordering::Equal;
151        }
152    }
153
154    pub fn binary_search(&self, source: usize, activity: usize) -> (bool, usize) {
155        if self.sources.is_empty() {
156            return (false, 0);
157        }
158
159        let mut size = self.sources.len();
160        let mut left = 0;
161        let mut right = size;
162        while left < right {
163            let mid = left + size / 2;
164
165            let cmp = Self::compare(source, activity, self.sources[mid], self.activities[mid]);
166
167            left = if cmp == Ordering::Less { mid + 1 } else { left };
168            right = if cmp == Ordering::Greater { mid } else { right };
169            if cmp == Ordering::Equal {
170                assert!(mid < self.sources.len());
171                return (true, mid);
172            }
173
174            size = right - left;
175        }
176
177        assert!(left <= self.sources.len());
178        (false, left)
179    }
180
181    pub fn set_activity_key(&mut self, activity_key: ActivityKey) {
182        self.activity_key = activity_key
183    }
184}
185
186impl TranslateActivityKey for DeterministicFiniteAutomaton {
187    fn translate_using_activity_key(&mut self, to_activity_key: &mut ActivityKey) {
188        let translator = ActivityKeyTranslator::new(&self.activity_key, to_activity_key);
189        self.activities
190            .iter_mut()
191            .for_each(|activity| *activity = translator.translate_activity(&activity));
192        self.activity_key = to_activity_key.clone();
193    }
194}
195
196impl Importable for DeterministicFiniteAutomaton {
197    const FILE_FORMAT_SPECIFICATION_LATEX: &str = concat!("A deterministic finite automaton is a JSON structure with the top level being an object.
198    This object contains the following key-value pairs:
199    \\begin{itemize}
200    \\item \\texttt{initialState} being the index of the initial state. This field is optional: if omitted, the DFA has an empty language.
201    \\item \\texttt{finalStates} being a list of indices of the final states.
202    A final state is not necessarily a deadlock state.
203    \\item \\texttt{transitions} being a list of transitions. 
204    Each transition is an object with \\texttt{from} being the source state index of the transition, \\texttt{to} being the target state index of the transition, and \texttt{{label}} being the activity of the transition. 
205    Silent transitions are not supported.
206    The file format supports deadlocks and livelocks.
207    \\end{itemize}
208    For instance:
209    \\lstinputlisting[language=json, style=boxed]{../testfiles/aa-ab-ba.dfa}", dfg_format_comparison!());
210
211    const IMPORTER_PARAMETERS: &[ImporterParameter] = &[];
212
213    fn import_as_object(
214        reader: &mut dyn BufRead,
215        parameter_values: &ImporterParameterValues,
216    ) -> Result<EbiObject> {
217        Ok(EbiObject::DeterministicFiniteAutomaton(Self::import(
218            reader,
219            parameter_values,
220        )?))
221    }
222
223    fn import(reader: &mut dyn BufRead, _: &ImporterParameterValues) -> Result<Self>
224    where
225        Self: Sized,
226    {
227        let json: Value = serde_json::from_reader(reader)?;
228
229        let mut result = DeterministicFiniteAutomaton::new();
230
231        result.set_initial_state(json::read_field_number(&json, "initialState").ok());
232
233        //read transitions
234        let jtrans = json::read_field_list(&json, "transitions")
235            .context("failed to read list of transitions")?;
236        for jtransition in jtrans {
237            let from =
238                json::read_field_number(jtransition, "from").context("could not read from")?;
239            let to = json::read_field_number(jtransition, "to").context("could not read to")?;
240            let label =
241                json::read_field_string(jtransition, "label").context("could not read label")?;
242            let activity = result.activity_key.process_activity(label.as_str());
243
244            result.ensure_states(from);
245            result.ensure_states(to);
246
247            result.add_transition(from, activity, to)?;
248        }
249
250        //read final states
251        let jfinal_states = json::read_field_list(&json, "finalStates")
252            .with_context(|| "failed to read list of final states")?;
253        for jfinal_state in jfinal_states {
254            let state = json::read_number(jfinal_state).context("could not read final state")?;
255
256            result.ensure_states(state);
257
258            result.final_states[state] = true;
259        }
260
261        return Ok(result);
262    }
263}
264from_string!(DeterministicFiniteAutomaton);
265
266impl Exportable for DeterministicFiniteAutomaton {
267    fn export_from_object(object: EbiObject, f: &mut dyn std::io::Write) -> Result<()> {
268        match object {
269            EbiObject::DeterministicFiniteAutomaton(dfa) => dfa.export(f),
270            EbiObject::FiniteLanguage(lang) => Into::<Self>::into(lang).export(f),
271            EbiObject::FiniteStochasticLanguage(slang) => Into::<Self>::into(slang).export(f),
272            EbiObject::EventLog(log) => Into::<Self>::into(log).export(f),
273            EbiObject::EventLogTraceAttributes(log) => Into::<Self>::into(log).export(f),
274            EbiObject::EventLogXes(log) => Into::<Self>::into(log).export(f),
275            EbiObject::EventLogCsv(log) => Into::<Self>::into(log).export(f),
276            EbiObject::StochasticDeterministicFiniteAutomaton(sdfa) => {
277                Into::<Self>::into(sdfa).export(f)
278            }
279            EbiObject::StochasticNondeterministicFiniteAutomaton(snfa) => {
280                Into::<Self>::into(snfa).export(f)
281            }
282            EbiObject::StochasticDirectlyFollowsModel(sdfm) => Into::<Self>::into(sdfm).export(f),
283            EbiObject::StochasticProcessTree(sdfm) => Into::<Self>::into(sdfm).export(f),
284            EbiObject::DirectlyFollowsModel(dfm) => Into::<Self>::into(dfm).export(f),
285            EbiObject::DirectlyFollowsGraph(dfg) => Into::<Self>::into(dfg).export(f),
286            _ => Err(anyhow!("Cannot export {} to DFA.", object.get_type())),
287        }
288    }
289
290    fn export(&self, f: &mut dyn std::io::Write) -> Result<()> {
291        Ok(write!(f, "{}", self)?)
292    }
293}
294
295impl Infoable for DeterministicFiniteAutomaton {
296    fn info(&self, f: &mut impl std::io::Write) -> Result<()> {
297        writeln!(f, "Number of states\t{}", self.number_of_states())?;
298        writeln!(f, "Number of transitions\t{}", self.sources.len())?;
299        writeln!(
300            f,
301            "Number of activities\t{}",
302            self.activity_key.get_number_of_activities()
303        )?;
304
305        writeln!(f, "")?;
306        self.activity_key().info(f)?;
307
308        Ok(write!(f, "")?)
309    }
310}
311
312impl Display for DeterministicFiniteAutomaton {
313    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
314        writeln!(f, "{{")?;
315        if let Some(state) = self.initial_state {
316            writeln!(f, "\"initialState\": {},", state)?;
317        }
318        writeln!(f, "\"transitions\": [")?;
319        for pos in 0..self.sources.len() {
320            write!(
321                f,
322                "{{\"from\":{},\"to\":{},\"label\":\"{}\"}}",
323                self.sources[pos],
324                self.targets[pos],
325                self.activity_key.get_activity_label(&self.activities[pos])
326            )?;
327            if pos + 1 == self.sources.len() {
328                writeln!(f, "")?;
329            } else {
330                writeln!(f, ",")?;
331            }
332        }
333        writeln!(f, "], \"finalStates\": [")?;
334        writeln!(
335            f,
336            "{}",
337            self.final_states
338                .iter()
339                .enumerate()
340                .filter_map(|(index, is)| if *is { Some(index.to_string()) } else { None })
341                .collect::<Vec<_>>()
342                .join(",")
343        )?;
344        writeln!(f, "]}}")?;
345        Ok(())
346    }
347}
348
349impl Graphable for DeterministicFiniteAutomaton {
350    fn to_dot(&self) -> Result<layout::topo::layout::VisualGraph> {
351        let mut graph = VisualGraph::new(layout::core::base::Orientation::LeftToRight);
352
353        let mut places = vec![];
354        for state in 0..self.number_of_states() {
355            if self.can_terminate_in_state(state) {
356                places.push(graphable::create_transition(
357                    &mut graph,
358                    &state.to_string(),
359                    "",
360                ));
361            } else {
362                places.push(graphable::create_place(&mut graph, &state.to_string()));
363            }
364        }
365
366        for pos in 0..self.sources.len() {
367            let source = places[self.sources[pos]];
368            let target = places[self.targets[pos]];
369            let activity = self.activity_key.get_activity_label(&self.activities[pos]);
370
371            graphable::create_edge(&mut graph, &source, &target, activity);
372        }
373
374        Ok(graph)
375    }
376}
377
378#[cfg(any(test, feature = "testactivities"))]
379impl TestActivityKey for DeterministicFiniteAutomaton {
380    fn test_activity_key(&self) {
381        self.activities
382            .iter()
383            .for_each(|activity| self.activity_key().assert_activity_is_of_key(activity));
384    }
385}
386
387#[cfg(test)]
388mod tests {
389    use super::DeterministicFiniteAutomaton;
390    use crate::HasActivityKey;
391
392    #[test]
393    fn insert_wrong_edge() {
394        let mut dfa = DeterministicFiniteAutomaton::new();
395        let state = dfa.initial_state.unwrap();
396        let activity = dfa.activity_key_mut().process_activity("a");
397
398        dfa.get_sources();
399
400        assert!(dfa.add_transition(state, activity, state).is_ok());
401        assert!(dfa.add_transition(state, activity, state).is_err());
402    }
403}
ebi_objects/ebi_objects/deterministic_finite_automaton.rs

ebi_objects/ebi_objects/
deterministic_finite_automaton.rs
