26456475151

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

Build # 26456475151

Build Type

Pull #288

github

Committed by

web-flow

Commit Message

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

caleb531 / automata / 26456475151

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