ref: efda6cff49e7579b5c10b16694ac57340ce2fc2b
parent: 72989cdf1d73b371fec933e905c5482d709ec6bb
author: Simon Tatham <anakin@pobox.com>
date: Sat Sep 10 05:39:29 EDT 2005
Completely rewrite the loop-detection algorithm used to check game completion, _again_. In r6174 I changed it from dsf to conventional graph theory so that it could actually highlight loops as opposed to just discovering that one existed. Unfortunately, yesterday I discovered a fundamental graph-theoretic error in the latter algorithm: if you had two entirely separate loops connected by a single path, the path would be highlighted as well as the loops. Therefore, I've reverted to the original dsf technique, combined with a subsequent pass to trace around each loop discovered. This version seems to do a better job of only highlighting the actual loops. [originally from svn r6283] [r6174 == 2bd8e241a93165a99f5e2c4a2dd9c3b3b1e3c6f3]