Adding subgraph_clusters argument to graphviz_string

[seblabbe]

We define some graph. It is the both sided Cayley graph of the monoid generated by two partial maps (defined in Chapter 5 Green’s relations and local theory of the book by Jean Éric Pin):

sage: S = FiniteSetMaps(5)
sage: I = S((0,1,2,3,4))
sage: a = S((0,1,3,0,0))
sage: b = S((0,2,4,1,0))
sage: roots = [I]
sage: succ = lambda v:[v*a,v*b,a*v,b*v]
sage: R = RecursivelyEnumeratedSet(roots, succ)
sage: G = R.to_digraph()
sage: G
Looped multi-digraph on 27 vertices

We view the graph:

sage: G.latex_options().set_options(prog='dot',format='dot2tex')
sage: view(G, tightpage=True)

We view it using dot language subgraphs clusters (here the strongly connected components) and also using optional package dot2tex:

sage: G.latex_options().set_options(prog='dot',format='dot2tex')
sage: C = G.strongly_connected_components()
sage: G.latex_options().set_options(subgraph_clusters=C)
sage: view(G, tightpage=True)

CC: @JeremiasE

Component: graph theory

Keywords: days79

Author: Sébastien Labbé

Branch/Commit: 9bba185

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/21918

[seblabbe]

New commits:

9bba185

21918: adding subgraph_clusters argument to graphviz_string

[seblabbe]

Branch: u/slabbe/21918

[seblabbe]

Commit: 9bba185

[seblabbe]

comment:5

Maybe you want to review this?

[seblabbe]

Author: Sébastien Labbé

[dcoudert]

comment:6

The patch is working well, except when we set edge_labels=True. Is such case, the vertices are effectively grouped by clusters, but the boxes around the clusters are not drawn.

sage: G = digraphs.Kautz(3, 2)
sage: C = [[u for u in G.vertices() if int(u[0])==l] for l in range(4)]
sage: G.latex_options().set_options(prog='dot',format='dot2tex', subgraph_clusters=C)
sage: view(G, tightpage=True)
sage: G = digraphs.Kautz(3, 2)
sage: G.latex_options().set_options(prog='dot',format='dot2tex', edge_labels=True, subgraph_clusters=C)
sage: view(G, tightpage=True)
sage: G = digraphs.Kautz(3, 2)
sage: G.latex_options().set_options(prog='dot',format='dot2tex', color_by_label=True, subgraph_clusters=C)
sage: view(G, tightpage=True)
sage: G = digraphs.Kautz(3, 2)
sage: G.latex_options().set_options(prog='dot',format='dot2tex', color_by_label=True, edge_labels=True, subgraph_clusters=C)
sage: view(G, tightpage=True)

[seblabbe]

comment:7

Indeed, but graphviz seems to create the boxes correctly:

sage: G = digraphs.Kautz(3, 2)
sage: C = [[u for u in G.vertices() if int(u[0])==l] for l in range(4)]
sage: with open('file.dot', 'w') as f:
....:     f.write(G.graphviz_string(edge_labels=True, subgraph_clusters=C, color_by_label=True))
....: 
sage: !dot file.dot -Tpdf -ofile.pdf
sage: !open file.pdf

so maybe it is a problem in dot2tex. I will see if I can find a workaround...

[seblabbe]

comment:8

I was able to construct a small example showing the bug:

edges = [(i,(i+1)%3,a) for i,a in enumerate('abc')]
G_no_labels = DiGraph(edges)
G_with_labels = DiGraph(edges)
C = [[0,1], [2]]
kwds = dict(subgraph_clusters=C,color_by_label=True,prog='dot',format='dot2tex')
G_no_labels.latex_options().set_options(edge_labels=False, **kwds)
G_with_labels.latex_options().set_options(edge_labels=True, **kwds)

With no labels, each cluster is constructed within a scope including a \filldraw line:

sage: latex(G_no_labels)
\begin{tikzpicture}[>=latex,line join=bevel,]
%%
\begin{scope}
  \pgfsetstrokecolor{black}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \definecolor{fillcol}{rgb}{0.94,1.0,1.0};
  \pgfsetfillcolor{fillcol}
  \filldraw (8.0bp,57.0bp) -- (8.0bp,135.0bp) -- (36.0bp,135.0bp) -- (36.0bp,57.0bp) -- cycle;
\end{scope}
\begin{scope}
  \pgfsetstrokecolor{black}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \definecolor{fillcol}{rgb}{0.94,1.0,1.0};
  \pgfsetfillcolor{fillcol}
  \filldraw (17.0bp,8.0bp) -- (17.0bp,37.0bp) -- (45.0bp,37.0bp) -- (45.0bp,8.0bp) -- cycle;
