java-topology/defects/naev-0001/test/test_naev_0001.c

/*
 * Unit test for naev-0001: Dijkstra/A* pathfinding linked-list
 * open/closed sets O(V^2) vs O(1) indexed lookup.
 *
 * Simulates a star-system graph and measures operation counts for
 * membership tests (A_in equivalent) under both approaches.
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* --- Minimal types to simulate Naev pathfinding --- */

typedef struct StarSystem_ {
   int         id;
   const char *name;
   int        *neighbors; /* array of neighbor IDs */
   int         nneighbors;
} StarSystem;

typedef struct SysNode_ {
   struct SysNode_ *next;
   struct SysNode_ *parent;
   StarSystem      *sys;
   int              g;
   double           d;
} SysNode;

/* --- DEFECTIVE: linked-list membership test O(N) --- */

static long ops_defective = 0;

static SysNode *defective_in( SysNode *first, const StarSystem *sys )
{
   SysNode *n = first;
   while ( n != NULL ) {
      ops_defective++;
      if ( n->sys == sys )
         return n;
      n = n->next;
   }
   return NULL;
}

static SysNode *defective_lowest( SysNode *first )
{
   if ( first == NULL )
      return NULL;
   SysNode *lowest = first;
   SysNode *n      = first->next;
   while ( n != NULL ) {
      ops_defective++;
      if ( n->g < lowest->g || ( n->g == lowest->g && n->d < lowest->d ) )
         lowest = n;
      n = n->next;
   }
   return lowest;
}

static SysNode *defective_add( SysNode *first, SysNode *cur )
{
   if ( first == NULL )
      return cur;
   SysNode *n = first;
   while ( n->next != NULL )
      n = n->next;
   n->next = cur;
   return first;
}

static SysNode *defective_rm( SysNode *first, const StarSystem *sys )
{
   if ( first == NULL )
      return NULL;
   if ( first->sys == sys ) {
      SysNode *n  = first->next;
      first->next = NULL;
      return n;
   }
   SysNode *p = first;
   while ( p->next != NULL ) {
      if ( p->next->sys == sys ) {
         SysNode *rem = p->next;
         p->next      = rem->next;
         rem->next    = NULL;
         return first;
      }
      p = p->next;
   }
   return first;
}

/* --- PATCHED: array-indexed O(1) membership test --- */

static long      ops_patched = 0;
static SysNode **patched_open_idx  = NULL;
static SysNode **patched_close_idx = NULL;

static SysNode *patched_addSorted( SysNode *first, SysNode *cur )
{
   patched_open_idx[cur->sys->id] = cur;
   ops_patched++;
   if ( first == NULL ) {
      cur->next = NULL;
      return cur;
   }
   if ( cur->g < first->g ||
        ( cur->g == first->g && cur->d < first->d ) ) {
      cur->next = first;
      return cur;
   }
   SysNode *p = first;
   while ( p->next != NULL &&
           ( p->next->g < cur->g ||
             ( p->next->g == cur->g && p->next->d <= cur->d ) ) ) {
      ops_patched++;
      p = p->next;
   }
   cur->next = p->next;
   p->next   = cur;
   return first;
}

static SysNode *patched_rmOpen( SysNode *first, const StarSystem *sys )
{
   patched_open_idx[sys->id] = NULL;
   ops_patched++;
   if ( first == NULL )
      return NULL;
   if ( first->sys == sys ) {
      SysNode *n  = first->next;
      first->next = NULL;
      return n;
   }
   SysNode *p = first;
   while ( p->next != NULL ) {
      ops_patched++;
      if ( p->next->sys == sys ) {
         SysNode *rem = p->next;
         p->next      = rem->next;
         rem->next    = NULL;
         return first;
      }
      p = p->next;
   }
   return first;
}

/* --- Graph generation: chain graph with some cross-links --- */

static StarSystem *make_graph( int V )
{
   StarSystem *sys = calloc( V, sizeof( StarSystem ) );
   for ( int i = 0; i < V; i++ ) {
      sys[i].id   = i;
      sys[i].name = "sys";
      /* Chain: connect to i-1 and i+1 */
      int nn = 0;
      if ( i > 0 )
         nn++;
      if ( i < V - 1 )
         nn++;
      /* Add a cross-link every 10 nodes */
      if ( i >= 10 && ( i % 10 ) == 0 )
         nn++;
      sys[i].neighbors  = calloc( nn, sizeof( int ) );
      sys[i].nneighbors = 0;
      if ( i > 0 )
         sys[i].neighbors[sys[i].nneighbors++] = i - 1;
      if ( i < V - 1 )
         sys[i].neighbors[sys[i].nneighbors++] = i + 1;
      if ( i >= 10 && ( i % 10 ) == 0 )
         sys[i].neighbors[sys[i].nneighbors++] = i - 10;
   }
   return sys;
}

static void free_graph( StarSystem *sys, int V )
{
   for ( int i = 0; i < V; i++ )
      free( sys[i].neighbors );
   free( sys );
}

/* --- Dijkstra with defective approach --- */

