Databases Reference
In-Depth Information
GenFactorGraph
Inputs:
(G= hV;Ei :PropagationGraph),
parameters low
1
,low
2
,high
1
,high
2
,high
3
,high
4
2 [0::1]
Returns:
a factor graphFfor the propagation graphG
1:
G
0
=MakeAcyclic(G)
2:
hX
src
;X
san
;X
snk
i =ComputePotentialSrcSanSnk(G)
3:
hTriples;Pairs
src
;Pairs
san
;Pairs
snk
i=ComputePairsAndTriples(G
0
;X
src
;X
san
;X
snk
)
4:
s=ComputeWAndSValues(G
0
)
5:
for each triple ha;b;ci2Triplesdo
6:
Create a factorf
B1
(x
a
;x
b
;x
c
) in the factor graph
7:
Letf
B1
(x
a
;x
b
;x
c
) =x
a
^:x
b
^x
c
8:
Let probabilityPr(f
B1
(x
a
;x
b
;x
c
) =true) =low
1
9:
end for
10:
for each pair hb
1
;b
2
i2Pairs
san
do
11:
Create a factorf
B2
(x
b
1
;x
b
2
) in the factor graph
12:
Letf
B2
(x
b
1
;x
b
2
) =x
b
1
^x
b
2
13:
Let probabilityPr(f
B2
(x
b
1
;x
b
2
) =true) =low
2
14:
end for
15:
for eachn2X
san
do
16:
Create a factorf
B3
(x
n
) in the factor graph
17:
Letf
B3
(x
n
) =x
n
18:
LetPr(f
B3
(x
n
) =true) =s(n)
19:
end for
20:
for each pair hx
a
1
;x
a
2
i2Pairs
src
do
21:
Create a factorf
B4
(x
a
1
;x
a
2
) in the factor graph
22:
Letf
B4
(x
a
1
;x
a
2
) =x
a
1
^:x
a
2
23:
Let probabilityPr(f
B4
(x
a
1
;x
a
2
) =true) =high
3
24:
end for
25:
for each pair hx
c
1
;x
c
2
i2Pairs
snk
do
26:
Create a factorf
B5
(x
c
1
;x
c
2
) in the factor graph
27:
Letf
B5
(x
c
1
;x
c
2
) = :x
c
1
^x
c
2
28:
Let probabilityPr(f
B5
(x
c
1
;x
c
2
) =true) =high
4
29:
end for
FIGURE 11.5: Generating a factor graph from a propagation graph.
Next in line 4, the functionComputeWAndSValues is invoked to
compute W(n) and s(n) for every potential sanitizer n. The function
ComputeWAndSValuesis described in Figure 11.6. In lines 5{9, the algorithm
creates a factor node for the constraints B1. In lines 10{14, the algorithm
iterates through all pairs hb
1
;b
2
i of potential sanitizers (that is, actual sani-
tizers as well as regular nodes) such that there is a path in the propagation
graph from b
1
to b
2
and adds factors for constraints B2. In lines 15{19, the
algorithm iterates through all potential sanitizers and adds factors for con-
straints B3. In lines 20{24, the algorithm iterates through all pairs ha
1
;a
2
i
of potential sources such that there is a path in the propagation graph from
a
1
to a
2
and adds factors for constraints B4. Similarly, in lines 25{29, the
algorithm iterates through all pairs hc
1
;c
2
i of potential sinks such that there
is a path from c
1
to c
2
and adds factors for constraints B5.
Search WWH ::
Custom Search