Opened 6 years ago

Closed 6 years ago

#21918 closed enhancement (fixed)

Adding subgraph_clusters argument to graphviz_string

Reported by: Sébastien Labbé Owned by:
Priority: major Milestone: sage-7.5
Component: graph theory Keywords: days79
Cc: Jeremias Epperlein Merged in:
Authors: Sébastien Labbé Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 9bba185 (Commits, GitHub, GitLab) Commit: 9bba1854eb533ae36caa3aac715dd5dd5cf7e2d5
Dependencies: Stopgaps:

Status badges

Description (last modified by Sébastien Labbé)

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)

Change History (17)

comment:1 Changed 6 years ago by Sébastien Labbé

Description: modified (diff)

comment:2 Changed 6 years ago by Sébastien Labbé

Description: modified (diff)

comment:3 Changed 6 years ago by Sébastien Labbé

Branch: u/slabbe/21918
Commit: 9bba1854eb533ae36caa3aac715dd5dd5cf7e2d5
Status: newneeds_review

New commits:

9bba18521918: adding subgraph_clusters argument to graphviz_string

comment:4 Changed 6 years ago by Sébastien Labbé

Summary: Adding subgraphs argument to graphviz_stringAdding subgraph_clusters argument to graphviz_string

comment:5 Changed 6 years ago by Sébastien Labbé

Authors: Sébastien Labbé
Cc: Jeremias Epperlein added

Maybe you want to review this?

comment:6 Changed 6 years ago by David Coudert

Status: needs_reviewneeds_work

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)

comment:7 Changed 6 years ago by Sébastien Labbé

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...

comment:8 Changed 6 years ago by Sébastien Labbé

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}

comment:9 Changed 6 years ago by David Coudert

Do you understand why?

comment:10 Changed 6 years ago by Sébastien Labbé

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.

Last edited 6 years ago by Sébastien Labbé (previous) (diff)

comment:11 Changed 6 years ago by Sébastien Labbé

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)
Last edited 6 years ago by Sébastien Labbé (previous) (diff)

comment:12 Changed 6 years ago by Sébastien Labbé

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

comment:13 Changed 6 years ago by Sébastien Labbé

Status: needs_workneeds_review

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.

comment:14 Changed 6 years ago by David Coudert

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

For me this patch is good to go.

comment:15 Changed 6 years ago by David Coudert

Reviewers: David Coudert
Status: needs_reviewpositive_review

comment:16 Changed 6 years ago by Sébastien Labbé

I created #22070 for the dot2tex issue.

comment:17 Changed 6 years ago by Volker Braun

Branch: u/slabbe/219189bba1854eb533ae36caa3aac715dd5dd5cf7e2d5
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.