26457671740

Committed 26 May 2026 03:22PM UTC coverage: 98.285% (-0.04%) from 98.323%

Build # 26457671740

Build Type

Pull #288

github

Committed by

web-flow

Commit Message

Merge f0e17295f into 04dc19473

Pull Request Pull Request #288: Feat: show_diagram support for Turing Machines

Coverage Stats

3393 of 3504 branches covered (96.83%)

49 of 51 new or added lines in 3 files covered. (96.08%)

3038 of 3091 relevant lines covered (98.29%)

4.9 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.92

/automata/tm/tm.py

"""Classes and methods for working with all Turing machines."""

from __future__ import annotations

import abc
import os
from collections import defaultdict
from typing import AbstractSet, Callable, Generator, Literal, Tuple, Union

import automata.base.exceptions as exceptions
from automata.base.automaton import Automaton, AutomatonStateT
from automata.base.utils import (
    LayoutMethod,
    _missing_visual_imports,
    create_graph,
    create_unique_random_id,
    save_graph,
)

# Optional imports for use with visual functionality
if not _missing_visual_imports:
    import pygraphviz as pgv

TMStateT = AutomatonStateT
TMDirectionT = Literal["L", "R", "N"]


class TM(Automaton, metaclass=abc.ABCMeta):
    """An abstract base class for Turing machines."""

    __slots__ = tuple()

    tape_symbols: AbstractSet[str]
    blank_symbol: str

    @staticmethod
    def _get_edge_name(
        input_symbol: str = "", write_symbol: str = "", move_direction: str = ""
    ) -> str:
        input_symbol = "␣" if input_symbol.isspace() else str(input_symbol)
        write_symbol = "␣" if write_symbol.isspace() else str(write_symbol)

        return f"{input_symbol}→{write_symbol},{move_direction}"

    def _read_input_symbol_subset(self) -> None:
        if not (self.input_symbols < self.tape_symbols):
            raise exceptions.MissingSymbolError(
                "The set of tape symbols is missing symbols from the input "
                "symbol set ({})".format(self.tape_symbols - self.input_symbols)
            )

    def _validate_blank_symbol(self) -> None:
        """Raise an error if blank symbol is not a tape symbol."""
        if self.blank_symbol not in self.tape_symbols:
            raise exceptions.InvalidSymbolError(
                "blank symbol {} is not a tape symbol".format(self.blank_symbol)
            )

    def _validate_nonfinal_initial_state(self) -> None:
        """Raise an error if the initial state is a final state."""
        if self.initial_state in self.final_states:
            raise exceptions.InitialStateError(
                "initial state {} cannot be a final state".format(self.initial_state)
            )

    @abc.abstractmethod
    def iter_transitions(
        self,
    ) -> Generator[Tuple[TMStateT, TMStateT, str, str, TMDirectionT], None, None]:
        """
        Iterate over all transitions in the DTM. Each transition is a tuple
        of the form (from_state, to_state, input_symbol, write_symbol, move_direction).
        """

        raise NotImplementedError(
            f"iter_transitions is not implemented for {self.__class__}"
        )

    def show_diagram(
        self,
        path: Union[str, os.PathLike, None] = None,
        *,
        layout_method: LayoutMethod = "dot",
        horizontal: bool = True,
        reverse_orientation: bool = False,
        fig_size: Union[Tuple[float, float], Tuple[float], None] = None,
        font_size: float = 14.0,
        arrow_size: float = 0.85,
        state_separation: float = 0.5,
        node_formatter: Union[Callable[[str], str], None] = None,
        edge_formatter: Union[Callable[[str, str, TMDirectionT], str], None] = None,
    ) -> pgv.AGraph:
        """
                Generates a diagram of the associated TM.

                Parameters
                ----------
                path : Union[str, os.PathLike, None], default: None
                    Path to output file. If None, the output will not be saved.
                horizontal : bool, default: True
                    Direction of node layout in the output graph.
                reverse_orientation : bool, default: False
                    Reverse direction of node layout in the output graph.
                fig_size : Union[Tuple[float, float], Tuple[float], None], default: None
                    Figure size.
                font_size : float, default: 14.0
                    Font size in the output graph.
                arrow_size : float, default: 0.85
                    Arrow size in the output graph.
                state_separation : float, default: 0.5
                    Distance between nodes in the output graph.
                node_formatter : Union[Callable[[str],str], None] , default: None
                    A function that takes a state as input and returns a string
                    representing the state in the diagram.
                edge_formatter : Union[Callable[[str,str,TMDirectionT],str], None
        ], default: None
                    A function that takes input_symbol, write_symbol, move_direction
                    as input and returns a string representing the edge in the diagram.

                Returns
                ------
                AGraph
                    A diagram of the given automaton.
        """

        if _missing_visual_imports:
            raise _missing_visual_imports

        if node_formatter is None:
            node_formatter = self._get_state_name

        if edge_formatter is None:
            edge_formatter = self._get_edge_name

        # Defining the graph.
        graph = create_graph(
            horizontal, reverse_orientation, fig_size, state_separation
        )

        font_size_str = str(font_size)
        arrow_size_str = str(arrow_size)

        # create unique id to avoid colliding with other states
        null_node = create_unique_random_id()

        graph.add_node(
            null_node,
            label="",
            tooltip=".",
            shape="point",
            fontsize=font_size_str,
        )
        initial_node = node_formatter(self.initial_state)
        graph.add_edge(
            null_node,
            initial_node,
            tooltip="->" + initial_node,
            arrowsize=arrow_size_str,
        )

        nonfinal_states = map(node_formatter, self.states - self.final_states)
        final_states = map(node_formatter, self.final_states)
        graph.add_nodes_from(nonfinal_states, shape="circle", fontsize=font_size_str)
        graph.add_nodes_from(final_states, shape="doublecircle", fontsize=font_size_str)

        edge_labels = defaultdict(list)
        for (
            from_state,
            to_state,
            input_symbol,
            write_symbol,
            move_direction,
        ) in self.iter_transitions():
            from_node = self._get_state_name(from_state)
            to_node = self._get_state_name(to_state)
            label = edge_formatter(
                input_symbol,
                write_symbol,
                move_direction,
            )
            # label = self._get_edge_name(input_symbol, write_symbol, move_direction)
            edge_labels[from_node, to_node].append(label)

        for (from_node, to_node), labels in edge_labels.items():
            graph.add_edge(
                from_node,
                to_node,
                label=",".join(sorted(labels)),
                arrowsize=arrow_size_str,
                fontsize=font_size_str,
            )

        # Set layout
        graph.layout(prog=layout_method)

        # Write diagram to file
        if path is not None:
            save_graph(graph, path)

        return graph

