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);