automaton

graph_enfa.rs (14774B)

---

 use crate::{
     dfa,
     enfa::{self, ENFA},
     Automaton, AutomatonError, Dot, FiniteStateAutomaton,
 };
 use petgraph::{graph::NodeIndex, visit::EdgeRef, Directed, Graph};
 use std::{
     collections::{BTreeMap, HashMap, HashSet},
     fmt::Display,
 };
 
 #[derive(Hash, Debug, PartialEq, Eq, Copy, Clone)]
 pub enum Transition {
     Char(char),
     Wildcard,
     Epsilon,
 }
 
 impl Display for Transition {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
             Transition::Char(c) => write!(f, "'{}'", c),
             Transition::Wildcard => write!(f, "•"),
             Transition::Epsilon => write!(f, "ε"),
         }
     }
 }
 
 impl From<Transition> for enfa::Transition {
     fn from(transition: Transition) -> Self {
         match transition {
             Transition::Char(c) => enfa::Transition::Char(c),
             Transition::Wildcard => enfa::Transition::Wildcard,
             Transition::Epsilon => enfa::Transition::Epsilon,
         }
     }
 }
 
 impl From<enfa::Transition> for Transition {
     fn from(transition: enfa::Transition) -> Self {
         match transition {
             enfa::Transition::Char(c) => Transition::Char(c),
             enfa::Transition::Wildcard => Transition::Wildcard,
             enfa::Transition::Epsilon => Transition::Epsilon,
         }
     }
 }
 
 impl From<dfa::Transition> for Transition {
     fn from(transition: dfa::Transition) -> Self {
         match transition {
             dfa::Transition::Char(c) => Transition::Char(c),
             dfa::Transition::Wildcard => Transition::Wildcard,
         }
     }
 }
 
 /// Intended as an easy way of constructing an ε-NFA in bits, adding onto it much like you'd build an ε-NFA on a whiteboard.
 #[derive(Clone)]
 pub struct GraphENFA {
     alphabet: HashSet<char>,
     states: HashSet<u64>,
     initial_state: u64,
     final_states: HashSet<u64>,
     graph: Graph<u64, Transition, Directed>,
     state_id_to_index_map: HashMap<u64, NodeIndex>,
     current_state_id: u64,
 }
 
 impl GraphENFA {
     /// Create a new graph ε-NFA
     pub fn new() -> (Self, u64) {
         let mut states = HashSet::new();
         let mut state_id_to_index_map = HashMap::new();
         let mut graph = Graph::new();
 
         let initial_state_id = 0;
 
         let initial_state_index = graph.add_node(initial_state_id);
 
         states.insert(initial_state_id);
         state_id_to_index_map.insert(initial_state_id, initial_state_index);
 
         (
             GraphENFA {
                 alphabet: HashSet::new(),
                 states,
                 initial_state: initial_state_id,
                 final_states: HashSet::new(),
                 graph,
                 state_id_to_index_map,
                 current_state_id: initial_state_id,
             },
             initial_state_id,
         )
     }
 
     /// Set the acceptance of a state, will return an error if the state is already in the desired acceptance or the state doesn't exist in the ε-NFA.
     pub fn set_state_acceptance(
         &mut self,
         state_id: u64,
         accept: bool,
     ) -> Result<(), AutomatonError> {
         if !self.states.contains(&state_id) {
             return Err(AutomatonError::builder_error(
                 "There's no state with that ID!",
             ));
         }
 
         if accept && !self.final_states.contains(&state_id) && self.final_states.insert(state_id) // adding to final states
             || !accept // Removing from final states
                 && self.final_states.contains(&state_id)
                 && self.final_states.remove(&state_id)
         {
             Ok(())
         } else {
             Err(AutomatonError::builder_error(
                 "The state was already in the desired acceptance!",
             ))
         }
     }
 
     /// Changes the initial state of the ε-NFA to the state with ID `state_id`, this will remove the other initial state. Returns `Ok` of the previous initial state, or an error describing the failure
     pub fn set_initial_state(&mut self, state_id: u64) -> Result<u64, AutomatonError> {
         if !self.states.contains(&state_id) {
             return Err(AutomatonError::builder_error(
                 "There is no state with the specified ID",
             ));
         }
 
         let prev_initial_state_id = self.initial_state;
         self.initial_state = state_id;
 
         Ok(prev_initial_state_id)
     }
 
     /// Inserts a new state with no transitions into the ε-NFA with the ID `state_id`
     fn insert_state(&mut self, state_id: u64) -> Result<(), AutomatonError> {
         if self.states.contains(&state_id) {
             return Err(AutomatonError::builder_error(
                 "There's already a state with that ID",
             ));
         }
 
         let node_index = self.graph.add_node(state_id);
         if !self
             .state_id_to_index_map
             .insert(state_id, node_index)
             .is_none()
         {
             return Err(AutomatonError::builder_error(
                 "There's already a state with that ID",
             ));
         }
 
         if !self.states.insert(state_id) {
             return Err(AutomatonError::builder_error(
                 "There's already a state with that ID",
             ));
         }
         Ok(())
     }
 
     /// Inserts a new state with no transitions into the ε-NFA with the ID of the max existing ID + 1.
     pub fn new_state(&mut self) -> Result<u64, AutomatonError> {
         self.current_state_id += 1;
 
         self.insert_state(self.current_state_id)?;
 
         Ok(self.current_state_id)
     }
 
     /// Add a transition from one state to another, returns an error if either of the states doesn't exist.
     /// An epsilon transition is done using the `None` of the `Option<char>` enum.
     pub fn insert_transition(
         &mut self,
         from_id: u64,
         to_id: u64,
         input: Transition,
     ) -> Result<(), AutomatonError> {
         if !self.states.contains(&from_id) || !self.states.contains(&to_id) {
             return Err(AutomatonError::builder_error(
                 "Tried adding a transition to/from a state that doesn't exist!",
             ));
         }
 
         match input {
             Transition::Char(c) => {
                 if !self.alphabet.contains(&c) {
                     self.alphabet.insert(c);
                 }
             }
             _ => (),
         }
 
         let from_index = self
             .state_id_to_index_map
             .get(&from_id)
             .ok_or(AutomatonError::builder_error(
                 "Couldn't get the index of the from state!",
             ))?
             .to_owned();
 
         let to_index = self
             .state_id_to_index_map
             .get(&to_id)
             .ok_or(AutomatonError::builder_error(
                 "Couldn't get the index of the to state!",
             ))?
             .to_owned();
 
         self.graph.add_edge(from_index, to_index, input);
 
         Ok(())
     }
 
     /// Convert into a regular ε-NFA backed by a `HashMap` instead of a `Graph`
     /// Whilst this can be used, the `as_dfa` method should be used if you're going to evaluate string acceptance.
     pub fn as_enfa(&self) -> Result<ENFA, AutomatonError> {
         let mut transition_table: HashMap<(u64, enfa::Transition), Vec<u64>> = HashMap::new();
         let mut current_states = vec![self.initial_state];
         let mut next_states = vec![];
         let mut visited = HashSet::new();
 
         while current_states.len() != 0 {
             for &current_state in current_states.iter() {
                 let current_state_index = self
                     .state_id_to_index_map
                     .get(&current_state)
                     .ok_or(AutomatonError::conversion_error(
                         "Couldn't get graph index of a state!",
                     ))?
                     .to_owned();
                 for edge in self.graph.edges(current_state_index) {
                     let mut transitions = transition_table
                         .get(&(current_state, Transition::into(*edge.weight())))
                         .map_or(vec![], |v: &Vec<u64>| v.to_owned());
                     let dest = self
                         .graph
                         .node_weight(edge.target())
                         .ok_or(AutomatonError::conversion_error(
                             "Error converting from graph to regular NFA!",
                         ))?
                         .to_owned();
                     if !transitions.contains(&dest) {
                         transitions.push(dest);
                     }
                     if !visited.contains(&dest) {
                         next_states.push(dest);
                     }
                     transition_table.insert(
                         (current_state, Transition::into(*edge.weight())),
                         transitions,
                     );
                 }
 
                 visited.insert(current_state);
             }
             current_states = next_states;
             next_states = vec![];
         }
 
         Ok(ENFA::new(
             self.alphabet.clone(),
             self.states.clone(),
             self.initial_state,
             self.final_states.clone(),
             transition_table,
         ))
     }
 }
 
 impl Automaton for GraphENFA {
     // This should never be used
     fn accepts(&self, input: &str) -> bool {
         let dfa = self.as_dfa().expect("Woops!");
         dfa.accepts(input)
     }
 }
 
 impl FiniteStateAutomaton for GraphENFA {
     /// Converts the `Graph` ε-NFA into a regular ε-NFA backed by a `HashMap`, then converts that to a DFA
     fn as_dfa(&self) -> std::result::Result<crate::dfa::DFA, AutomatonError> {
         let enfa = self.as_enfa()?;
         enfa.as_dfa()
     }
 
     /// This should never be used... Unless you really badly want to modify an existing DFA.
     fn from_dfa(dfa: crate::dfa::DFA) -> std::result::Result<Self, AutomatonError>
     where
         Self: Sized,
     {
         let mut state_id_to_index_map: HashMap<u64, NodeIndex> = HashMap::new();
         let mut graph = Graph::new();
 
         for ((from, input), to) in dfa.transition_table {
             let from_index = state_id_to_index_map
                 .get(&from)
                 .map_or_else(|| graph.add_node(from), |n| n.to_owned());
             state_id_to_index_map.insert(from, from_index);
             let to_index = state_id_to_index_map
                 .get(&to)
                 .map_or_else(|| graph.add_node(to), |n| n.to_owned());
             state_id_to_index_map.insert(to, to_index);
             graph.add_edge(from_index, to_index, Transition::from(input));
         }
 
         let current_state_id = *dfa
             .states
             .iter()
             .max()
             .ok_or(AutomatonError::conversion_error(
                 "Unable to get the current state ID",
             ))?;
 
         Ok(GraphENFA {
             alphabet: dfa.alphabet,
             states: dfa.states,
             initial_state: dfa.initial_state,
             final_states: dfa.final_states,
             graph,
             state_id_to_index_map,
             current_state_id,
         })
     }
 }
 
 impl Display for GraphENFA {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         let mut alphabet_vec: Vec<char> = self.alphabet.iter().copied().collect();
         let mut states_vec: Vec<u64> = self.states.iter().copied().collect();
         let mut final_states_vec: Vec<u64> = self.final_states.iter().copied().collect();
 
         alphabet_vec.sort();
         states_vec.sort();
         final_states_vec.sort();
 
         let alphabet_str: String =
             alphabet_vec
                 .iter()
                 .enumerate()
                 .fold("[".to_owned(), |st, (index, c)| {
                     let ending = if index == self.alphabet.len() - 1 {
                         "]"
                     } else {
                         ", "
                     };
                     format!("{}{}{}", st, c, ending)
                 });
 
         let states_str: String =
             states_vec
                 .iter()
                 .enumerate()
                 .fold("[".to_owned(), |st, (index, n)| {
                     let ending = if index == self.states.len() - 1 {
                         "]"
                     } else {
                         ", "
                     };
                     format!("{}{}{}", st, n, ending)
                 });
 
         let initial_state_str: String = self.initial_state.to_string();
 
         let final_states_str: String =
             final_states_vec
                 .iter()
                 .enumerate()
                 .fold("[".to_owned(), |st, (index, n)| {
                     let ending = if index == self.final_states.len() - 1 {
                         "]"
                     } else {
                         ", "
                     };
                     format!("{}{}{}", st, n, ending)
                 });
 
         writeln!(f, "Alphabet: {}", alphabet_str)?;
         writeln!(f, "States: {}", states_str)?;
         writeln!(f, "Initial State: {}", initial_state_str)?;
         writeln!(f, "Final States: {}", final_states_str)?;
         let graphviz_repr: Result<Dot<Transition>, AutomatonError> = self.try_into();
         match graphviz_repr {
             Ok(s) => writeln!(f, "Graphviz Representation:\n{}", s),
             Err(e) => writeln!(f, "Error getting Graphviz representation: {}", e),
         }
     }
 }
 
 impl From<&GraphENFA> for Graph<u64, Transition, Directed> {
     fn from(graph_enfa: &GraphENFA) -> Self {
         graph_enfa.graph.clone()
     }
 }
 
 impl TryFrom<&GraphENFA> for Dot<Transition> {
     type Error = AutomatonError;
     fn try_from(graph_enfa: &GraphENFA) -> Result<Self, Self::Error> {
         let states = graph_enfa
             .states
             .iter()
             .map(|s| graph_enfa.state_id_to_index_map.get(s).map(|&ix| (*s, ix)))
             .collect::<Option<BTreeMap<u64, _>>>()
             .ok_or(AutomatonError::dot_error(
                 "Unable to get the graph index of one of the states!",
             ))?;
         let initial_state_id =
             *states
                 .get(&graph_enfa.initial_state)
                 .ok_or(AutomatonError::dot_error(
                     "Unable to get the graph index of the initial state!",
                 ))?;
         let final_states = graph_enfa
             .final_states
             .iter()
             .map(|s| states.get(s).map(|&ix| (*s, ix)))
             .collect::<Option<BTreeMap<u64, _>>>()
             .ok_or(AutomatonError::dot_error(
                 "Unable to get the graph index of a final state!",
             ))?;
         Ok(Self::new(
             graph_enfa.into(),
             (graph_enfa.initial_state, initial_state_id),
             final_states,
         ))
     }
 }