\end{scope}
...
\end{tikzpicture}

With labels, some \filldraw line is missing in one of the scope:

sage: latex(G_with_labels)
\begin{tikzpicture}[>=latex,line join=bevel,]
%%
\begin{scope}
  \pgfsetstrokecolor{black}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \definecolor{fillcol}{rgb}{0.94,1.0,1.0};
  \pgfsetfillcolor{fillcol}
\end{scope}
\begin{scope}
  \pgfsetstrokecolor{black}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \definecolor{fillcol}{rgb}{0.94,1.0,1.0};
  \pgfsetfillcolor{fillcol}
  \filldraw (25.0bp,8.0bp) -- (25.0bp,37.0bp) -- (53.0bp,37.0bp) -- (53.0bp,8.0bp) -- cycle;
\end{scope}
...
\end{tikzpicture}

[dcoudert]

comment:9

Do you understand why?

[seblabbe]

comment:10

Not yet. My first hypothesis was: it works when the size of the cluster is one. But it turns out to be false when I constructed another example where bigger cluster were drawn. Next thing I want to do is check dot2tex code to see why \filldraw is missing.

[seblabbe]

comment:11

The only place where \filldraw appears in dot2tex.py file is inside the method draw_polygon. The only place where draw_polygon is called is in method do_draw_op which does something like:

            if op in ['e', 'E']:
                s += self.draw_ellipse(drawop, style)
            elif op in ['p', 'P']:
                s += self.draw_polygon(drawop, style)
            elif op == 'L':
                s += self.draw_polyline(drawop, style)
            elif op in ['C', 'c']:
                s += self.set_color(drawop)
            elif op == 'S':
                s += self.set_style(drawop)
            elif op in ['B']:
                s += self.draw_bezier(drawop, style)
            elif op in ['T']:
                ...
                many lines
                ...
                s += self.draw_text(drawop, lblstyle)
         return s

with no else: clause!! So, I did this change:

$ diff upstream/dot2tex-2.9.0/dot2tex/dot2tex.py local/lib/python2.7/site-packages/dot2tex/dot2tex.py
607a608,609
>             else:
>                 raise ValueError("Unknown op(={})".format(op))

and I get:

sage: _ = latex(G_no_labels)       # no errors
sage: _ = latex(G_with_labels)
Traceback (most recent call last):
...
ValueError: Unknown op(=F)

[seblabbe]

comment:12

And the fix is not as easy as:

$ diff upstream/dot2tex-2.9.0/dot2tex/dot2tex.py local/lib/python2.7/site-packages/dot2tex/dot2tex.py
543c543
<             elif op in ['p', 'P']:
---
>             elif op in ['p', 'P', 'F']:
607a608,609
>             else:
>                 raise ValueError("Unknown op(={})".format(op))

because

sage: _ = latex(G_with_labels)
...
/home/labbe/Applications/sage-git/local/lib/python2.7/site-packages/dot2tex/dot2tex.py in do_draw_op(self, drawoperations, drawobj, stat, texlbl_name, use_drawstring_pos)
    542                 s += self.draw_ellipse(drawop, style)
    543             elif op in ['p', 'P', 'F']:
--> 544                 s += self.draw_polygon(drawop, style)
    545             elif op == 'L':
    546                 s += self.draw_polyline(drawop, style)

/home/labbe/Applications/sage-git/local/lib/python2.7/site-packages/dot2tex/dot2tex.py in draw_polygon(self, drawop, style)
   1735 
   1736     def draw_polygon(self, drawop, style=None):
-> 1737         op, points = drawop
   1738         pp = ['(%sbp,%sbp)' % (smart_float(p[0]), smart_float(p[1])) for p in points]
   1739         cmd = "draw"

ValueError: too many values to unpack

[seblabbe]

comment:13

In summary, the bug reported by the reviewer when edge_labels=True really belongs to dot2tex. The method graphviz_string that is enhanced in this ticket works correctly as confirmed by running dot on the dot string output by graphviz_string (see comment 7). Therefore, if David you agree, I suggest to open another ticket to deal with that missing \filldraw line and continue the review of this ticket independently of that dot2tex bug.

[dcoudert]

comment:14

I agree with you to open an independent ticket to fix the dot2tex issue.

For me this patch is good to go.

[dcoudert]

Reviewer: David Coudert

[seblabbe]

comment:16

I created #22070 for the dot2tex issue.

[vbraun]

Changed branch from u/slabbe/21918 to 9bba185