source: vis_dev/vis-2.3/src/mark/markInProb.c@ 93

Last change on this file since 93 was 14, checked in by cecile, 15 years ago

vis2.3
File size: 8.4 KB
Line 
1/**CFile***********************************************************************
2
3 FileName [markInProb.c]
4
5 PackageName [mark]
6
7 Synopsis [Computation of transition probability matrix and convergence
8 checks in markov analysis.]
9
10 Description [[Computation of transition probability matrix and convergence
11 checks in markov analysis.]
12
13 Author [Balakrishna Kumthekar]
14
15 Copyright [This file was created at the University of Colorado at
16 Boulder. The University of Colorado at Boulder makes no warranty
17 about the suitability of this software for any purpose. It is
18 presented on an AS IS basis.]
19
20******************************************************************************/
21
22#include "markInt.h"
23
24/*---------------------------------------------------------------------------*/
25/* Constant declarations */
26/*---------------------------------------------------------------------------*/
27
28
29/*---------------------------------------------------------------------------*/
30/* Stucture declarations */
31/*---------------------------------------------------------------------------*/
32
33
34/*---------------------------------------------------------------------------*/
35/* Type declarations */
36/*---------------------------------------------------------------------------*/
37
38
39/*---------------------------------------------------------------------------*/
40/* Variable declarations */
41/*---------------------------------------------------------------------------*/
42
43
44/*---------------------------------------------------------------------------*/
45/* Macro declarations */
46/*---------------------------------------------------------------------------*/
47
48
49/**AutomaticStart*************************************************************/
50
51/*---------------------------------------------------------------------------*/
52/* Static function prototypes */
53/*---------------------------------------------------------------------------*/
54
55
56/**AutomaticEnd***************************************************************/
57
58
59/*---------------------------------------------------------------------------*/
60/* Definition of exported functions */
61/*---------------------------------------------------------------------------*/
62
63/**Function********************************************************************
64
65 Synopsis [Computes one-step transition probability matrix given the 0-1
66 ADD of transition relation and a table of primary input probabiliites.]
67
68 Description [Computes one-step transition probability matrix given the 0-1
69 ADD of transition relation and a table of primary input probabiliites. tr is
70 the 0-1 ADD, cube is a cube of primary inputs and probTable is a hash table
71 that stores (<mdd_id>,<probability of x = 1>). The function returns the ADD
72 for one-step transition probability matrix.]
73
74 SideEffects [None]
75
76 SeeAlso []
77
78******************************************************************************/
79bdd_node *
80Mark_addInProb(
81 bdd_manager *manager,
82 bdd_node *tr,
83 bdd_node *cube,
84 st_table *probTable)
85{
86 st_table *visited;
87 st_generator *gen;
88 bdd_node *result, *r, *k;
89
90 do {
91 bdd_set_reordered_field(manager, 0);
92 visited = st_init_table(st_ptrcmp,st_ptrhash);
93 bdd_ref(result = bdd_read_one(manager));
94 st_insert(visited,(char *)result,(char *)result);
95 bdd_ref(result = bdd_read_zero(manager));
96 st_insert(visited,(char *)result,(char *)result);
97 result = MarkAddInProbRecur(manager,tr,cube,probTable,visited);
98 if (result)
99 bdd_ref(result);
100 st_foreach_item(visited,gen,&k,&r) {
101 bdd_recursive_deref(manager,r);
102 }
103 st_free_table(visited);
104 } while (bdd_read_reordered_field(manager) == 1);
105
106 bdd_deref(result);
107 return(result);
108
109} /* end of Mark_addInProb */
110
111
112/*---------------------------------------------------------------------------*/
113/* Definition of internal functions */
114/*---------------------------------------------------------------------------*/
115
116/**Function********************************************************************
117
118 Synopsis [Implements the recursive step of Mark_addInProb.]
119
120 Description [Implements the recursive step of Mark_addInProb.]
121
122 SideEffects [None]
123
124 SeeAlso []
125
126******************************************************************************/
127bdd_node *
128MarkAddInProbRecur(
129 bdd_manager *manager,
130 bdd_node *tr,
131 bdd_node *cube,
132 st_table *probTable,
133 st_table *visited)
134{
135 int topTR,topC;
136 int index;
137 double *prob;
138 bdd_node *solT,*solE;
139 bdd_node *solPT,*solPE;
140 bdd_node *result;
141 bdd_node *unique;
142
143 /* lookup in the cache */
144 if(st_lookup(visited,tr,&result))
145 return(result);
146
147 /* the cube is one then return */
148 if ( cube == bdd_read_one(manager))
149 return tr;
150
151 /* Obtain the top variable indexes */
152 topTR = bdd_get_level_from_id(manager,bdd_node_read_index(tr));
153 topC = bdd_get_level_from_id(manager,bdd_node_read_index(cube));
154
155 /* The function does not depend on the top variable of the cube */
156 if (topTR > topC ) {
157 result = MarkAddInProbRecur(manager,tr,bdd_bdd_T(cube),probTable,visited);
158 return(result);
159 }
160
161 /* If both top variables are equal, solve subproblems and combine */
162 if (topTR == topC ) {
163 solT = MarkAddInProbRecur(manager,bdd_bdd_T(tr),bdd_bdd_T(cube),
164 probTable,visited);
165 if (solT == NULL) {
166 return NULL;
167 }
168 bdd_ref(solT);
169 solE = MarkAddInProbRecur(manager,bdd_bdd_E(tr),bdd_bdd_T(cube),
170 probTable,visited);
171 if (solE == NULL) {
172 bdd_recursive_deref(manager,solT);
173 return NULL;
174 }
175 bdd_ref(solE);
176 index = bdd_node_read_index(cube);
177 st_lookup(probTable,(char *)(long)index,&prob);
178 unique = bdd_add_const(manager,*prob);
179 if(unique == NULL) {
180 bdd_recursive_deref(manager,solT);
181 bdd_recursive_deref(manager,solE);
182 return NULL;
183 }
184 bdd_ref(unique);
185 solPT = bdd_add_apply_recur(manager,bdd_add_times,solT,unique);
186 if (solPT == NULL) {
187 bdd_recursive_deref(manager,solT);
188 bdd_recursive_deref(manager,solE);
189 bdd_recursive_deref(manager,unique);
190 return NULL;
191 }
192 bdd_ref(solPT);
193 bdd_recursive_deref(manager,unique);
194 bdd_recursive_deref(manager,solT);
195 unique = bdd_add_const(manager,1.0 - *prob);
196 if (unique == NULL) {
197 bdd_recursive_deref(manager,solE);
198 bdd_recursive_deref(manager,solPT);
199 return NULL;
200 }
201 bdd_ref(unique);
202 solPE = bdd_add_apply_recur(manager,bdd_add_times,solE,unique);
203 if (solPE == NULL) {
204 bdd_recursive_deref(manager,unique);
205 bdd_recursive_deref(manager,solPT);
206 bdd_recursive_deref(manager,solE);
207 return NULL;
208 }
209 bdd_ref(solPE);
210 bdd_recursive_deref(manager,unique);
211 bdd_recursive_deref(manager,solE);
212 result = bdd_add_apply_recur(manager,bdd_add_plus,solPT,solPE);
213 if (result == NULL) {
214 bdd_recursive_deref(manager,solPT);
215 bdd_recursive_deref(manager,solPE);
216 return NULL;
217 }
218 bdd_ref(result);
219 bdd_recursive_deref(manager,solPE);
220 bdd_recursive_deref(manager,solPT);
221 st_insert(visited,(char *)tr,(char *)result);
222 /* bdd_deref(result); */
223 return(result);
224 }
225
226 /* Split on a state variable, solve subproblems and combine by ite */
227 solT = MarkAddInProbRecur(manager,bdd_bdd_T(tr),cube, probTable,visited);
228 if (solT == NULL) {
229 return NULL;
230 }
231 bdd_ref(solT);
232 solE = MarkAddInProbRecur(manager,bdd_bdd_E(tr),cube,
233 probTable,visited);
234 if (solE == NULL) {
235 bdd_recursive_deref(manager,solT);
236 return NULL;
237 }
238 bdd_ref(solE);
239 result = bdd_unique_inter(manager,bdd_node_read_index(tr),
240 solT,solE);
241 if (result == NULL) {
242 bdd_recursive_deref(manager,solT);
243 bdd_recursive_deref(manager,solE);
244 return NULL;
245 }
246 bdd_ref(result);
247 bdd_recursive_deref(manager,solT);
248 bdd_recursive_deref(manager,solE);
249 st_insert(visited,(char *)tr,(char *)result);
250 /* bdd_deref(result); */
251 return(result);
252
253} /* end of MarkAddInProbRecur */
254
255
256/*---------------------------------------------------------------------------*/
257/* Definition of static functions */
258/*---------------------------------------------------------------------------*/
259
Note: See TracBrowser for help on using the repository browser.