>This is a two part question:
>a) is there any semi-automatic way for generating xboat and other
> routes from the information on a sector map?
I am not sure how automatic this is, or if it would work on files of sector
data, but...I'll see if I can remember the algorithm.
This is totally based on graph theory, so if you're not that interested, kill
it now. Also, I have had only minimal graph theory, so if anyone catches
my errors, please post the corrections.
In any graph (vertices and edges) you can get a Minimal cost Spanning Tree by
the following algorithm:
1. set up a table listing the edges and their cost (this can be cost in
anything...i.e. time, number of jumps, length of jumps, etc.) in
INCREASING order by cost.
2. add to a separate list of edges, all edges whose addition would not create
a cycle (i.e. the ability to go in circles :-)
You now have a MST which includes all edges necessary to reach every system (or
some subset of every system, perhaps all A and B starports? ).
Example: if in a certain sector/subsector, you want to link all vertices in
the following graph into an X-boat system,
A the table for this subsector would look like:
1|\ 6 EDGE COST
2 | \ 5 ==================
G--- B C------D A-B 1
| | |6 |1 D-E 1
6| 3\ | | H-F 1
| \F------E B-G 2
H--------| 2 E-F 2
1 |3 B-F 3
| F-I 3
I C-D 5
A-C 6
G-H 6
C-F 6
The MST table would look like: The MST would look like:
EDGE COST
============== A
A-B 1 |
D-E 1 |
H-F 1 G---B C------D
B-G 2 | |
E-F 2 \ |
B-F 3 \F------E
F-I 3 H-------|
C-D 5 |
|
I
This alorithm gives the minimal cost (in whatever we measure cost in, travel
time?) for the entire tree, NOT for any specific starting/ending vertices.
I.E. following the MST route from A to C would take a cost of 12 (A-B-F-E-D-C),
while going from A to C directly, by a non-MST route would only take a cost of
6. If thecost is measured in number of weeks in jump space this represents 50%
savings in travel time. I haven't worked out the concept, but perhaps the
algorithm in this case (TRAVELLER x-boat routes) could be modified to allow
only 1 cycle per graph.
Is there anyone out there with more graph theory who could tell us the
answer? Obviously this is no longer an MST, but what is it? Also, could
this algorithm be converted to use on a computer to automatically calculate
x-boat routes from a given sector/subsector data file?
I've already gone beyond my knowledge so I pass these questions along to
the list for answers.
Paul.