00001 /* 00002 * Revision Control Information 00003 * 00004 * $Source$ 00005 * $Author$ 00006 * $Revision$ 00007 * $Date$ 00008 * 00009 */ 00010 //#include "port.h" 00011 //#include "utility.h" 00012 #include "sparse.h" 00013 #include "mincov.h" 00014 00015 #include "util_hack.h" // added 00016 00017 00018 typedef struct stats_struct stats_t; 00019 struct stats_struct { 00020 int debug; /* 1 if debugging is enabled */ 00021 int max_print_depth; /* dump stats for levels up to this level */ 00022 int max_depth; /* deepest the recursion has gone */ 00023 int nodes; /* total nodes visited */ 00024 int component; /* currently solving a component */ 00025 int comp_count; /* number of components detected */ 00026 int gimpel_count; /* number of times Gimpel reduction applied */ 00027 int gimpel; /* currently inside Gimpel reduction */ 00028 long start_time; /* cpu time when the covering started */ 00029 int no_branching; 00030 int lower_bound; 00031 }; 00032 00033 00034 00035 typedef struct solution_struct solution_t; 00036 struct solution_struct { 00037 sm_row *row; 00038 int cost; 00039 }; 00040 00041 00042 extern solution_t *solution_alloc(); 00043 extern void solution_free(); 00044 extern solution_t *solution_dup(); 00045 extern void solution_accept(); 00046 extern void solution_reject(); 00047 extern void solution_add(); 00048 extern solution_t *solution_choose_best(); 00049 00050 extern solution_t *sm_maximal_independent_set(); 00051 extern solution_t *sm_mincov(); 00052 extern int gimpel_reduce(); 00053 00054 00055 #define WEIGHT(weight, col) (weight == NIL(int) ? 1 : weight[col])
1.6.1