Opened 10 years ago

Closed 10 years ago

#10124 closed defect (fixed)

Graph drawing has issues with edge labels

Reported by: rs Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-4.7
Component: graph theory Keywords: graph drawing, edge labels
Cc: jason Merged in: sage-4.7.alpha5
Authors: Douglas McNeil Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by nthiery)

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.

Attachments (2)

trac_10124_fix_edge_label_locations.patch (8.4 KB) - added by dsm 10 years ago.
trac_10124_fix_edge_label_locations_v2.patch (11.0 KB) - added by dsm 10 years ago.
version with (hopefully) fixed colons

Download all attachments as: .zip

Change History (13)

comment:1 Changed 10 years ago by jason

  • Cc jason added

comment:2 Changed 10 years ago by nthiery

  • Description modified (diff)

comment:3 follow-up: Changed 10 years ago by dsm

  • Authors set to Douglas McNeil
  • Status changed from new to 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 10 years ago by dsm

Replying to 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 10 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to 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: Changed 10 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 10 years ago by ncohen

Replying to 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?

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 10 years ago by dsm

version with (hopefully) fixed colons

comment:8 Changed 10 years ago by dsm

  • Status changed from needs_work to needs_review

comment:9 Changed 10 years ago by ncohen

  • Status changed from needs_review to positive_review

Theeeeeeeeen it's good to go :-)

Nathann

comment:10 Changed 10 years ago by jdemeyer

  • Milestone set to sage-4.7

comment:11 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.