5 DEBUG_DEFINE_DEBUGF(search);
7 typedef struct Neighbour {
8 struct Neighbour *next;
13 static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
14 static sqlite3_stmt *ss_neigh;
16 static int ports[MAX_ROUTELEN];
18 static Neighbour *get_neighbours(int isle) {
19 Neighbour **np= &neighbours[isle];
21 if (head) return head;
23 SQL_BIND(ss_neigh, 1, isle);
24 while (SQL_STEP(ss_neigh)) {
25 Neighbour *add= mmalloc(sizeof(*add));
26 add->islandid= sqlite3_column_int(ss_neigh, 0);
27 add->dist= sqlite3_column_int(ss_neigh, 1);
31 SQL_MUST( sqlite3_reset(ss_neigh) );
37 static double best_absolute, best_perleague;
39 static void process_route(int nports, int totaldist) {
42 debugf("========== ROUTE");
43 for (i=0; i<nports; i++)
44 debugf(" %d",ports[i]);
47 double absolute= value_route(nports, ports);
48 double perleague= absolute / (totaldist + nports);
50 if (absolute < best_absolute && perleague < best_perleague) return;
52 #define CHK(absperl) \
53 fprintf(stderr,#absperl " %15f", absperl); \
54 if (absperl < best_##absperl) fputs(" ",stderr); \
55 else { best_##absperl= absperl; fputs("** ",stderr); }
60 fputs(" route",stderr);
62 for (i=0; i<nports; i++)
63 fprintf(stderr," %d",ports[i]);
67 static void recurse(int last_isle,
68 int nports, /* excluding last_isle */
69 int totaldist /* including last_isle */) {
70 ports[nports++]= last_isle;
71 process_route(nports, totaldist);
72 if (nports >= MAX_ROUTELEN) return;
75 for (add= get_neighbours(last_isle); add; add=add->next) {
76 int newdist= totaldist + add->dist;
77 if (newdist > max_dist) continue;
79 recurse(add->islandid, nports, newdist);
83 void search(int start_isle) {
84 recurse(start_isle,0,0);
87 void setup_search(void) {
88 neighbours= mcalloc(sizeof(*neighbours) * islandtablesz);
91 "SELECT biid, dist FROM routes WHERE aiid=?");