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