Opened 18 months ago

Closed 17 months ago

Last modified 12 months ago

#31381 closed defect (fixed)

Fix the handling of the orientation of edges provided by the edge_option of G.graphviz_string

Reported by: slabbe Owned by:
Priority: major Milestone: sage-9.3
Component: graph theory Keywords:
Cc: Merged in:
Authors: Sébastien Labbé Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 4cfdde3 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by slabbe)

The documentation of G.graphviz_string says:

sage: f(x) = -1 / x
sage: g(x) = 1 / (x + 1)
sage: G = DiGraph()
sage: G.add_edges((i, f(i), f) for i in (1, 2, 1/2, 1/4))
sage: G.add_edges((i, g(i), g) for i in (1, 2, 1/2, 1/4))

[...]

sage: def edge_options(data):
....:     u, v, label = data
....:     options = {"color": {f: "red", g: "blue"}[label]}
....:     if (u,v) == (1/2, -2): options["label"]       = "coucou"; options["label_style"] = "string"
....:     if (u,v) == (1/2,2/3): options["dot"]         = "x=1,y=2"
....:     if (u,v) == (1,   -1): options["label_style"] = "latex"
....:     if (u,v) == (1,  1/2): options["edge_string"] = "<-"
....:     if (u,v) == (1/2,  1): options["backward"]    = True
....:     return options
sage: print(G.graphviz_string(edge_options=edge_options))  # random
digraph {                                                                                           
  node_0  [label="-1"];                      
  node_1  [label="-1/2"];          
  node_2  [label="1/2"];            
  node_3  [label="-2"];                                                                             
  node_4  [label="1/4"];            
  node_5  [label="-4"];             
  node_6  [label="1/3"];             
  node_7  [label="2/3"];
  node_8  [label="4/5"];                          
  node_9  [label="1"];                            
  node_10  [label="2"];                                                                             
                                                  
  node_2 -> node_3 [label="coucou", color = "red"];                  
  node_2 -> node_7 [x=1,y=2, color = "blue"];     
  node_4 -> node_5 [color = "red"];               
  node_4 -> node_8 [color = "blue"];              
  node_9 -> node_0 [label=" ", texlbl="$x \ {\mapsto}\ -\frac{1}{x}$", color = "red"];
  node_9 <- node_2 [color = "blue"];
  node_10 -> node_1 [color = "red"];
  node_10 -> node_6 [color = "blue"];
}

