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

Last change on this file since 93 was 14, checked in by cecile, 14 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.