Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
| Download
GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Views: 418346############################################################################# ## #W drawgraph.gi GAP library Manuel Delgado <[email protected]> #W Jose Morais <[email protected]> ## #H @(#)$Id: drawgraph.gi,v 1.13 $ ## #Y Copyright (C) 2004, CMUP, Universidade do Porto, Portugal ## ## The functions in this file make use of the external program dot (from ## the freely available software package graphviz, for graph visualization) ## to display the graphs. ############################################################################ ############################################################################ ## #F SetDrawingsExtraFormat(f) ## ## This function sets the value of DrawingsExtraFormat to <f>. ## InstallGlobalFunction(SetDrawingsExtraFormat, function(f) if not f in DrawingsListOfExtraFormats then 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"); return; fi; MakeReadWriteGlobal("DrawingsExtraFormat"); DrawingsExtraFormat := f; MakeReadOnlyGlobal("DrawingsExtraFormat"); end); ############################################################################ ## #F SetDrawingsExtraGraphAttributes(L) ## ## This function sets the value of DrawingsExtraGraphAttributes to <L>. ## For example if we wanted to define the graph size to be 7x9, we would call ## SetDrawingsExtraGraphAttributes(["size=7,9"]); ## InstallGlobalFunction(SetDrawingsExtraGraphAttributes, function(L) if not (IsList(L) and ForAll(L, l -> IsString(l))) then Error("The argument must be a list of strings"); fi; MakeReadWriteGlobal("DrawingsExtraGraphAttributes"); DrawingsExtraGraphAttributes := L; MakeReadOnlyGlobal("DrawingsExtraGraphAttributes"); end); ############################################################################ ## #F ClearDrawingsExtraGraphAttributes() ## ## This function sets DrawingsExtraGraphAttributes to "none" ## Thus indicating that the graph should be drawn with dot's default parameters. ## InstallGlobalFunction(ClearDrawingsExtraGraphAttributes, function() MakeReadWriteGlobal("DrawingsExtraGraphAttributes"); DrawingsExtraGraphAttributes := "none"; MakeReadOnlyGlobal("DrawingsExtraGraphAttributes"); end); #======================================================================== # This function parses the arguments for the functions DrawAutomaton and DrawSCCAutomaton. #------------------------------------------------------------------------ InstallGlobalFunction(AUX__parseDrawAutArgs, function(LA) local A, fich, state_names, states_to_colorize, l, s; A := LA[1]; # the automaton to draw fich := "automaton"; # this is a string with the name of the .dot file state_names := List([1..A!.states], s -> String(s)); # this is a list of strings with new state names states_to_colorize := []; # ------------------------------------------------------------------------------ # ----- Treat the arguments ---------------------------------------------------- # Check if there is a second argument if IsBound(LA[2]) then if IsString(LA[2]) then # this is a string with the name of the .dot file fich := LA[2]; elif IsList(LA[2]) and IsString(LA[2][1]) then # this is a list of strings with new state names state_names := LA[2]; if Length(state_names) <> A!.states then Error("The list of new state names must have length equal to the number of states of the automaton"); fi; 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 states_to_colorize := LA[2]; for l in states_to_colorize do for s in l do if s < 1 or s > A!.states then Error("The states to colorize must be integers in [1 ..", A!.states, "]"); fi; od; od; else Error("Wrong second argument, please check the manual"); fi; # Check if there is a third argument if IsBound(LA[3]) then if IsString(LA[3]) then # this is a string with the name of the .dot file fich := LA[3]; elif IsList(LA[3]) and IsString(LA[3][1]) then # this is a list of strings with new state names state_names := LA[3]; if Length(state_names) <> A!.states then Error("The list of new state names must have length equal to the number of states of the automaton"); fi; 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 states_to_colorize := LA[3]; for l in states_to_colorize do for s in l do if s < 1 or s > A!.states then Error("The states to colorize must be integers in [1 ..", A!.states, "]"); fi; od; od; else Error("Wrong third argument, please check the manual"); fi; # Check if there is a fourth argument if IsBound(LA[4]) then if IsString(LA[4]) then # this is a string with the name of the .dot file fich := LA[4]; elif IsList(LA[4]) and IsString(LA[4][1]) then # this is a list of strings with new state names state_names := LA[4]; if Length(state_names) <> A!.states then Error("The list of new state names must have length equal to the number of states of the automaton"); fi; 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 states_to_colorize := LA[4]; for l in states_to_colorize do for s in l do if s < 1 or s > A!.states then Error("The states to colorize must be integers in [1 ..", A!.states, "]"); fi; od; od; else Error("Wrong fourth argument, please check the manual"); fi; fi; fi; fi; # ----- End of Treat the arguments -------------------------------------------- # ------------------------------------------------------------------------------ return [A, fich, state_names, states_to_colorize]; end); #======================================================================== # This function writes the .dot file specifying a graph. # It is used by DrawAutomaton and DrawSCCAutomaton. # # The argument 'who_called' specifies which function requested the .dot file: # who_called = 1 ---> DrawAutomaton # who_called = 2 ---> DrawSCCAutomaton #------------------------------------------------------------------------ InstallGlobalFunction(WriteDotFileForGraph, function(A, fich, map, states_to_colorize, who_called) local letters, edge_colors, len_alph, node_colors, tdir, name, alph, T, str, out_str, scc, G, p, q, a, color_of_node, k; alph := AlphabetOfAutomaton(A); # When the alphabet has more than 27 letters, they are given in the form if IsList(AlphabetOfAutomatonAsList(A)[1]) then letters := AlphabetOfAutomatonAsList(A); else letters := List(AlphabetOfAutomatonAsList(A), a -> [a]); fi; edge_colors := ["red", "blue", "green", "purple", "orange", "brown", "darksalmon", "darkseagreen", "darkturquoise", "darkviolet", "deeppink", "deepskyblue", "dodgerblue", "firebrick", "forestgreen", "gold"]; if alph > 16 then edge_colors := List([1 .. alph], i -> edge_colors[(i mod 16) + 1]);#to reuse colors fi; node_colors := [ "white", "brown", "burlywood", "cadetblue", "chartreuse", "chocolate", "coral", "cornflowerblue", "crimson", "cyan", "darkgoldenrod", "darkkhaki", "darkorange", "darkorchid", "darksalmon", "darkseagreen", "darkturquoise", "darkviolet", "deeppink", "deepskyblue", "dodgerblue", "firebrick", "forestgreen", "gold", "goldenrod", "green", "greenyellow", "grey", "hotpink", "indianred", "khaki", "lawngreen", "lightblue", "lightcoral", "lightpink", "lightsalmon", "lightseagreen", "lightskyblue", "lightslateblue", "lightslategrey", "limegreen", "magenta", "maroon", "mediumaquamarine", "mediumorchid", "mediumpurple", "mediumseagreen", "mediumspringgreen", "mediumturquoise", "mediumvioletred", "moccasin", "navajowhite", "olivedrab2", "orange", "orangered", "orchid", "palegreen", "paleturquoise", "palevioletred", "peachpuff", "peru", "pink", "plum", "powderblue", "purple", "red", "rosybrown", "royalblue1", "saddlebrown", "salmon", "sandybrown", "seagreen", "skyblue", "slateblue", "slategrey", "springgreen", "steelblue", "tan", "thistle", "tomato", "turquoise", "violet", "violetred", "wheat", "yellow", "yellowgreen" ]; tdir := CMUP__getTempDir(); name := Filename(tdir, Concatenation(fich, ".dot")); # --------------------------------------------------------------------------------- T := StructuralCopy(A!.transitions); str := "digraph Automaton{\n"; # the string that will hold the code of the .dot file out_str := OutputTextString(str, true); # --------------------------------------------------------------------------------- # If we were called by DrawSCCAutomaton, determine the edges to be drawn with dotted lines if who_called = 2 then scc := GraphStronglyConnectedComponents(UnderlyingGraphOfAutomaton(A)); G := []; for p in scc do for q in p do G[q] := p; od; od; fi; # --------------------------------------------------------------------------------- # --------------------------------------------------------------------------------- # Write the edges for a in [1 .. alph] do for p in [1 .. A!.states] do if IsList(T[a][p]) then # this is a nondet or epsilon automaton if who_called = 1 then for q in T[a][p] do # write edge p --a--> q AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); od; elif who_called = 2 then for q in T[a][p] do # write edge p --a--> q if p in G[p] and q in G[p] and IsBound(G[p][2]) then AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); else AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], ",style = dotted];\n"); fi; od; fi; else q := T[a][p]; if q > 0 then if who_called = 1 then AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); elif who_called = 2 then if p in G[p] and q in G[p] and IsBound(G[p][2]) then AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], "];\n"); else AppendTo(out_str, "\"", map[p], "\" -> \"", map[q], "\" [label=\"", letters[a], "\",color=", edge_colors[a], ",style = dotted];\n"); fi; fi; fi; fi; od; od; # --------------------------------------------------------------------------------- # --------------------------------------------------------------------------------- # Prepare the list color_of_node, such that state p will be in color node_colors[k] <==> color_of_node[p] = k color_of_node := List([1 .. A!.states], _ -> 1); for k in [1 .. Length(states_to_colorize)] do for p in states_to_colorize[k] do color_of_node[p] := k+1; od; od; # --------------------------------------------------------------------------------- # --------------------------------------------------------------------------------- # Write the nodes for p in Difference(A!.initial, A!.accepting) do AppendTo(out_str, "\"", map[p], "\" [shape=triangle, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); od; for p in A!.accepting do if p in A!.initial then AppendTo(out_str, "\"", map[p], "\" [shape=triangle,peripheries=2, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); else AppendTo(out_str, "\"", map[p], "\" [shape=doublecircle, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); fi; od; for p in Difference([1 .. A!.states], Concatenation(A!.initial, A!.accepting)) do AppendTo(out_str, "\"", map[p], "\" [shape=circle, style=filled, fillcolor=", node_colors[color_of_node[p]], "];\n"); od; AppendTo(out_str,"}","\n"); # --------------------------------------------------------------------------------- CloseStream(out_str); PrintTo(name, str); return tdir; end); ## ---- End of WriteDotFileForGraph() ---- #======================================================================== ############################################################################# ## #F DrawAutomaton( arg ) . . . . . . . . . . . produces a ps file with the ## automaton A using the dot language and stops after showing it ## InstallGlobalFunction(DrawAutomaton, function(arg) local A, fich, state_names, states_to_colorize, l, s, gv, dot, tdir, res; if Length(arg) = 0 then Error("Please give me an automaton to draw"); fi; if not IsAutomatonObj(arg[1]) then Error("The first argument must be an automaton"); fi; res := AUX__parseDrawAutArgs(arg); # parse the arguments A := res[1]; fich := res[2]; state_names := res[3]; states_to_colorize := res[4]; gv := CMUP__getPsViewer(); dot := CMUP__getDotExecutable(); tdir := WriteDotFileForGraph(A, fich, state_names, states_to_colorize, 1); CMUP__executeDotAndViewer(tdir, dot, gv, Concatenation(fich, ".dot")); end); ############################################################################# ## #F dotGraph( <G>, fich ) . . . . . . . . . . . Prepares a file in the DOT ## language to draw the graph G using dot ## InstallGlobalFunction(dotGraph, function(G, fich) local k, l, name, tdir, nome; if not IsString(fich) then Error("The second argument must be a string"); fi; tdir := CMUP__getTempDir(); name := Filename(tdir, Concatenation(fich, ".dot")); nome := "Graph__"; PrintTo(name, "digraph ", nome, "{", "\n"); for l in [ 1 .. Length( G ) ] do for k in G[ l ] do AppendTo(name, l, " -> ", k," [style=bold, color=black];","\n"); od; od; for k in [1..Length(G)] do AppendTo(name, k, " [shape=circle];","\n"); od; AppendTo(name,"}","\n"); return([tdir, Concatenation(fich, ".dot")]); end); ############################################################################# ## #F DrawGraph( arg ) . . . . . . . . . . . produces a ps file with the ## Graph A using the dot language and stops after showing it ## InstallGlobalFunction(DrawGraph, function(arg) local gv, dot, tdir, name, res; if Length(arg) = 0 then Error("Please give me a graph to draw"); fi; gv := CMUP__getPsViewer(); dot := CMUP__getDotExecutable(); if IsBound(arg[2]) then res := dotGraph(arg[1], arg[2]); else res := dotGraph(arg[1], "graph"); fi; tdir := res[1]; name := res[2]; CMUP__executeDotAndViewer(tdir, dot, gv, name); end); ############################################################################ ## #F dotAutomata( [ <A> , <B> ] ) . . . . . . . . Prepares a file in the DOT ## language to draw the automaton B and showing the automaton A as a ## subautomaton. ## InstallGlobalFunction(dotAutomata, function(A) local au, au1, aut1, aut2, l1, l2, arr, array, colors, i, j, k, letters, max, name, tdir, nome, R, l, s, t, xname; if not (IsList(A) and 1 < Length(A) and Length(A) < 4 and IsAutomatonObj(A[1]) and IsAutomatonObj(A[2]) ) then Error("The argument of dotAutomata is a list of automata"); fi; tdir := CMUP__getTempDir(); if Length(A) = 3 then name := Filename(tdir, Concatenation(String(A[3]), ".dot")); xname := Concatenation(String(A[3]), ".dot"); aut1 := A[1]; aut2 := A[2]; elif Length(A) = 2 then name := Filename(tdir, "automaton.dot"); xname := "automato.dot"; aut1 := A[1]; aut2 := A[2]; fi; nome := "Automaton"; # letters := []; letters := List(AlphabetOfAutomatonAsList(A), a -> [a]); au := StructuralCopy(aut2!.transitions); au1 := StructuralCopy(aut1!.transitions); for i in [1 .. Length(aut1!.transitions)] do for j in [1 .. Length(aut1!.transitions[1])] do if not IsBound(au1[i][j]) or au1[i][j] = 0 or au1[i][j] = [0] or au1[i][j] = [] then au1[i][j] := " "; fi; od; od; for i in [1 .. Length(aut2!.transitions)] do for j in [1 .. Length(aut2!.transitions[1])] do if not IsBound(au[i][j]) or au[i][j] = 0 or au[i][j] = [0] or au[i][j] = [] then au[i][j] := " "; fi; od; od; if aut2!.alphabet < 7 then ## for small alphabets, the letters ## a, b, c, d are used # letters := ["a", "b", "c", "d", "e", "f"]; colors := ["red", "blue", "green", "yellow", "brown", "black"]; else # for i in [1 .. aut2!.alphabet] do # Add(letters, Concatenation("a", String(i))); # od; colors := []; for i in [1 .. aut2!.alphabet] do colors[i]:= "black"; od; fi; l2 := []; array := []; s := []; arr := List( au, x -> List( x, String ) ); max := Maximum( List( arr, x -> Maximum( List(x,Length) ) ) ); for i in [1 .. aut2!.states] do for j in [1 .. aut2!.alphabet] do if IsBound(au[j]) and IsBound(au[j][i]) and au[j][i] <> " " then if IsList(au[j][i]) then for k in au[j][i] do if i <= aut1!.states and j <= aut1!.alphabet and IsBound(au1[j]) and IsBound(au1[j][i]) and k in au1[j][i] and au1[j][i] <> " " then Add(array, [i, " -> ", k," [label=", "\"", letters[j],"\"",",color=", colors[j],"];"]); else Add(array, [i, " -> ", k," [label=", "\"", letters[j],"\"",",color=", colors[j], ",style = dotted];"]); fi; od; else if i <= aut1!.states and j <= aut1!.alphabet and IsBound(au1[j]) and IsBound(au1[j][i]) and au1[j][i] <> " " then Add(array, [i, " -> ", au[j][i]," [label=", "\"", letters[j],"\"",",color=", colors[j], "];"]); else Add(array, [i, " -> ", au[j][i]," [label=", "\"", letters[j],"\"",",color=", colors[j], ",style = dotted];"]); fi; fi; fi; od; od; arr := List( array, x -> List( x, String ) ); PrintTo(name, "digraph ", nome, "{", "\n"); for l in [ 1 .. Length( arr ) ] do for k in [ 1 .. Length( arr[ l ] ) ] do AppendTo(name, String( arr[ l ][ k ]) ); od; if l = Length( arr ) then AppendTo(name, "\n" ); else AppendTo(name, "\n" ); fi; od; for i in aut1!.initial do AppendTo(name, i, " [shape=triangle];","\n"); od; for i in Difference(aut2!.initial,aut1!.initial) do AppendTo(name, i, " [shape=triangle,color=gray];","\n"); od; for j in aut1!.accepting do if j in aut1!.initial then AppendTo(name, j, " [shape=triangle,peripheries=2];","\n"); else AppendTo(name, j, " [shape=doublecircle];","\n"); fi; od; for j in Difference(aut2!.accepting,aut1!.accepting) do if j in aut2!.initial then AppendTo(name, i, " [shape=triangle,peripheries=2,color=gray];","\n"); else AppendTo(name, j, " [shape=doublecircle,color=gray];","\n"); fi; od; for k in Difference(Difference([1..aut1!.states],aut2!.accepting),Concatenation(aut1!.initial, aut2!.initial,aut1!.accepting)) do AppendTo(name, k, " [shape=circle];","\n"); od; for k in Difference(Difference([1..aut2!.states],aut2!.accepting),Concatenation(aut1!.initial, aut2!.initial, [1..aut1!.states])) do AppendTo(name, k, " [shape=circle,color=gray];","\n"); od; AppendTo(name,"}","\n"); return([tdir, xname]); end); ############################################################################# ## #F DrawAutomata( <A>, fich ) . . . . . . . . . . . produces a ps file with the ## automaton A using the dot language and stops after showing it ## InstallGlobalFunction(DrawAutomata, function(arg) local fich, A, B, q, a, k, gv, dot, tdir, name, res; if not (IsBound(arg[1]) and IsBound(arg[2])) then Error("This function takes two automata as arguments"); fi; A := arg[1]; B := arg[2]; if not IsAutomatonObj(A) then Error("The first argument must be an automaton"); fi; if not IsAutomatonObj(B) then Error("The second argument must be an automaton"); fi; if IsBound(arg[3]) then if not IsString(arg[3]) or arg[3] = "" then fich := "implausible987678"; else fich := arg[3]; fi; else fich := "implausible987678"; fi; if A!.states > B!.states or A!.alphabet > B!.alphabet then Print("The first argument is not a subautomaton of the second argument.\n"); return; fi; gv := CMUP__getPsViewer(); dot := CMUP__getDotExecutable(); for a in [1 .. A!.alphabet] do for q in [1 .. A!.states] do k := A!.transitions[a][q]; if IsInt(k) then if not (k = B!.transitions[a][q] or k = 0) then Print("The first argument is not a subautomaton of the second argument.\n"); return; fi; else if not ForAll(k, s -> s in B!.transitions[a][q]) then Print("The first argument is not a subautomaton of the second argument.\n"); return; fi; fi; od; od; res := dotAutomata([A,B, fich]); tdir := res[1]; name := res[2]; CMUP__executeDotAndViewer(tdir, dot, gv, name); end); ############################################################################# ## #F DrawSCCAutomaton( <A>, fich ) . . . . . . . . produces a ps file with the ## automaton A using the dot language. The strongly connected components are ## emphasized. ## InstallGlobalFunction(DrawSCCAutomaton, function(arg) local A, fich, state_names, states_to_colorize, l, s, gv, dot, tdir, res; if Length(arg) = 0 then Error("Please give me an automaton to draw"); fi; if not IsAutomatonObj(arg[1]) then Error("The first argument must be an automaton"); fi; res := AUX__parseDrawAutArgs(arg); # parse the arguments A := res[1]; fich := res[2]; state_names := res[3]; states_to_colorize := res[4]; gv := CMUP__getPsViewer(); dot := CMUP__getDotExecutable(); tdir := WriteDotFileForGraph(A, fich, state_names, states_to_colorize, 2); CMUP__executeDotAndViewer(tdir, dot, gv, Concatenation(fich, ".dot")); end); ## #E