1	"""Classes and methods for working with all Turing machines."""	5✔
2
3	from __future__ import annotations	5✔
4
5	import abc	5✔
6	import os	5✔
7	from collections import defaultdict	5✔
8	from typing import AbstractSet, Callable, Generator, Literal, Tuple, Union	5✔
9
10	import automata.base.exceptions as exceptions	5✔
11	from automata.base.automaton import Automaton, AutomatonStateT	5✔
12	from automata.base.utils import (	5✔
13	LayoutMethod,
14	_missing_visual_imports,
15	create_graph,
16	create_unique_random_id,
17	save_graph,
18	)
19
20	# Optional imports for use with visual functionality
21	if not _missing_visual_imports:	5✔
22	import pygraphviz as pgv	5✔
23
24	TMStateT = AutomatonStateT	5!
25	TMDirectionT = Literal["L", "R", "N"]	5✔
26
27
28	class TM(Automaton, metaclass=abc.ABCMeta):	5✔
29	"""An abstract base class for Turing machines."""	5✔
30
31	__slots__ = tuple()	5✔
32
33	tape_symbols: AbstractSet[str]	5✔
34	blank_symbol: str	5✔
35
36	@staticmethod	5✔
37	def _get_edge_name(	5✔
38	input_symbol: str = "", write_symbol: str = "", move_direction: str = ""
39	) -> str:
40	input_symbol = "␣" if input_symbol.isspace() else str(input_symbol)	5✔
41	write_symbol = "␣" if write_symbol.isspace() else str(write_symbol)	5✔
42
43	return f"{input_symbol}→{write_symbol},{move_direction}"	5✔
44
45	def _read_input_symbol_subset(self) -> None:	5✔
46	if not (self.input_symbols < self.tape_symbols):	5✔
47	raise exceptions.MissingSymbolError(	5✔
48	"The set of tape symbols is missing symbols from the input "
49	"symbol set ({})".format(self.tape_symbols - self.input_symbols)
50	)
51
52	def _validate_blank_symbol(self) -> None:	5✔
53	"""Raise an error if blank symbol is not a tape symbol."""
54	if self.blank_symbol not in self.tape_symbols:	5✔
55	raise exceptions.InvalidSymbolError(	5✔
56	"blank symbol {} is not a tape symbol".format(self.blank_symbol)
57	)
58
59	def _validate_nonfinal_initial_state(self) -> None:	5✔
60	"""Raise an error if the initial state is a final state."""
61	if self.initial_state in self.final_states:	5✔
62	raise exceptions.InitialStateError(	5✔
63	"initial state {} cannot be a final state".format(self.initial_state)
64	)
65
66	@abc.abstractmethod	5✔
67	def iter_transitions(	5✔
68	self,
69	) -> Generator[Tuple[TMStateT, TMStateT, str, str, TMDirectionT], None, None]:
70	"""
71	Iterate over all transitions in the DTM. Each transition is a tuple
72	of the form (from_state, to_state, input_symbol, write_symbol, move_direction).
73	"""
74
NEW 75	raise NotImplementedError(	×
76	f"iter_transitions is not implemented for {self.__class__}"
77	)
78
79	def show_diagram(	5✔
80	self,
81	path: Union[str, os.PathLike, None] = None,
82	*,
83	layout_method: LayoutMethod = "dot",
84	horizontal: bool = True,
85	reverse_orientation: bool = False,
86	fig_size: Union[Tuple[float, float], Tuple[float], None] = None,
87	font_size: float = 14.0,
88	arrow_size: float = 0.85,
89	state_separation: float = 0.5,
90	node_formatter: Union[Callable[[str], str], None] = None,
91	edge_formatter: Union[Callable[[str, str, TMDirectionT], str], None] = None,
92	) -> pgv.AGraph:
93	"""
94	Generates a diagram of the associated TM.
95
96	Parameters
97	----------
98	path : Union[str, os.PathLike, None], default: None
99	Path to output file. If None, the output will not be saved.
100	horizontal : bool, default: True
101	Direction of node layout in the output graph.
102	reverse_orientation : bool, default: False
103	Reverse direction of node layout in the output graph.
104	fig_size : Union[Tuple[float, float], Tuple[float], None], default: None
105	Figure size.
106	font_size : float, default: 14.0
107	Font size in the output graph.
108	arrow_size : float, default: 0.85
109	Arrow size in the output graph.
110	state_separation : float, default: 0.5
111	Distance between nodes in the output graph.
112	node_formatter : Union[Callable[[str],str], None] , default: None
113	A function that takes a state as input and returns a string
114	representing the state in the diagram.
115	edge_formatter : Union[Callable[[str,str,TMDirectionT],str], None
116	], default: None
117	A function that takes input_symbol, write_symbol, move_direction
118	as input and returns a string representing the edge in the diagram.
119
120	Returns
121	------
122	AGraph
123	A diagram of the given automaton.
124	"""
125
126	if _missing_visual_imports:	5✔
NEW 127	raise _missing_visual_imports	×
128
129	if node_formatter is None:	5✔
130	node_formatter = self._get_state_name	5✔
131
132	if edge_formatter is None:	5!
133	edge_formatter = self._get_edge_name	5✔
134
135	# Defining the graph.
136	graph = create_graph(	5!
137	horizontal, reverse_orientation, fig_size, state_separation
138	)
139
140	font_size_str = str(font_size)	5✔
141	arrow_size_str = str(arrow_size)	5✔
142
143	# create unique id to avoid colliding with other states
144	null_node = create_unique_random_id()	5✔
145
146	graph.add_node(	5✔
147	null_node,
148	label="",
149	tooltip=".",
150	shape="point",
151	fontsize=font_size_str,
152	)
153	initial_node = node_formatter(self.initial_state)	5✔
154	graph.add_edge(	5✔
155	null_node,
156	initial_node,
157	tooltip="->" + initial_node,
158	arrowsize=arrow_size_str,
159	)
160
161	nonfinal_states = map(node_formatter, self.states - self.final_states)	5✔
162	final_states = map(node_formatter, self.final_states)	5✔
163	graph.add_nodes_from(nonfinal_states, shape="circle", fontsize=font_size_str)	5✔
164	graph.add_nodes_from(final_states, shape="doublecircle", fontsize=font_size_str)	5✔
165
166	edge_labels = defaultdict(list)	5✔
167	for (	5✔
168	from_state,
169	to_state,
170	input_symbol,
171	write_symbol,
172	move_direction,
173	) in self.iter_transitions():
174	from_node = self._get_state_name(from_state)	5✔
175	to_node = self._get_state_name(to_state)	5✔
176	label = edge_formatter(	5✔
177	input_symbol,
178	write_symbol,
179	move_direction,
180	)
181	# label = self._get_edge_name(input_symbol, write_symbol, move_direction)
182	edge_labels[from_node, to_node].append(label)	5✔
183
184	for (from_node, to_node), labels in edge_labels.items():	5✔
185	graph.add_edge(	5✔
186	from_node,
187	to_node,
188	label=",".join(sorted(labels)),
189	arrowsize=arrow_size_str,
190	fontsize=font_size_str,
191	)
192
193	# Set layout
194	graph.layout(prog=layout_method)	5✔
195
196	# Write diagram to file
197	if path is not None:	5✔
198	save_graph(graph, path)	5✔
199
200	return graph	5✔

caleb531 / automata / 26457671740

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous