X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/rocl/blobdiff_plain/843ab469ed91b5b4caa07b02be5caa71ef8d04fd..refs/heads/mdw/wip.crybaby.2016-05-05:/elite-reach

diff --git a/elite-reach b/elite-reach
index 7e72204..e44b5c3 100755
--- a/elite-reach
+++ b/elite-reach
@@ -1,45 +1,98 @@
 #! /usr/bin/tclsh
-#
-# $Id: elite-reach,v 1.3 2003/03/07 00:41:46 mdw Exp $
+###
+### Determine the connected components of the various galaxies
+###
+### (c) 2003 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program is free software; you can redistribute it and/or modify
+### it under the terms of the GNU General Public License as published by
+### the Free Software Foundation; either version 2 of the License, or
+### (at your option) any later version.
+###
+### This program is distributed in the hope that it will be useful,
+### but WITHOUT ANY WARRANTY; without even the implied warranty of
+### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+### GNU General Public License for more details.
+###
+### You should have received a copy of the GNU General Public License
+### along with this program; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 
 package require "elite" "1.0.1"
 
+###--------------------------------------------------------------------------
+### Support functions.
+
 proc reach {dist seed} {
+  ## Given a hyperspace range DIST and a galaxy SEED, determine and print the
+  ## connected components of the reachability graph.
+
+  ## Determine the graph.  Throughout, we use world seeds as indices: a(W)
+  ## maintains a list of worlds adjacent to W.  p(W) is set (to an
+  ## uninteresting value) if it's awaiting tracing.  The algorithm is simple:
+  ## repeatedly pick a world awaiting tracing, do a depth-first search of
+  ## graph starting from the chosen world adding each one encountered to the
+  ## current component and removing it from the waiting list.
   set ww [elite-galaxylist $seed]
   elite-adjacency a $ww $dist
   foreach {s x w} $ww { set p($s) 1 }
+
+  ## Initially there are no components.
   set pp {}
+
+  ## Iterate over the untraced worlds.
   while 1 {
+
+    ## Find an untraced world.  If there are none left then we're done.
     set ps [array startsearch p]
     if {![array anymore p $ps]} { array donesearch p $ps; break }
     set cc [array nextelement p $ps]
     array donesearch p $ps
+
+    ## Now we do the depth-first search.  For each world in $trace,
+    ## accumulate the untraced worlds reachable from it, and add them to the
+    ## component.  Do this until we stop tracing new worlds.
+    set trace $cc
     unset p($cc)
-    set go 1
-    while {$go} {
-      set go 0
-      foreach c $cc {
+    while {[llength $trace]} {
+      set tt $trace; set trace {}
+      foreach c $tt {
 	foreach w $a($c) {
 	  if {[info exists p($w)]} {
 	    unset p($w)
-	    lappend cc $w
-	    set go 1
+	    lappend trace $w
 	  }
 	}
       }
+      set cc [concat $cc $trace]
     }
+
+    ## We've finished the component.  Add it to the list.
     lappend pp $cc
   }
+
+  ## Output the components.
   foreach cc $pp {
+
+    ## Firstly, accumulate the summary data for all the worlds in the
+    ## component.  Also, do dead-end analysis: if there's no world in the
+    ## component with tech level 10 or higher then the component as a whole
+    ## is a `dead end', and can't be escaped by buying a galactic hyperdrive
+    ## (and you can't have one of those already, because you must have used
+    ## it to reach the component in the first pace).
     set de 1
     set l {}
     foreach c $cc {
       elite-worldinfo i $c
-      if {$i(techlevel) >= 10} {
-	set de 0
-      }
+      if {$i(techlevel) >= 10} { set de 0 }
       lappend l [world-summary $i(seed)]
     }
+
+    ## Secondly, output the component information.  Separate components using
+    ## blank lines.
     foreach n $l {
       if {$de} { append n " *" }
       puts $n
@@ -48,6 +101,11 @@ proc reach {dist seed} {
   }
 }
 
+###--------------------------------------------------------------------------
+### Main program.
+
+## Parse the command line.  The default will be to scan all of the standard
+## galaxies.
 if {[llength $argv] == 0} {
   set argv {1 2 3 4 5 6 7 8}
 }
@@ -75,7 +133,11 @@ for {set i 0} {$i < [llength $argv]} {incr i} {
     }
   }
 }
+
+## Analyse the requested galaxies.
 foreach {d ng g} $gg {
   puts "*** GALAXY $ng ***"
   reach $d $g
 }
+
+###----- That's all, folks --------------------------------------------------