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:  sage7.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: 
Description (last modified by )
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 multidigraph 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:2 Changed 6 years ago by
Description:  modified (diff) 

comment:3 Changed 6 years ago by
Branch:  → u/slabbe/21918 

Commit:  → 9bba1854eb533ae36caa3aac715dd5dd5cf7e2d5 
Status:  new → needs_review 
New commits:
9bba185  21918: adding subgraph_clusters argument to graphviz_string

comment:4 Changed 6 years ago by
Summary:  Adding subgraphs argument to graphviz_string → Adding subgraph_clusters argument to graphviz_string 

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

Cc:  Jeremias Epperlein added 
Maybe you want to review this?
comment:6 Changed 6 years ago by
Status:  needs_review → needs_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
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
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:10 Changed 6 years ago by
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.
comment:11 Changed 6 years ago by
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/dot2tex2.9.0/dot2tex/dot2tex.py local/lib/python2.7/sitepackages/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)
comment:12 Changed 6 years ago by
And the fix is not as easy as:
$ diff upstream/dot2tex2.9.0/dot2tex/dot2tex.py local/lib/python2.7/sitepackages/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/sagegit/local/lib/python2.7/sitepackages/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/sagegit/local/lib/python2.7/sitepackages/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
Status:  needs_work → needs_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
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
Reviewers:  → David Coudert 

Status:  needs_review → positive_review 
comment:17 Changed 6 years ago by
Branch:  u/slabbe/21918 → 9bba1854eb533ae36caa3aac715dd5dd5cf7e2d5 

Resolution:  → fixed 
Status:  positive_review → closed 