From 0145dc7f4fcaf62090a77fb2d69d5d7807c8d48d Mon Sep 17 00:00:00 2001 From: Ian Jackson Date: Sat, 3 Oct 2009 09:38:04 +0100 Subject: [PATCH 1/1] WIP routesearch; searcher --- yarrg/Makefile | 2 +- yarrg/rscommon.h | 11 +++++-- yarrg/rsmain.c | 27 ++++++++++++----- yarrg/rssearch.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++ yarrg/rssql.c | 7 +++-- yarrg/rsvalue.c | 35 +++++++++++----------- 6 files changed, 127 insertions(+), 30 deletions(-) create mode 100644 yarrg/rssearch.c diff --git a/yarrg/Makefile b/yarrg/Makefile index ed4f372..a9c833b 100644 --- a/yarrg/Makefile +++ b/yarrg/Makefile @@ -38,7 +38,7 @@ all: default routesearch CONVERT_OBJS= convert.o ocr.o pages.o structure.o rgbimage.o resolve.o COMMON_OBJS= common.o -ROUTESEARCH_OBJS= rsvalue.o rsmain.o rssql.o +ROUTESEARCH_OBJS= rsvalue.o rsmain.o rssql.o rssearch.o yarrg: $(CONVERT_OBJS) $(COMMON_OBJS) -lnetpbm -lXtst -lX11 -lpcre -lm $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) diff --git a/yarrg/rscommon.h b/yarrg/rscommon.h index d068fa0..1e710dc 100644 --- a/yarrg/rscommon.h +++ b/yarrg/rscommon.h @@ -8,7 +8,9 @@ DF(sql2) \ DF(value) \ DF(lp) + #define debug stdout +#define DEBUG_DEV "/dev/stdout" #include "common.h" @@ -43,14 +45,19 @@ void sql_bind(sqlite3_stmt *ss, int index, int value, extern sqlite3 *db; -void setup(void); +void setup_sql(void); double value_route(int nislands, const int *islands); void setup_value(void); -void setup_commods(void); +void setup_search(void); +void search(int start_isle); extern double max_mass, max_volu, max_capi; extern double distance_loss_factor_per_league; +extern int max_dist; #define LOSS_FACTOR_PER_DELAY_SLOT (1-1e-8) +extern int islandtablesz; + + #endif /*RSCOMMON_H*/ diff --git a/yarrg/rsmain.c b/yarrg/rsmain.c index 49a59a4..4b7dea9 100644 --- a/yarrg/rsmain.c +++ b/yarrg/rsmain.c @@ -5,12 +5,16 @@ int o_quiet= 0; double max_mass=-1, max_volu=-1, max_capi=-1; double distance_loss_factor_per_league; +int max_dist= -1; int main(int argc, const char **argv) { - int ia[argc], ni=0; + const char *arg; debug_flags= ~( dbg_sql2 ); - setup(); + + setup_sql(); + setup_value(); + setup_search(); max_mass= atof(*++argv); max_volu= atof(*++argv); @@ -20,11 +24,20 @@ int main(int argc, const char **argv) { if (!loss_per_league) loss_per_league= 1e-7; distance_loss_factor_per_league= 1.0 - loss_per_league; - const char *arg; - while ((arg= *++argv)) { - ia[ni++]= atoi(arg); + arg= *++argv; + if (!strcmp(arg,"specific")) { + int ia[argc], ni=0; + while ((arg= *++argv)) + ia[ni++]= atoi(arg); + + double val= value_route(ni, ia); + printf("route value is %g\n", val); + } else if (!strcmp(arg,"search")) { + max_dist= atoi(*++argv); + while ((arg= *++argv)) + search(atoi(arg)); + } else { + abort(); } - double val= value_route(ni, ia); - printf("route value is %g\n", val); return 0; } diff --git a/yarrg/rssearch.c b/yarrg/rssearch.c new file mode 100644 index 0000000..c51aae0 --- /dev/null +++ b/yarrg/rssearch.c @@ -0,0 +1,75 @@ +/**/ + +#include "rscommon.h" + +typedef struct Neighbour { + struct Neighbour *next; + int islandid; + int dist; +} Neighbour; + +static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */ +static sqlite3_stmt *ss_neigh; + +static int ports[MAX_ROUTELEN]; + +static Neighbour *get_neighbours(int isle) { + Neighbour **np= &neighbours[isle]; + Neighbour *head= *np; + if (head) return head; + + SQL_BIND(ss_neigh, 1, isle); + while (SQL_STEP(ss_neigh)) { + Neighbour *add= mmalloc(sizeof(*add)); + add->islandid= sqlite3_column_int(ss_neigh, 0); + add->dist= sqlite3_column_int(ss_neigh, 1); + add->next= head; + head= add; + } + SQL_MUST( sqlite3_reset(ss_neigh) ); + + *np= head; + return head; +} + +static double bestsofar; + +static void process_route(int nports) { + double value= value_route(nports, ports); + if (value < bestsofar) return; + + fprintf(stderr,"value %20f route", value); + int i; + for (i=0; i= MAX_ROUTELEN) return; + + Neighbour *add; + for (add= get_neighbours(last_isle); add; add=add->next) { + int newdist= totaldist + add->dist; + if (newdist > max_dist) continue; + + recurse(add->islandid, nports, newdist); + } +} + +void search(int start_isle) { + recurse(start_isle,0,0); +} + +void setup_search(void) { + neighbours= mcalloc(sizeof(*neighbours) * islandtablesz); + + SQL_PREPARE(ss_neigh, + "SELECT biid, dist FROM routes WHERE aiid=?"); +} diff --git a/yarrg/rssql.c b/yarrg/rssql.c index 463ef8b..898ac3b 100644 --- a/yarrg/rssql.c +++ b/yarrg/rssql.c @@ -4,6 +4,8 @@ sqlite3 *db; sqlite3_stmt *ss_ipair; +int islandtablesz; + DEBUG_DEFINE_DEBUGF(sql); static int busy_handler(void *u, int previous) { @@ -12,7 +14,7 @@ static int busy_handler(void *u, int previous) { return 1; } -void setup(void) { +void setup_sql(void) { sqlite3_stmt *sst; SQL_MUST( sqlite3_open("OCEAN-Midnight.db", &db) ); @@ -22,7 +24,8 @@ void setup(void) { assert( !SQL_STEP(sst) ); sqlite3_finalize(sst); - setup_value(); + islandtablesz= 1 + sql_single_int("SELECT max(islandid) FROM islands"); + debugf("SQL islandtablesz=%d\n",islandtablesz); } int sql_single_int(const char *stmt) { diff --git a/yarrg/rsvalue.c b/yarrg/rsvalue.c index f1a8d22..f046c99 100644 --- a/yarrg/rsvalue.c +++ b/yarrg/rsvalue.c @@ -32,7 +32,6 @@ typedef struct { TradesBlock *trades; } IslandPair; -int nislands; IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */ typedef struct IslandTradeEnd { @@ -108,7 +107,7 @@ static int setup_leg_constraints(double max_thing, int legs, const char *wh) { int leg, startrow; if (max_thing < 0 || !legs) return -1; startrow= lpx_add_rows(lp, legs); - for (leg=0; legdst_price - t->src_price) * loss_factor; debugf(" unit profit %f\n", unit_profit); -assert(unit_profit < 1e6); lpx_set_col_bnds(lp, col, LPX_LO, 0, 0); lpx_set_obj_coef(lp, col, unit_profit); @@ -325,17 +323,21 @@ assert(unit_profit < 1e6); next_s:; } /* for (s) */ - if (DEBUGP(lp)) - lpx_write_cpxlp(lp, (char*)"/dev/stdout"); + double profit= 0; - int ipr= lpx_interior(lp); - assert(ipr==LPX_E_OK); + if (lpx_get_num_cols(lp)) { + if (DEBUGP(lp)) + lpx_write_cpxlp(lp, (char*)DEBUG_DEV); - if (DEBUGP(lp)) - lpx_print_ips(lp, (char*)"/dev/stdout"); + int ipr= lpx_interior(lp); + assert(ipr==LPX_E_OK); - assert(lpx_ipt_status(lp) == LPX_T_OPT); - double profit= lpx_ipt_obj_val(lp); + if (DEBUGP(lp)) + lpx_print_ips(lp, (char*)DEBUG_DEV); + + assert(lpx_ipt_status(lp) == LPX_T_OPT); + profit= lpx_ipt_obj_val(lp); + } lpx_delete_prob(lp); lp= 0; @@ -347,9 +349,6 @@ void setup_value(void) { sqlite3_stmt *sst; int i; - nislands= sql_single_int("SELECT max(islandid) FROM islands") + 1; - debugf("VALUE nislands=%d\n",nislands); - commodstablesz= sql_single_int("SELECT max(commodid) FROM commods") + 1; commodstable= mmalloc(sizeof(*commodstable)*commodstablesz); for (i=0; i