Quelle  drawing.xml   Sprache: unbekannt

<?xml version="1.0" encoding="UTF-8"?>
  <Appendix>
    <Heading>
      Drawing automata
    </Heading>
    The drawing of graphs described here uses
    <C>graphviz</C> <Cite Key="KoutsofiosNorth:2002"/>, a software for drawing graphs developed at AT
    <Alt Only="LaTeX">
      \&#38;
    </Alt>
    <Alt Not="LaTeX">
      <Alt Only="HTML">
        &#38;amp;
      </Alt>
      <Alt Not="HTML">
        &#38;
      </Alt>
    </Alt>
    T Labs, that can be obtained at
    <URL>https://www.graphviz.org/</URL>.

    
    <Section>
      <Heading>
        Installing some external programs
      </Heading>
      In order to create the drawings you should have <URL Text="graphviz">https://www.graphviz.org/</URL>
      installed and to view them you should have installed some <C>pdf</C> viewer.
    </Section>
    
    <Section>
      <Heading>
        Functions to draw automata
      </Heading>
      
      <ManSection>
        <Func Arg="A [state_names, L]" Name="DrawAutomaton" />
        <Description>
          This function draws automaton
          <A>A</A>.
   The arguments <A>state_names</A>, <A>L</A> and <A>file</A> are optional.

   <P />
   An automaton with <C>n</C> states will be drawn with numbers <C>1</C> to <C>n</C>
   written inside the corresponding graph node.
   The argument <A>state_names</A> is a list of <C>n</C> strings which will be the new text
   written inside the corresponding graph node.

   <P />
   The argument <A>L</A> is a list of lists of integers, each of which specifies a set
   of states to be drawn in a different color.

</Description>
      </ManSection>
