Opened 12 years ago

Closed 12 years ago

# Graph drawing has issues with edge labels

Reported by: Owned by: rs jason, ncohen, rlm minor sage-4.7 graph theory graph drawing, edge labels jason sage-4.7.alpha5 Douglas McNeil Nathann Cohen N/A

The following code should produce a drawing of the Frucht graph with edges labeled 0 upto 17. However, labels 16 and 17 are missing, while 15 is misplaced. The edge labels are set correctly (as the last line shows), they only don't show up. The weird thing is that other graphs work OK (at least those I tried).

```sage:   G=graphs.FruchtGraph()
sage:   E=G.edges()
sage:   for i in range(len(E)):
....:           G.set_edge_label(E[i][0],E[i][1],i)
....:
sage:   G.show(edge_labels=True)
sage:   print G.edges()
```

It seems it happens rather rarely, so I'm not sure if it's an issue with this graph's constructor or with the graph drawing algorithm. Anyway, it would be nice to have this feature reliable, I find it very useful.

### comment:2 Changed 12 years ago by nthiery

Description: modified (diff)

### comment:3 follow-up:  4 Changed 12 years ago by dsm

Authors: → Douglas McNeil new → needs_review

This turns out to be because the edge label locations are computed by

```[(self._pos[a][0]+self._pos[b][0])/2, (self._pos[a][1]+self._pos[b][1])/2]
```

so if the positions are Python integers (as happens for many of the graphs in graph_generators.py), the divisions will truncate and the labels wind up in the wrong locations.

This can be fixed by replacing 2 with 2., but that's pretty fragile, as there are other instances in graph_plot.py where it looks like the same problem can occur:

```                    p1 = self._pos[a]
p2 = self._pos[b]
M = ((p1[0]+p2[0])/2, (p1[1]+p2[1])/2) # midpoint
if not p1[1] == p2[1]:
S = (p1[0]-p2[0])/(p2[1]-p1[1]) # perp slope
```

Moreover, since the user could be using a custom layout method, we can't guarantee that the positions are floats on that side. So it seems the most robust solution is to ensure that _pos contains floats in graph_plot itself. This only takes between 1-10 ms for a graph with 1000 nodes which takes seconds to plot, so the added time is negligible.

I've attached a patch which

(1) modifies set_pos, which is always called by GraphPlot?.init, to ensure that _pos contains float values; this suffices to handle both the original case and some related multiedge bugs

(2) float-protects real divisions throughout the file (some are genuinely integer divisions meant to be truncating, e.g. len(local_labels)/2, where dealing with the possible remainder of 1 is handled explicitly), even where I don't know for certain that there's a realized path which could break. This way even if _pos were somehow changed after construction, set_edges would still behave as intended.

(3) adds doctests to set_pos, set_edges, and _polar_hack_for_multidigraph to verify the new behaviour. Coming up with a doctest for set_edges was a bit of a challenge, so if there's a more natural way to do the test it should probably be replaced.

(4) fixes a typo.

The patch passes all tests in graphs and beneath; am running testall long now.

### comment:4 in reply to:  3 Changed 12 years ago by dsm

The patch passes all tests in graphs and beneath; am running testall long now.

Works for me with 4.6.2.rc0. Still have the usual "Detected SAGE64" noise, etc., but no new failures.

### comment:5 Changed 12 years ago by ncohen

Reviewers: → Nathann Cohen needs_review → needs_work

Hello ! `:-)`

This can get in as soon as you can add another semicolumn at the end of

```in some cases where they weren't due to truncating division (trac #10124):
```

Nathann

### comment:6 follow-up:  7 Changed 12 years ago by dsm

Aargh, these colons will be the death of me.  But it looks like there are a lot of colon problems: there are several "EXAMPLE:" / "EXAMPLES:" cases with code immediately after, and shouldn't those have two as well?

### comment:7 in reply to:  6 Changed 12 years ago by ncohen

Aargh, these colons will be the death of me.  But it looks like there are a lot of colon problems: there are several "EXAMPLE:" / "EXAMPLES:" cases with code immediately after, and shouldn't those have two as well?

Yep, each time you have some code there should be a double column before. If not, it does not appear nicely in the documentation when you build it

```sage -docbuild reference html
```

though I think they are still tested by sage -t... If you feel like fixing those you meet..... `:-)`

Nathann

### Changed 12 years ago by dsm

version with (hopefully) fixed colons

### comment:8 Changed 12 years ago by dsm

Status: needs_work → needs_review

### comment:9 Changed 12 years ago by ncohen

Status: needs_review → positive_review

Theeeeeeeeen it's good to go `:-)`

Nathann

### comment:10 Changed 12 years ago by jdemeyer

Milestone: → sage-4.7

### comment:11 Changed 12 years ago by jdemeyer

Merged in: → sage-4.7.alpha5 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.