chiark / gitweb /
Fix homology bug (!) in Net's loop highlighter.
authorSimon Tatham <anakin@pobox.com>
Mon, 29 Dec 2014 10:11:47 +0000 (10:11 +0000)
committerSimon Tatham <anakin@pobox.com>
Mon, 29 Dec 2014 10:11:47 +0000 (10:11 +0000)
commit79874f18e41cbbe796c0252dc96a85e150af1a15
treecbb47c21741b35088ea26306385c66ad219362be
parent546fbe6774ce4c8b630f33a341963a77e1e151e4
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 .
net.c