static int dijkstra_defective( StarSystem *sys, int V, int src, int dst )
{
   SysNode *nodes = calloc( V, sizeof( SysNode ) );
   SysNode *open = NULL, *closed = NULL;

   ops_defective = 0;

   nodes[src].sys = &sys[src];
   nodes[src].g   = 0;
   nodes[src].d   = 0.0;
   open           = defective_add( open, &nodes[src] );

   int iter = 0;
   while ( 1 ) {
      SysNode *cur = defective_lowest( open );
      if ( cur == NULL )
         break;
      if ( cur->sys->id == dst )
         break;
      if ( ++iter > V * 2 )
         break;

      open   = defective_rm( open, cur->sys );
      closed = defective_add( closed, cur );

      int cost = cur->g + 1;
      for ( int i = 0; i < cur->sys->nneighbors; i++ ) {
         int         nid = cur->sys->neighbors[i];
         StarSystem *ns  = &sys[nid];

         SysNode *cc = defective_in( closed, ns );
         if ( cc != NULL && cost >= cc->g )
            continue;

         SysNode *oc = defective_in( open, ns );
         if ( oc != NULL ) {
            if ( cost < oc->g )
               open = defective_rm( open, ns );
            else
               continue;
         }

         nodes[nid].sys    = ns;
         nodes[nid].g      = cost;
         nodes[nid].d      = (double)cost;
         nodes[nid].parent = cur;
         nodes[nid].next   = NULL;
         open              = defective_add( open, &nodes[nid] );
      }
   }

   free( nodes );
   return (int)ops_defective;
}

/* --- Dijkstra with patched approach --- */

static int dijkstra_patched( StarSystem *sys, int V, int src, int dst )
{
   SysNode *nodes = calloc( V, sizeof( SysNode ) );
   SysNode *open = NULL, *closed = NULL;

   ops_patched    = 0;
   patched_open_idx  = calloc( V, sizeof( SysNode * ) );
   patched_close_idx = calloc( V, sizeof( SysNode * ) );

   nodes[src].sys = &sys[src];
   nodes[src].g   = 0;
   nodes[src].d   = 0.0;
   open           = patched_addSorted( open, &nodes[src] );

   int iter = 0;
   while ( open != NULL ) {
      SysNode *cur = open; /* Head is always lowest (sorted insert). */
      if ( cur->sys->id == dst )
         break;
      if ( ++iter > V * 2 )
         break;

      /* Move from open to closed. */
      open                             = open->next;
      patched_open_idx[cur->sys->id]   = NULL;
      cur->next                        = closed;
      closed                           = cur;
      patched_close_idx[cur->sys->id]  = cur;
      ops_patched++;

      int cost = cur->g + 1;
      for ( int i = 0; i < cur->sys->nneighbors; i++ ) {
         int         nid = cur->sys->neighbors[i];
         StarSystem *ns  = &sys[nid];

         /* O(1) closed check */
         SysNode *cc = patched_close_idx[ns->id];
         ops_patched++;
         if ( cc != NULL && cost >= cc->g )
            continue;

         /* O(1) open check */
         SysNode *oc = patched_open_idx[ns->id];
         ops_patched++;
         if ( oc != NULL ) {
            if ( cost < oc->g )
               open = patched_rmOpen( open, ns );
            else
               continue;
         }

         nodes[nid].sys    = ns;
         nodes[nid].g      = cost;
         nodes[nid].d      = (double)cost;
         nodes[nid].parent = cur;
         nodes[nid].next   = NULL;
         open              = patched_addSorted( open, &nodes[nid] );
      }
   }

   free( patched_open_idx );
   free( patched_close_idx );
   free( nodes );
   return (int)ops_patched;
}

int main( void )
{
   int sizes[] = { 50, 100, 200, 500 };
   int nsizes  = sizeof( sizes ) / sizeof( sizes[0] );
   int pass    = 1;

   printf( "naev-0001: Dijkstra linked-list O(V^2) vs indexed O(V)\n" );
   printf( "%-8s %12s %12s %8s\n", "V", "defective", "patched", "ratio" );
   printf( "-------- ------------ ------------ --------\n" );

   for ( int t = 0; t < nsizes; t++ ) {
      int         V   = sizes[t];
      StarSystem *sys = make_graph( V );
      int         src = 0;
      int         dst = V - 1;

      long def_ops = dijkstra_defective( sys, V, src, dst );
      long pat_ops = dijkstra_patched( sys, V, src, dst );

      double ratio = ( pat_ops > 0 ) ? (double)def_ops / (double)pat_ops : 0.0;
      printf( "%-8d %12ld %12ld %8.1fx\n", V, def_ops, pat_ops, ratio );

      if ( ratio < 2.0 ) {
         fprintf( stderr,
                  "FAIL: V=%d ratio=%.1fx, expected >= 2.0x improvement\n", V,
                  ratio );
         pass = 0;
      }

      free_graph( sys, V );
   }

   printf( "\n%s\n", pass ? "PASS" : "FAIL" );
   return pass ? 0 : 1;
}