1 /****************************************************************************/ 2 /* */ 3 /* This file is part of CONCORDE */ 4 /* */ 5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */ 6 /* Vasek Chvatal, and William Cook */ 7 /* */ 8 /* Permission is granted for academic research use. For other uses, */ 9 /* contact the authors for licensing options. */ 10 /* */ 11 /* Use at your own risk. We make no guarantees about the */ 12 /* correctness or usefulness of this code. */ 13 /* */ 14 /****************************************************************************/ 15 16 /****************************************************************************/ 17 /****************************************************************************/ 18 /* */ 19 /* PROTOTYPES FOR FILES IN EDGEGEN */ 20 /* */ 21 /****************************************************************************/ 22 /****************************************************************************/ 23 24 #ifndef __EDGEGEN_H 25 #define __EDGEGEN_H 26 27 #include "util.h" 28 29 30 /****************************************************************************/ 31 /* */ 32 /* edgegen.c */ 33 /* */ 34 /****************************************************************************/ 35 36 typedef struct CCedgegengroup { 37 struct { 38 int count; 39 int quadnearest; 40 int nearest; 41 int nearest_start; 42 int greedy_start; 43 int boruvka_start; 44 int qboruvka_start; 45 int random_start; 46 int nkicks; 47 } linkern; 48 49 struct { 50 int twoopt_count; 51 int twoopt5_count; 52 int threeopt_count; 53 int greedy; 54 int boruvka; 55 int qboruvka; 56 int nearest_count; 57 int random_count; 58 } tour; 59 60 struct { 61 int wantit; 62 int basic; 63 int priced; 64 } f2match; 65 66 struct { 67 int number; 68 int basic; 69 int priced; 70 } f2match_nearest; 71 72 int random; 73 int nearest; 74 int quadnearest; 75 int want_tree; 76 int nearest_twomatch_count; 77 int delaunay; 78 int mlinkern; 79 } CCedgegengroup; 80 81 82 83 int 84 CCedgegen_read (char *egname, CCedgegengroup *plan), 85 CCedgegen_edges (CCedgegengroup *plan, int ncount, CCdatagroup *dat, 86 double *wcoord, int *ecount, int **elist, int silent, 87 CCrandstate *rstate); 88 void 89 CCedgegen_init_edgegengroup (CCedgegengroup *plan); 90 91 92 93 94 /****************************************************************************/ 95 /* */ 96 /* xnear.c */ 97 /* */ 98 /****************************************************************************/ 99 100 typedef struct CCxnear { 101 struct CCdatagroup dat; 102 double *w; 103 int *nodenames; 104 int *invnames; 105 } CCxnear; 106 107 108 109 int 110 CCedgegen_x_k_nearest (int ncount, int num, CCdatagroup *dat, 111 double *wcoord, int wantlist, int *ecount, int **elist, int silent), 112 CCedgegen_x_quadrant_k_nearest (int ncount, int num, CCdatagroup *dat, 113 double *wcoord, int wantlist, int *ecount, int **elist, int silent), 114 CCedgegen_x_node_k_nearest (CCxnear *xn, int n, int nearnum, int ncount, 115 int *list), 116 CCedgegen_x_node_quadrant_k_nearest (CCxnear *xn, int n, int nearnum, 117 int ncount, int *list), 118 CCedgegen_x_node_nearest (CCxnear *xn, int ncount, int ni, char *marks), 119 CCedgegen_x_nearest_neighbor_tour (int ncount, int start, CCdatagroup *dat, 120 int *outcycle, double *val), 121 CCedgegen_x_greedy_tour (int ncount, CCdatagroup *dat, int *outcycle, 122 double *val, int ecount, int *elist, int silent), 123 CCedgegen_x_qboruvka_tour (int ncount, CCdatagroup *dat, int *outcycle, 124 double *val, int ecount, int *elist, int silent), 125 CCedgegen_junk_k_nearest (int ncount, int num, CCdatagroup *dat, 126 double *wcoord, int wantlist, int *ecount, int **elist, int silent), 127 CCedgegen_junk_node_k_nearest (CCdatagroup *dat, double *wcoord, int n, 128 int nearnum, int ncount, int *list), 129 CCedgegen_junk_node_nearest (CCdatagroup *dat, double *wcoord, int ncount, 130 int n, char *marks), 131 CCedgegen_junk_nearest_neighbor_tour (int ncount, int start, 132 CCdatagroup *dat, int *outcycle, double *val, int silent), 133 CCedgegen_junk_greedy_tour (int ncount, CCdatagroup *dat, int *outcycle, 134 double *val, int ecount, int *elist, int silent), 135 CCedgegen_junk_qboruvka_tour (int ncount, CCdatagroup *dat, int *outcycle, 136 double *val, int ecount, int *elist, int silent), 137 CCedgegen_xnear_build (int ncount, CCdatagroup *dat, double *wcoord, 138 CCxnear *xn); 139 140 void 141 CCedgegen_xnear_free (CCxnear *xn); 142 143 144 #endif /* __EDGEGEN_H */ 145