<Example><![CDATA[
gap> x:=Automaton("det",3,2,[ [ 2, 3, 0 ], [ 0, 1, 2 ] ],[ 1 ],[ 1, 2, 3 ]);;
gap> DrawAutomaton(x);

gap> DrawAutomaton(x,["st 1", "2", "C"]);

gap> DrawAutomaton(x,["st 1", "2", "C"],[[2],[1,3]]);
]]></Example>
The output of the three previous <C>DrawAutomaton</C> commands would be the following diagrams,
respectively.
<P />
    <Alt Only="LaTeX">
      \begin{figure}[htbp] \begin{center} \leavevmode \includegraphics[bb=0 0 74 250]{aut2.jpg} \end{center} \label{fig:aut2} \end{figure}
    </Alt>
    <Alt Only="HTML">
      &#60;br&#62;&#60;center&#62;&#60;img src=&#pan style='color: green'>34;aut2.jpg&#34;&#62;&#60;/center&#62;&#n style='color: green'>60;br&#62;
    </Alt>
    <P />
    <Alt Only="LaTeX">
      \begin{figure}[htbp] \begin{center} \leavevmode \includegraphics[bb=0 0 100 250]{aut2_1.jpg} \end{center} \label{fig:aut2_1} \end{figure}
    </Alt>
    <Alt Only="HTML">
      &#60;br&#62;&#60;center&#62;&#60;img src=&#pan style='color: green'>34;aut2_1.jpg&#34;&#62;&#60;/center&#62;&#pan style='color: green'>60;br&#62;
    </Alt>
    <P />
    <Alt Only="LaTeX">
      \begin{figure}[htbp] \begin{center} \leavevmode \includegraphics[bb=0 0 100 250]{aut2_2.jpg} \end{center} \label{fig:aut2_2} \end{figure}
    </Alt>
    <Alt Only="HTML">
      &#60;br&#62;&#60;center&#62;&#60;img src=&#pan style='color: green'>34;aut2_2.jpg&#34;&#62;&#60;/center&#62;&#pan style='color: green'>60;br&#62;
    </Alt>

    <ManSection>
        <Func Arg="arg" Name="DotForDrawingAutomaton" />
        <Description>
   This function computes the dot code that can be used to display an automaton. This can be done by using the function <Ref Func="DrawAutomaton" /> (if the system is properly configured) or by the user in some independent way. The arguments and options are the same than those of  <Ref Func="DrawAutomaton" />.
        </Description>
      </ManSection>
      <Example><![CDATA[
gap> DotStringForDrawingAutomaton(x);
"digraph  Automaton{\n\"1\" -> \"2\" [label=\"a\",color=red];\n\"2\" -> \"3\" \
[label=\"a\",color=red];\n\"2\" -> \"1\" [label=\"b\",color=blue];\n\"3\" -> \
\"2\" [label=\"b\",color=blue];\n\"1\" [shape=triangle,peripheries=2, style=fi\
lled, fillcolor=white];\n\"2\" [shape=doublecircle, style=filled, fillcolor=wh\
ite];\n\"3\" [shape=doublecircle, style=filled, fillcolor=white];\n}\n"
      ]]></Example>
      By using Print (or PrinTo, if one wants to print to a file) the string is displayed as follows:
      <Example><![CDATA[
gap> Print(last);
digraph  Automaton{
"1" -> "2" [label="a",color=red];
"2" -> "3" [label="a",color=red];
"2" -> "1" [label="b",color=blue];
"3" -> "2" [label="b",color=blue];
"1" [shape=triangle,peripheries=2, style=filled, fillcolor=white];
"2" [shape=doublecircle, style=filled, fillcolor=white];
"3" [shape=doublecircle, style=filled, fillcolor=white];
}
]]></Example>
      The dot code produced for the remaining pictures:
      <Example><![CDATA[
gap> Print(DotStringForDrawingAutomaton(x,["st 1", "2", "C"]));
digraph  Automaton{
"st 1" -> "2" [label="a",color=red];
"2" -> "C" [label="a",color=red];
"2" -> "st 1" [label="b",color=blue];
"C" -> "2" [label="b",color=blue];
"st 1" [shape=triangle,peripheries=2, style=filled, fillcolor=white];
"2" [shape=doublecircle, style=filled, fillcolor=white];
"C" [shape=doublecircle, style=filled, fillcolor=white];
}
gap> Print(DotStringForDrawingAutomaton(x,["st 1", "2", "C"],[[2],[1,3]]));
digraph  Automaton{
"st 1" -> "2" [label="a",color=red];
"2" -> "C" [label="a",color=red];
"2" -> "st 1" [label="b",color=blue];
"C" -> "2" [label="b",color=blue];
"st 1" [shape=triangle,peripheries=2, style=filled, fillcolor=burlywood];
"2" [shape=doublecircle, style=filled, fillcolor=brown];
"C" [shape=doublecircle, style=filled, fillcolor=burlywood];
}
]]></Example>
      <ManSection>
        <Func Arg="A, B" Name="DrawSubAutomaton" />
        <Description>
          This function tests if automaton
          <C>
            A
          </C>
          is a subautomaton of
          <C>
            B
          </C>
          in which case draws
          <C>
            B
          </C>
          highlighting the edges not in
          <C>
            A
          </C>
          by drawing them in a dotted style, while the others are drawn in a plain style.
        </Description>
      </ManSection>
 <Example><![CDATA[
gap> A := Automaton("nondet",5,"abc",[ [ [ 2, 3 ], [ 5 ], [ 1, 4, 5 ], [ 1, 5 ],
[ 3, 4 ] ], [ [ 1, 4, 5 ], [ ], [ 1 ], [ 1, 3, 5 ], [ 1, 2, 5 ] ], [ [ ],
[ 2, 4, 5 ], [ 1, 3, 5 ], [ ], [ 2, 3, 4 ] ] ],[ ],[ 2, 3, 4 ]);;
gap> B := Automaton("nondet",5,"abc",[ [ [ 2, 3 ], [ 5 ], [ 1, 4, 5 ], [ 1, 5 ],
[ 3, 4 ] ], [ [ 1, 4, 5 ], [ ], [ 1 ], [ 1, 3, 5 ], [ 1, 2, 5 ] ], [ [ 1, 4, 5 ],
[ 2, 4, 5 ], [ 1, 3, 5 ], [ 2, 3, 4, 5 ], [ 2, 3, 4 ] ] ],[ 3, 4, 5 ],[ 2, 3, 4 ]);;
gap> DrawSubAutomaton(A,B);
]]></Example>
The output is as follows, in case the configuration of your computer permits. Otherwise, you may be interested in the dot code, as pshown below.
<P />
<Alt Only="LaTeX">
          \begin{center}
        \includegraphics[width=0.5\textwidth]{subaut.jpg}
        \end{center}
    </Alt>
    <Alt Only="HTML">
      &#60;br&#62;&#60;center&#62;&#60;img src=&#pan style='color: green'>34;subaut.jpg&#34;&#62;&#60;/center&#62;&#pan style='color: green'>60;br&#62;
    </Alt>
    <P />
           <ManSection>
        <Func Arg="A, B" Name="DotStringForDrawingSubAutomaton" />
        <Description>
   This function computes the dot code that can be used to draw automata A, with the subsutomaton B emphasized. It is silently used by the function <Ref Func="DrawSubAutomaton" /> (if the system is properly configured) or can be used by the user in some independent way.
        </Description>
      </ManSection>
      <Example><![CDATA[
gap> DotStringForDrawingSubAutomaton(A,B);
"digraph  Automaton {\n1 -> 2 [label=\"a\",color=red];\n1 -> 3 [label=\"a\",co\
lor=red];\n1 -> 1 [label=\"b\",color=blue];\n1 -> 4 [label=\"b\",color=blue];\
\n1 -> 5 [label=\"b\",color=blue];\n1 -> 1 [label=\"c\",color=green,style = do\
tted];\n1 -> 4 [label=\"c\",color=green,style = dotted];\n1 -> 5 [label=\"c\",\
color=green,style = dotted];\n2 -> 5 [label=\"a\",color=red];\n2 -> 2 [label=\
\"c\",color=green];\n2 -> 4 [label=\"c\",color=green];\n2 -> 5 [label=\"c\",co\
lor=green];\n3 -> 1 [label=\"a\",color=red];\n3 -> 4 [label=\"a\",color=red];\
\n3 -> 5 [label=\"a\",color=red];\n3 -> 1 [label=\"b\",color=blue];\n3 -> 1 [l\
abel=\"c\",color=green];\n3 -> 3 [label=\"c\",color=green];\n3 -> 5 [label=\"c\
\",color=green];\n4 -> 1 [label=\"a\",color=red];\n4 -> 5 [label=\"a\",color=r\
ed];\n4 -> 1 [label=\"b\",color=blue];\n4 -> 3 [label=\"b\",color=blue];\n4 ->\
 5 [label=\"b\",color=blue];\n4 -> 2 [label=\"c\",color=green,style = dotted];\
\n4 -> 3 [label=\"c\",color=green,style = dotted];\n4 -> 4 [label=\"c\",color=\
green,style = dotted];\n4 -> 5 [label=\"c\",color=green,style = dotted];\n5 ->\
 3 [label=\"a\",color=red];\n5 -> 4 [label=\"a\",color=red];\n5 -> 1 [label=\"\
b\",color=blue];\n5 -> 2 [label=\"b\",color=blue];\n5 -> 5 [label=\"b\",color=\
blue];\n5 -> 2 [label=\"c\",color=green];\n5 -> 3 [label=\"c\",color=green];\n\
5 -> 4 [label=\"c\",color=green];\n3 [shape=triangle,color=gray];\n4 [shape=tr\
iangle,color=gray];\n5 [shape=triangle,color=gray];\n2 [shape=doublecircle];\n\
3 [shape=doublecircle];\n4 [shape=doublecircle];\n1 [shape=circle];\n}\n"
      ]]></Example>
      By using Print (or PrinTo, if one wants to print to a file) the string is displayed as follows:
      <Example><![CDATA[
gap> Print(last);
digraph  Automaton {
1 -> 2 [label="a",color=red];
1 -> 3 [label="a",color=red];
1 -> 1 [label="b",color=blue];
1 -> 4 [label="b",color=blue];
1 -> 5 [label="b",color=blue];
1 -> 1 [label="c",color=green,style = dotted];
1 -> 4 [label="c",color=green,style = dotted];
1 -> 5 [label="c",color=green,style = dotted];
2 -> 5 [label="a",color=red];
2 -> 2 [label="c",color=green];
2 -> 4 [label="c",color=green];
2 -> 5 [label="c",color=green];
3 -> 1 [label="a",color=red];
3 -> 4 [label="a",color=red];
3 -> 5 [label="a",color=red];
3 -> 1 [label="b",color=blue];
3 -> 1 [label="c",color=green];
3 -> 3 [label="c",color=green];
3 -> 5 [label="c",color=green];
4 -> 1 [label="a",color=red];
4 -> 5 [label="a",color=red];
4 -> 1 [label="b",color=blue];
4 -> 3 [label="b",color=blue];
4 -> 5 [label="b",color=blue];
4 -> 2 [label="c",color=green,style = dotted];
4 -> 3 [label="c",color=green,style = dotted];
4 -> 4 [label="c",color=green,style = dotted];
4 -> 5 [label="c",color=green,style = dotted];
5 -> 3 [label="a",color=red];
5 -> 4 [label="a",color=red];
5 -> 1 [label="b",color=blue];
5 -> 2 [label="b",color=blue];
5 -> 5 [label="b",color=blue];
5 -> 2 [label="c",color=green];
5 -> 3 [label="c",color=green];
5 -> 4 [label="c",color=green];
3 [shape=triangle,color=gray];
4 [shape=triangle,color=gray];
5 [shape=triangle,color=gray];
2 [shape=doublecircle];
3 [shape=doublecircle];
4 [shape=doublecircle];
1 [shape=circle];
}
]]></Example>
      <ManSection>
        <Func Arg="G" Name="DotStringForDrawingGraph" />
        <Func Arg="G" Name="DrawGraph" />
        <Description>
          Draws a graph specified as an adjacency list
          <C>G</C>.
        </Description>
      </ManSection>
      <Example><![CDATA[ 
gap> G := [[1,2,3],[5],[3,4],[1],[2,5]];
[ [ 1, 2, 3 ], [ 5 ], [ 3, 4 ], [ 1 ], [ 2, 5 ] ]
gap> Print(DotStringForDrawingGraph(G));
digraph Graph__{
1 -> 1 [style=bold, color=black];
1 -> 2 [style=bold, color=black];
1 -> 3 [style=bold, color=black];
2 -> 5 [style=bold, color=black];
3 -> 3 [style=bold, color=black];
3 -> 4 [style=bold, color=black];
4 -> 1 [style=bold, color=black];
5 -> 2 [style=bold, color=black];
5 -> 5 [style=bold, color=black];
1 [shape=circle];
2 [shape=circle];
3 [shape=circle];
4 [shape=circle];
5 [shape=circle];
}
]]></Example>
      The dot code can be used to produce the following picture (which may also be produced by typing <Code>DrawGraph(G);</Code>
      <Alt Only="LaTeX">
        \begin{center}
        \includegraphics[width=0.45\textwidth]{graph2.pdf}
        \end{center}
      </Alt>

    <Alt Only="HTML">
      &#60;br&#62;&#60;center&#62;&#60;img src=&#pan style='color: green'>34;graph2.jpg&#34;&#62;&#60;/center&#62;&#pan style='color: green'>60;br&#62;
    </Alt>
<ManSection>
        <Func Arg="A [state_names, L]" Name="DrawSCCAutomaton" />
        <Description>
          Draws automaton
          <C>
            A
          </C>
          and highlights it&#39;s strongly connected components by drawing the other edges in a dotted style.
   <P />
   The optional arguments <A>state_names</A> and <A>L</A> are as described in
   <Ref Func="DrawAutomaton" />.
        </Description>
</ManSection>
      <Example><![CDATA[
gap> rcg := Automaton("det",6,"ab",[ [ 3, 3, 6, 5, 6, 6 ], [ 4, 6, 2, 6, 4, 6 ] ],
[ ],[ ]);;
gap> Print(DotStringForDrawingSCCAutomaton(rcg));
digraph  Automaton{
"1" -> "3" [label="a",color=red,style = dotted];
"2" -> "3" [label="a",color=red];
"3" -> "6" [label="a",color=red,style = dotted];
"4" -> "5" [label="a",color=red];
"5" -> "6" [label="a",color=red,style = dotted];
"6" -> "6" [label="a",color=red,style = dotted];
"1" -> "4" [label="b",color=blue,style = dotted];
"2" -> "6" [label="b",color=blue,style = dotted];
"3" -> "2" [label="b",color=blue];
"4" -> "6" [label="b",color=blue,style = dotted];
"5" -> "4" [label="b",color=blue];
"6" -> "6" [label="b",color=blue,style = dotted];
"1" [shape=circle, style=filled, fillcolor=white];
"2" [shape=circle, style=filled, fillcolor=white];
"3" [shape=circle, style=filled, fillcolor=white];
"4" [shape=circle, style=filled, fillcolor=white];
"5" [shape=circle, style=filled, fillcolor=white];
"6" [shape=circle, style=filled, fillcolor=white];
}
]]></Example>
      The dot code can be used to produce the following picture (which may also be produced by typing <Code>DrawGraph(G);</Code>
      <Alt Only="LaTeX">
        \begin{center}
        \includegraphics[width=0.45\textwidth]{sccpoi2.pdf}
        \end{center}
      </Alt>

    <Alt Only="HTML">
      &#60;br&#62;&#60;center&#62;&#60;img src=&#pan style='color: green'>34;sccpoi2.jpg&#34;&#62;&#60;/center&#62;&#<span style='color: green'>60;br&#62;
    </Alt>

    </Section>

  </Appendix>