Opened 13 years ago

Closed 6 years ago

#9593 closed defect (wontfix)

spring layout does not converge on some graphs

Reported by: Carl Witty Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: Robert Miller, Frédéric Chapoton Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Try the following in 4.5.2.alpha0 (or after applying #9532):

sage: G = graphs.PetersenGraph()
sage: set_random_seed(0); G.plot(layout='spring', iterations=10000)
sage: set_random_seed(0); G.plot(layout='spring', iterations=10001)

I get very different-looking graphs. (If you go back and try with iterations=10000 again, you get the same graph again, showing that #9532 did make it reproducible, at least.)

Maybe some constants need tweaking?

I think this may be causing the problem reported in the first comment on #9584.

Change History (7)

comment:1 in reply to:  description Changed 13 years ago by Leif Leonhardy

Replying to cwitty:

I think this may be causing the problem reported in the first comment on #9584.

Carl, should we fix that one here (numeric noise causing doctest failure)?

comment:2 Changed 13 years ago by Carl Witty

The story so far: #9532 tried to make spring layout reproducible (and added tests to see that it was reproducible), but it wasn't enough and so the layout is actually not reproducible across platforms. Before #9532, spring layout was totally non-reproducible.

So in my opinion, the correct thing to do for the next release is just to remove the failing doctest. Spring layout wasn't reproducible before, so nobody can be depending on it being reproducible; and it isn't now, so there's no point in a test that verifies that it is reproducible. The patch that removes the doctest should not go on this ticket (removing the doctest is not part of fixing layout convergence). When this ticket is fixed, the doctest (or a similar one) should be added, to show that spring layout then does become reproducible.

comment:3 Changed 13 years ago by Leif Leonhardy

Ok, I'll open a new ticket that simply adds a # random to that doctest.

comment:4 in reply to:  3 Changed 13 years ago by Leif Leonhardy

Replying to leif:

Ok, I'll open a new ticket that simply adds a # random to that doctest.

Oh, I completely forgot to add this here: The related doctest error in Sage 4.5.2.alpha0 is now #9594, which already has positive review. (The comment in the patch links back to this ticket, which I found more appropriate, since the # random tag can hopefully be removed again once we have reproducible spring layout.)

comment:5 Changed 7 years ago by Jori Mäntysalo

Cc: Frédéric Chapoton added
Milestone: sage-duplicate/invalid/wontfix
Status: newneeds_review

I think that this one has just forgotten to be closed. Frédéric, please click positive_review if you agree.

comment:6 Changed 7 years ago by Frédéric Chapoton

Status: needs_reviewpositive_review

ok, let us close that

comment:7 Changed 6 years ago by Erik Bray

Resolution: wontfix
Status: positive_reviewclosed

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).

Note: See TracTickets for help on using tickets.