1############################################################################# 2## 3#W dot.gi Manuel Delgado <mdelgado@fc.up.pt> 4#W Pedro A. Garcia-Sanchez <pedro@ugr.es> 5#W Andrés Herrera-Poyatos <andreshp9@gmail.com> 6## 7## 8#Y Copyright 2017 by Manuel Delgado and Pedro Garcia-Sanchez 9#Y We adopt the copyright regulations of GAP as detailed in the 10#Y copyright notice in the GAP manual. 11## 12############################################################################# 13 14############################################################################ 15## 16#F DotSplash(dots...) 17## Launches a browser and visualizes the dots diagrams 18## provided as arguments. 19## 20############################################################################ 21InstallGlobalFunction(DotSplash, function(dots...) 22 local str, temp_file, digraph, html, i, line, out; 23 24 str:=function(s) 25 return Concatenation("\"",String(s),"\""); 26 end; 27 28 # Open a temporal file 29 temp_file := Filename(DirectoryTemporary(), "graph-viz.html"); 30 out := OutputTextFile(temp_file, false); 31 SetPrintFormattingStatus(out, false); 32 33 # HTML header 34 html := "<!DOCTYPE html>\n<html>\n<head>\n<meta charset=\"utf-8\">\n <title>Graph Viz</title>\n"; 35 html := Concatenation(html, "<style>\n .content {\n display: inline-block;\n text-align: center;\n vertical-align: top;\n}\n</style></head>\n<body>\n<script src=\"http://mdaines.github.io/viz.js/bower_components/viz.js/viz.js\">\n</script>\n"); 36 #html:=Concatenation(html, "<style>\n .content {\n display: inline-block;\n text-align: center;\n vertical-align: top;\n}\n</style></head>\n<body>\n<script src=\"viz.js\">\n</script>\n"); 37 38 # Assign an ID to each graph 39 for i in [1..Length(dots)] do 40 line := Concatenation("<span id=", str(i), " class='content'>Graph to be displayed here (internet connection required) </span>\n"); 41 html := Concatenation(html, line); 42 od; 43 44 # Draw each graph 45 line := "<script>\n"; 46 html := Concatenation(html, line); 47 i := 1; 48 for digraph in dots do 49 line := Concatenation(" document.getElementById(", str(i), ").innerHTML =Viz('", NormalizedWhitespace(digraph), "', {engine: \"", DotNSEngine, "\"});\n"); 50 html := Concatenation(html, line); 51 i := i+1; 52 od; 53 54 # End the HTML code 55 line := "</script>\n</body>\n</html>"; 56 html := Concatenation(html, line); 57 58 # Draw the graph 59 PrintTo(out, html); 60 CloseStream(out); 61 Print("Saved to ", temp_file, "\n"); 62 if ARCH_IS_MAC_OS_X() then 63 Exec("open ", temp_file); 64 elif ARCH_IS_WINDOWS() then 65 Exec("start firefox ", temp_file); 66 elif ARCH_IS_UNIX() then 67 Exec("xdg-open ", temp_file); 68 fi; 69 70 return html; 71end); 72 73############################################################################ 74## 75#F DotBinaryRelation(br) 76## Returns a GraphViz dot which represents the binary relation br. 77## The set of vertices of the resulting graph is the source of br. 78## Edges join those elements which are related in br. 79## 80############################################################################ 81InstallGlobalFunction(DotBinaryRelation, function(br) 82 local pre, element, im, output, out, str, i, d; 83 84 str := function(i) 85 return Concatenation("\"",String(i),"\""); 86 end; 87 88 if not IsBinaryRelation(br) then 89 Error("The argument must be a binary relation"); 90 fi; 91 92 # Add the header of the GraphViz code 93 out := ""; 94 output := OutputTextString(out, true); 95 AppendTo(output,"digraph NSGraph{rankdir = TB; edge[dir=back];\n"); 96 97 # Add the vertices 98 pre := Source(br); 99 d := NewDictionary(false, true, pre); 100 i := 1; 101 for element in pre do 102 AddDictionary(d, element, i); 103 AppendTo(output, i," [label=", str(element), "];\n"); 104 i := i+1; 105 od; 106 107 # Add the edges 108 i := 1; 109 for element in pre do 110 for im in Image(br, [element]) do 111 AppendTo(output, LookupDictionary(d, im), " -> ", i, ";\n"); 112 od; 113 i := i+1; 114 od; 115 116 AppendTo(output, "}"); 117 CloseStream(output); 118 return out; 119end); 120 121############################################################################ 122## 123#F HasseDiagramOfNumericalSemigroup(s, A) 124## Returns a binary relation which is the Hasse diagram of A with 125## respect to the ordering a <= b if b - a in S. 126## 127############################################################################ 128InstallGlobalFunction(HasseDiagramOfNumericalSemigroup, function(s, A) 129 local rel, p, D; 130 131 if not IsNumericalSemigroup(s) then 132 Error("The argument must be a numerical semigroup.\n"); 133 fi; 134 135 # Build the binary relation and returns its Hasse diagram 136 D := Domain(Set(A)); 137 rel := Tuples(D, 2); 138 rel := Filtered(rel, p -> p[2] - p[1] in s); 139 rel := List(rel, p -> DirectProductElement([p[1], p[2]])); 140 rel := BinaryRelationByElements(D, rel); 141 return HasseDiagramBinaryRelation(rel); 142end); 143 144############################################################################ 145## 146#F HasseDiagramOfBettiElementsOfNumericalSemigroup(s) 147## Returns a binary relation which is the Hasse diagram of the Betti 148## elements of s with respect to the ordering a <= b if b - a in S. 149## 150############################################################################ 151InstallGlobalFunction(HasseDiagramOfBettiElementsOfNumericalSemigroup, function(s) 152 if not IsNumericalSemigroup(s) then 153 Error("The argument must be a numerical semigroup.\n"); 154 fi; 155 156 return HasseDiagramOfNumericalSemigroup(s, BettiElementsOfNumericalSemigroup(s)); 157end); 158 159############################################################################ 160## 161#F HasseDiagramOfAperyListOfNumericalSemigroup(s, n) 162## 163############################################################################ 164InstallGlobalFunction(HasseDiagramOfAperyListOfNumericalSemigroup, function(s, n...) 165 local a; 166 167 if not IsNumericalSemigroup(s) then 168 Error("The argument must be a numerical semigroup.\n"); 169 fi; 170 171 if Length(n) = 0 then 172 a := MultiplicityOfNumericalSemigroup(s); 173 elif Length(n) = 1 then 174 a := n[1]; 175 else 176 Error("The number of arguments must be one or two"); 177 fi; 178 179 return HasseDiagramOfNumericalSemigroup(s, AperyListOfNumericalSemigroup(s, a)); 180end); 181 182############################################################################ 183## 184#F DotTreeOfGluingsOfNumericalSemigroup(s, depth...) 185## Returns a GraphViz dot that represents the tree of gluings of the 186## numerical semigroup s. 187## The tree is truncated at the given depth. If the depth is not provided, 188## then the tree is fully built. 189## 190############################################################################ 191InstallGlobalFunction(DotTreeOfGluingsOfNumericalSemigroup, function(s, depth...) 192 local SystemOfGeneratorsToString, rgluings, out, output, labels, edges, index, d; 193 194 SystemOfGeneratorsToString := function(sg) 195 return Concatenation("〈 ", JoinStringsWithSeparator(sg, ", "), " 〉"); 196 end; 197 198 if not IsNumericalSemigroup(s) then 199 Error("The argument must be a numerical semigroup.\n"); 200 fi; 201 202 if Length(depth) = 0 then 203 d := -1; 204 else 205 d:= depth[1]; 206 fi; 207 208 # Recursively plot the gluings tree 209 rgluings := function(s, level, parent) 210 local lg, label, gen1, gen2, p, son1, son2; 211 212 lg := AsGluingOfNumericalSemigroups(s); 213 214 labels := Concatenation(labels, String(parent), " [label=\"", SystemOfGeneratorsToString(MinimalGenerators(s)), "\", style=filled]; \n"); 215 #labels := Concatenation(labels, String(parent), " [label=\"", SystemOfGeneratorsToString(MinimalGenerators(s)), "\"]; \n"); 216 217 if level = 0 then 218 return ; 219 fi; 220 221 # For each possible gluing plot the gluing and the numerical semigroups associated. 222 for p in lg do 223 # Add the gluing 224 label := Concatenation(SystemOfGeneratorsToString(p[1])," + ", SystemOfGeneratorsToString(p[2])); 225 labels := Concatenation(labels, String(index), " [label=\"", label, "\" , shape=box]; \n"); 226 edges := Concatenation(edges, String(parent), " -> ", String(index), "; \n"); 227 228 # Add the two numerical semigroups involved 229 son1 := index+1; 230 son2 := index+2; 231 232 gen1 := p[1] / Gcd(p[1]); 233 gen2 := p[2] / Gcd(p[2]); 234 235 edges := Concatenation(edges, String(index), " -> ", String(son1), "; \n"); 236 edges := Concatenation(edges, String(index), " -> ", String(son2), "; \n"); 237 238 # Call the function recursively 239 index := index + 3; 240 rgluings(NumericalSemigroup(gen1), level-1, son1); 241 rgluings(NumericalSemigroup(gen2), level-1, son2); 242 od; 243 244 return ; 245 end; 246 247 # Create the root of the tree 248 labels := ""; 249 edges := ""; 250 index := 1; 251 labels := Concatenation(labels, "0", " [label=\"", SystemOfGeneratorsToString(MinimalGenerators(s)), "\"]; \n"); 252 # Compute the tree 253 rgluings(s, d, 0); 254 255 # Prepare the output 256 out := ""; 257 output := OutputTextString(out, true); 258 SetPrintFormattingStatus(output, false); 259 AppendTo(output,"digraph NSGraph{rankdir = TB; \n"); 260 AppendTo(output, labels); 261 AppendTo(output, edges); 262 AppendTo(output, "}"); 263 CloseStream(output); 264 265 return out; 266end); 267 268 269############################################################################ 270## 271#F DotOverSemigroupsNumericalSemigroup(s) 272## Returns a GraphViz dot that represents the Hasse diagram of 273## oversemigroupstree of the numerical semigroup s. 274## Irreducible numerical semigroups are highlighted. 275## 276############################################################################ 277InstallGlobalFunction(DotOverSemigroupsNumericalSemigroup, function(s) 278 local ov, c,i,r,n,hasse, str, output, out, SystemOfGeneratorsToString; 279 280 hasse:=function(rel) 281 local dom, out; 282 dom:=Flat(rel); 283 out:=Filtered(rel, p-> ForAny(dom, x->([p[1],x] in rel) and ([x,p[2]] in rel))); 284 return Difference(rel,out); 285 end; 286 287 str := function(i) 288 return Concatenation("\"",String(i),"\""); 289 end; 290 291 SystemOfGeneratorsToString := function(sg) 292 return Concatenation("〈 ", JoinStringsWithSeparator(sg, ", "), " 〉"); 293 end; 294 295 ov:=OverSemigroupsNumericalSemigroup(s); 296 n:=Length(ov); 297 298 # Add the header of the GraphViz code 299 out := ""; 300 output := OutputTextString(out, true); 301 SetPrintFormattingStatus(output, false); 302 AppendTo(output,"digraph NSGraph{rankdir = TB; edge[dir=back];\n"); 303 304 # Add vertices 305 for i in [1..n] do 306 if IsIrreducible(ov[i]) then 307 AppendTo(output,i," [label=\"",SystemOfGeneratorsToString(MinimalGenerators(ov[i])) ,"\", style=filled];\n"); 308 else 309 AppendTo(output,i," [label=\"",SystemOfGeneratorsToString(MinimalGenerators(ov[i])) ,"\"];\n"); 310 fi; 311 od; 312 313 # Add edges 314 c:=Cartesian([1..n],[1..n]); 315 c:=Filtered(c, p-> p[2]<>p[1]); 316 c:=Filtered(c, p-> IsSubset(ov[p[1]],ov[p[2]])); 317 c:=hasse(c); 318 319 for r in c do 320 AppendTo(output,r[1]," -> ",r[2],";\n"); 321 od; 322 323 AppendTo(output, "}"); 324 CloseStream(output); 325 return out; 326end); 327 328InstallMethod(DotOverSemigroups, 329 "for numerical semigrousp", 330 [IsNumericalSemigroup], 331 DotOverSemigroupsNumericalSemigroup); 332 333############################################################################ 334## 335#O DotRosalesGraph(n,s) 336## s is either a numerical semigroup or an affine semigroup, and n is an 337## element of s 338## returns the graph associated to n in s in dot. 339## 340############################################################################# 341InstallMethod(DotRosalesGraph, "for numerical semigroups", [IsInt,IsNumericalSemigroup], 342function(n,s) 343 local msg, out, output, c, i, r, e; 344 msg:=Filtered(MinimalGenerators(s), g->n-g in s); 345 e:=Length(msg); 346 out := ""; 347 output := OutputTextString(out, true); 348 SetPrintFormattingStatus(output, false); 349 AppendTo(output,"graph NSGraph{\n"); 350 351 # Add vertices 352 for i in [1..e] do 353 AppendTo(output,i," [label=\"",String(msg[i]) ,"\"];\n"); 354 od; 355 356 # Add edges 357 c:=Cartesian([1..e],[1..e]); 358 c:=Filtered(c, p-> p[2]< p[1]); 359 c:=Filtered(c, p-> n-msg[p[1]]-msg[p[2]] in s); 360 361 for r in c do 362 AppendTo(output, r[1]," -- ",r[2],";\n"); 363 od; 364 365 AppendTo(output, "}"); 366 CloseStream(output); 367 return out; 368end); 369 370InstallMethod(DotRosalesGraph, "for affine semigroups", [IsHomogeneousList,IsAffineSemigroup], 371function(n,s) 372 local msg, out, output, c, i, r, e; 373 msg:=Filtered(MinimalGenerators(s), g->n-g in s); 374 e:=Length(msg); 375 out := ""; 376 output := OutputTextString(out, true); 377 SetPrintFormattingStatus(output, false); 378 AppendTo(output,"graph NSGraph{\n"); 379 380 # Add vertices 381 for i in [1..e] do 382 AppendTo(output,i," [label=\"",String(msg[i]) ,"\"];\n"); 383 od; 384 385 # Add edges 386 c:=Cartesian([1..e],[1..e]); 387 c:=Filtered(c, p-> p[2]< p[1]); 388 c:=Filtered(c, p-> n-msg[p[1]]-msg[p[2]] in s); 389 390 for r in c do 391 AppendTo(output, r[1]," -- ",r[2],";\n"); 392 od; 393 394 AppendTo(output, "}"); 395 CloseStream(output); 396 return out; 397end); 398 399############################################################################ 400## 401#O DotFactorizationGraph(f) 402## 403## f is a set of factorizations 404## returns the graph of factorizations associated to f: a complete graph 405## whose vertices are the elements of f. Edges are labelled with 406## distances between nodes they join. Kruskal algorithm is used to 407## draw in red a spannin tree with minimal distances. Thus the catenary 408## degree is reached in the edges of the tree. 409## 410############################################################################# 411InstallMethod(DotFactorizationGraph, [IsRectangularTable], 412 function(f) 413 local fs, c, nf, i, p, ln, distance, Kruskal, tv, out, output, d; 414 415 Kruskal := function(V, E) 416 local trees, needed, v, e, i,j, nv; 417 418 trees := List(V, v-> [v]); 419 needed := []; 420 nv:=Length(V); 421 for e in E do 422 i:=First([1..Length(trees)], k-> e[1] in trees[k]); 423 j:=First([1..Length(trees)], k-> e[2] in trees[k]); 424 if i<>j then 425 trees[i]:=Union(trees[i], trees[j]); 426 trees[j]:=[]; 427 Add(needed,e); 428 fi; 429 if Length(needed)=nv-1 then 430 break; 431 fi; 432 od; 433 return needed; 434 end; 435 436 distance := function(a,b) 437 local k, gcd, i; 438 439 k := Length(a); 440 if k <> Length(b) then 441 Error("The lengths of a and b are different.\n"); 442 fi; 443 444 445 gcd := []; 446 for i in [1..k] do 447 Add(gcd, Minimum(a[i],b[i])); 448 od; 449 return(Maximum(Sum(a-gcd),Sum(b-gcd))); 450 451 end; 452 453 out := ""; 454 output := OutputTextString(out, true); 455 SetPrintFormattingStatus(output, false); 456 AppendTo(output,"graph NSGraph{\n"); 457 458 nf:=Length(f); 459 fs:=[]; 460 for i in [1..nf] do 461 AppendTo(output,i," [label=\" (", JoinStringsWithSeparator(f[i], ", ") ,")\"];\n"); 462 od; 463 c:=Cartesian([1..nf],[1..nf]); 464 c:=Filtered(c,p->p[1]<p[2]); 465 Sort(c,function(e,ee) return distance(f[e[1]],f[e[2]])<distance(f[ee[1]],f[ee[2]]); end); 466 tv:=Kruskal(f,List(c,p->[f[p[1]],f[p[2]]])); 467 for p in c do 468 d:= distance(f[p[1]],f[p[2]]); 469 if [f[p[1]],f[p[2]]] in tv then 470 AppendTo(output, p[1], " -- ", p[2], "[label=\"", d ,"\", color=\"red\"];\n" ); 471 else 472 AppendTo(output, p[1], " -- ", p[2], "[label=\"", d,"\" ];\n" ); 473 fi; 474 od; 475 AppendTo(output, "}"); 476 CloseStream(output); 477 return out; 478end); 479 480 481############################################################################ 482## 483#O DotEliahouGraph(f) 484## 485## f is a set of factorizations 486## returns the Eliahou graph of factorizations associated to f: a graph 487## whose vertices are the elements of f, and there is an edge between 488## two vertices if they have common support. Edges are labelled with 489## distances between nodes they join. 490## 491############################################################################# 492InstallMethod(DotEliahouGraph, [IsRectangularTable], 493 function(f) 494 local fs, c, nf, i, p, ln, distance, tv, out, output, d; 495 496 distance := function(a,b) 497 local k, gcd, i; 498 499 k := Length(a); 500 if k <> Length(b) then 501 Error("The lengths of a and b are different.\n"); 502 fi; 503 504 505 gcd := []; 506 for i in [1..k] do 507 Add(gcd, Minimum(a[i],b[i])); 508 od; 509 return(Maximum(Sum(a-gcd),Sum(b-gcd))); 510 511 end; 512 513 out := ""; 514 output := OutputTextString(out, true); 515 SetPrintFormattingStatus(output, false); 516 AppendTo(output,"graph NSGraph{\n"); 517 518 nf:=Length(f); 519 fs:=[]; 520 for i in [1..nf] do 521 AppendTo(output,i," [label=\" (", JoinStringsWithSeparator(f[i], ", ") ,")\"];\n"); 522 od; 523 c:=Cartesian([1..nf],[1..nf]); 524 c:=Filtered(c,p->p[1]<p[2] and f[p[1]]*f[p[2]]<>0); 525 Sort(c,function(e,ee) return distance(f[e[1]],f[e[2]])<distance(f[ee[1]],f[ee[2]]); end); 526 for p in c do 527 d:= distance(f[p[1]],f[p[2]]); 528 AppendTo(output, p[1], " -- ", p[2], "[label=\"", d,"\" ];\n" ); 529 od; 530 AppendTo(output, "}"); 531 CloseStream(output); 532 return out; 533end); 534 535############################################################################ 536## 537#F SetDotNSEngine(engine) 538## 539## This sets de value of DotNSEngine to engine, which must be any of 540## the following "circo","dot","fdp","neato","osage","twopi". 541## 542############################################################################ 543InstallGlobalFunction(SetDotNSEngine, 544function(s) 545 if not(IsString(s)) then 546 Error("The argument must be a string"); 547 fi; 548 if not(s in ["circo","dot","fdp","neato","osage","twopi"]) then 549 Error("Engine not recognized"); 550 fi; 551 MakeReadWriteGlobal("DotNSEngine"); 552 DotNSEngine:=s; 553 MakeReadOnlyGlobal("DotNSEngine"); 554 return true; 555end);