#10124: Graph drawing has issues with edge labels
------------------------------+---------------------------------------------
Reporter: rs | Owner: jason, ncohen, rlm
Type: defect | Status: needs_review
Priority: minor | Milestone:
Component: graph theory | Keywords: graph drawing, edge labels
Author: Douglas McNeil | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------------+---------------------------------------------
Changes (by newvalueoldvalue):
* status: new => needs_review
* author: => Douglas McNeil
Comment:
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10124#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
