split left symmetric and I hope it works.Still fails on lin105.Revision 1.124  96/09/13  13:06:24  netoMore debugging output.Reach case 2 when psa=psb=0, psc=psd=1.  Mabye need to enforce 4 or moregroups?Revision 1.123  96/09/13  12:13:11  netoAdded updating of sequence numbers in Case 1.  Oops.Revision 1.122  96/09/13  11:54:30  netoMore checks of the twolevel data structure.Revision 1.121  96/09/12  16:46:05  netoMore debugging output. Somewhere, sequence numbers aren't properly beingmaintained.Revision 1.120  96/09/12  15:45:50  netoEnsure that modulus returns non-negative result in the important places.Revision 1.119  96/09/12  15:38:02  netoFixed debugging stuff a bit.Revision 1.118  96/09/12  14:18:09  netoFinished the redundancy code to check two-level trees.It compiles too, and catches an error in lin105.Revision 1.117  96/09/11  17:18:51  netoStarted adding debugging code.Revision 1.116  96/09/10  16:51:35  netoFixed problem in creating the data structure.  We need to compute a new group size internally.Revision 1.115  96/09/10  15:57:58  netoNow it compiles.  (Two minor errors regarding the normalization macro.)Revision 1.114  96/09/10  15:55:03  netoFixed the parent renumbering.It TeXs to my satisfaction.  We'll see if it compiles.Revision 1.113  96/09/09  17:06:05  netoFixed some of the problem with interening in parents.Need to fix the parent sequence number updating.Revision 1.112  96/09/06  16:03:10  netoFixed problem in flipping, case 1. We might have had portion b-d contained in a-c.Still a problem in parents.  See research notes.Also, need to add a comment about avoiding a performance bug inchoosing shorter sequence of parents.Revision 1.111  96/09/05  16:05:43  netoNow it compiles cleanly.Fixed precedence problems, vestiges of the ``city'' field, accessingwrong link array, variables declared twice, suggested parentheses, etc.Revision 1.110  96/09/05  15:37:22  netoFinished coding flipping.Revision 1.109  96/09/05  14:15:41  netoFixed outbound sibling pointers in city list reversal.Revision 1.108  96/09/05  12:53:55  netoCheck for case 1 after split c-d.Revision 1.107  96/09/04  17:14:23  netoFinished coding Case 3 of flipping.Revision 1.106  96/09/03  17:06:17  netoFinished coding case 1 in flip.Revision 1.105  96/09/03  15:45:52  netoMade city numbers implicit, as per first paragraph of p. 444 ofFredman et al.Revision 1.104  1996/08/30  21:28:38  davidMore of flip.Revision 1.103  1996/08/30  20:38:17  davidUse plain sequence numbers and still protect against wraparound.Revision 1.102  1996/08/30  20:28:16  davidLots and lots and lots of coding.Revision 1.101  1996/08/23  20:55:43  davidInitial revision.}@@*A two-level tree implementation of the oriented tour ADT.This module implements the oriented tour ADT using two-level trees.These were introduced by M.~L.~Fredman, D.~S.~Johnson, L.~A.~McGeoch,and G.~Ostheimer in {\sl Data Structures for Traveling Salesmen}, Journal of Algorithms, {\bf 18}, 432--479 (1995), (andan earlier conference paper).  @@^Fredman, M.~L.@@>@@^Johnson, D.~S.@@>@@^McGeoch, L.~A.@@>@@^Ostheimer, G.@@>That paper introduces three new data structures for the oriented tourADT: splay trees, two-level trees, and segment trees.  These threeare compared with the traditional array-based representation.  Some broad conclusions are drawn:below a thousand cities, arrays are the fastest; between a thousand  and a million cities, two-leveltrees are best; above a million, splay trees appear to win out.This module implements the oriented tour ADT in terms of two-level trees.Just like the \module{ARRAY} module, only one tour is supported at atime, although it shouldn't be too hard to make this code purely object-oriented.@@ Fredman \etal.~define an oriented tour abstract data type supportingthree queries and one update operation.  The most common and effectivelocal search algorithms for the traveling salesman problem ---2-opt, 3-opt, and Lin-Kernighan--- may all be implemented in terms of this abstraction.@@^oriented tour ADT@@>The oriented tour ADT consists of the following operations(I will use the names as implemented in this module, \ie, prepended bythe word |twolevel_|.):|twolevel_next(a)| is a query that returns the city that follows $a$ in thecurrent tour.|twolevel_prev(a)| is a query that returns the city that precedes $a$ in thecurrent tour.  It must be the case that |next(prev(a))==prev(next(a))==a|.|twolevel_between(a,b,c)| is a query that returns true or false.  It answersthe question:  ``In a forward traversal starting at city $a$, do we reachcity $b$ no later than city $c$?''|twolevel_flip(a,b,c,d)| updates the tour by replacing the edges $(a,b)$ and$(c,d)$ by the edges $(b,c)$ and $(a,d)$.  It assumes that |a==next(b)| and |d==next(c)|.  The orientation of the updated touris not specified.These four operations are the ones defined by Fredman \etal.  In fact, Ihave lifted these descriptions from that paper and lightly edited themfor inclusion here.  For convenience's sake, I also define |twolevel_set(int *t)|, whichsets the current tour to be the same as the array ofintegers |t|.  That is, city |i| in the tour is city |t[i]|.Note that we don't need a ``get'' routine because the tour can be read offby successively following |next| cities until we wrap to the startagain.We also define the standard setup and clean procedures: |twolevel_setup(int n, int seg_start_size)|and|twolevel_cleanup(void)|.  The parameters to the setup procedure is the numberof cities in the instance and the starting segment size (see below).@@ The outline of this module is as follows:@@c#include <config.h>#include "lkconfig.h"@@<System headers@@>@@;@@<Module headers@@>@@;@@<Module type definitions@@>@@;@@<Module variables@@>@@;@@<Module prototypes@@>@@;@@<Subroutines@@>@@;const char *twolevel_rcs_id="$Id: twolevel.w,v 1.144 1997/09/27 18:04:13 neto Exp neto $";@@ We will be using many routines from external libraries.  The interfacesto those routines are described in the following headers.@@<System headers@@>=#include <stdio.h>#include <stdlib.h>#include <stddef.h>@@ The exported interface is contained in the \file{twolevel.h} header file,which has the following form.@@(twolevel.h@@>=extern const char *twolevel_rcs_id;@@<Exported subroutines@@>@@;@@ To ensure consistency between the interface and the implementation,we include our own header.@@<Module headers@@>=#include "twolevel.h"@@*Two-level trees.A two-level tree on $n$ cities is much like a B+tree of degree $\sqrt{n}$.That is, the tour is stored as a linked list of cities.  They are clustered into into $\sqrt{n}$ segments of $\sqrt{n}$ cities each.Each segment is represented at the root level by aparent node. The roughly $\sqrt{n}$ parentnodes are themselves organized in a doubly linked list.To facilitate ordering comparisons, the parent nodes are given consecutivesequence numbers, and city nodes are given consecutive sequence numberswithin the context of their own segment.To facilitate quick reversals of large portions of the tour, each parent node has an associated reversal bit, indicating whether the citiesin the associated segment should are traversed from left to right or fromright to left.When the parent's reversal bit is off, succesive cities in the tourare found by following |next| pointers, encountering increasingsequence numbers within a segment. When the parent's reversal bit is on, succesive cities in the tourare found by following |prev| pointers, encountering decreasingsequence numbers within a segment. @@ The diagram of a two-level tree that Fredman \etal.\ provide include an explicitly stored city number inthe city nodes.  However, they say ---at the top of page 444--- thatthe city nodes are stored in an array and that therefore looking upthe city node from the city number can be done in constant time.  I take this to mean that they also save space by not explicitly storing the city number in the city node.  This should also speed thingsup by making more effective use of the cache and the communicationbandwidth betweenlevels of the memory hierarchy.@@ Here are the type definitions for a parent node, |parent_node_t|,and for a city node, |city_node_t|.  Parents point to the head and tailof their associated, segments.  Each city node points to its parent.In both kinds of nodes, sibling pointers are held in the |link| array;macros |next| and |prev| are just a shorthand for the next and previoussiblings, respectively.  Similarly, |head| and |tail| are abbreviationsfor access into the |city_link| array.(Here's a gotcha under AIX.  I used to use \CWEB/'s @@@@d facility tomake these preprocessor definitions.  But that puts the definitionsat the start of the \CEE/ file, before the includes.  But the |prev|macro conflicts with a \file{stdio.h} structure definition.  So I makethese definitions after the standard includes.  There is still a possibilitythat a macro, \eg\ |putchar|, might want to use the |prev| field in the \file{stdio} structure.  However, until I come across this problem, I'll stick to thecurrent solution.  I suppose I could use a |union| type to alias |prev| to |link[LINK_PREV]|, but that would make everything far uglier.)@@^system dependencies@@>@@<Module type definitions@@>=#define LINK_PREV 0#define LINK_NEXT 1#define prev link[LINK_PREV]#define next link[LINK_NEXT]#define CITY_LINK_HEAD 0#define CITY_LINK_TAIL 1#define head city_link[CITY_LINK_HEAD]#define tail city_link[CITY_LINK_TAIL]typedef struct parent_node_s {	int seq;	/* Sequence number.  Fredman \etal.\ call this |ID| */	int reverse;	/* Either 0 (forward), or 1 (reverse) */	struct parent_node_s *link[2];	struct city_node_s *city_link[2];} parent_node_t;typedef struct city_node_s {	struct parent_node_s *parent;	int seq;	/* Sequence number.  Fredman \etal.\ call this |ID| */	struct city_node_s *link[2];} city_node_t;@@ The city nodes and parent nodes will reside in statically allocatedarrays.  These are |city_node| and |parent_node|, respectively.%% We'll also need a mapping  from city numbers to city nodes.  This is done%% by the array |city_to_node|.  @@<Module variables@@>=static parent_node_t *parent_node=NULL;static city_node_t *city_node=NULL;@@ These variables get allocated in the setup routine.  We will be addingto this code later, so we separate it out in a new named section.@@<Subroutines@@>=voidtwolevel_setup(const int num_vertices, const int start_seg_size) {	@@<Set up the two-level data structure@@>@@;}@@ We also need a symmetrical tear down routine.@@<Subroutines@@>=void twolevel_cleanup(void) {	@@<Clean up the two-level data structure@@>@@;}@@ We must export these routines.@@<Exported subroutines@@>=void twolevel_setup(const int num_vertices, const int start_seg_size);void twolevel_cleanup(void);@@  We allocate these arrays using the |new_arr_of| macro from the \module{MEMORY} module.@@<Set up the two-level data structure@@>=city_node = new_arr_of(city_node_t,num_vertices);@@ We need the interface to the \module{MEMORY} module.    We'll also later dosanity checks using the macros from the \module{ERROR} module.@@<Module headers@@>=#include "error.h"#include "memory.h"@@ We use the |free_mem| macro to deallocate these arrays.@@<Clean up the two-level data structure@@>=free_mem(city_node);@@ There are at least two possible descriptions of the two-leveltree data structure.To derive goodworst-case time bounds, segment sizes are kept between $\sqrt{n}/2$ and$2\sqrt{n}$ cities via explicit balancing.   Under these conditions, the queries take constant time, and the |flip|update takes $O(\sqrt{n})$ time.However, the balancing required to achieve that worst-case timefor flips can be quite time consuming.  For practical purposes, Fredman \etal.~describe a variantwhere each segment starts out with roughly |groupsize| elements.Furthermore, explicit balancing is dispensed with in favour of implicit balancing with lower overhead .In the practical variant, queries remain constant time, but flips may degenerate to linear time.  However, Fredman \etal.~citethe conventional wisdom that data structures stay balanced in practice,so they expect this bad behaviour to be rare.We'll see later what implicit balancing entails, but for now wedeclare the |groupsize| variable.It will also be convenient to know the number of groups, |num_groups|.@@<Module variables@@>=static int groupsize, num_groups;@@ I'll leave the setting of |groupsize| to the main module; it's passedas a parameter to the setup routine.  However, Fredman \etal.'s experimentswere run with |groupsize==100| on instances of $10^3$ to $10^5$ cities,and |groupsize==200| on instances of $10^6$ cities.  For these million-cityinstances, this larger group size made each |flip| 27\% faster on average;performance was stable up to a group size of 800.Given an initial segment size of |groupsize|, there should be$\lfloor$|num_vertices/ groupsize|$\rfloor$ parent nodes.  @@<Set up the two-level data structure@@>=groupsize = start_seg_size;num_groups = num_vertices/groupsize;parent_node = new_arr_of(parent_node_t,num_groups);@@ While we're at it, let's  write down how we deallocate the |parent_node| array.@@<Clean up the two-level data structure@@>=free_mem(parent_node);@@ It will also be convenient to remember the number of cities; we'llstore it in the variable |n|.@@<Module variables@@>=static int n=0;@@ We set it at setup time. @@<Set up the two-level data structure@@>=n = num_vertices;@@ For defensiveness' sake, we'll put a garbage value into it at cleanup time.@@<Clean up the two-level data structure@@>=n = 0;