-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtext.tex
182 lines (140 loc) · 6.77 KB
/
text.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
\documentclass{article}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{courier}
\usepackage{graphicx}
\usepackage{float}
\usepackage[hidelinks]{hyperref}
\definecolor{lightgray}{gray}{0.95}
\lstset{
basicstyle=\ttfamily,
backgroundcolor=\color{lightgray},
numbers=left,
tabsize=3,
frame=tblr,
keywordstyle=\color{blue},
morekeywords={graph, digraph, shape, node, label}
}
\title{Graphviz for State Diagrams}
\date{March 2021}
\author{Raha Moradi Shahmiri\\raham9619@gmail.com}
\begin{document}
\pagenumbering{gobble}
\maketitle
\newpage
\tableofcontents
\newpage
\pagenumbering{arabic}
\section{Introduction}
Graphviz is a popular opensource tool for visualizing graphs, as its name suggests. In this tutorial, we use it for drawing state diagrams. Thus, we shall be equiped with a powerful tool for designing and illustrating state machines. Graphviz is a package with many capabilities, from which we only use dot, which parses dot language and produces graph visualizations.
\newline
From the DOT description, many output formats may be generated. One way to generate PNG images, suitable for many usecases, is the following command:
\newline \newline
\textbf{\lstinline{dot -Tpng [input file name] -o [output file name]}}
\section{Basic Notation}
Graphviz uses DOT Language to describe graphs. A simple DOT description is shown in listing \ref{lst:dot1}.
\lstinputlisting[caption={Sample graph description},label={lst:dot1} ]{listing1.dot}
\begin{figure}[H]
\begin{center}
\includegraphics[width=25mm]{figure1.png}
\end{center}
\caption{dot output for listing \ref{lst:dot1}.}
\label{fig:png1}
\end{figure}
Lets investigate the above code.
\subparagraph{Graph declaration}
Graph must be declared. Its name comes in "double quotes." The keyword \lstinline{digraph} can also be used, indicating a digraph, eg. a directed graph.
\subparagraph{Edge declaration}
Undirected edges are declared using \lstinline{--} operator. For directed edges, \lstinline{->} is used. Mixing directed and undirected edges is not supported: Directed edges should only be used in digraphs, while undirected edges should only be used in graphs.
\subparagraph{Node declaration}
Nodes can be implicitly or explicitly declared. In this snippet, they are declared implicitly, through edge definitions.
\subsection{Edge Attributes}
In general, attributes for nodes, edges and graphs can be assigned using braces, \lstinline{[ ]}. Some common attributes for edges are demonstrated in listing \ref{lst:dot2}.
\lstinputlisting[caption={Demonstration of some edge attributes},label={lst:dot2} ]{listing2.dot}
\begin{figure}[H]
\begin{center}
\includegraphics[width=25mm]{figure2.png}
\end{center}
\caption{dot output for listing \ref{lst:dot2}.}
\label{fig:png2}
\end{figure}
Here, \lstinline{color} and \lstinline{label} attributes of edges have been illustrated.
\subsection{Node Attributes}
Nodes can also have attributes. In this specific application, we usually would like to choose their shapes, for aesthetic reasons as well as highlighting special nodes. In addition to defining node-specific attributes, it's possible to define global attributes for nodes, which hold true, unless overriden by their node-specific counterparts. The same holds true for edges.
\lstinputlisting[caption={Demonstrating of node shapes},label={lst:dot3} ]{listing3.dot}
\begin{figure}[H]
\begin{center}
\includegraphics[width=25mm]{figure3.png}
\end{center}
\caption{dot output for listing \ref{lst:dot3} }
\label{fig:png3}
\end{figure}
It can be seen that \lstinline{node} defines global attributes.
\subsection{Digraphs}
A digraph is declared using \lstinline{digraph} keyword in the beginning. The edges are shown using \lstinline{->}.
\lstinputlisting[caption={Digraph declaration},label={lst:digraph} ]{digraph.dot}
\begin{figure}[H]
\begin{center}
\includegraphics[width=25mm]{digraph.png}
\end{center}
\caption{dot output for listing \ref{lst:digraph} }
\label{fig:digraph}
\end{figure}
\subsection{Common Colors}
\subparagraph{TBA}
\subsection{Common Node Shapes}
\subparagraph{TBA}
\section{State Diagrams}
In order to illustrate a state diagram, we can show the state names as node labels, state transitions using edges, and use edge labels to show state transition conditions. In table \ref{tbl:state1} a sample state machine is shown. Its corresponding state diagram is shown in figure \ref{fig:state1}, and its DOT description in listing \ref{lst:state1}.
\begin{table}[H]
\begin{center}
\caption{Sample state machine.}
\label{tbl:state1}
\begin{tabular}{c|c|c|c}
\textbf{Input} & \textbf{Current State} & \textbf{Output} & \textbf{Next State}\\
\hline
0 & 00 & 0 & 00\\
1 & 00 & 0 & 01\\
0 & 01 & 0 & 01\\
1 & 01 & 0 & 11\\
0 & 10 & 0 & 10\\
1 & 10 & 0 & 00\\
0 & 11 & 1 & 11\\
1 & 11 & 1 & 00\\
\end{tabular}
\end{center}
\end{table}
\begin{figure}[H]
\begin{center}
\includegraphics[width=25mm]{state1.png}
\end{center}
\caption{Sample state diagram}
\label{fig:state1}
\end{figure}
\lstinputlisting[caption={Sample state machine DOT description},label={lst:state1} ]{state1.dot}
The notation used in this example is already familiar, but we can add a couple commands to make the diagram more visually beautiful. First, we can force the loop on node \lstinline{01} to be shown on the left side of the node:
\begin{figure}[H]
\begin{center}
\includegraphics[width=25mm]{state1.1.png}
\end{center}
\caption{Moved the loop}
\label{fig:state1.1}
\end{figure}
\lstinputlisting[caption={Moving the loop in DOT},label={lst:state1.1} ]{state1.1.dot}
The \lstinline{headport} and \lstinline{tailport} attributes are self explanatory. Not that \lstinline{nw} stands for 'north west' and \lstinline{sw} stands for 'south west.' It can be inferred that \lstinline{n}, \lstinline{ne}, \lstinline{e}, \lstinline{se}, \lstinline{s}, \lstinline{sw}, \lstinline{w}, \lstinline{nw} are possible values.
Next, we can force 01 and 11 to be shown in the same line:
\begin{figure}[H]
\begin{center}
\includegraphics[width=45mm]{state1.2.png}
\end{center}
\caption{forced 01 and 11 to be in the same line}
\label{fig:state1.2}
\end{figure}
\lstinputlisting[caption={DOT description for figure \ref{fig:state1.2} },label={lst:state1.2} ]{state1.2.dot}
\lstinline{rank=same} forces the nodes mentioned to be of the same rank, eg. vertical position. Note that \lstinline{dpi} attribute has been used only to improved image quality.
\section{References}
The reference used here is the Graphviz official documentation, available at\newline
\url{https://graphviz.org/documentation} \newline
In particular, the list of attributes would come in handy:\newline
\url{https://graphviz.org/doc/info/attrs.html}
\end{document}