Opened 18 months ago

Closed 17 months ago

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

Reported by: Owned by: slabbe major sage-9.3 graph theory Sébastien Labbé Frédéric Chapoton N/A 4cfdde3

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

### 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:

 ​f492947 31381: 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)

### 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: ↓ 16 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:

 ​e42fa04 31381: better handling of the backward orientation drawing of an edge in graphviz string ​996f29b 31381: 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

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:

 ​4cfdde3 31381: 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.

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.