ref: 79874f18e41cbbe796c0252dc96a85e150af1a15
parent: 546fbe6774ce4c8b630f33a341963a77e1e151e4
author: Simon Tatham <anakin@pobox.com>
date: Mon Dec 29 05:11:47 EST 2014
Fix homology bug (!) in Net's loop highlighter. I unthinkingly transplanted into Net the same loop-finding algorithm used in Loopy and Slant, which identifies the connected components into which the grid lines divide the plane, and marks an edge as part of a loop iff it separates two different components. This works fine for a planar graph, but in Net's wrapping mode, it's possible to have loops which do not have this property - e.g. a loop can go off the top of the grid and back on the bottom to join up with itself, and then it _doesn't_ disconnect the surface into two components. (In principle, this kind of problem can turn up in any topological space with a non-trivial H_1 homology group, which is why it fails on the torus to which Net's wrapping mode corresponds, but not on the plane or sphere. I think it's forgivable that I hadn't expected homology to be the cause of any bug in practical code ever!) Fixed by inventing yet another dsf-based loop-finding algorithm, this one based on tracing round the outside of connected components of the graph. It's still not _fully_ general, in that this one still depends on the graph being drawn on an orientable surface (so it'll need another rewrite if I ever add Mobius strip or Klein bottle modes for Net...), but it's fairly simple to state and implement, and detects loops that the previous implementation did not, such as the one in the starting position of 3x3w:1a39ac6a8 .