abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
gimpel.c
Go to the documentation of this file.
1 /*
2  * Revision Control Information
3  *
4  * $Source$
5  * $Author$
6  * $Revision$
7  * $Date$
8  *
9  */
10 #include "mincov_int.h"
11 
13 
14 
15 
16 /*
17  * check for:
18  *
19  * c1 c2 rest
20  * -- -- ---
21  * 1 1 0 0 0 0 <-- primary row
22  * 1 0 S1 <-- secondary row
23  * 0 1 T1
24  * 0 1 T2
25  * 0 1 Tn
26  * 0 0 R
27  */
28 
29 int
30 gimpel_reduce(A, select, weight, lb, bound, depth, stats, best)
31 sm_matrix *A;
32 solution_t *select;
33 int *weight;
34 int lb;
35 int bound;
36 int depth;
37 stats_t *stats;
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 }
112 
int length
Definition: sparse.h:46
sm_row * next_row
Definition: sparse.h:50
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: gimpel.c:30
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 ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
#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
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
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