Merged prob.h, factorgraph.h, factograph.cpp from SVN head (broken!)
[libdai.git] / FILEFORMAT
1 This file describes the .fg fileformat used in libDAI to store factor graphs.
2
3 Markov Random Fields are special cases of factor graphs, as are Bayesian
4 networks. A factor graph can be specified as follows: for each factor, one has
5 to specify which variables occur in the factor, what their respective
6 cardinalities (i.e., number of possible values) are, and a table listing all
7 the values of that factor for all possible configurations of these variables.
8 A .fg file is not much more than that. It starts with a line containing the
9 number of factors in that graph, followed by an empty line. Then all factors
10 are specified, one block for each factor, where the blocks are seperated by
11 empty lines. Each variable occurring in the factor graph has a unique
12 identifier, its index (which should be a nonnegative integer). Comment lines
13 start with #.
14
15 Each block starts with a line containing the number of variables in that
16 factor. The second line contains the indices of these variables, seperated by
17 spaces (indices are nonnegative integers and to avoid confusion, it is
18 suggested to start counting at 0). The third line contains the number of
19 possible values of each of these variables, also seperated by spaces. Note that
20 there is some redundancy here, since if a variable appears in more than one
21 factor, the cardinality of that variable appears several times in the .fg file.
22 The fourth line contains the number of nonzero entries in the factor table.
23 The rest of the lines contain these nonzero entries; each entry consists of a
24 table index, followed by white-space, followed by the value corresponding to
25 that table index. The most difficult part is getting the indexing right. The
26 convention that is used is that the left-most variables cycle through their
27 values the fastest (similar to MATLAB indexing of multidimensional arrays). An
28 example block describing one factor is:
29
30 3
31 4 8 7
32 3 2 2
33 11
34 0 0.1
35 1 3.5
36 2 2.8
37 3 6.3
38 4 8.4
39 6 7.4
40 7 2.4
41 8 8.9
42 9 1.3
43 10 1.6
44 12 6.4
45 11 2.6
46
47 which corresponds to the following factor:
48
49 x_4 x_8 x_7 | value
50 0 0 0 | 0.1
51 1 0 0 | 3.5
52 2 0 0 | 2.8
53 0 1 0 | 6.3
54 1 1 0 | 8.4
55 2 1 0 | 0.0
56 0 0 1 | 7.4
57 1 0 1 | 2.4
58 2 0 1 | 8.9
59 0 1 1 | 1.3
60 1 1 1 | 1.6
61 2 1 1 | 2.6
62
63 Note that the value of x_4 changes fastest, followed by that of x_8, and x_7
64 varies the slowest, corresponding to the second line of the block ("4 8 7").
65 Further, x_4 can take on three values, and x_8 and x_7 each have two possible
66 values, as described in the third line of the block ("3 2 2"). The table
67 contains 11 non-zero entries (all except for the fifth entry). Note that the
68 eleventh and twelveth entries are interchanged.
69
70 A final note: the internal representation in libDAI of the factor above is
71 different, because the variables are ordered according to their indices
72 (i.e., the ordering would be x_4 x_7 x_8) and the values of the table are
73 stored accordingly, with the variable having the smallest index changing
74 fastest:
75
76 x_4 x_7 x_8 | value
77 0 0 0 | 0.1
78 1 0 0 | 3.5
79 2 0 0 | 2.8
80 0 1 0 | 7.4
81 1 1 0 | 2.4
82 2 1 0 | 8.9
83 0 0 1 | 6.3
84 1 0 1 | 8.4
85 2 0 1 | 0.0
86 0 1 1 | 1.3
87 1 1 1 | 1.6
88 2 1 1 | 2.6