graph-algorithms/tsp/tsp.c
int tsp(const adj_lst_t *a,
	size_t start,
	void *dist,
	const tsp_ht_t *tht,
	void (*add_wt)(void *, const void *, const void *),
	int (*cmp_wt)(const void *, const void *)){
  const char *p = NULL, *p_start = NULL, *p_end = NULL;
  size_t wt_size = a->wt_size;
  size_t set_count, set_size;
  size_t u, v;
  size_t i;
  size_t *prev_set = NULL;
  void *sum_wt = NULL;
  boolean_t final_dist_updated = FALSE;
  stack_t prev_s, next_s;
  ht_def_t ht_def;
  context_t context;
  tsp_ht_t tht_def;
  const tsp_ht_t *thtp = tht;
  set_count = a->num_vts / C_SET_ELT_BIT;
  if (a->num_vts % C_SET_ELT_BIT){
    set_count++;
  }
  set_count++; /* + last reached vertex representation */
  set_size = set_count * C_SET_ELT_SIZE;
  prev_set = calloc_perror(1, set_size);
  sum_wt = malloc_perror(1, wt_size);
  prev_set[0] = start;
  memset(dist, 0, wt_size);
  stack_init(&prev_s, 1, set_size, NULL);
  stack_push(&prev_s, prev_set);
  if (thtp == NULL){
    context.num_vts = a->num_vts;
    tht_def.ht = &ht_def;
    tht_def.context = &context;
    tht_def.init = (tsp_ht_init)ht_def_init;
    tht_def.insert = (tsp_ht_insert)ht_def_insert;
    tht_def.search = (tsp_ht_search)ht_def_search;
    tht_def.remove = (tsp_ht_remove)ht_def_remove;
    tht_def.free = (tsp_ht_free)ht_def_free;
    thtp = &tht_def;
  }
  thtp->init(thtp->ht, set_size, wt_size, NULL, thtp->context);
  thtp->insert(thtp->ht, prev_set, dist);
  for (i = 0; i < a->num_vts - 1; i++){
    stack_init(&next_s, 1, set_size, NULL);
    build_next(a, &prev_s, &next_s, thtp, add_wt, cmp_wt);
    stack_free(&prev_s);
    prev_s = next_s;
    if (prev_s.num_elts == 0){
      /* no progress made */
      stack_free(&prev_s);
      thtp->free(thtp->ht);
      free(prev_set);
      free(sum_wt);
      thtp = NULL;
      prev_set = NULL;
      sum_wt = NULL;
      return 1;
    }
  }
  /* compute the return to start */
  while (prev_s.num_elts > 0){
    stack_pop(&prev_s, prev_set);
    u = prev_set[0];
    p_start = a->vt_wts[u]->elts;
    p_end = p_start + a->vt_wts[u]->num_elts * a->pair_size;
    for (p = p_start; p != p_end; p += a->pair_size){
      v = *(const size_t *)p;
      if (v == start){
	add_wt(sum_wt,
	       thtp->search(thtp->ht, prev_set),
	       p + a->offset);
	if (!final_dist_updated){
	  memcpy(dist, sum_wt, wt_size);
	  final_dist_updated = TRUE;
	}else if (cmp_wt(dist, sum_wt) > 0){
	  memcpy(dist, sum_wt, wt_size);
	}
      }
    }
  }
  stack_free(&prev_s);
  thtp->free(thtp->ht);
  free(prev_set);
  free(sum_wt);
  thtp = NULL;
  prev_set = NULL;
  sum_wt = NULL;
  if (!final_dist_updated && a->num_vts > 1) return 1;
  return 0;
}
/**
   Copies to the block pointed to by dist the shortest tour length from 
   start to start across all vertices without revisiting, if a tour exists. 
   Returns 0 if a tour exists, otherwise returns 1.
   a           : pointer to an adjacency list with at least one vertex
   start       : start vertex for running the algorithm
   dist        : pointer to a preallocated block of the size of a weight in
                 the adjacency list
   tht         : - NULL pointer, if a default hash table is used for
                 set hashing operations; a default hash table contains an
                 array with a count that is equal to n * 2^n, where n is the
                 number of vertices in the adjacency list; the maximal n
                 in a default hash table is system-dependent and is less
                 than sizeof(size_t) * CHAR_BIT; if the allocation of a
                 default hash table fails, the program terminates with an
                 error message
                 - a pointer to a set of parameters specifying a hash table
                 used for set hashing operations; the size of a hash key is 
                 k * (1 + lowest # k-sized blocks s.t. # bits >= # vertices),
                 where k = sizeof(size_t)
   add_wt      : addition function which copies the sum of the weight values
                 pointed to by the second and third arguments to the
                 preallocated weight block pointed to by the first argument
   cmp_wt      : comparison function which returns a negative integer value
                 if the weight value pointed to by the first argument is
                 less than the weight value pointed to by the second, a
                 positive integer value if the weight value pointed to by
                 the first argument is greater than the weight value 
                 pointed to by the second, and zero integer value if the two
                 weight values are equal
*/
Copies to the block pointed to by dist the shortest tour length from
start to start across all vertices without revisiting, if a tour exists.
Returns 0 if a tour exists, otherwise returns 1.
a           : pointer to an adjacency list with at least one vertex
start       : start vertex for running the algorithm
dist        : pointer to a preallocated block of the size of a weight in
the adjacency list
tht         : - NULL pointer, if a default hash table is used for
set hashing operations; a default hash table contains an
array with a count that is equal to n * 2^n, where n is the
number of vertices in the adjacency list; the maximal n
in a default hash table is system-dependent and is less
than sizeof(size_t) * CHAR_BIT; if the allocation of a
default hash table fails, the program terminates with an
error message
a pointer to a set of parameters specifying a hash table
used for set hashing operations; the size of a hash key is
k * (1 + lowest # k-sized blocks s.t. # bits >= # vertices),
where k = sizeof(size_t)
add_wt      : addition function which copies the sum of the weight values
pointed to by the second and third arguments to the
preallocated weight block pointed to by the first argument
cmp_wt      : comparison function which returns a negative integer value
if the weight value pointed to by the first argument is
less than the weight value pointed to by the second, a
positive integer value if the weight value pointed to by
the first argument is greater than the weight value
pointed to by the second, and zero integer value if the two
weight values are equal
Copies to the block pointed to by dist the shortest tour length from start to start across all vertices without revisiting if a tour exists . Returns 0 if a tour exists otherwise returns 1 . a : pointer to an adjacency list with at least one vertex start : start vertex for running the algorithm dist : pointer to a preallocated block of the size of a weight in the adjacency list tht : - NULL pointer if a default hash table is used for set hashing operations ; a default hash table contains an array with a count that is equal to n * 2^n where n is the number of vertices in the adjacency list ; the maximal n in a default hash table is system - dependent and is less than sizeof ( size_t ) * CHAR_BIT ; if the allocation of a default hash table fails the program terminates with an error message a pointer to a set of parameters specifying a hash table used for set hashing operations ; the size of a hash key is k * ( 1 + lowest # k - sized blocks s . t . # bits > = # vertices ) where k = sizeof ( size_t ) add_wt : addition function which copies the sum of the weight values pointed to by the second and third arguments to the preallocated weight block pointed to by the first argument cmp_wt : comparison function which returns a negative integer value if the weight value pointed to by the first argument is less than the weight value pointed to by the second a positive integer value if the weight value pointed to by the first argument is greater than the weight value pointed to by the second and zero integer value if the two weight values are equal
int tsp(const adj_lst_t *a,
	size_t start,
	void *dist,
	const tsp_ht_t *tht,
	void (*add_wt)(void *, const void *, const void *),
	int (*cmp_wt)(const void *, const void *)){
  const char *p = NULL, *p_start = NULL, *p_end = NULL;
  size_t wt_size = a->wt_size;
  size_t set_count, set_size;
  size_t u, v;
  size_t i;
  size_t *prev_set = NULL;
  void *sum_wt = NULL;
  boolean_t final_dist_updated = FALSE;
  stack_t prev_s, next_s;
  ht_def_t ht_def;
  context_t context;
  tsp_ht_t tht_def;
  const tsp_ht_t *thtp = tht;
  set_count = a->num_vts / C_SET_ELT_BIT;
  if (a->num_vts % C_SET_ELT_BIT){
    set_count++;
  }
  set_count++; 
  set_size = set_count * C_SET_ELT_SIZE;
  prev_set = calloc_perror(1, set_size);
  sum_wt = malloc_perror(1, wt_size);
  prev_set[0] = start;
  memset(dist, 0, wt_size);
  stack_init(&prev_s, 1, set_size, NULL);
  stack_push(&prev_s, prev_set);
  if (thtp == NULL){
    context.num_vts = a->num_vts;
    tht_def.ht = &ht_def;
    tht_def.context = &context;
    tht_def.init = (tsp_ht_init)ht_def_init;
    tht_def.insert = (tsp_ht_insert)ht_def_insert;
    tht_def.search = (tsp_ht_search)ht_def_search;
    tht_def.remove = (tsp_ht_remove)ht_def_remove;
    tht_def.free = (tsp_ht_free)ht_def_free;
    thtp = &tht_def;
  }
  thtp->init(thtp->ht, set_size, wt_size, NULL, thtp->context);
  thtp->insert(thtp->ht, prev_set, dist);
  for (i = 0; i < a->num_vts - 1; i++){
    stack_init(&next_s, 1, set_size, NULL);
    build_next(a, &prev_s, &next_s, thtp, add_wt, cmp_wt);
    stack_free(&prev_s);
    prev_s = next_s;
    if (prev_s.num_elts == 0){
      stack_free(&prev_s);
      thtp->free(thtp->ht);
      free(prev_set);
      free(sum_wt);
      thtp = NULL;
      prev_set = NULL;
      sum_wt = NULL;
      return 1;
    }
  }
  while (prev_s.num_elts > 0){
    stack_pop(&prev_s, prev_set);
    u = prev_set[0];
    p_start = a->vt_wts[u]->elts;
    p_end = p_start + a->vt_wts[u]->num_elts * a->pair_size;
    for (p = p_start; p != p_end; p += a->pair_size){
      v = *(const size_t *)p;
      if (v == start){
	add_wt(sum_wt,
	       thtp->search(thtp->ht, prev_set),
	       p + a->offset);
	if (!final_dist_updated){
	  memcpy(dist, sum_wt, wt_size);
	  final_dist_updated = TRUE;
	}else if (cmp_wt(dist, sum_wt) > 0){
	  memcpy(dist, sum_wt, wt_size);
	}
      }
    }
  }
  stack_free(&prev_s);
  thtp->free(thtp->ht);
  free(prev_set);
  free(sum_wt);
  thtp = NULL;
  prev_set = NULL;
  sum_wt = NULL;
  if (!final_dist_updated && a->num_vts > 1) return 1;
  return 0;
}
int tsp ( const adj_lst_t * a , size_t start , void * dist , const tsp_ht_t * tht , void ( * add_wt ) ( void * , const void * , const void * ) , int ( * cmp_wt ) ( const void * , const void * ) ) { const char * p = NULL , * p_start = NULL , * p_end = NULL ; size_t wt_size = a -> wt_size ; size_t set_count , set_size ; size_t u , v ; size_t i ; size_t * prev_set = NULL ; void * sum_wt = NULL ; boolean_t final_dist_updated = FALSE ; stack_t prev_s , next_s ; ht_def_t ht_def ; context_t context ; tsp_ht_t tht_def ; const tsp_ht_t * thtp = tht ; set_count = a -> num_vts / C_SET_ELT_BIT ; if ( a -> num_vts % C_SET_ELT_BIT ) { set_count ++ ; } set_count ++ ; set_size = set_count * C_SET_ELT_SIZE ; prev_set = calloc_perror ( 1 , set_size ) ; sum_wt = malloc_perror ( 1 , wt_size ) ; prev_set [ 0 ] = start ; memset ( dist , 0 , wt_size ) ; stack_init ( & prev_s , 1 , set_size , NULL ) ; stack_push ( & prev_s , prev_set ) ; if ( thtp == NULL ) { context . num_vts = a -> num_vts ; tht_def . ht = & ht_def ; tht_def . context = & context ; tht_def . init = ( tsp_ht_init ) ht_def_init ; tht_def . insert = ( tsp_ht_insert ) ht_def_insert ; tht_def . search = ( tsp_ht_search ) ht_def_search ; tht_def . remove = ( tsp_ht_remove ) ht_def_remove ; tht_def . free = ( tsp_ht_free ) ht_def_free ; thtp = & tht_def ; } thtp -> init ( thtp -> ht , set_size , wt_size , NULL , thtp -> context ) ; thtp -> insert ( thtp -> ht , prev_set , dist ) ; for ( i = 0 ; i < a -> num_vts - 1 ; i ++ ) { stack_init ( & next_s , 1 , set_size , NULL ) ; build_next ( a , & prev_s , & next_s , thtp , add_wt , cmp_wt ) ; stack_free ( & prev_s ) ; prev_s = next_s ; if ( prev_s . num_elts == 0 ) { stack_free ( & prev_s ) ; thtp -> free ( thtp -> ht ) ; free ( prev_set ) ; free ( sum_wt ) ; thtp = NULL ; prev_set = NULL ; sum_wt = NULL ; return 1 ; } } while ( prev_s . num_elts > 0 ) { stack_pop ( & prev_s , prev_set ) ; u = prev_set [ 0 ] ; p_start = a -> vt_wts [ u ] -> elts ; p_end = p_start + a -> vt_wts [ u ] -> num_elts * a -> pair_size ; for ( p = p_start ; p != p_end ; p += a -> pair_size ) { v = * ( const size_t * ) p ; if ( v == start ) { add_wt ( sum_wt , thtp -> search ( thtp -> ht , prev_set ) , p + a -> offset ) ; if ( ! final_dist_updated ) { memcpy ( dist , sum_wt , wt_size ) ; final_dist_updated = TRUE ; } else if ( cmp_wt ( dist , sum_wt ) > 0 ) { memcpy ( dist , sum_wt , wt_size ) ; } } } } stack_free ( & prev_s ) ; thtp -> free ( thtp -> ht ) ; free ( prev_set ) ; free ( sum_wt ) ; thtp = NULL ; prev_set = NULL ; sum_wt = NULL ; if ( ! final_dist_updated && a -> num_vts > 1 ) return 1 ; return 0 ; }
Copies to the block pointed to by dist the shortest tour length from
start to start across all vertices without revisiting, if a tour exists.
Copies to the block pointed to by dist the shortest tour length from start to start across all vertices without revisiting if a tour exists .
/* + last reached vertex representation */ /* no progress made */ /* compute the return to start */