abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
gimpel.c File Reference
#include "mincov_int.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START int gimpel_reduce (sm_matrix *A, solution_t *select, int *weight, int lb, int bound, int depth, stats_t *stats, solution_t **best)
 

Function Documentation

ABC_NAMESPACE_IMPL_START int gimpel_reduce ( sm_matrix A,
solution_t select,
int *  weight,
int  lb,
int  bound,
int  depth,
stats_t stats,
solution_t **  best 
)

Definition at line 30 of file gimpel.c.

39 {
40  register sm_row *prow, *save_sec;
41  register sm_col *c1 = NULL, *c2 = NULL; // Suppress "might be used uninitialized"
42  register sm_element *p, *p1;
43  int c1_col_num, c2_col_num;
44  int primary_row_num = -1, secondary_row_num = -1; // Suppress "might be used uninitialized"
45  int reduce_it;
46 
47  reduce_it = 0;
48  for(prow = A->first_row; prow != 0; prow = prow->next_row) {
49  if (prow->length == 2) {
50  c1 = sm_get_col(A, prow->first_col->col_num);
51  c2 = sm_get_col(A, prow->last_col->col_num);
52  if (c1->length == 2) {
53  reduce_it = 1;
54  } else if (c2->length == 2) {
55  c1 = sm_get_col(A, prow->last_col->col_num);
56  c2 = sm_get_col(A, prow->first_col->col_num);
57  reduce_it = 1;
58  }
59  if (reduce_it) {
60  primary_row_num = prow->row_num;
61  secondary_row_num = c1->first_row->row_num;
62  if (secondary_row_num == primary_row_num) {
63  secondary_row_num = c1->last_row->row_num;
64  }
65  break;
66  }
67  }
68  }
69 
70  if (reduce_it) {
71  c1_col_num = c1->col_num;
72  c2_col_num = c2->col_num;
73  save_sec = sm_row_dup(sm_get_row(A, secondary_row_num));
74  sm_row_remove(save_sec, c1_col_num);
75 
76  for(p = c2->first_row; p != 0; p = p->next_row) {
77  if (p->row_num != primary_row_num) {
78  /* merge rows S1 and T */
79  for(p1 = save_sec->first_col; p1 != 0; p1 = p1->next_col) {
80  (void) sm_insert(A, p->row_num, p1->col_num);
81  }
82  }
83  }
84 
85  sm_delcol(A, c1_col_num);
86  sm_delcol(A, c2_col_num);
87  sm_delrow(A, primary_row_num);
88  sm_delrow(A, secondary_row_num);
89 
90  stats->gimpel_count++;
91  stats->gimpel++;
92  *best = sm_mincov(A, select, weight, lb-1, bound-1, depth, stats);
93  stats->gimpel--;
94 
95  if (*best != NIL(solution_t)) {
96  /* is secondary row covered ? */
97  if (sm_row_intersects(save_sec, (*best)->row)) {
98  /* yes, actually select c2 */
99  solution_add(*best, weight, c2_col_num);
100  } else {
101  solution_add(*best, weight, c1_col_num);
102  }
103  }
104 
105  sm_row_free(save_sec);
106  return 1;
107  } else {
108  return 0;
109  }
110 }
int length
Definition: sparse.h:46
sm_row * next_row
Definition: sparse.h:50
static Llb_Mgr_t * p
Definition: llb3Image.c:950
sm_element * last_col
Definition: sparse.h:49
sm_element * last_row
Definition: sparse.h:64
int length
Definition: sparse.h:61
#define NIL(type)
Definition: avl.h:25
void solution_add()
sm_row * sm_row_dup(sm_row *prow)
Definition: rows.c:82
int row_num
Definition: sparse.h:45
void sm_delrow(sm_matrix *A, int i)
Definition: matrix.c:273
#define sm_get_row(A, rownum)
Definition: sparse.h:93
sm_element * first_row
Definition: sparse.h:63
#define sm_get_col(A, colnum)
Definition: sparse.h:89
sm_element * sm_insert(sm_matrix *A, int row, int col)
Definition: matrix.c:155
int col_num
Definition: sparse.h:60
sm_row * first_row
Definition: sparse.h:79
solution_t * sm_mincov(sm_matrix *A, solution_t *select, int *weight, int lb, int bound, int depth, stats_t *stats)
Definition: mincov.c:119
typedefABC_NAMESPACE_HEADER_START struct sm_element_struct sm_element
Definition: sparse.h:21
void sm_row_free(sm_row *prow)
Definition: rows.c:53
void sm_row_remove(sm_row *prow, int col)
Definition: rows.c:126
void sm_delcol(sm_matrix *A, int i)
Definition: matrix.c:307
int sm_row_intersects(sm_row *p1, sm_row *p2)
Definition: rows.c:190
sm_element * first_col
Definition: sparse.h:48