The above output is invalid according to the dot language because <- is not allowed (http://www.graphviz.org/doc/info/lang.html). Processing it with graphviz + dot2tex, for example using the TikzPicture module of the slabbe package, we obtain a broken image:

sage: from slabbe import TikzPicture
sage: TikzPicture.from_graph(G, edge_options=edge_options).pdf()

Compared to:

sage: TikzPicture.from_graph(G).pdf()

In this ticket, we fix the above by returning a ValueError if the edge_string is invalid with respect to the dot language.

We also improve the code by allowing the user to choose the direction of each edge to be none, forward, backward or both as explained here http://www.graphviz.org/doc/info/attrs.html#k:dirType:

sage: edges = [(0,1,'a'), (1,2,'b'), (2,3,'c'), (3,4,'d')]                             
sage: G = DiGraph(edges)          
sage: def edge_options(data): 
....:     u,v,label = data 
....:     if label == 'a': return {'dir':'forward'} 
....:     if label == 'b': return {'dir':'back'} 
....:     if label == 'c': return {'dir':'none'} 
....:     if label == 'd': return {'dir':'both'} 
sage: print(G.graphviz_string(edge_options=edge_options))                          
digraph {
  node_0  [label="0"];
  node_1  [label="1"];
  node_2  [label="2"];
  node_3  [label="3"];
  node_4  [label="4"];

  node_0 -> node_1;
  node_1 -> node_2 [dir=back];
  node_2 -> node_3 [dir=none];
  node_3 -> node_4 [dir=both];
}
sage: TikzPicture.from_graph(G, edge_options=edge_options).pdf()                                         

As a consequence, we deprecate {'backward':True} in favor of the more versatile {'dir':'back'}.

Attachments (4)

example1.png (9.9 KB) - added by slabbe 18 months ago.
example2.png (10.9 KB) - added by slabbe 18 months ago.
example3.png (9.2 KB) - added by slabbe 18 months ago.
example4.png (1.5 KB) - added by slabbe 18 months ago.

Download all attachments as: .zip

Change History (30)

Changed 18 months ago by slabbe

Changed 18 months ago by slabbe

Changed 18 months ago by slabbe

comment:1 Changed 18 months ago by slabbe

  • Description modified (diff)

comment:2 Changed 18 months ago by slabbe

  • Description modified (diff)

comment:3 Changed 18 months ago by slabbe

According to the DOT language description, -- is the format for an edge of a graph and -> is the format for an edge of a digraph and nothing else.

Therefore, it is a bug in the documentation to suggest <- or -- for digraph.

Moreover, according to the thread Graphviz Dot, mix directed and undirected on stackoverflow, it seems that the proper way to remove the headarrow for one edge of a digraph to set dir=none.

Therefore, the edge_option should allow one to set dir=none.

comment:4 Changed 18 months ago by slabbe

Moreover, according to http://www.graphviz.org/doc/info/attrs.html#k:dirType, the possible values for the direction of an edge are none, forward, back and both. The default for a graph is none and the default for a digraph is forward.

comment:5 Changed 18 months ago by slabbe

  • Branch set to u/slabbe/31381
  • Commit set to f492947f87de8cbe41a17080fad0dab162f1fd48

New commits:

f49294731381: better handling of the backward orientation drawing of an edge in graphviz string

comment:6 Changed 18 months ago by slabbe

  • Description modified (diff)

comment:7 Changed 18 months ago by slabbe

  • Description modified (diff)

Changed 18 months ago by slabbe

comment:8 Changed 18 months ago by slabbe

  • Description modified (diff)
  • Status changed from new to needs_review

comment:9 Changed 18 months ago by slabbe

  • Description modified (diff)
  • Summary changed from Edge option "--" of G.graphviz_string method output is ignored to Fix the handling of the orientation of edges provided by the edge_option of G.graphviz_string

comment:10 Changed 18 months ago by slabbe

  • Description modified (diff)

comment:11 Changed 18 months ago by slabbe

  • Description modified (diff)

comment:12 Changed 18 months ago by slabbe

  • Authors set to Sébastien Labbé

comment:13 follow-up: Changed 18 months ago by chapoton

doc does not build, see patchbot

comment:14 Changed 18 months ago by git

  • Commit changed from f492947f87de8cbe41a17080fad0dab162f1fd48 to 996f29beb45ff506eedb1847b832df2c2866c746

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e42fa0431381: better handling of the backward orientation drawing of an edge in graphviz string
996f29b31381: fixing docstring : -> :: at one place

comment:15 Changed 18 months ago by slabbe

I rebased the branch on top of the most recent development version and replaced one : by ::.

comment:16 in reply to: ↑ 13 Changed 18 months ago by slabbe

Replying to chapoton:

doc does not build, see patchbot

looks good now

comment:17 Changed 18 months ago by chapoton

ok, good, but "misspelled" takes 2 s

comment:18 Changed 18 months ago by git

  • Commit changed from 996f29beb45ff506eedb1847b832df2c2866c746 to 4cfdde3859985728d45497d1459b99d29ddafb04

Branch pushed to git repo; I updated commit sha1. New commits:

4cfdde331381: misspelled 'misspelled'

comment:19 Changed 18 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok.

Pour info, juste pousser une branche git n'envoie pas de mail, donc ne prévient pas les participants au ticket.

comment:20 Changed 18 months ago by slabbe

ok

Merci Frédéric!

comment:21 Changed 17 months ago by vbraun

  • Branch changed from u/slabbe/31381 to 4cfdde3859985728d45497d1459b99d29ddafb04
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:22 Changed 12 months ago by tscrim

  • Commit 4cfdde3859985728d45497d1459b99d29ddafb04 deleted

I was not paying enough attention in #31719. The result is now that the arrows are backwards rather than being an indication that the arrows should be considered as moving in the opposite direction for the layout. The key change was not adding back in this line:

if edge_options['backward']:
    v,u = u,v    # <------------------------------
    dot_options.append('dir=back')

So implementing the deprecation message is actually giving a change in the behavior. This feature is really useful in having nicer layout for KR crystals.


The question is what to do going forward. Should we have dir='back' implement the old behavior or add back in the backward input for what will be distinct behavior?

comment:23 Changed 12 months ago by slabbe

While working on this ticket, I spent a lot of time thinking about all cases and tested all of them. To me, there was a bug in the backward=True code. To my opinion, the line u,v=v,u is changing the graph and should not be done inside a method which just draws it. I think if the user really want to change the graph, the user should do this before drawing it.

If I well remember (it is too bad I did not copy pasted an example here), the option backward=True was not working at all. Because swapping u and v and setting dir=back was like doing nothing for showing a digraph. After this ticket, writting dir=back really does dir=back as understood by the dot language.

What happens if in #31719 you instead just removed the backward=True as follows?

             G = Crystals().parent_class.digraph(self, subset, index_set)
-            if have_dot2tex():
-                f = lambda u_v_label: ({"backward": u_v_label[2] == 0})
-                G.set_latex_options(edge_options=f)
             return G

comment:24 Changed 12 months ago by tscrim

It was not a bug at all. The major effect was the layout, and it was something that was documented. When drawing the digraphs, it tries to make all of the arrows pointing downward. The classical crystals are posets, so it is okay. Now the KR crystals are those posets plus some extra arrows that go in the wrong direction. With that option, it would basically just add them in without altering the layout. If we remove that option, then what happens is those special backwards arrows are no longer special, so the layout is much more difficult to read.

We do not want to change the digraph either because the arrows carry mathematical meaning. So it would need to be done locally within the latex construction. Hence we arrive at what the code was doing before.

comment:25 Changed 12 months ago by slabbe

Ok, I see. Then, it was a mistake from me. I am sorry. I think we should then add back the backward option.

comment:26 Changed 12 months ago by tscrim

No problem. I should have caught it when I was doing #31719. This is now #32438.

Note: See TracTickets for help on using tickets.