graph-algorithms/tsp/tsp.c
static void build_next(const adj_lst_t *a,
		       stack_t *prev_s,
		       stack_t *next_s,
		       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_size = prev_s->elt_size;
  size_t u, v;
  size_t *prev_set = NULL, *next_set = NULL;
  void *prev_wt = NULL, *next_wt = NULL, *sum_wt = NULL;
  ibit_t ibit;
  prev_set = malloc_perror(1, set_size);
  next_set = malloc_perror(1, set_size);
  prev_wt = malloc_perror(1, wt_size);
  sum_wt = malloc_perror(1, wt_size);
  while (prev_s->num_elts > 0){
    stack_pop(prev_s, prev_set);
    tht->remove(tht->ht, prev_set, prev_wt);
    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;
      set_init(&ibit, v);
      if (set_member(&ibit, &prev_set[1]) == NULL){
	memcpy(next_set, prev_set, set_size);
        next_set[0] = v;
        set_init(&ibit, u);
	set_union(&ibit, &next_set[1]);
	add_wt(sum_wt,
	       prev_wt,
	       p + a->offset);
	next_wt = tht->search(tht->ht, next_set);
	if (next_wt == NULL){
	  tht->insert(tht->ht, next_set, sum_wt);
	  stack_push(next_s, next_set);
	}else if (cmp_wt(next_wt, sum_wt) > 0){
	  tht->insert(tht->ht, next_set, sum_wt);
	}
      }
    }
  }
  free(prev_set);
  free(next_set);
  free(prev_wt);
  free(sum_wt);
  prev_set = NULL;
  next_set = NULL;
  prev_wt = NULL;
  sum_wt = NULL;
}
/**
   Builds reachable sets from previous sets and updates a hash table
   mapping a set to a distance. 
 */
Builds reachable sets from previous sets and updates a hash table
mapping a set to a distance.
Builds reachable sets from previous sets and updates a hash table mapping a set to a distance .
static void build_next(const adj_lst_t *a,
		       stack_t *prev_s,
		       stack_t *next_s,
		       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_size = prev_s->elt_size;
  size_t u, v;
  size_t *prev_set = NULL, *next_set = NULL;
  void *prev_wt = NULL, *next_wt = NULL, *sum_wt = NULL;
  ibit_t ibit;
  prev_set = malloc_perror(1, set_size);
  next_set = malloc_perror(1, set_size);
  prev_wt = malloc_perror(1, wt_size);
  sum_wt = malloc_perror(1, wt_size);
  while (prev_s->num_elts > 0){
    stack_pop(prev_s, prev_set);
    tht->remove(tht->ht, prev_set, prev_wt);
    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;
      set_init(&ibit, v);
      if (set_member(&ibit, &prev_set[1]) == NULL){
	memcpy(next_set, prev_set, set_size);
        next_set[0] = v;
        set_init(&ibit, u);
	set_union(&ibit, &next_set[1]);
	add_wt(sum_wt,
	       prev_wt,
	       p + a->offset);
	next_wt = tht->search(tht->ht, next_set);
	if (next_wt == NULL){
	  tht->insert(tht->ht, next_set, sum_wt);
	  stack_push(next_s, next_set);
	}else if (cmp_wt(next_wt, sum_wt) > 0){
	  tht->insert(tht->ht, next_set, sum_wt);
	}
      }
    }
  }
  free(prev_set);
  free(next_set);
  free(prev_wt);
  free(sum_wt);
  prev_set = NULL;
  next_set = NULL;
  prev_wt = NULL;
  sum_wt = NULL;
}
static void build_next ( const adj_lst_t * a , stack_t * prev_s , stack_t * next_s , 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_size = prev_s -> elt_size ; size_t u , v ; size_t * prev_set = NULL , * next_set = NULL ; void * prev_wt = NULL , * next_wt = NULL , * sum_wt = NULL ; ibit_t ibit ; prev_set = malloc_perror ( 1 , set_size ) ; next_set = malloc_perror ( 1 , set_size ) ; prev_wt = malloc_perror ( 1 , wt_size ) ; sum_wt = malloc_perror ( 1 , wt_size ) ; while ( prev_s -> num_elts > 0 ) { stack_pop ( prev_s , prev_set ) ; tht -> remove ( tht -> ht , prev_set , prev_wt ) ; 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 ; set_init ( & ibit , v ) ; if ( set_member ( & ibit , & prev_set [ 1 ] ) == NULL ) { memcpy ( next_set , prev_set , set_size ) ; next_set [ 0 ] = v ; set_init ( & ibit , u ) ; set_union ( & ibit , & next_set [ 1 ] ) ; add_wt ( sum_wt , prev_wt , p + a -> offset ) ; next_wt = tht -> search ( tht -> ht , next_set ) ; if ( next_wt == NULL ) { tht -> insert ( tht -> ht , next_set , sum_wt ) ; stack_push ( next_s , next_set ) ; } else if ( cmp_wt ( next_wt , sum_wt ) > 0 ) { tht -> insert ( tht -> ht , next_set , sum_wt ) ; } } } } free ( prev_set ) ; free ( next_set ) ; free ( prev_wt ) ; free ( sum_wt ) ; prev_set = NULL ; next_set = NULL ; prev_wt = NULL ; sum_wt = NULL ; }
Builds reachable sets from previous sets and updates a hash table
mapping a set to a distance.
Builds reachable sets from previous sets and updates a hash table mapping a set to a distance .