- Main Page
- Namespaces
- Classes
- Files
LKH.h Go to the documentation of this file.
1 #ifndef _LKH_H 2 #define _LKH_H 3 4 /* 5 * This header is used by almost all functions of the program. It defines 6 * macros and specifies data structures and function prototypes. 7 */ 8 9 #undef NDEBUG 10 #include <assert.h> 11 #include <ctype.h> 12 #include <float.h> 13 #include <limits.h> 14 #include <math.h> 15 #include <stdlib.h> 16 #include <stdio.h> 17 #include <string.h> 18 #include <time.h> 19 #include "GainType.h" 20 21 /* Macro definitions */ 22 23 #define Fixed(a, b) ((a)->FixedTo1 == (b) || (a)->FixedTo2 == (b)) 24 #define FixedOrCommon(a, b) (Fixed(a, b) || IsCommonEdge(a, b)) 25 #define InBestTour(a, b) ((a)->BestSuc == (b) || (b)->BestSuc == (a)) 26 #define InNextBestTour(a, b)\ 27 ((a)->NextBestSuc == (b) || (b)->NextBestSuc == (a)) 28 #define InInputTour(a, b) ((a)->InputSuc == (b) || (b)->InputSuc == (a)) 29 #define InInitialTour(a, b)\ 30 ((a)->InitialSuc == (b) || (b)->InitialSuc == (a)) 31 #define Near(a, b)\ 32 ((a)->BestSuc ? InBestTour(a, b) : (a)->Dad == (b) || (b)->Dad == (a)) 33 34 #define Link(a, b) { ((a)->Suc = (b))->Pred = (a); } 35 #define Follow(b, a)\ 36 { Link((b)->Pred, (b)->Suc); Link(b, b); Link(b, (a)->Suc); Link(a, b); } 37 #define Precede(a, b)\ 38 { Link((a)->Pred, (a)->Suc); Link(a, a); Link((b)->Pred, a); Link(a, b); } 39 #define SLink(a, b) { (a)->Suc = (b); (b)->Pred = (a); } 40 41 enum Types { TSP, ATSP, SOP, HCP, CVRP, TOUR, HPP, GTSP, AGTSP };
42 enum CoordTypes { TWOD_COORDS, THREED_COORDS, NO_COORDS };
43 enum EdgeWeightTypes { EXPLICIT, EUC_2D, EUC_3D, MAX_2D, MAX_3D, MAN_2D,
44 MAN_3D, CEIL_2D, CEIL_3D, GEO, GEOM, GEO_MEEUS, GEOM_MEEUS, ATT,
45 XRAY1, XRAY2, SPECIAL
46 };
47 enum EdgeWeightFormats { FUNCTION, FULL_MATRIX, UPPER_ROW, LOWER_ROW,
48 UPPER_DIAG_ROW, LOWER_DIAG_ROW, UPPER_COL, LOWER_COL,
49 UPPER_DIAG_COL, LOWER_DIAG_COL
50 };
51 enum CandidateSetTypes { ALPHA, DELAUNAY, NN, QUADRANT };
52 enum InitialTourAlgorithms { BORUVKA, GREEDY, MOORE, NEAREST_NEIGHBOR,
53 QUICK_BORUVKA, SIERPINSKI, WALK
54 };
55 56 typedef struct Node Node;
57 typedef struct Candidate Candidate;
58 typedef struct Cluster Cluster;
59 typedef struct Segment Segment;
60 typedef struct SSegment SSegment;
61 typedef struct SwapRecord SwapRecord;
62 typedef Node *(*MoveFunction) (Node * t1, Node * t2, GainType * G0,
63 GainType * Gain);
64 typedef int (*CostFunction) (Node * Na, Node * Nb);
65 66 /* The Node structure is used to represent nodes (cities) of the problem */ 67 68 struct Node {
69 int Id;
/* Number of the node (1...Dimension) */ 70 int Loc;
/* Location of the node in the heap 71 (zero, if the node is not in the heap) */ 72 int Rank;
/* During the ascent, the priority of the node. 73 Otherwise, the ordinal number of the node in 74 the tour */ 75 int V;
/* During the ascent the degree of the node minus 2. 76 Otherwise, the variable is used to mark nodes */ 77 int LastV;
/* Last value of V during the ascent */ 78 int Cost;
/* "Best" cost of an edge emanating from the node */ 79 int NextCost;
/* During the ascent, the next best cost of an edge 80 emanating from the node */ 81 int PredCost,
/* The costs of the neighbor edges on the current tour */ 82 SucCost;
83 int Pi;
/* Pi-value of the node */ 84 int BestPi;
/* Currently best pi-value found during the ascent */ 85 int Beta;
/* Beta-value (used for computing alpha-values) */ 86 int Subproblem;
/* Number of the subproblem the node is part of */ 87 int Sons;
/* Number of sons in the minimum spanning tree */ 88 int *C;
/* A row in the cost matrix */ 89 Node *Pred, *Suc;
/* Predecessor and successor node in 90 the two-way list of nodes */ 91 Node *OldPred, *OldSuc;
/* Previous values of Pred and Suc */ 92 Node *BestSuc,
/* Best and next best successor node in the */ 93 *NextBestSuc;
/* currently best tour */ 94 Node *Dad;
/* Father of the node in the minimum 1-tree */ 95 Node *Nearest;
/* Nearest node (used in the greedy heuristics) */ 96 Node *Next;
/* Auxiliary pointer, usually to the next node in a list 97 of nodes (e.g., the list of "active" nodes) */ 98 Node *Prev;
/* Auxiliary pointer, usually to the previous node 99 in a list of nodes */ 100 Node *Mark;
/* Visited mark */ 101 Node *FixedTo1,
/* Pointers to the opposite end nodes of fixed edges. */ 102 *FixedTo2;
/* A maximum of two fixed edges can be incident 103 to a node */ 104 Node *FixedTo1Saved,
/* Saved values of FixedTo1 and FixedTo2 */ 105 *FixedTo2Saved;
106 Node *Head;
/* Head of a segment of common edges */ 107 Node *Tail;
/* Tail of a segment of common edges */ 108 Node *InputSuc;
/* Successor in the INPUT_TOUR file */ 109 Node *InitialSuc;
/* Successor in the INITIAL_TOUR file */ 110 Node *SubproblemPred;
/* Predecessor in the SUBPROBLEM_TOUR file */ 111 Node *SubproblemSuc;
/* Successor in the SUBPROBLEM_TOUR file */ 112 Node *SubBestPred;
/* The best predecessor node in a subproblem */ 113 Node *SubBestSuc;
/* The best successor node in a subproblem */ 114 Node **MergeSuc;
/* Successors in the MERGE_TOUR files */ 115 Node *Added1, *Added2;
/* Pointers to the opposite end nodes 116 of added edges in a submove */ 117 Node *Deleted1, *Deleted2;
/* Pointers to the opposite end nodes 118 of deleted edges in a submove */ 119 Candidate *CandidateSet;
/* Candidate array */ 120 Candidate *BackboneCandidateSet;
/* Backbone candidate array */ 121 Segment *Parent;
/* Parent segment of a node when the two-level 122 tree representation is used */ 123 double X, Y, Z;
/* Coordinates of the node */ 124 double Xc, Yc, Zc;
/* Converted coordinates */ 125 char Axis;
/* The axis partitioned when the node is part of a KDTree */ 126 char OldPredExcluded, OldSucExcluded;
/* Booleans used for indicating 127 whether one (or both) of the 128 adjoining nodes on the old tour 129 has been excluded */ 130 };
131 132 /* The Candidate structure is used to represent candidate edges */ 133 134 struct Candidate {
135 Node *To;
/* The end node of the edge */ 136 int Cost;
/* Cost (distance) of the edge */ 137 int Alpha;
/* Its alpha-value */ 138 };
139 140 /* The Segment structure is used to represent the segments in the two-level 141 representation of tours */ 142 143 struct Segment {
144 char Reversed;
/* Reversal bit */ 145 Node *First, *Last;
/* First and last node in the segment */ 146 Segment *Pred, *Suc;
/* Predecessor and successor in the two-way 147 list of segments */ 148 int Rank;
/* Ordinal number of the segment in the list */ 149 int Size;
/* Number of nodes in the segment */ 150 SSegment *Parent;
/* The parent super segment */ 151 };
152 153 struct SSegment {
154 char Reversed;
/* Reversal bit */ 155 Segment *First, *Last;
/* The first and last node in the segment */ 156 SSegment *Pred, *Suc;
/* The predecessor and successor in the 157 two-way list of super segments */ 158 int Rank;
/* The ordinal number of the segment in the list */ 159 int Size;
/* The number of nodes in the segment */ 160 };
161 162 struct Cluster {
163 Node *First;
164 Cluster *Next;
165 int Size;
166 };
167 168 /* The SwapRecord structure is used to record 2-opt moves (swaps) */ 169 170 struct SwapRecord {
171 Node *t1, *t2, *t3, *t4;
/* The 4 nodes involved in a 2-opt move */ 172 };
173 174 int AscentCandidates;
/* Number of candidate edges to be associated 175 with each node during the ascent */ 176 int BackboneTrials;
/* Number of backbone trials in each run */ 177 int Backtracking;
/* Specifies whether backtracking is used for 178 the first move in a sequence of moves */ 179 GainType BestCost;
/* Cost of the tour in BestTour */ 180 int *BestTour;
/* Table containing best tour found */ 181 GainType BetterCost;
/* Cost of the tour stored in BetterTour */ 182 int *BetterTour;
/* Table containing the currently best tour 183 in a run */ 184 int CacheMask;
/* Mask for indexing the cache */ 185 int *CacheVal;
/* Table of cached distances */ 186 int *CacheSig;
/* Table of the signatures of cached 187 distances */ 188 int CandidateFiles;
/* Number of CANDIDATE_FILEs */ 189 int *CostMatrix;
/* Cost matrix */ 190 int Dimension;
/* Number of nodes in the problem */ 191 int DimensionSaved;
/* Saved value of Dimension */ 192 double Excess;
/* Maximum alpha-value allowed for any 193 candidate edge is set to Excess times the 194 absolute value of the lower bound of a 195 solution tour */ 196 int ExtraCandidates;
/* Number of extra neighbors to be added to 197 the candidate set of each node */ 198 Node *FirstActive, *LastActive;
/* First and last node in the list 199 of "active" nodes */ 200 Cluster *FirstCluster, *LastCluster;
201 Node *FirstNode;
/* First node in the list of nodes */ 202 Segment *FirstSegment;
/* A pointer to the first segment in the cyclic 203 list of segments */ 204 SSegment *FirstSSegment;
/* A pointer to the first super segment in 205 the cyclic list of segments */ 206 int Gain23Used;
/* Specifies whether Gain23 is used */ 207 int GainCriterionUsed;
/* Specifies whether L&K's gain criterion is 208 used */ 209 int GTSPSets;
/* Specifies the number of clusters in a GTSP instance */ 210 int InitialPeriod;
/* Length of the first period in the ascent */ 211 int InitialStepSize;
/* Initial step size used in the ascent */ 212 double InitialTourFraction;
/* Fraction of the initial tour to be 213 constructed by INITIAL_TOUR_FILE edges */ 214 char *LastLine;
/* Last input line */ 215 double LowerBound;
/* Lower bound found by the ascent */ 216 int Kicks;
/* Specifies the number of K-swap-kicks */ 217 int KickType;
/* Specifies K for a K-swap-kick */ 218 int M;
/* The M-value is used when solving an ATSP- 219 instance by transforming it to a 220 STSP-instance */ 221 int MaxBreadth;
/* The maximum number of candidate edges 222 considered at each level of the search for 223 a move */ 224 int MaxCandidates;
/* Maximum number of candidate edges to be 225 associated with each node */ 226 int MaxMatrixDimension;
/* Maximum dimension for an explicit cost matrix */ 227 int MaxSwaps;
/* Maximum number of swaps made during the 228 search for a move */ 229 int MaxPopulationSize;
/* The maximum size of the population */ 230 int MaxTrials;
/* Maximum number of trials in each run */ 231 int MergeTourFiles;
/* Number of MERGE_TOUR_FILEs */ 232 int MoveType;
/* Specifies the sequantial move type to be used 233 in local search. A value K >= 2 signifies 234 that a k-opt moves are tried for k <= K */ 235 Node *NodeSet;
/* Array of all nodes */ 236 int Norm;
/* Measure of a 1-tree's discrepancy from a tour */ 237 int NonsequentialMoveType;
/* Specifies the nonsequential move type to 238 be used in local search. A value 239 L >= 4 signifies that nonsequential 240 l-opt moves are tried for l <= L */ 241 GainType Optimum;
/* Known optimal tour length. 242 If StopAtOptimum is 1, a run will be 243 terminated as soon as a tour length 244 becomes equal this value */ 245 int PatchingA;
/* Specifies the maximum number of alternating 246 cycles to be used for patching disjunct cycles */ 247 int PatchingC;
/* Specifies the maximum number of disjoint cycles to be 248 patched (by one or more alternating cycles) */ 249 int Precision;
/* Internal precision in the representation of 250 transformed distances */ 251 int PredSucCostAvailable;
/* PredCost and SucCost are available */ 252 unsigned *Rand;
/* Table of random values */ 253 int RestrictedSearch;
/* Specifies whether the choice of the first 254 edge to be broken is restricted */ 255 short Reversed;
/* Boolean used to indicate whether a tour has 256 been reversed */ 257 int Run;
/* Current run number */ 258 int Runs;
/* Total number of runs */ 259 unsigned Seed;
/* Initial seed for random number generation */ 260 int StopAtOptimum;
/* Specifies whether a run will be terminated if 261 the tour length becomes equal to Optimum */ 262 int Subgradient;
/* Specifies whether the Pi-values should be 263 determined by subgradient optimization */ 264 int SubproblemSize;
/* Number of nodes in a subproblem */ 265 int SubsequentMoveType;
/* Specifies the move type to be used for all 266 moves following the first move in a sequence 267 of moves. The value K >= 2 signifies that a 268 K-opt move is to be used */ 269 int SubsequentPatching;
/* Species whether patching is used for 270 subsequent moves */ 271 SwapRecord *SwapStack;
/* Stack of SwapRecords */ 272 int Swaps;
/* Number of swaps made during a tentative move */ 273 double TimeLimit;
/* The time limit in seconds for each run */ 274 int TraceLevel;
/* Specifies the level of detail of the output 275 given during the solution process. 276 The value 0 signifies a minimum amount of 277 output. The higher the value is the more 278 information is given */ 279 int Trial;
/* Ordinal number of the current trial */ 280 281 /* The following variables are read by the functions ReadParameters and 282 ReadProblem: */ 283 284 char *ParameterFileName, *ProblemFileName, *PiFileName,
285 *TourFileName, *OutputTourFileName, *InputTourFileName,
286 **CandidateFileName, *InitialTourFileName,
287 *SubproblemTourFileName, **MergeTourFileName;
288 char *Name, *Type, *EdgeWeightType, *EdgeWeightFormat,
289 *EdgeDataFormat, *NodeCoordType, *DisplayDataType;
290 int CandidateSetSymmetric, CandidateSetType,
291 CoordType, DelaunayPartitioning, DelaunayPure,
292 ExtraCandidateSetSymmetric, ExtraCandidateSetType,
293 InitialTourAlgorithm,
294 KarpPartitioning, KCenterPartitioning, KMeansPartitioning,
295 MoorePartitioning,
296 PatchingAExtended, PatchingARestricted,
297 PatchingCExtended, PatchingCRestricted,
298 ProblemType,
299 RohePartitioning, SierpinskiPartitioning,
300 SubproblemBorders, SubproblemsCompressed, WeightType, WeightFormat;
301 302 FILE *ParameterFile, *ProblemFile, *PiFile, *InputTourFile,
303 *TourFile, *InitialTourFile, *SubproblemTourFile, **MergeTourFile;
304 CostFunction Distance, D, C, c;
305 MoveFunction BestMove, BacktrackMove, BestSubsequentMove;
306 307 /* Function prototypes: */ 308 309 int Distance_1(Node * Na, Node * Nb);
310 int Distance_ATSP(Node * Na, Node * Nb);
311 int Distance_ATT(Node * Na, Node * Nb);
312 int Distance_CEIL_2D(Node * Na, Node * Nb);
313 int Distance_CEIL_3D(Node * Na, Node * Nb);
314 int Distance_EXPLICIT(Node * Na, Node * Nb);
315 int Distance_EUC_2D(Node * Na, Node * Nb);
316 int Distance_EUC_3D(Node * Na, Node * Nb);
317 int Distance_GEO(Node * Na, Node * Nb);
318 int Distance_GEOM(Node * Na, Node * Nb);
319 int Distance_GEO_MEEUS(Node * Na, Node * Nb);
320 int Distance_GEOM_MEEUS(Node * Na, Node * Nb);
321 int Distance_MAN_2D(Node * Na, Node * Nb);
322 int Distance_MAN_3D(Node * Na, Node * Nb);
323 int Distance_MAX_2D(Node * Na, Node * Nb);
324 int Distance_MAX_3D(Node * Na, Node * Nb);
325 int Distance_SPECIAL(Node * Na, Node * Nb);
326 int Distance_XRAY1(Node * Na, Node * Nb);
327 int Distance_XRAY2(Node * Na, Node * Nb);
328 329 int D_EXPLICIT(Node * Na, Node * Nb);
330 int D_FUNCTION(Node * Na, Node * Nb);
331 332 int C_EXPLICIT(Node * Na, Node * Nb);
333 int C_FUNCTION(Node * Na, Node * Nb);
334 335 int c_ATT(Node * Na, Node *Nb);
336 int c_CEIL_2D(Node * Na, Node * Nb);
337 int c_CEIL_3D(Node * Na, Node * Nb);
338 int c_EUC_2D(Node * Na, Node * Nb);
339 int c_EUC_3D(Node * Na, Node * Nb);
340 int c_GEO(Node * Na, Node * Nb);
341 int c_GEOM(Node * Na, Node * Nb);
342 int c_GEO_MEEUS(Node * Na, Node * Nb);
343 int c_GEOM_MEEUS(Node * Na, Node * Nb);
344 345 void AllocateStructures(
void);
346 void eprintf(
const char *fmt, ...);
347 int fscanint(FILE *f,
int *v);
348 double GetTime(
void);
349 void InitializeStatistics(
void);
350 int IsCandidate(
const Node * ta,
const Node * tb);
351 void printff(
char *fmt, ...);
352 void PrintParameters(
void);
353 void PrintStatistics(
void);
354 unsigned Random(
void);
355 char *ReadLine(FILE * InputFile);
356 void ReadParameters(
void);
357 int ReadPenalties(
void);
358 void ReadProblem(
void);
359 void ReadTour(
char * FileName, FILE ** File);
360 void SRandom(
unsigned seed);
361 void UpdateStatistics(GainType Cost,
double Time);
362 void WriteCandidates(
void);
363 void WriteTour(
char * FileName,
int * Tour, GainType Cost);
364 365 #endifMAN_3DDefinition: LKH.h:44 THREED_COORDSDefinition: LKH.h:42 Segment::Rankint RankDefinition: LKH.h:148 ProblemFileNamechar * ProblemFileNameDefinition: LKH.h:284 EdgeWeightTypesEdgeWeightTypesDefinition: LKH.h:43 FirstSegmentSegment * FirstSegmentDefinition: LKH.h:202 TWOD_COORDSDefinition: LKH.h:42 D_EXPLICITint D_EXPLICIT(Node *Na, Node *Nb) Node::OldPredNode * OldPredDefinition: LKH.h:91 ALPHADefinition: LKH.h:51 Trialint TrialDefinition: LKH.h:279 IsCandidateint IsCandidate(const Node *ta, const Node *tb)Definition: IsCandidate.c:10 Dimensionint DimensionDefinition: LKH.h:190 Gain23Usedint Gain23UsedDefinition: LKH.h:206 Candidate::Alphaint AlphaDefinition: LKH.h:137 fscanintint fscanint(FILE *f, int *v)Definition: fscanint.c:13 ReadProblemvoid ReadProblem(void)Definition: ReadProblem.c:230 NonsequentialMoveTypeint NonsequentialMoveTypeDefinition: LKH.h:237 PredSucCostAvailableint PredSucCostAvailableDefinition: LKH.h:251 LOWER_DIAG_COLDefinition: LKH.h:49 InputTourFileFILE * InputTourFileDefinition: LKH.h:302 TOURDefinition: LKH.h:41 Node::SubproblemPredNode * SubproblemPredDefinition: LKH.h:110 InitialTourFractiondouble InitialTourFractionDefinition: LKH.h:212 Node::Ydouble YDefinition: LKH.h:123 SSegment::LastSegment * LastDefinition: LKH.h:155 DCostFunction DDefinition: LKH.h:304 Node::Added1Node * Added1Definition: LKH.h:115 PrintStatisticsvoid PrintStatistics(void)Definition: Statistics.c:41 MaxSwapsint MaxSwapsDefinition: LKH.h:227 Node::PrevNode * PrevDefinition: LKH.h:98 ExtraCandidateSetTypeint ExtraCandidateSetTypeDefinition: LKH.h:290 GEODefinition: LKH.h:44 SubsequentMoveTypeint SubsequentMoveTypeDefinition: LKH.h:265 WALKDefinition: LKH.h:53 SubproblemTourFileNamechar * SubproblemTourFileNameDefinition: LKH.h:284 time.h LOWER_ROWDefinition: LKH.h:47 CandidateSetSymmetricint CandidateSetSymmetricDefinition: LKH.h:290 Precisionint PrecisionDefinition: LKH.h:249 GainType.h HCPDefinition: LKH.h:41 SubproblemSizeint SubproblemSizeDefinition: LKH.h:264 NO_COORDSDefinition: LKH.h:42 MAX_2DDefinition: LKH.h:43 CacheMaskint CacheMaskDefinition: LKH.h:184 SSegment::Reversedchar ReversedDefinition: LKH.h:154 SPECIALDefinition: LKH.h:45 KMeansPartitioningint KMeansPartitioningDefinition: LKH.h:290 Node::Rankint RankDefinition: LKH.h:72 XRAY2Definition: LKH.h:45 GTSPSetsint GTSPSetsDefinition: LKH.h:209 LastLinechar * LastLineDefinition: LKH.h:214 SwapRecordDefinition: LKH.h:170 Node::Xcdouble XcDefinition: LKH.h:124 Kicksint KicksDefinition: LKH.h:216 Node::NextBestSucNode * NextBestSucDefinition: LKH.h:92 FirstSSegmentSSegment * FirstSSegmentDefinition: LKH.h:204 Node::Subproblemint SubproblemDefinition: LKH.h:86 BestSubsequentMoveMoveFunction BestSubsequentMoveDefinition: LKH.h:305 Node::LastVint LastVDefinition: LKH.h:77 GainCriterionUsedint GainCriterionUsedDefinition: LKH.h:207 Node::Betaint BetaDefinition: LKH.h:85 CoordTypeint CoordTypeDefinition: LKH.h:290 PrintParametersvoid PrintParameters(void)Definition: PrintParameters.c:8 printffvoid printff(char *fmt,...)Definition: printff.c:10 FULL_MATRIXDefinition: LKH.h:47 Distance_MAN_2Dint Distance_MAN_2D(Node *Na, Node *Nb)Definition: Distance.c:104 InitialTourFileFILE * InitialTourFileDefinition: LKH.h:302 Distance_GEOM_MEEUSint Distance_GEOM_MEEUS(Node *Na, Node *Nb)Definition: Distance.c:180 SubproblemBordersint SubproblemBordersDefinition: LKH.h:290 SwapRecord::t4Node * t4Definition: LKH.h:171 Node::TailNode * TailDefinition: LKH.h:107 HPPDefinition: LKH.h:41 LOWER_DIAG_ROWDefinition: LKH.h:48 NodeDefinition: LKH.h:68 SOPDefinition: LKH.h:41 MaxCandidatesint MaxCandidatesDefinition: LKH.h:224 CVRPDefinition: LKH.h:41 Node::HeadNode * HeadDefinition: LKH.h:106 RohePartitioningint RohePartitioningDefinition: LKH.h:290 Node::Idint IdDefinition: LKH.h:69 EdgeWeightFormatchar * EdgeWeightFormatDefinition: LKH.h:288 GEOM_MEEUSDefinition: LKH.h:44 WeightTypeint WeightTypeDefinition: LKH.h:290 XRAY1Definition: LKH.h:45 Node::Xdouble XDefinition: LKH.h:123 c_GEOM_MEEUSint c_GEOM_MEEUS(Node *Na, Node *Nb) Node::CandidateSetCandidate * CandidateSetDefinition: LKH.h:119 EdgeWeightFormatsEdgeWeightFormatsDefinition: LKH.h:47 WriteCandidatesvoid WriteCandidates(void) MAN_2DDefinition: LKH.h:43 TSPDefinition: LKH.h:41 Segment::ParentSSegment * ParentDefinition: LKH.h:150 Distance_SPECIALint Distance_SPECIAL(Node *Na, Node *Nb)Definition: Distance_SPECIAL.c:18 Node::OldPredExcludedchar OldPredExcludedDefinition: LKH.h:126 TypesTypesDefinition: LKH.h:41 Node::BestPiint BestPiDefinition: LKH.h:84 ClusterDefinition: LKH.h:162 UPPER_COLDefinition: LKH.h:48 CEIL_2DDefinition: LKH.h:44 Node::Deleted2Node * Deleted2Definition: LKH.h:117 Node::BackboneCandidateSetCandidate * BackboneCandidateSetDefinition: LKH.h:120 Node::NearestNode * NearestDefinition: LKH.h:95 Node::Ycdouble YcDefinition: LKH.h:124 Node::PredCostint PredCostDefinition: LKH.h:81 MergeTourFileFILE ** MergeTourFileDefinition: LKH.h:302 KCenterPartitioningint KCenterPartitioningDefinition: LKH.h:290 CacheSigint * CacheSigDefinition: LKH.h:186 Node::FixedTo2Node * FixedTo2Definition: LKH.h:101 MoveFunctionNode *(* MoveFunction)(Node *t1, Node *t2, GainType *G0, GainType *Gain)Definition: LKH.h:62 SSegment::Sizeint SizeDefinition: LKH.h:159 KickTypeint KickTypeDefinition: LKH.h:217 Node::SubBestSucNode * SubBestSucDefinition: LKH.h:113 DistanceCostFunction DistanceDefinition: LKH.h:304 CostMatrixint * CostMatrixDefinition: LKH.h:189 DelaunayPartitioningint DelaunayPartitioningDefinition: LKH.h:290 Node::ParentSegment * ParentDefinition: LKH.h:121 ReadPenaltiesint ReadPenalties(void)Definition: ReadPenalties.c:19 PatchingAExtendedint PatchingAExtendedDefinition: LKH.h:290 SwapStackSwapRecord * SwapStackDefinition: LKH.h:271 assert.h BestMoveMoveFunction BestMoveDefinition: LKH.h:305 ATTDefinition: LKH.h:44 Distance_XRAY2int Distance_XRAY2(Node *Na, Node *Nb) Node::Zdouble ZDefinition: LKH.h:123 GEO_MEEUSDefinition: LKH.h:44 OptimumGainType OptimumDefinition: LKH.h:241 MaxBreadthint MaxBreadthDefinition: LKH.h:221 NodeSetNode * NodeSetDefinition: LKH.h:235 SubproblemsCompressedint SubproblemsCompressedDefinition: LKH.h:290 UPPER_DIAG_COLDefinition: LKH.h:49 MaxTrialsint MaxTrialsDefinition: LKH.h:230 LowerBounddouble LowerBoundDefinition: LKH.h:215 OutputTourFileNamechar * OutputTourFileNameDefinition: LKH.h:284 Distance_ATTint Distance_ATT(Node *Na, Node *Nb)Definition: Distance.c:24 UPPER_ROWDefinition: LKH.h:47 MergeTourFilesint MergeTourFilesDefinition: LKH.h:231 ATSPDefinition: LKH.h:41 LastClusterCluster * LastClusterDefinition: LKH.h:200 Excessdouble ExcessDefinition: LKH.h:192 CacheValint * CacheValDefinition: LKH.h:185 Distance_ATSPint Distance_ATSP(Node *Na, Node *Nb)Definition: Distance.c:14 Node::Locint LocDefinition: LKH.h:70 SSegmentDefinition: LKH.h:153 Swapsint SwapsDefinition: LKH.h:272 QUICK_BORUVKADefinition: LKH.h:53 Node::PredNode * PredDefinition: LKH.h:89 Node::DadNode * DadDefinition: LKH.h:94 UPPER_DIAG_ROWDefinition: LKH.h:48 PatchingAint PatchingADefinition: LKH.h:245 SIERPINSKIDefinition: LKH.h:53 SSegment::Rankint RankDefinition: LKH.h:158 ExtraCandidatesint ExtraCandidatesDefinition: LKH.h:196 c_CEIL_2Dint c_CEIL_2D(Node *Na, Node *Nb) AGTSPDefinition: LKH.h:41 DelaunayPureint DelaunayPureDefinition: LKH.h:290 Node::InputSucNode * InputSucDefinition: LKH.h:108 RestrictedSearchint RestrictedSearchDefinition: LKH.h:253 SwapRecord::t1Node * t1Definition: LKH.h:171 MOOREDefinition: LKH.h:52 Cluster::NextCluster * NextDefinition: LKH.h:164 EUC_3DDefinition: LKH.h:43 DimensionSavedint DimensionSavedDefinition: LKH.h:191 Node::SucNode * SucDefinition: LKH.h:89 BetterCostGainType BetterCostDefinition: LKH.h:181 ReadParametersvoid ReadParameters(void)Definition: ReadParameters.c:354 Node::SubBestPredNode * SubBestPredDefinition: LKH.h:112 DisplayDataTypechar * DisplayDataTypeDefinition: LKH.h:288 Node::MergeSucNode ** MergeSucDefinition: LKH.h:114 Node::NextCostint NextCostDefinition: LKH.h:79 FirstNodeNode * FirstNodeDefinition: LKH.h:201 C_EXPLICITint C_EXPLICIT(Node *Na, Node *Nb) Distance_CEIL_3Dint Distance_CEIL_3D(Node *Na, Node *Nb)Definition: Distance.c:36 ParameterFileFILE * ParameterFileDefinition: LKH.h:302 BetterTourint * BetterTourDefinition: LKH.h:182 Distance_XRAY1int Distance_XRAY1(Node *Na, Node *Nb) MoorePartitioningint MoorePartitioningDefinition: LKH.h:290 Distance_CEIL_2Dint Distance_CEIL_2D(Node *Na, Node *Nb)Definition: Distance.c:30 TourFileFILE * TourFileDefinition: LKH.h:302 SegmentDefinition: LKH.h:143 Node::InitialSucNode * InitialSucDefinition: LKH.h:109 Distance_1int Distance_1(Node *Na, Node *Nb)Definition: Distance.c:9 AllocateStructuresvoid AllocateStructures(void) c_EUC_2Dint c_EUC_2D(Node *Na, Node *Nb) InitializeStatisticsvoid InitializeStatistics(void)Definition: Statistics.c:7 TraceLevelint TraceLevelDefinition: LKH.h:274 c_EUC_3Dint c_EUC_3D(Node *Na, Node *Nb) eprintfvoid eprintf(const char *fmt,...)Definition: eprintf.c:8 Candidate::ToNode * ToDefinition: LKH.h:135 c_GEOMint c_GEOM(Node *Na, Node *Nb) Node::Zcdouble ZcDefinition: LKH.h:124 DELAUNAYDefinition: LKH.h:51 Node::Cint * CDefinition: LKH.h:88 Node::MarkNode * MarkDefinition: LKH.h:100 Node::Costint CostDefinition: LKH.h:78 QUADRANTDefinition: LKH.h:51 PiFileNamechar * PiFileNameDefinition: LKH.h:284 Subgradientint SubgradientDefinition: LKH.h:262 Distance_GEOMint Distance_GEOM(Node *Na, Node *Nb)Definition: Distance.c:90 PiFileFILE * PiFileDefinition: LKH.h:302 EXPLICITDefinition: LKH.h:43 Segment::LastNode * LastDefinition: LKH.h:145 MaxPopulationSizeint MaxPopulationSizeDefinition: LKH.h:229 Normint NormDefinition: LKH.h:236 PatchingCint PatchingCDefinition: LKH.h:247 Node::Vint VDefinition: LKH.h:75 KarpPartitioningint KarpPartitioningDefinition: LKH.h:290 SSegment::SucSSegment * SucDefinition: LKH.h:156 Seedunsigned SeedDefinition: LKH.h:259 c_CEIL_3Dint c_CEIL_3D(Node *Na, Node *Nb) Runsint RunsDefinition: LKH.h:258 FirstActiveNode * FirstActiveDefinition: LKH.h:198 Node::Sonsint SonsDefinition: LKH.h:87 Distance_GEO_MEEUSint Distance_GEO_MEEUS(Node *Na, Node *Nb)Definition: Distance.c:167 TourFileNamechar * TourFileNameDefinition: LKH.h:284 Node::FixedTo1SavedNode * FixedTo1SavedDefinition: LKH.h:104 StopAtOptimumint StopAtOptimumDefinition: LKH.h:260 Runint RunDefinition: LKH.h:257 Distance_EUC_2Dint Distance_EUC_2D(Node *Na, Node *Nb)Definition: Distance.c:42 ReadLinechar * ReadLine(FILE *InputFile)Definition: ReadLine.c:23 NEAREST_NEIGHBORDefinition: LKH.h:52 Node::NextNode * NextDefinition: LKH.h:96 ReadTourvoid ReadTour(char *FileName, FILE **File)Definition: ReadProblem.c:1343 Distance_MAX_3Dint Distance_MAX_3D(Node *Na, Node *Nb)Definition: Distance.c:122 Node::SucCostint SucCostDefinition: LKH.h:81 InitialTourAlgorithmint InitialTourAlgorithmDefinition: LKH.h:290 Node::BestSucNode * BestSucDefinition: LKH.h:92 Node::OldSucExcludedchar OldSucExcludedDefinition: LKH.h:126 Namechar * NameDefinition: LKH.h:288 Distance_MAX_2Dint Distance_MAX_2D(Node *Na, Node *Nb)Definition: Distance.c:115 ParameterFileNamechar * ParameterFileNameDefinition: LKH.h:284 Distance_MAN_3Dint Distance_MAN_3D(Node *Na, Node *Nb)Definition: Distance.c:109 Typechar * TypeDefinition: LKH.h:288 Cluster::Sizeint SizeDefinition: LKH.h:165 FirstClusterCluster * FirstClusterDefinition: LKH.h:200 EdgeDataFormatchar * EdgeDataFormatDefinition: LKH.h:288 ProblemTypeint ProblemTypeDefinition: LKH.h:290 TimeLimitdouble TimeLimitDefinition: LKH.h:273 Node::Piint PiDefinition: LKH.h:83 Candidate::Costint CostDefinition: LKH.h:136 Segment::SucSegment * SucDefinition: LKH.h:146 AscentCandidatesint AscentCandidatesDefinition: LKH.h:174 SierpinskiPartitioningint SierpinskiPartitioningDefinition: LKH.h:290 Distance_EUC_3Dint Distance_EUC_3D(Node *Na, Node *Nb)Definition: Distance.c:48 c_GEOint c_GEO(Node *Na, Node *Nb) GREEDYDefinition: LKH.h:52 Node::FixedTo1Node * FixedTo1Definition: LKH.h:101 Node::OldSucNode * OldSucDefinition: LKH.h:91 Node::Deleted1Node * Deleted1Definition: LKH.h:117 PatchingARestrictedint PatchingARestrictedDefinition: LKH.h:290 InitialStepSizeint InitialStepSizeDefinition: LKH.h:211 MergeTourFileNamechar ** MergeTourFileNameDefinition: LKH.h:284 Backtrackingint BacktrackingDefinition: LKH.h:177 Segment::Reversedchar ReversedDefinition: LKH.h:144 BacktrackMoveMoveFunction BacktrackMoveDefinition: LKH.h:305 LOWER_COLDefinition: LKH.h:48 CandidateDefinition: LKH.h:134 PatchingCRestrictedint PatchingCRestrictedDefinition: LKH.h:290 SubproblemTourFileFILE * SubproblemTourFileDefinition: LKH.h:302 WriteTourvoid WriteTour(char *FileName, int *Tour, GainType Cost)Definition: WriteTour.c:16 InitialTourAlgorithmsInitialTourAlgorithmsDefinition: LKH.h:52 ProblemFileFILE * ProblemFileDefinition: LKH.h:302 Node::Axischar AxisDefinition: LKH.h:125 FUNCTIONDefinition: LKH.h:47 WeightFormatint WeightFormatDefinition: LKH.h:290 GEOMDefinition: LKH.h:44 NNDefinition: LKH.h:51 Mint MDefinition: LKH.h:218 cCostFunction cDefinition: LKH.h:304 SubsequentPatchingint SubsequentPatchingDefinition: LKH.h:269 GetTimedouble GetTime(void)Definition: GetTime.c:21 CandidateFilesint CandidateFilesDefinition: LKH.h:188 CEIL_3DDefinition: LKH.h:44 Distance_GEOint Distance_GEO(Node *Na, Node *Nb)Definition: Distance.c:62 C_FUNCTIONint C_FUNCTION(Node *Na, Node *Nb) Segment::Sizeint SizeDefinition: LKH.h:149 InitialTourFileNamechar * InitialTourFileNameDefinition: LKH.h:284 c_ATTint c_ATT(Node *Na, Node *Nb) EdgeWeightTypechar * EdgeWeightTypeDefinition: LKH.h:288 GTSPDefinition: LKH.h:41 Node::Added2Node * Added2Definition: LKH.h:115 EUC_2DDefinition: LKH.h:43 c_GEO_MEEUSint c_GEO_MEEUS(Node *Na, Node *Nb) SRandomvoid SRandom(unsigned seed)Definition: Random.c:58 InputTourFileNamechar * InputTourFileNameDefinition: LKH.h:284 CandidateSetTypesCandidateSetTypesDefinition: LKH.h:51 MAX_3DDefinition: LKH.h:43 SwapRecord::t2Node * t2Definition: LKH.h:171 Node::FixedTo2SavedNode * FixedTo2SavedDefinition: LKH.h:104 Randunsigned * RandDefinition: LKH.h:252 MaxMatrixDimensionint MaxMatrixDimensionDefinition: LKH.h:226 CandidateFileNamechar ** CandidateFileNameDefinition: LKH.h:284 MoveTypeint MoveTypeDefinition: LKH.h:232 InitialPeriodint InitialPeriodDefinition: LKH.h:210 BestTourint * BestTourDefinition: LKH.h:180 ExtraCandidateSetSymmetricint ExtraCandidateSetSymmetricDefinition: LKH.h:290 GainTypelong long GainTypeDefinition: GainType.h:13 UpdateStatisticsvoid UpdateStatistics(GainType Cost, double Time)Definition: Statistics.c:20 Reversedshort ReversedDefinition: LKH.h:255 NodeCoordTypechar * NodeCoordTypeDefinition: LKH.h:288 LastActiveNode * LastActiveDefinition: LKH.h:198 Distance_EXPLICITint Distance_EXPLICIT(Node *Na, Node *Nb)Definition: Distance.c:54 CandidateSetTypeint CandidateSetTypeDefinition: LKH.h:290 BestCostGainType BestCostDefinition: LKH.h:179 Randomunsigned Random(void)Definition: Random.c:43 BackboneTrialsint BackboneTrialsDefinition: LKH.h:176 CoordTypesCoordTypesDefinition: LKH.h:42 BORUVKADefinition: LKH.h:52 PatchingCExtendedint PatchingCExtendedDefinition: LKH.h:290 CostFunctionint(* CostFunction)(Node *Na, Node *Nb)Definition: LKH.h:64 Node::SubproblemSucNode * SubproblemSucDefinition: LKH.h:111 D_FUNCTIONint D_FUNCTION(Node *Na, Node *Nb) Cluster::FirstNode * FirstDefinition: LKH.h:163 glkh_solver Author(s): Francisco Suarez-Ruiz autogenerated on Mon Jun 10 2019 13:50:26