- Generated on Wed Oct 12 2011 00:34:49 for VIS by
1.7.3
|
VIS
|
00001 00022 #include "markInt.h" 00023 00024 /*---------------------------------------------------------------------------*/ 00025 /* Constant declarations */ 00026 /*---------------------------------------------------------------------------*/ 00027 00028 00029 /*---------------------------------------------------------------------------*/ 00030 /* Stucture declarations */ 00031 /*---------------------------------------------------------------------------*/ 00032 00033 00034 /*---------------------------------------------------------------------------*/ 00035 /* Type declarations */ 00036 /*---------------------------------------------------------------------------*/ 00037 00038 00039 /*---------------------------------------------------------------------------*/ 00040 /* Variable declarations */ 00041 /*---------------------------------------------------------------------------*/ 00042 00043 00044 /*---------------------------------------------------------------------------*/ 00045 /* Macro declarations */ 00046 /*---------------------------------------------------------------------------*/ 00047 00048 00051 /*---------------------------------------------------------------------------*/ 00052 /* Static function prototypes */ 00053 /*---------------------------------------------------------------------------*/ 00054 00055 00059 /*---------------------------------------------------------------------------*/ 00060 /* Definition of exported functions */ 00061 /*---------------------------------------------------------------------------*/ 00062 00079 bdd_node * 00080 Mark_addInProb( 00081 bdd_manager *manager, 00082 bdd_node *tr, 00083 bdd_node *cube, 00084 st_table *probTable) 00085 { 00086 st_table *visited; 00087 st_generator *gen; 00088 bdd_node *result, *r, *k; 00089 00090 do { 00091 bdd_set_reordered_field(manager, 0); 00092 visited = st_init_table(st_ptrcmp,st_ptrhash); 00093 bdd_ref(result = bdd_read_one(manager)); 00094 st_insert(visited,(char *)result,(char *)result); 00095 bdd_ref(result = bdd_read_zero(manager)); 00096 st_insert(visited,(char *)result,(char *)result); 00097 result = MarkAddInProbRecur(manager,tr,cube,probTable,visited); 00098 if (result) 00099 bdd_ref(result); 00100 st_foreach_item(visited,gen,&k,&r) { 00101 bdd_recursive_deref(manager,r); 00102 } 00103 st_free_table(visited); 00104 } while (bdd_read_reordered_field(manager) == 1); 00105 00106 bdd_deref(result); 00107 return(result); 00108 00109 } /* end of Mark_addInProb */ 00110 00111 00112 /*---------------------------------------------------------------------------*/ 00113 /* Definition of internal functions */ 00114 /*---------------------------------------------------------------------------*/ 00115 00127 bdd_node * 00128 MarkAddInProbRecur( 00129 bdd_manager *manager, 00130 bdd_node *tr, 00131 bdd_node *cube, 00132 st_table *probTable, 00133 st_table *visited) 00134 { 00135 int topTR,topC; 00136 int index; 00137 double *prob; 00138 bdd_node *solT,*solE; 00139 bdd_node *solPT,*solPE; 00140 bdd_node *result; 00141 bdd_node *unique; 00142 00143 /* lookup in the cache */ 00144 if(st_lookup(visited,tr,&result)) 00145 return(result); 00146 00147 /* the cube is one then return */ 00148 if ( cube == bdd_read_one(manager)) 00149 return tr; 00150 00151 /* Obtain the top variable indexes */ 00152 topTR = bdd_get_level_from_id(manager,bdd_node_read_index(tr)); 00153 topC = bdd_get_level_from_id(manager,bdd_node_read_index(cube)); 00154 00155 /* The function does not depend on the top variable of the cube */ 00156 if (topTR > topC ) { 00157 result = MarkAddInProbRecur(manager,tr,bdd_bdd_T(cube),probTable,visited); 00158 return(result); 00159 } 00160 00161 /* If both top variables are equal, solve subproblems and combine */ 00162 if (topTR == topC ) { 00163 solT = MarkAddInProbRecur(manager,bdd_bdd_T(tr),bdd_bdd_T(cube), 00164 probTable,visited); 00165 if (solT == NULL) { 00166 return NULL; 00167 } 00168 bdd_ref(solT); 00169 solE = MarkAddInProbRecur(manager,bdd_bdd_E(tr),bdd_bdd_T(cube), 00170 probTable,visited); 00171 if (solE == NULL) { 00172 bdd_recursive_deref(manager,solT); 00173 return NULL; 00174 } 00175 bdd_ref(solE); 00176 index = bdd_node_read_index(cube); 00177 st_lookup(probTable,(char *)(long)index,&prob); 00178 unique = bdd_add_const(manager,*prob); 00179 if(unique == NULL) { 00180 bdd_recursive_deref(manager,solT); 00181 bdd_recursive_deref(manager,solE); 00182 return NULL; 00183 } 00184 bdd_ref(unique); 00185 solPT = bdd_add_apply_recur(manager,bdd_add_times,solT,unique); 00186 if (solPT == NULL) { 00187 bdd_recursive_deref(manager,solT); 00188 bdd_recursive_deref(manager,solE); 00189 bdd_recursive_deref(manager,unique); 00190 return NULL; 00191 } 00192 bdd_ref(solPT); 00193 bdd_recursive_deref(manager,unique); 00194 bdd_recursive_deref(manager,solT); 00195 unique = bdd_add_const(manager,1.0 - *prob); 00196 if (unique == NULL) { 00197 bdd_recursive_deref(manager,solE); 00198 bdd_recursive_deref(manager,solPT); 00199 return NULL; 00200 } 00201 bdd_ref(unique); 00202 solPE = bdd_add_apply_recur(manager,bdd_add_times,solE,unique); 00203 if (solPE == NULL) { 00204 bdd_recursive_deref(manager,unique); 00205 bdd_recursive_deref(manager,solPT); 00206 bdd_recursive_deref(manager,solE); 00207 return NULL; 00208 } 00209 bdd_ref(solPE); 00210 bdd_recursive_deref(manager,unique); 00211 bdd_recursive_deref(manager,solE); 00212 result = bdd_add_apply_recur(manager,bdd_add_plus,solPT,solPE); 00213 if (result == NULL) { 00214 bdd_recursive_deref(manager,solPT); 00215 bdd_recursive_deref(manager,solPE); 00216 return NULL; 00217 } 00218 bdd_ref(result); 00219 bdd_recursive_deref(manager,solPE); 00220 bdd_recursive_deref(manager,solPT); 00221 st_insert(visited,(char *)tr,(char *)result); 00222 /* bdd_deref(result); */ 00223 return(result); 00224 } 00225 00226 /* Split on a state variable, solve subproblems and combine by ite */ 00227 solT = MarkAddInProbRecur(manager,bdd_bdd_T(tr),cube, probTable,visited); 00228 if (solT == NULL) { 00229 return NULL; 00230 } 00231 bdd_ref(solT); 00232 solE = MarkAddInProbRecur(manager,bdd_bdd_E(tr),cube, 00233 probTable,visited); 00234 if (solE == NULL) { 00235 bdd_recursive_deref(manager,solT); 00236 return NULL; 00237 } 00238 bdd_ref(solE); 00239 result = bdd_unique_inter(manager,bdd_node_read_index(tr), 00240 solT,solE); 00241 if (result == NULL) { 00242 bdd_recursive_deref(manager,solT); 00243 bdd_recursive_deref(manager,solE); 00244 return NULL; 00245 } 00246 bdd_ref(result); 00247 bdd_recursive_deref(manager,solT); 00248 bdd_recursive_deref(manager,solE); 00249 st_insert(visited,(char *)tr,(char *)result); 00250 /* bdd_deref(result); */ 00251 return(result); 00252 00253 } /* end of MarkAddInProbRecur */ 00254 00255 00256 /*---------------------------------------------------------------------------*/ 00257 /* Definition of static functions */ 00258 /*---------------------------------------------------------------------------*/ 00259
1.7.3