26457543706

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

Build # 26457543706

Build Type

Pull #288

github

Committed by

web-flow

Commit Message

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

caleb531 / automata / 26457543706

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