1 This file describes the .fg fileformat used in libDAI to store factor graphs.

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 #.

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:

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

47 which corresponds to the following factor:

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

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.

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:

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