geometry_tools.automata.fsa

  1"""Work with finite-state automata.
  2
  3Finite-state automata are really just finite directed labeled graphs,
  4subject to the constraint that each vertex `v` has at most one
  5outgoing edge with a given label. One or more of the vertices are
  6"start states;" a word `w` in the set of edge labels is "accepted" if
  7there is an edge path in the graph (starting at a start state) whose
  8sequence of edge labels gives `w`.
  9
 10This module provides the `FSA` class, which can be used to perform
 11simple tasks with finite-state automata. A common use-case is
 12enumerating the list of words accepted by a particular automaton:
 13
 14```python
 15from geometry_tools.automata import fsa
 16
 17# load a word-acceptor automaton for the (3,3,4) triangle group
 18cox_aut = fsa.load_builtin("cox334.wa")
 19
 20# list all the words accepted by this automaton with length at most 3.
 21list(cox_aut.enumerate_words(3))
 22
 23```
 24     ['',
 25     'a',
 26     'b',
 27     'c',
 28     'ab',
 29     'ac',
 30     'ba',
 31     'bc',
 32     'ca',
 33     'cb',
 34     'aba',
 35     'abc',
 36     'aca',
 37     'acb',
 38     'bac',
 39     'bca',
 40     'bcb',
 41     'cab',
 42     'cac',
 43     'cba']
 44
 45    """
 46import os
 47import copy
 48import importlib.resources
 49from collections import deque, defaultdict
 50
 51
 52from . import kbmag_utils, gap_parse
 53from .. import automata
 54from .. import utils
 55
 56from ..utils import words
 57
 58BUILTIN_DIR = "builtin"
 59
 60
 61class FSAException(Exception):
 62    pass
 63
 64class FSA:
 65    """FSA: a finite state-automaton.
 66
 67    The underlying data structure of a finite-state automaton is a
 68    python dictionary of the form:
 69
 70    ```
 71    {
 72      vertex1: {label_a: neighbor_a, label_b: neighbor_b, ...},
 73      vertex2: ....,
 74    }
 75    ```
 76
 77    That is, `vertex1` is connected to `neighbor_a` by an edge with
 78    label `label_a`, etc.
 79
 80    The automaton can be constructed by passing it a dictionary of
 81    this form, or by adding vertices/edges individually through the
 82    built-in methods.
 83
 84    """
 85    def __init__(self, vert_dict={}, start_vertices=[], graph_dict=True):
 86        """
 87
 88        Parameters
 89        ----------
 90        vert_dict : dict
 91            dictionary of vertices used to build the automaton. By
 92            default, this dictionary should have the format specified
 93            above.
 94
 95        start_vertices : list
 96            list of vertices which are valid start states
 97            for this automaton. Currently, the `FSA` class will not
 98            correctly handle lists of length > 1.
 99
100        graph_dict : bool
101            If `True` (the default), expect a dictionary of the format
102            listed above. If `False`, instead expect a dictionary with format:
103
104            ```
105            {
106              vertex1: {neighbor_a: [neighbor_a_label1, neighbor_a_label2, ...],
107                        neighbor_b: [neighbor_b_label1, neighbor_b_label2, ...], ....},
108              vertex2: ....,
109            }
110            ```
111        """
112        if graph_dict:
113            self._from_graph_dict(vert_dict)
114        else:
115            self._out_dict = FSA._defaultify_out_dict(vert_dict)
116
117            self._build_in_dict()
118            self._build_graph_dict()
119
120        self.start_vertices = start_vertices
121
122    @staticmethod
123    def _defaultify_out_dict(out_dict):
124        return {
125            key: defaultdict(list, copy.deepcopy(value))
126            for key, value in out_dict.items()
127        }
128
129    def _from_graph_dict(self, graph_dict):
130        self._graph_dict = copy.deepcopy(graph_dict)
131        hidden = _hidden_vertices(graph_dict)
132        for v in hidden:
133            self._graph_dict[v] = {}
134
135        out_dict = {v : {} for v in self._graph_dict}
136
137        for v, neighbors in self._graph_dict.items():
138            out_dict[v] = defaultdict(list)
139            for label, neighbor in neighbors.items():
140                out_dict[v][neighbor].append(label)
141
142        self._out_dict = out_dict
143        self._build_in_dict()
144
145    def _build_graph_dict(self):
146        label_dict = {v:{} for v in self._out_dict}
147        for v, neighbors_out in self._out_dict.items():
148            for w, labels in neighbors_out.items():
149                for label in labels:
150                    label_dict[v][label] = w
151        self._graph_dict = label_dict
152
153    def _build_in_dict(self):
154        in_dict = defaultdict(dict)
155        for v, neighbors_out in self._out_dict.items():
156            for w, labels in neighbors_out.items():
157                in_dict[w][v] = labels
158        self._in_dict = in_dict
159
160    def __str__(self):
161        return "FSA with dict:\n{}".format(self._graph_dict.__str__())
162
163    def __repr__(self):
164        return "FSA({})".format(self._graph_dict.__repr__())
165
166    @property
167    def out_dict(self):
168        return self._out_dict
169
170    @property
171    def graph_dict(self):
172        return self._graph_dict
173
174    @property
175    def in_dict(self):
176        return self._in_dict
177
178    def has_edge(self, tail, head):
179        return len(self._out_dict[tail][head]) > 0
180
181    def edges_out(self, vertex):
182        """Get the list of edges directed away from a vertex.
183        """
184        for w, labels in self._out_dict[vertex].items():
185            for label in labels:
186                yield (vertex, w, label)
187
188    def edges_in(self, vertex):
189        """Get the list of edges directed towards a vertex."""
190        for w, labels in self._in_dict[vertex].items():
191            for label in labels:
192                yield (w, vertex, label)
193
194    def neighbors_out(self, vertex):
195        """Get the list of outward neighbors of a vertex."""
196        return self._out_dict[vertex].keys()
197
198    def neighbors_in(self, vertex):
199        """Get the list of inward neighbors of a vertex."""
200        return self._in_dict[vertex].keys()
201
202    def edge_label(self, tail, head):
203        """Get the label of an edge from its tail and head vertex.
204
205        This function will raise an exception if there is not a unique
206        edge between `tail` and `head`.
207
208        """
209        if len(self._out_dict[tail][head]) == 1:
210            return self._out_dict[tail][head][0]
211        else:
212            raise ValueError("ambiguous edge specification: there is not exactly"
213                            f" one edge between {tail} and {head}" )
214
215    def edge_labels(self, tail, head):
216        """Get the list of labels associated to all the edges between `tail`
217        and `head`.
218
219        """
220        return self._out_dict[tail][head]
221
222    def add_vertices(self, vertices):
223        """Add vertices to the FSA.
224        """
225        for v in vertices:
226            if v not in self._out_dict:
227                self._out_dict[v] = defaultdict(list)
228                self._in_dict[v] = defaultdict(list)
229                self._graph_dict[v] = defaultdict(dict)
230
231    def add_edges(self, edges, elist=False,
232                  ignore_redundant=True):
233        """Add edges to the FSA.
234
235        Parameters
236        ----------
237        edges : list
238            a list of tuples of the form `(tail, head, label)`,
239            specifying an edge to add.
240
241        elist : bool
242            if `True`, then `label` should be interpreted as a single
243            edge label. Otherwise, `label` is interpreted as a list of
244            labels for multiple edges to be added between vertices.
245
246        """
247        for e in edges:
248            tail, head, label = e
249
250            # no-op if vertices are already in FSA
251            self.add_vertices([tail, head])
252
253            if head not in self._out_dict[tail]:
254                self._out_dict[tail][head] = []
255                self._in_dict[head][tail] = []
256
257            if ignore_redundant and label in self._out_dict[tail][head]:
258                continue
259
260            if elist:
261                self._out_dict[tail][head] += label
262                self._in_dict[head][tail] += label
263                for l in label:
264                    self._graph_dict[tail][l] = head
265
266            else:
267                self._out_dict[tail][head].append(label)
268                self._in_dict[head][tail].append(label)
269                self._graph_dict[tail][label] = head
270
271    def delete_vertices(self, vertices):
272        """Delete several vertices from the FSA.
273        """
274        for v in vertices:
275            self.delete_vertex(v)
276
277    def delete_vertex(self, vertex):
278        """Delete a single vertex from the FSA.
279        """
280        for w in self.neighbors_out(vertex):
281            self._in_dict[w].pop(vertex)
282        for w in self.neighbors_in(vertex):
283            self._out_dict[w].pop(vertex)
284
285            for lab in list(self._graph_dict[w]):
286                if self._graph_dict[w][lab] == vertex:
287                    self._graph_dict[w].pop(lab)
288
289        self._out_dict.pop(vertex)
290        self._in_dict.pop(vertex)
291        self._graph_dict.pop(vertex)
292
293    def vertices(self):
294        return self._out_dict.keys()
295
296    def edges(self, with_labels=False):
297        """Get all of the edges of this FSA
298
299        Yields
300        ------
301        tuple
302            An ordered pair of the form `(tail, head)` for each edge
303            in the automaton
304
305        """
306        for v, nbrs in self._graph_dict.items():
307            for label, w in nbrs.items():
308                if with_labels:
309                    yield (v, w, label)
310                else:
311                    yield (v, w)
312
313    def recurrent(self, inplace=False):
314        """Find a version of the automaton which is recurrent, i.e. which has
315        no (forward or backward) dead ends.
316
317        Parameters
318        ----------
319        inplace : bool
320            if `True`, modify the automaton in-place. Otherwise,
321            return a recurrent copy.
322
323        Returns
324        -------
325        FSA or None
326            A recurrent version of the automaton if `inplace` is
327            `True`, otherwise `None`.
328
329        """
330
331        to_modify = self
332
333        if not inplace:
334            to_modify = copy.deepcopy(self)
335
336        still_pruning = True
337        while still_pruning:
338            still_pruning = False
339            vertices = list(to_modify._out_dict.keys())
340            for v in vertices:
341                if (len(to_modify._out_dict[v]) == 0 or
342                    len(to_modify._in_dict[v]) == 0):
343                    to_modify.delete_vertex(v)
344                    still_pruning = True
345
346        if not inplace:
347            return to_modify
348
349    def remove_long_paths(self, root=None, edge_ties=True,
350                          return_distances=False):
351        """Find a version of the automaton which does not backtrack.
352
353        This function is the opposite of `make_recurrent`: it finds a
354        subgraph of the automaton which is the union of
355        shortest-length paths from the root vertex to each node. This
356        will be a directed acyclic graph (in fact, a tree if
357        `edge_ties` is false).
358
359        It is mostly useful for visualizing the structure of the
360        automaton.
361
362        Parameters
363        ----------
364        edge_ties : bool
365            if `True`, if two edges give rise to paths of the
366            same length, include both of them in the new graph.
367
368    """
369        H = FSA({})
370        H.add_vertices(self.vertices())
371
372        #Dijkstra's algorithm!
373        distance = {}
374        marked = {v:False for v in self.vertices()}
375
376        if root is None:
377            root = self.start_vertices[0]
378
379        marked[root] = True
380        distance[root] = 0
381        vertex_queue = deque([root])
382        while len(vertex_queue) > 0:
383            v = vertex_queue.popleft()
384
385            to_visit = [w for w in self.neighbors_out(v) if not marked[w]]
386            for w in to_visit:
387                marked[w] = True
388                distance[w] = distance[v] + 1
389
390            short_nbrs = to_visit
391            if edge_ties:
392                short_nbrs = [w for w in self.neighbors_out(v)
393                               if distance[w] == distance[v] + 1]
394
395            H.add_edges([(v, w, self.edge_labels(v,w)) for w in short_nbrs],
396                        elist= True)
397            vertex_queue.extend(to_visit)
398
399        return H
400
401    def initial_accepted_subword(self, word):
402        """Find an initial subword of a given word which is accepted by the
403        automaton.
404
405        Parameters
406        ----------
407        word : string
408            The word the automaton should try to accept
409
410        Returns
411        -------
412        string
413            An initial subword of `word` which is accepted by the
414            automaton, with maximal length. This may be either the
415            empty word or `word` itself.
416
417    """
418        vertex = self.start_vertices[0]
419        subword = ""
420        for letter in word:
421            try:
422                vertex = self.graph_dict[vertex][letter]
423            except KeyError:
424                return subword
425            subword += letter
426
427        return subword
428
429    def initial_rejected_subword(self, word):
430        """Find an initial subword of a given word which is accepted by the
431        automaton, or None if the given word is accepted.
432
433        Parameters
434        ----------
435        word : string
436            The word the automaton should try to accept.
437
438        Returns
439        -------
440        string
441            An initial subword of `word` which is rejected by the
442            automaton, with minimal length. If the word is accepted,
443            return None.
444
445        """
446        vertex = self.start_vertices[0]
447        subword = ""
448        for letter in word:
449            try:
450                vertex = self.graph_dict[vertex][letter]
451            except KeyError:
452                return subword + letter
453            subword += letter
454
455        return subword
456
457
458    def follow_word(self, word, start_vertex=None):
459        """Find the final state of the automaton when it tries to accept a word
460
461        Parameters
462        ----------
463        word : string
464            The word the automaton should try to accept
465
466        start_vertex: object
467            The start state for the automaton. If `None` (the
468            default), use the automaton's default start state.
469
470        Returns
471        -------
472        object
473            The state of the automaton when it accepts `word`
474
475        Raises
476        ------
477        FSAException
478            Raised if word is not accepted by this automaton.
479
480        """
481
482        if start_vertex is None:
483            start_vertex = self.start_vertices[0]
484        vertex = start_vertex
485
486        for letter in word:
487            try:
488                vertex = self.graph_dict[vertex][letter]
489            except KeyError:
490                raise FSAException(
491                    f"The word '{word}' is not accepted by the automaton."
492                )
493
494        return vertex
495
496    def enumerate_fixed_length_paths(self, length, start_vertex=None,
497                                     with_states=False):
498        """Enumerate all words of a fixed length accepted by the automaton,
499        starting at a given state.
500
501        Parameters
502        ----------
503        length : int
504            the length of the words we want to enumerate
505
506        start_vertex : object
507            which vertex to start at. If `None`, use the
508            default starting state for the automaton.
509
510        with_states : bool
511            if `True`, also yield the state of the
512            automaton at each accepted word.
513
514        Yields
515        ------
516        string or (string, object)
517            If `with_states` is false, yield the sequence of words
518            accepted (in some arbitrary order). Otherwise, yield pairs
519            of the form `(word, end_state)`, where `end_state` is the
520            final state the automaton reaches when accepting `word`.
521        """
522        if start_vertex is None:
523            start_vertex = self.start_vertices[0]
524
525        if length <= 0:
526            if with_states:
527                yield ("", start_vertex)
528            else:
529                yield ""
530        else:
531            for word, vertex in self.enumerate_fixed_length_paths(
532                    length - 1, start_vertex=start_vertex, with_states=True):
533                for label, neighbor in self._graph_dict[vertex].items():
534                    if with_states:
535                        yield (word + label, neighbor)
536                    else:
537                        yield word + label
538
539    def enumerate_words(self, max_length, start_vertex=None,
540                        with_states=False):
541        """Enumerate all words up to a given length accepted by the automaton.
542
543        Parameters
544        ----------
545        max_length : int
546            maximum length of a word to enumerate
547        start_vertex : object
548            the start vertex for accepting words. If `None`, use the
549            automaton's start vertex
550        with_states : bool
551            if `True`, also yield the state of the automaton at each
552            accepted word
553
554        Yields
555        ------
556        string or (string, object)
557            If `with_states` is false, yield the sequence of words
558            accepted (in some arbitrary order). Otherwise, yield pairs
559            of the form `(word, end_state)`, where `end_state` is the
560            final state the automaton reaches when accepting `word`.
561        """
562
563        for i in range(max_length + 1):
564            for word in self.enumerate_fixed_length_paths(
565                    i, start_vertex=start_vertex, with_states=with_states):
566                yield word
567
568    def rename_generators(self, rename_map, inplace=True):
569        """Get a new automaton whose edge labels have been renamed by a
570        specified map.
571
572        Parameters
573        ----------
574        rename_map : dict
575            dictionary giving the mapping from old labels to new
576            labels. Must provide a mapping for every label appearing
577            in the original automaton.
578
579        inplace : bool
580            If True (the default), modify the current automaton
581            in-place. If False, construct and return a new automaton
582            and leave this one unchanged.
583
584        Returns
585        -------
586        FSA or None
587            If inplace is False, return a new automaton with renamed
588            edge labels. Otherwise, None.
589
590    """
591        new_dict = {
592            vertex: {
593                rename_map[label]: neighbor
594                for label, neighbor in neighbors.items()
595            }
596            for vertex, neighbors in self._graph_dict.items()
597        }
598        if inplace:
599            self._from_graph_dict(new_dict)
600        else:
601            return FSA(new_dict, self.start_vertices)
602
603    def automaton_multiple(self, multiple):
604        """Get a new automaton, which accepts words in the language of this
605        automaton whose length is a multiple of k for some fixed k.
606
607        Parameters
608        ----------
609        multiple : int
610            Integer k such that every word accepted by the new
611            automaton has length kn for some n.
612
613        Returns
614        -------
615        FSA
616            A finite-state automaton which accepts exactly the words
617            accepted by self whose length is a multiple of k.
618
619        """
620        to_visit = deque(self.start_vertices)
621        visited = {
622            v : False for v in self.vertices()
623        }
624        new_automaton = FSA(start_vertices=self.start_vertices)
625        while(len(to_visit) > 0):
626            v = to_visit.popleft()
627            visited[v] = True
628            new_automaton.add_vertices([v])
629
630            for word, neighbor in self.enumerate_fixed_length_paths(
631                multiple,
632                start_vertex=v,
633                with_states=True
634            ):
635                new_automaton.add_vertices([neighbor])
636                new_automaton.add_edges([(v, neighbor, word)],
637                                        elist=False)
638
639                if not visited[neighbor]:
640                    to_visit.append(neighbor)
641
642        return new_automaton
643
644    def even_automaton(self):
645        """Get a new automaton which accepts exactly the the words accepted by
646        this automaton which have even length.
647
648        Alias for automaton_multiple(2).
649
650        Returns
651        -------
652        FSA
653            A finite-state automaton which accepts exactly the words
654            accepted by self whose length is even.
655
656        """
657        return self.automaton_multiple(2)
658
659    def accepts(self, word, start_vertex=None):
660        """Determine if this automaton accepts a given word.
661
662        Parameters
663        ----------
664        word : string
665            word to test for acceptance
666        start_vertex : object
667            The start state for the automaton. If `None` (the
668            default), any start state is allowed.
669
670        Returns
671        -------
672        bool
673            True if word is accepted by the automaton, False
674            otherwise.
675
676        """
677        start_vertices = [start_vertex]
678        if start_vertex is None:
679            start_vertices = self.start_vertices
680
681        for vertex in start_vertices:
682            try:
683                self.follow_word(word, vertex)
684                return True
685            except FSAException:
686                pass
687
688        return False
689
690
691
692def load_kbmag_file(filename) -> FSA:
693
694    """Build a finite-state automaton from a GAP record file produced by
695    the kbmag program.
696
697    Parameters
698    ----------
699    filename : string
700        the GAP record file containing automaton data.
701
702    Returns
703    -------
704    FSA
705        The automaton described by the
706        file.
707
708    """
709    gap_record = gap_parse.load_record_file(filename)
710    return _from_gap_record(gap_record)
711
712
713def _from_gap_record(gap_record) -> FSA:
714    """Load an automaton from a GAP record
715
716    Parameters
717    ----------
718    gap_record : dict
719        Preparsed GAP record to load
720
721    Returns
722    -------
723    FSA
724        finite-state automaton represented by this record
725
726    """
727
728    for fsa_dict in gap_record.values():
729        if fsa_dict["isFSA"] == "true":
730            labels = fsa_dict["alphabet"]["names"]
731            transitions = fsa_dict["table"]["transitions"]
732            initial = fsa_dict["initial"]
733
734            out_dict = kbmag_utils.build_dict(
735                transitions, labels, to_filter=[0]
736            )
737
738            return FSA(out_dict, start_vertices=initial)
739
740
741def load_builtin(filename):
742    """Load a finite-state automaton built in to the automata subpackage.
743
744    Parameters
745    ----------
746    filename : string
747        Name of the automaton file to load
748
749    Returns
750    -------
751    FSA
752        finite-state automaton read from this file
753
754    """
755    try:
756        builtin_path = importlib.resources.files(automata) / BUILTIN_DIR / filename
757        with open(builtin_path) as builtin_file:
758            aut_string = builtin_file.read()
759    except AttributeError as e:
760        # we still support python 3.8 since it's not EOL yet
761        from pkg_resources import resource_string as resource_bytes
762        aut_bytes = resource_bytes(
763            __name__, "{}/{}".format(BUILTIN_DIR, filename)
764        )
765        aut_string = aut_bytes.decode('utf-8')
766
767
768    record, _ = gap_parse.parse_record(aut_string)
769    return _from_gap_record(record)
770
771
772def list_builtins():
773    """Return a list of all the automata included with the automata
774    subpackage.
775
776    """
777    try:
778        builtin_dir = importlib.resources.files(automata) / BUILTIN_DIR
779        return [
780            os.path.basename(name)
781            for name in builtin_dir.iterdir()
782        ]
783    except AttributeError as e:
784        # we still support python 3.8 since it's not EOL
785        from pkg_resources import resource_listdir
786        return resource_listdir(__name__, BUILTIN_DIR)
787
788def free_automaton(generating_set):
789    """Return an automaton accepting freely reduced words in a set of
790    generators
791
792    Parameters
793    ----------
794    generating_set : iterable of strings
795        Names of the generators for this free group
796
797    Returns
798    -------
799    FSA
800        Automaton accepting freely reduced words in the generators
801        (and their inverses)
802
803    """
804    generators = list(generating_set) + [
805        words.invert_gen(g) for g in generating_set
806    ]
807    graph = {
808        g : {h:h for h in generators
809             if words.invert_gen(h) != g}
810        for g in [''] + generators
811    }
812    fsa = FSA(graph, start_vertices=[''])
813    return fsa
814
815def _hidden_vertices(graph_dict):
816    vertices = list(graph_dict)
817    hidden = []
818    for v, neighbors in graph_dict.items():
819        for _, neighbor in neighbors.items():
820            if (neighbor not in vertices and
821                neighbor not in hidden):
822                hidden.append(neighbor)
823
824    return hidden