1############################################################################# 2## 3#W drawgraph.gi GAP library Manuel Delgado <mdelgado@fc.up.pt> 4#W Jose Morais <josejoao@fc.up.pt> 5## 6## 7#Y Copyright (C) 2004, CMUP, Universidade do Porto, Portugal 8## 9## The functions in this file make use of the external program dot (from 10## the freely available software package graphviz, for graph visualization) 11## to display the graphs. 12############################################################################ 13 14#Siegen 15# ############################################################################ 16# ## 17# #F SetDrawingsExtraFormat(f) 18# ## 19# ## This function sets the value of DrawingsExtraFormat to <f>. 20# ## 21# InstallGlobalFunction(SetDrawingsExtraFormat, function(f) 22# if not f in DrawingsListOfExtraFormats then 23# Print("The specified format is not valid.\nThe valid formats are:\n", DrawingsListOfExtraFormats, ".\nPlease check http://www.graphviz.org/doc/info/output.html\nfor more info.\n"); 24# return; 25# fi; 26# MakeReadWriteGlobal("DrawingsExtraFormat"); 27# DrawingsExtraFormat := f; 28# MakeReadOnlyGlobal("DrawingsExtraFormat"); 29# end); 30 31 32# ############################################################################ 33# ## 34# #F SetDrawingsExtraGraphAttributes(L) 35# ## 36# ## This function sets the value of DrawingsExtraGraphAttributes to <L>. 37# ## For example if we wanted to define the graph size to be 7x9, we would call 38# ## SetDrawingsExtraGraphAttributes(["size=7,9"]); 39# ## 40# InstallGlobalFunction(SetDrawingsExtraGraphAttributes, function(L) 41# if not (IsList(L) and ForAll(L, l -> IsString(l))) then 42# Error("The argument must be a list of strings"); 43# fi; 44# MakeReadWriteGlobal("DrawingsExtraGraphAttributes"); 45# DrawingsExtraGraphAttributes := L; 46# MakeReadOnlyGlobal("DrawingsExtraGraphAttributes"); 47# end); 48 49# ############################################################################ 50# ## 51# #F ClearDrawingsExtraGraphAttributes() 52# ## 53# ## This function sets DrawingsExtraGraphAttributes to "none" 54# ## Thus indicating that the graph should be drawn with dot's default parameters. 55# ## 56# InstallGlobalFunction(ClearDrawingsExtraGraphAttributes, function() 57# MakeReadWriteGlobal("DrawingsExtraGraphAttributes"); 58# DrawingsExtraGraphAttributes := "none"; 59# MakeReadOnlyGlobal("DrawingsExtraGraphAttributes"); 60# end); 61 62 63 64 65#======================================================================== 66# This function parses the arguments for the functions DrawAutomaton and DrawSCCAutomaton. 67#------------------------------------------------------------------------ 68InstallGlobalFunction(AUX__parseDrawAutArgs, function(LA) 69 local A, fich, state_names, states_to_colorize, l, s; 70 71 A := LA[1]; # the automaton to draw 72 fich := "automaton"; # this is a string with the name of the .dot file 73 state_names := List([1..A!.states], s -> String(s)); # this is a list of strings with new state names 74 states_to_colorize := []; 75 76 # ------------------------------------------------------------------------------ 77 # ----- Treat the arguments ---------------------------------------------------- 78 # Check if there is a second argument 79 if IsBound(LA[2]) then 80 if IsString(LA[2]) then # this is a string with the name of the .dot file 81 fich := LA[2]; 82 elif IsList(LA[2]) and IsString(LA[2][1]) then # this is a list of strings with new state names 83 state_names := LA[2]; 84 if Length(state_names) <> A!.states then 85 Error("The list of new state names must have length equal to the number of states of the automaton"); 86 fi; 87 elif IsList(LA[2]) and IsList(LA[2][1]) and IsPosInt(LA[2][1][1]) then # this is a list of lists of state numbers to draw in colorize 88 states_to_colorize := LA[2]; 89 for l in states_to_colorize do 90 for s in l do 91 if s < 1 or s > A!.states then 92 Error("The states to colorize must be integers in [1 ..", A!.states, "]"); 93 fi; 94 od; 95 od; 96 else 97 Error("Wrong second argument, please check the manual"); 98 fi; 99 # Check if there is a third argument 100 if IsBound(LA[3]) then 101 if IsString(LA[3]) then # this is a string with the name of the .dot file 102 fich := LA[3]; 103 elif IsList(LA[3]) and IsString(LA[3][1]) then # this is a list of strings with new state names 104 state_names := LA[3]; 105 if Length(state_names) <> A!.states then 106 Error("The list of new state names must have length equal to the number of states of the automaton"); 107 fi; 108 elif IsList(LA[3]) and IsList(LA[3][1]) and IsPosInt(LA[3][1][1]) then # this is a list of lists of state numbers to draw in colorize 109 states_to_colorize := LA[3]; 110 for l in states_to_colorize do 111 for s in l do 112 if s < 1 or s > A!.states then 113 Error("The states to colorize must be integers in [1 ..", A!.states, "]"); 114 fi; 115 od; 116 od; 117 else 118 Error("Wrong third argument, please check the manual"); 119 fi; 120 # Check if there is a fourth argument 121 if IsBound(LA[4]) then 122 if IsString(LA[4]) then # this is a string with the name of the .dot file 123 fich := LA[4]; 124 elif IsList(LA[4]) and IsString(LA[4][1]) then # this is a list of strings with new state names 125 state_names := LA[4]; 126 if Length(state_names) <> A!.states then 127 Error("The list of new state names must have length equal to the number of states of the automaton"); 128 fi; 129 elif IsList(LA[4]) and IsList(LA[4][1]) and IsPosInt(LA[4][1][1]) then # this is a list of lists of state numbers to draw in colorize 130 states_to_colorize := LA[4]; 131 for l in states_to_colorize do 132 for s in l do 133 if s < 1 or s > A!.states then 134 Error("The states to colorize must be integers in [1 ..", A!.states, "]"); 135 fi; 136 od; 137 od; 138 else 139 Error("Wrong fourth argument, please check the manual"); 140 fi; 141 fi; 142 fi; 143 fi; 144 # ----- End of Treat the arguments -------------------------------------------- 145 # ------------------------------------------------------------------------------ 146 return [A, fich, state_names, states_to_colorize]; 147end); 148 149 150#======================================================================== 151########################################################################### 152## 153#F DotStringForDrawingAutomaton 154## 155## ouputs a string consisting of dot code for an automaton 156## 157#### the code is based on the code for the outdated function WriteDotFileForGraph 158## A is an automaton, map a list of states names and states_to_colorize 159 160 161 162#======================================================================== 163# This function writes the .dot file specifying a graph. 164# It is used by DrawAutomaton and DrawSCCAutomaton. 165# 166# The argument 'who_called' specifies which function requested the .dot file: 167# who_called = 1 ---> DrawAutomaton 168# who_called = 2 ---> DrawSCCAutomaton 169#------------------------------------------------------------------------ 170InstallGlobalFunction(WriteDotFileForGraph, function(A, fich, map, states_to_colorize, who_called) 171 local alph, letters, edge_colors, node_colors, T, str, out_str, scc, G, p, 172 q, a, color_of_node, k; 173 174 alph := AlphabetOfAutomaton(A); 175 176 # When the alphabet has more than 27 letters, they are given in the form 177 if IsList(AlphabetOfAutomatonAsList(A)[1]) then 178 letters := AlphabetOfAutomatonAsList(A); 179 else 180 letters := List(AlphabetOfAutomatonAsList(A), a -> [a]); 181 fi; 182 183 edge_colors := ["red", "blue", "green", "purple", "orange", "brown", "darksalmon", "darkseagreen", "darkturquoise", 184 "darkviolet", "deeppink", "deepskyblue", "dodgerblue", "firebrick", "forestgreen", "gold"]; 185 186 if alph > 16 then 187 edge_colors := List([1 .. alph], i -> edge_colors[(i mod 16) + 1]);#to reuse colors 188 fi; 189 190 node_colors := [ "white", "brown", "burlywood", "cadetblue", "chartreuse", "chocolate", "coral", "cornflowerblue", 191 "crimson", "cyan", "darkgoldenrod", "darkkhaki", "darkorange", "darkorchid", "darksalmon", 192 "darkseagreen", "darkturquoise", "darkviolet", "deeppink", "deepskyblue", "dodgerblue", "firebrick", 193 "forestgreen", "gold", "goldenrod", "green", "greenyellow", "grey", "hotpink", "indianred", "khaki", 194 "lawngreen", "lightblue", "lightcoral", "lightpink", "lightsalmon", "lightseagreen", "lightskyblue", 195 "lightslateblue", "lightslategrey", "limegreen", "magenta", "maroon", "mediumaquamarine", "mediumorchid", 196 "mediumpurple", "mediumseagreen", "mediumspringgreen", "mediumturquoise", "mediumvioletred", 197 "moccasin", "navajowhite", "olivedrab2", "orange", "orangered", "orchid", "palegreen", "paleturquoise", 198 "palevioletred", "peachpuff", "peru", "pink", "plum", "powderblue", "purple", "red", "rosybrown", "royalblue1", 199 "saddlebrown", "salmon", "sandybrown", "seagreen", "skyblue", "slateblue", "slategrey", "springgreen", 200 "steelblue", "tan", "thistle", "tomato", "turquoise", "violet", "violetred", "wheat", "yellow", "yellowgreen" ]; 201 202# tdir := CMUP__getTempDir(); 203# name := Filename(tdir, Concatenation(fich, ".dot")); 204 205 # --------------------------------------------------------------------------------- 206 207 T := StructuralCopy(A!.transitions); 208 str := "digraph Automaton{\n"; # the string that will hold the code of the .dot file 209 out_str := OutputTextString(str, true); 210 211 # --------------------------------------------------------------------------------- 212 # If we were called by DrawSCCAutomaton, determine the edges to be drawn with dotted lines 213 if who_called = 2 then 214 scc := GraphStronglyConnectedComponents(UnderlyingGraphOfAutomaton(A)); 215 G := []; 216 for p in scc do 217 for q in p do 218 G[q] := p; 219 od; 220 od; 221 fi; 222 # --------------------------------------------------------------------------------- 223 224 # --------------------------------------------------------------------------------- 225 # Write the edges 226 for a in [1 .. alph] do 227 for p in [1 .. A!.states] do 228 if IsList(T[a][p]) then # this is a nondet or epsilon automaton 229 if who_called = 1 then 230 for q in T[a][p] do # write edge p --a--> q 231 AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); 232 od; 233 elif who_called = 2 then 234 for q in T[a][p] do # write edge p --a--> q 235 if p in G[p] and q in G[p] and IsBound(G[p][2]) then 236 AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); 237 else 238 AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], ",style = dotted];\n"); 239 fi; 240 od; 241 fi; 242 else 243 q := T[a][p]; 244 if q > 0 then 245 if who_called = 1 then 246 AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); 247 elif who_called = 2 then 248 if p in G[p] and q in G[p] and IsBound(G[p][2]) then 249 AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); 250 else 251 AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], ",style = dotted];\n"); 252 fi; 253 fi; 254 255 fi; 256 fi; 257 od; 258 od; 259 # --------------------------------------------------------------------------------- 260 261 # --------------------------------------------------------------------------------- 262 # Prepare the list color_of_node, such that state p will be in color node_colors[k] <==> color_of_node[p] = k 263 color_of_node := List([1 .. A!.states], _ -> 1); 264 for k in [1 .. Length(states_to_colorize)] do 265 for p in states_to_colorize[k] do 266 color_of_node[p] := k+1; 267 od; 268 od; 269 # --------------------------------------------------------------------------------- 270 271 # --------------------------------------------------------------------------------- 272 # Write the nodes 273 for p in Difference(A!.initial, A!.accepting) do 274 AppendTo(out_str, "\"", map[p], "\" [shape=triangle, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); 275 od; 276 for p in A!.accepting do 277 if p in A!.initial then 278 AppendTo(out_str, "\"", map[p], "\" [shape=triangle,peripheries=2, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); 279 else 280 AppendTo(out_str, "\"", map[p], "\" [shape=doublecircle, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); 281 fi; 282 od; 283 for p in Difference([1 .. A!.states], Concatenation(A!.initial, A!.accepting)) do 284 AppendTo(out_str, "\"", map[p], "\" [shape=circle, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); 285 od; 286 AppendTo(out_str,"}","\n"); 287 # --------------------------------------------------------------------------------- 288 289 CloseStream(out_str); 290 #Siegen PrintTo(name, str); 291 292 #Siegen return tdir; 293 return str; 294 295end); 296## ---- End of WriteDotFileForGraph() ---- 297#======================================================================== 298 299 300 301############################################################################# 302## 303#F DotStringForDrawingAutomaton( arg ) 304## 305## ouputs a string consisting of dot code for an automaton 306## 307InstallGlobalFunction(DotStringForDrawingAutomaton, function(arg) 308 local A, fich, state_names, states_to_colorize, l, s, gv, 309 dot, tdir, res; 310 311 if Length(arg) = 0 then 312 Error("Please give me an automaton to draw"); 313 fi; 314 if not IsAutomatonObj(arg[1]) then 315 Error("The first argument must be an automaton"); 316 fi; 317 318 res := AUX__parseDrawAutArgs(arg); # parse the arguments 319 A := res[1]; 320 fich := res[2]; 321 state_names := res[3]; 322 states_to_colorize := res[4]; 323 324 return WriteDotFileForGraph(A, fich, state_names, states_to_colorize, 1); 325end); 326 327############################################################################# 328## 329#F DotStringForDrawingGraph( <G> ) . . . . . . . . . . . 330## ouputs a string consisting of dot code for a graph 331## 332## 333InstallGlobalFunction(DotStringForDrawingGraph, function(G) 334 local dotstr, l, k; 335 336 dotstr := "digraph Graph__{\n"; 337 # the string that will hold the code of the .dot file 338 for l in [ 1 .. Length( G ) ] do 339 for k in G[ l ] do 340 Append(dotstr, Concatenation(String(l), " -> ")); 341 Append(dotstr, Concatenation(String(k)," [style=bold, color=black];\n")); 342 od; 343 od; 344 345 for k in [1..Length(G)] do 346 Append(dotstr, Concatenation(String(k), " [shape=circle];\n")); 347 od; 348 Append(dotstr,"}\n"); 349 return(dotstr); 350end); 351 352############################################################################ 353## 354#F AUX__DotStringForDrawingSubAutomaton( <A> , <B> ) . . . . . . . . Prepares a file in the DOT 355## language to draw the automaton B and showing the automaton A as a 356## subautomaton. 357## 358InstallGlobalFunction(AUX__DotStringForDrawingSubAutomaton, function(A,B) 359 local nome, letters, au, au1, i, j, colors, l2, array, s, arr, max, k, 360 dotstr, l; 361 362 # if not (IsList(A) and 1 < Length(A) and Length(A) < 4 and 363 # IsAutomatonObj(A[1]) and IsAutomatonObj(A[2]) ) then 364 # Error("The argument of dotAutomata is a list of automata"); 365 # fi; 366 367## tdir := CMUP__getTempDir(); 368# if Length(A) = 3 then 369# name := Filename(tdir, Concatenation(String(A[3]), ".dot")); 370# xname := Concatenation(String(A[3]), ".dot"); 371# aut1 := A[1]; 372# aut2 := A[2]; 373# elif Length(A) = 2 then 374# name := Filename(tdir, "automaton.dot"); 375# xname := "automato.dot"; 376# aut1 := A[1]; 377# aut2 := A[2]; 378 # fi; 379 380 381 nome := "Automaton"; 382# letters := []; 383 letters := List(AlphabetOfAutomatonAsList(A), a -> [a]); 384 385 au := StructuralCopy(B!.transitions); 386 au1 := StructuralCopy(A!.transitions); 387 for i in [1 .. Length(A!.transitions)] do 388 for j in [1 .. Length(A!.transitions[1])] do 389 if not IsBound(au1[i][j]) or au1[i][j] = 0 or au1[i][j] = [0] 390 or au1[i][j] = [] then 391 au1[i][j] := " "; 392 fi; 393 od; 394 od; 395 for i in [1 .. Length(B!.transitions)] do 396 for j in [1 .. Length(B!.transitions[1])] do 397 if not IsBound(au[i][j]) or au[i][j] = 0 or au[i][j] = [0] 398 or au[i][j] = [] then 399 au[i][j] := " "; 400 fi; 401 od; 402 od; 403 404 if B!.alphabet < 7 then ## for small alphabets, the letters 405 ## a, b, c, d are used 406# letters := ["a", "b", "c", "d", "e", "f"]; 407 colors := ["red", "blue", "green", "yellow", "brown", "black"]; 408 else 409# for i in [1 .. B!.alphabet] do 410# Add(letters, Concatenation("a", String(i))); 411# od; 412 colors := []; 413 for i in [1 .. B!.alphabet] do 414 colors[i]:= "black"; 415 od; 416 fi; 417 418 l2 := []; 419 array := []; 420 s := []; 421 arr := List( au, x -> List( x, String ) ); 422 max := Maximum( List( arr, x -> Maximum( List(x,Length) ) ) ); 423 424 for i in [1 .. B!.states] do 425 for j in [1 .. B!.alphabet] do 426 if IsBound(au[j]) and IsBound(au[j][i]) and 427 au[j][i] <> " " then 428 if IsList(au[j][i]) then 429 for k in au[j][i] do 430 if i <= A!.states and j <= A!.alphabet and 431 IsBound(au1[j]) and IsBound(au1[j][i]) and k in au1[j][i] and 432 au1[j][i] <> " " then 433 434 Add(array, [i, " -> ", k," [label=", "\"", letters[j],"\"",",color=", colors[j],"];"]); 435 else 436 Add(array, [i, " -> ", k," [label=", "\"", letters[j],"\"",",color=", colors[j], ",style = dotted];"]); 437 438 fi; 439 od; 440 else 441 if i <= A!.states and j <= A!.alphabet and 442 IsBound(au1[j]) and IsBound(au1[j][i]) and 443 au1[j][i] <> " " then 444 Add(array, [i, " -> ", au[j][i]," [label=", "\"", letters[j],"\"",",color=", colors[j], "];"]); 445 else 446 Add(array, [i, " -> ", au[j][i]," [label=", "\"", letters[j],"\"",",color=", colors[j], ",style = dotted];"]); 447 fi; 448 fi; 449 fi; 450 451 od; 452 od; 453 454 arr := List( array, x -> List( x, String ) ); 455 456 dotstr :="digraph Automaton {\n"; 457 ## PrintTo(name, "digraph ", nome, "{", "\n"); 458 for l in [ 1 .. Length( arr ) ] do 459 for k in [ 1 .. Length( arr[ l ] ) ] do 460 Append(dotstr, String( arr[ l ][ k ]) ); 461 od; 462 if l = Length( arr ) then 463 Append(dotstr, "\n" ); 464 else 465 Append(dotstr, "\n" ); 466 fi; 467 od; 468 for i in A!.initial do 469 Append(dotstr, Concatenation(String(i), " [shape=triangle];\n")); 470 od; 471 for i in Difference(B!.initial,A!.initial) do 472 Append(dotstr, Concatenation(String(i), " [shape=triangle,color=gray];\n")); 473 od; 474 for j in A!.accepting do 475 if j in A!.initial then 476 Append(dotstr, Concatenation(String(j), " [shape=triangle,peripheries=2];\n")); 477 else 478 Append(dotstr, Concatenation(String(j), " [shape=doublecircle];\n")); 479 fi; 480 od; 481 for j in Difference(B!.accepting,A!.accepting) do 482 if j in B!.initial then 483 Append(dotstr, Concatenation(String(i), " [shape=triangle,peripheries=2,color=gray];\n")); 484 else 485 Append(dotstr, Concatenation(String(j), " [shape=doublecircle,color=gray];n")); 486 fi; 487 od; 488 for k in Difference(Difference([1..A!.states],B!.accepting),Concatenation(A!.initial, B!.initial,A!.accepting)) do 489 Append(dotstr, Concatenation(String(k), " [shape=circle];\n")); 490 od; 491 for k in Difference(Difference([1..B!.states],B!.accepting),Concatenation(A!.initial, B!.initial, [1..A!.states])) do 492 Append(dotstr, Concatenation(String(k), " [shape=circle,color=gray];\n")); 493 od; 494 Append(dotstr,"}\n"); 495 return(dotstr); 496end); 497 498############################################################################# 499## 500#F DotStringForDrawingSubAutomaton( <A> , <B> ) 501## ouputs a string consisting of dot code for automaton B and showing A as a subautomaton. 502## 503InstallGlobalFunction(DotStringForDrawingSubAutomaton, function(arg) 504 local A, B, fich, a, q, k, dotstr; 505 506 if not (IsBound(arg[1]) and IsBound(arg[2])) then 507 Error("This function takes two automata as arguments"); 508 fi; 509 A := arg[1]; 510 B := arg[2]; 511 if not IsAutomatonObj(A) then 512 Error("The first argument must be an automaton"); 513 fi; 514 if not IsAutomatonObj(B) then 515 Error("The second argument must be an automaton"); 516 fi; 517 if IsBound(arg[3]) then 518 if not IsString(arg[3]) or arg[3] = "" then 519 fich := "implausible987678"; 520 else 521 fich := arg[3]; 522 fi; 523 else 524 fich := "implausible987678"; 525 fi; 526 527 if A!.states > B!.states or A!.alphabet > B!.alphabet then 528 Print("The first argument is not a subautomaton of the second argument.\n"); 529 return; 530 fi; 531 532# gv := CMUP__getPsViewer(); 533# dot := CMUP__getDotExecutable(); 534 535 for a in [1 .. A!.alphabet] do 536 for q in [1 .. A!.states] do 537 k := A!.transitions[a][q]; 538 if IsInt(k) then 539 if not (k = B!.transitions[a][q] or k = 0) then 540 Print("The first argument is not a subautomaton of the second argument.\n"); 541 return; 542 fi; 543 else 544 if not ForAll(k, s -> s in B!.transitions[a][q]) then 545 Print("The first argument is not a subautomaton of the second argument.\n"); 546 return; 547 fi; 548 fi; 549 od; 550 od; 551 552 dotstr := AUX__DotStringForDrawingSubAutomaton(A,B); 553 return dotstr; 554 555 # res := dotAutomata([A,B, fich]); 556 557 # tdir := res[1]; 558 # name := res[2]; 559 # CMUP__executeDotAndViewer(tdir, dot, gv, name); 560end); 561############################################################################# 562## 563#F DotStringForDrawingSCCAutomaton( <A>, fich ) . . . . . . . . produces a ps file with the 564## automaton A using the dot language. The strongly connected components are 565## emphasized. 566## 567InstallGlobalFunction(DotStringForDrawingSCCAutomaton, function(arg) 568 local res, A, fich, state_names, states_to_colorize, dotstr; 569 570 if Length(arg) = 0 then 571 Error("Please give me an automaton to draw"); 572 fi; 573 if not IsAutomatonObj(arg[1]) then 574 Error("The first argument must be an automaton"); 575 fi; 576 577 res := AUX__parseDrawAutArgs(arg); # parse the arguments 578 A := res[1]; 579 fich := res[2]; 580 state_names := res[3]; 581 states_to_colorize := res[4]; 582 583 dotstr := WriteDotFileForGraph(A, fich, state_names, states_to_colorize, 2); 584 return dotstr; 585 586 587 # gv := CMUP__getPsViewer(); 588 # dot := CMUP__getDotExecutable(); 589 # tdir := WriteDotFileForGraph(A, fich, state_names, states_to_colorize, 2); 590 # CMUP__executeDotAndViewer(tdir, dot, gv, Concatenation(fich, ".dot")); 591end); 592 593## 594#E 595 596