ff48eb81839ddfd1c0b39c73ec4613ec03e0d1fc
[libdai.git] / include / dai / doc.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2008-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 */
9
10
11 /** \file
12 * \brief Contains additional doxygen documentation
13 *
14 * \todo Document tests and utils
15 *
16 * \todo Add FAQ
17 *
18 * \todo Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming
19 *
20 * \todo Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html
21 *
22 * \todo Replace VarSets by SmallSet<size_t> where appropriate, in order to minimize the use of FactorGraph::findVar().
23 *
24 * \idea Disentangle structures. In particular, ensure that graphical properties are not
25 * entangled with probabilistic properties. For example, a FactorGraph contains several components:
26 * - a BipartiteGraph
27 * - an array of variable labels
28 * - an array of variable state space sizes
29 * - an array of pointers to factor value vectors
30 * In this way, each factor could be implemented differently, e.g., we could have
31 * some sparse factors, some noisy-OR factors, some dense factors, some arbitrary
32 * precision factors, etcetera.
33 *
34 * \idea Use boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.
35 * See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
36 * However: I read somewhere that boost::uBLAS concentrates more on correct implementation than on performance.
37 *
38 * \idea Introduce naming scheme:
39 * - all Vars should be named v_..., e.g. v_i instead of i
40 * - all VarSets should be named vs_..., e.g. v_i instead of i
41 * - all Factors should be named f_..., e.g. f_I instead of I
42 * - all indices should be named _..., e.g. _k instead of k
43 * - all iterators should be named i_, e.g. i_i is an iterator to i
44 * - all const_iterators should be named ci_, e.g. ci_i is an iterator to i
45 **/
46
47
48 /** \mainpage Reference manual for libDAI - A free/open source C++ library for Discrete Approximate Inference methods
49 * \author Joris Mooij
50 * \version DAI_VERSION
51 * \date DAI_DATE
52 *
53 * <hr size="1">
54 * \section about About libDAI
55 * libDAI is a free/open source C++ library (licensed under GPLv2+) that provides
56 * implementations of various (approximate) inference methods for discrete
57 * graphical models. libDAI supports arbitrary factor graphs with discrete
58 * variables; this includes discrete Markov Random Fields and Bayesian
59 * Networks.
60 *
61 * The library is targeted at researchers. To be able to use the library, a
62 * good understanding of graphical models is needed.
63 *
64 * \section features Features
65 * Currently, libDAI supports the following (approximate) inference methods:
66 * - Exact inference by brute force enumeration;
67 * - Exact inference by junction-tree methods;
68 * - Mean Field;
69 * - Loopy Belief Propagation [\ref KFL01];
70 * - Tree Expectation Propagation [\ref MiQ04];
71 * - Generalized Belief Propagation [\ref YFW05];
72 * - Double-loop GBP [\ref HAK03];
73 * - Various variants of Loop Corrected Belief Propagation
74 * [\ref MoK07, \ref MoR05];
75 * - Gibbs sampler;
76 * - Conditioned BP [\ref EaG09].
77 *
78 * These inference methods can be used to calculate partition sums, marginals
79 * over subsets of variables, and MAP states (the joint state of variables that
80 * has maximum probability).
81 *
82 * In addition, libDAI supports parameter learning of conditional probability
83 * tables by Expectation Maximization.
84 *
85 * \section limitations Limitations
86 * libDAI is not intended to be a complete package for approximate inference.
87 * Instead, it should be considered as an "inference engine", providing
88 * various inference methods. In particular, it contains no GUI, currently
89 * only supports its own file format for input and output (although support
90 * for standard file formats may be added later), and provides very limited
91 * visualization functionalities. The only learning method supported currently
92 * is Expectation Maximization (or Maximum Likelihood if no data is missing)
93 * for learning factor parameters.
94 *
95 * \section language Why C++?
96 * Because libDAI is implemented in C++, it is very fast compared with
97 * implementations in MatLab (a factor 1000 faster is not uncommon).
98 * libDAI does provide a (limited) MatLab interface for easy integration with MatLab.
99 *
100 * \section compatibility Compatibility
101 *
102 * The code has been developed under Debian GNU/Linux with the GCC compiler suite.
103 * libDAI compiles successfully with g++ versions 3.4, 4.1, 4.2 and 4.3.
104 *
105 * libDAI has also been successfully compiled with MS Visual Studio 2008 under Windows
106 * (but not all build targets are supported yet) and with Cygwin under Windows.
107 *
108 * Finally, libDAI has been compiled successfully on MacOS X.
109 *
110 * \section download Downloading libDAI
111 * The libDAI sources and documentation can be downloaded from the libDAI website:
112 * http://www.libdai.org.
113 */
114
115
116 /** \page license License
117 * <hr size="1">
118 * \section license-license License
119 *
120 * libDAI is free software; you can redistribute it and/or modify
121 * it under the terms of the GNU General Public License as published by
122 * the Free Software Foundation; either version 2 of the License, or
123 * (at your option) any later version.
124 *
125 * libDAI is distributed in the hope that it will be useful,
126 * but WITHOUT ANY WARRANTY; without even the implied warranty of
127 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
128 * GNU General Public License for more details.
129 *
130 * <hr size="1">
131 * \section license-gpl GNU General Public License version 2
132 *
133 * \verbinclude COPYING
134 */
135
136
137 /** \page citations Citing libDAI
138 * <hr size="1">
139 * \section citations-citations Citing libDAI
140 *
141 * If you write a scientific paper describing research that made substantive use
142 * of this program, please:
143 * - mention the fashion in which this software was
144 * used, including the version number, with a citation to the literature,
145 * to allow replication;
146 * - mention this software in the Acknowledgements section. An
147 * appropriate citation would be:\n
148 * J. M. Mooij (2008) "libDAI 0.2.2: A free/open source C++ library for Discrete
149 * Approximate Inference methods", http://www.libdai.org
150 *
151 * Moreover, as a personal note, I would appreciate it if you would email
152 * (citations of) papers referencing this work to joris dot mooij at libdai dot org.
153 */
154
155
156 /** \page authors Authors
157 * \section authors-authors People who contributed to libDAI
158 *
159 * \verbinclude AUTHORS
160 */
161
162
163 /** \page build Building libDAI
164 * <hr size="1">
165 * \section build-unix Building libDAI under UNIX variants (Linux / Cygwin / Mac OS X)
166 *
167 * You need:
168 * - a recent version of gcc (at least version 3.4)
169 * - GNU make
170 * - doxygen
171 * - graphviz
172 * - recent boost C++ libraries (at least version 1.34, or 1.37 for cygwin;
173 * version 1.37 shipped with Ubuntu 9.04 is known not to work)
174 *
175 * On Debian/Ubuntu, you can easily install all these packages with a single command:
176 * <pre> apt-get install g++ make doxygen graphviz libboost-dev libboost-graph-dev libboost-program-options-dev</pre>
177 * (root permissions needed).
178 *
179 * On Mac OS X (10.4 is known to work), these packages can be installed easily via MacPorts.
180 * If MacPorts is not already installed, install it according to the instructions at http://www.macports.org/.
181 * Then, a simple
182 * <pre> sudo port install gmake boost doxygen graphviz</pre>
183 * should be enough to install everything that is needed.
184 *
185 * On Cygwin, the prebuilt Cygwin package boost-1.33.1-x is known not to work.
186 * You can however obtain the latest boost version (you need at least 1.37.0)
187 * from http://www.boost.org/ and compile/install it with:
188 *
189 * <pre> ./configure
190 * make
191 * make install
192 * </pre>
193 *
194 * To build the libDAI source, first copy a template Makefile.* to Makefile.conf
195 * (for example, copy Makefile.LINUX to Makefile.conf if you use GNU/Linux).
196 * Then, edit the Makefile.conf template to adapt it to your local setup.
197 * Especially directories may differ from system to system. Finally, run
198 * <pre> make</pre>
199 * The build includes a regression test, which may take a while to complete.
200 *
201 * If the build was successful, you can test the example program:
202 * <pre> examples/example tests/alarm.fg</pre>
203 * or the more elaborate test program:
204 * <pre> tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>
205 *
206 *
207 * <hr size="1">
208 * \section build-windows Building libDAI under Windows
209 *
210 * You need:
211 * - A recent version of MicroSoft Visual Studio (2008 works)
212 * - recent boost C++ libraries (version 1.34 or higher)
213 * - GNU make (can be obtained from http://gnuwin32.sourceforge.net)
214 *
215 * For the regression test, you need:
216 * - GNU diff, GNU sed (can be obtained from http://gnuwin32.sourceforge.net)
217 *
218 * To build the source, copy Makefile.WINDOWS to Makefile.conf. Then, edit
219 * Makefile.conf to adapt it to your local setup. Finally, run (from the command line)
220 * <pre> make</pre>
221 * The build includes a regression test, which may take a while to complete.
222 *
223 * If the build was successful, you can test the example program:
224 * <pre> example tests\alarm.fg</pre>
225 * or the more elaborate test program:
226 * <pre> tests\\testdai --aliases tests\aliases.conf --filename tests\alarm.fg --methods JTREE_HUGIN BP_SEQMAX</pre>
227 *
228 *
229 * <hr size="1">
230 * \section build-matlab Building the libDAI MatLab interface
231 *
232 * You need:
233 * - MatLab
234 * - The platform-dependent requirements described above
235 *
236 * First, you need to build the libDAI source as described above for your
237 * platform. By default, the MatLab interface is disabled, so before compiling the
238 * source, you have to enable it in the Makefile.conf by setting
239 * <pre> WITH_MATLAB=true</pre>
240 * Also, you have to configure the MatLab-specific parts of
241 * Makefile.conf to match your system (in particular, the Makefile variables ME,
242 * MATLABDIR and MEX). The MEX file extension depends on your platform; for a
243 * 64-bit linux x86_64 system this would be "ME=.mexa64", for a 32-bit linux x86
244 * system "ME=.mexglx". If you are unsure about your MEX file
245 * extension: it needs to be the same as what the MatLab command "mexext" returns.
246 * The required MEX files are built by issuing
247 * <pre> make</pre>
248 * from the command line. The MatLab interface is much less powerful than using
249 * libDAI from C++. There are two reasons for this: (i) it is boring to write MEX
250 * files; (ii) the large performance penalty paid when large data structures (like
251 * factor graphs) have to be converted between their native C++ data structure to
252 * something that MatLab understands.
253 *
254 * A simple example of how to use the MatLab interface is the following (entered
255 * at the MatLab prompt), which performs exact inference by the junction tree
256 * algorithm and approximate inference by belief propagation on the ALARM network:
257 * <pre> cd path_to_libdai/matlab
258 * [psi] = dai_readfg ('../examples/alarm.fg');
259 * [logZ,q,md,qv,qf] = dai (psi, 'JTREE', '[updates=HUGIN,verbose=0]')
260 * [logZ,q,md,qv,qf] = dai (psi, 'BP', '[updates=SEQMAX,tol=1e-9,maxiter=10000,logdomain=0]')</pre>
261 * where "path_to_libdai" has to be replaced with the directory in which libDAI
262 * was installed. For other algorithms and some default parameters, see the file
263 * tests/aliases.conf.
264 *
265 * <hr size="1">
266 * \section build-doxygen Building the documentation
267 *
268 * Install doxygen and use
269 * <pre> make doc</pre>
270 * to build the documentation. If the documentation is not clear enough, feel free
271 * to send me an email (or even better, to improve the documentation and send a patch!).
272 */
273
274
275 /** \page changelog Change Log
276 * \verbinclude ChangeLog
277 */
278
279
280 /** \page fileformats libDAI file formats
281 *
282 * \section fileformats-factorgraph Factor graph (.fg) file format
283 *
284 * This section describes the .fg file format used in libDAI to store factor graphs.
285 * Markov Random Fields are special cases of factor graphs, as are Bayesian
286 * networks. A factor graph can be specified as follows: for each factor, one has
287 * to specify which variables occur in the factor, what their respective
288 * cardinalities (i.e., number of possible values) are, and a table listing all
289 * the values of that factor for all possible configurations of these variables.
290 *
291 * A .fg file is not much more than that. It starts with a line containing the
292 * number of factors in that graph, followed by an empty line. Then all factors
293 * are specified, using one block for each factor, where the blocks are seperated
294 * by empty lines. Each variable occurring in the factor graph has a unique
295 * identifier, its label (which should be a nonnegative integer). Comment lines
296 * which start with # are ignored.
297 *
298 * \subsection fileformats-factorgraph-factor Factor block format
299 *
300 * Each block describing a factor starts with a line containing the number of
301 * variables in that factor. The second line contains the labels of these
302 * variables, seperated by spaces (labels are nonnegative integers and to avoid
303 * confusion, it is suggested to start counting at 0). The third line contains
304 * the number of possible values of each of these variables, also seperated by
305 * spaces. Note that there is some redundancy here, since if a variable appears
306 * in more than one factor, the cardinality of that variable appears several
307 * times in the .fg file; obviously, these cardinalities should be consistent.
308 * The fourth line contains the number of nonzero entries
309 * in the factor table. The rest of the lines contain these nonzero entries;
310 * each line consists of a table index, followed by white-space, followed by the
311 * value corresponding to that table index. The most difficult part is getting
312 * the indexing right. The convention that is used is that the left-most
313 * variables cycle through their values the fastest (similar to MatLab indexing
314 * of multidimensional arrays).
315 *
316 * \subsubsection fileformats-factorgraph-factor-example Example
317 *
318 * An example block describing one factor is:
319 *
320 * <pre>
321 * 3
322 * 4 8 7
323 * 3 2 2
324 * 11
325 * 0 0.1
326 * 1 3.5
327 * 2 2.8
328 * 3 6.3
329 * 4 8.4
330 * 6 7.4
331 * 7 2.4
332 * 8 8.9
333 * 9 1.3
334 * 10 1.6
335 * 12 6.4
336 * 11 2.6
337 * </pre>
338 *
339 * which corresponds to the following factor:
340 *
341 * \f[
342 * \begin{array}{ccc|c}
343 * x_4 & x_8 & x_7 & \mbox{value}\\
344 * \hline
345 * 0 & 0 & 0 & 0.1\\
346 * 1 & 0 & 0 & 3.5\\
347 * 2 & 0 & 0 & 2.8\\
348 * 0 & 1 & 0 & 6.3\\
349 * 1 & 1 & 0 & 8.4\\
350 * 2 & 1 & 0 & 0.0\\
351 * 0 & 0 & 1 & 7.4\\
352 * 1 & 0 & 1 & 2.4\\
353 * 2 & 0 & 1 & 8.9\\
354 * 0 & 1 & 1 & 1.3\\
355 * 1 & 1 & 1 & 1.6\\
356 * 2 & 1 & 1 & 2.6
357 * \end{array}
358 * \f]
359 *
360 * Note that the value of \f$x_4\f$ changes fastest, followed by that of \f$x_8\f$, and \f$x_7\f$
361 * varies the slowest, corresponding to the second line of the block ("4 8 7").
362 * Further, \f$x_4\f$ can take on three values, and \f$x_8\f$ and \f$x_7\f$ each have two possible
363 * values, as described in the third line of the block ("3 2 2"). The table
364 * contains 11 non-zero entries (all except for the fifth entry). Note that the
365 * eleventh and twelveth entries are interchanged.
366 *
367 * A final note: the internal representation in libDAI of the factor above is
368 * different, because the variables are ordered according to their indices
369 * (i.e., the ordering would be \f$x_4 x_7 x_8\f$) and the values of the table are
370 * stored accordingly, with the variable having the smallest index changing
371 * fastest:
372 *
373 * \f[
374 * \begin{array}{ccc|c}
375 * x_4 & x_7 & x_8 & \mbox{value}\\
376 * \hline
377 * 0 & 0 & 0 & 0.1\\
378 * 1 & 0 & 0 & 3.5\\
379 * 2 & 0 & 0 & 2.8\\
380 * 0 & 1 & 0 & 7.4\\
381 * 1 & 1 & 0 & 2.4\\
382 * 2 & 1 & 0 & 8.9\\
383 * 0 & 0 & 1 & 6.3\\
384 * 1 & 0 & 1 & 8.4\\
385 * 2 & 0 & 1 & 0.0\\
386 * 0 & 1 & 1 & 1.3\\
387 * 1 & 1 & 1 & 1.6\\
388 * 2 & 1 & 1 & 2.6
389 * \end{array}
390 * \f]
391 *
392 *
393 * \section fileformats-evidence Evidence (.tab) file format
394 *
395 * This section describes the .tab fileformat used in libDAI to store "evidence",
396 * i.e., a data set consisting of multiple samples, where each sample is the
397 * observed joint state of some variables.
398 *
399 * A .tab file is a tabular data file, consisting of a header line, followed by
400 * an empty line, followed by the data points, with one line for each data point.
401 * Each line (apart from the empty one) should have the same number of columns,
402 * where columns are separated by one tab character. Each column corresponds to
403 * a variable. The header line consists of the variable labels (corresponding to
404 * dai::Var::label()). The other lines are observed joint states of the variables, i.e.,
405 * each line corresponds to a joint observation of the variables, and each column
406 * of a line contains the state of the variable associated with that column.
407 * Missing data is handled simply by having two consecutive tab characters,
408 * without any characters in between.
409 *
410 * \subsection fileformats-evidence-example Example
411 *
412 * <pre>
413 * 1 3 2
414 *
415 * 0 0 1
416 * 1 0 1
417 * 1 1
418 * </pre>
419 *
420 * This would correspond to a data set consisting of three observations concerning
421 * the variables with labels 1, 3 and 2; the first observation being
422 * \f$x_1 = 0, x_3 = 0, x_2 = 1\f$, the second observation being
423 * \f$x_1 = 1, x_3 = 0, x_2 = 1\f$, and the third observation being
424 * \f$x_1 = 1, x_2 = 1\f$ (where the state of \f$x_3\f$ is missing).
425 *
426 * \section fileformats-emalg Expectation Maximization (.em) file format
427 *
428 * This section describes the file format of .em files, which are used
429 * to specify a particular EM algorithm. The .em files are complementary
430 * to .fg files; in other words, an .em file without a corresponding .fg
431 * file is useless. Furthermore, one also needs a corresponding .tab file
432 * containing the data used for parameter learning.
433 *
434 * An .em file starts with a line specifying the number of maximization steps,
435 * followed by an empty line. Then, each maximization step is described in a
436 * block, which should satisfy the format described in the next subsection.
437 *
438 * \subsection fileformats-emalg-maximizationstep Maximization Step block format
439 *
440 * A maximization step block of an .em file starts with a single line
441 * describing the number of shared parameters blocks that will follow.
442 * Then, each shared parameters block follows, in the format described in
443 * the next subsection.
444 *
445 * \subsection fileformats-emalg-sharedparameters Shared parameters block format
446 *
447 * A shared parameters block of an .em file starts with a single line
448 * consisting of the name of a ParameterEstimation subclass
449 * and its parameters in the format of a PropertySet. For example:
450 * <pre> CondProbEstimation [target_dim=2,total_dim=4,pseudo_count=1]</pre>
451 * The next line contains the number of factors that share their parameters.
452 * Then, each of these factors is specified on separate lines (possibly
453 * seperated by empty lines), where each line consists of several fields
454 * seperated by a space or a tab character. The first field contains
455 * the index of the factor in the factor graph. The following fields should
456 * contain the variable labels of the variables on which that factor depends,
457 * in a specific ordering. This ordering can be different from the canonical
458 * ordering of the variables used internally in libDAI (which would be sorted
459 * ascendingly according to the variable labels). The odering of the variables
460 * specifies the implicit ordering of the shared parameters: when iterating
461 * over all shared parameters, the corresponding index of the first variable
462 * changes fastest (in the inner loop), and the corresponding index of the
463 * last variable changes slowest (in the outer loop). By choosing the right
464 * ordering, it is possible to let different factors (depending on different
465 * variables) share parameters in parameter learning using EM. This convention
466 * is similar to the convention used in factor blocks in a factor graph .fg
467 * file (see \ref fileformats-factorgraph-factor).
468 */
469
470 /** \page bibliography Bibliography
471 * \anchor KFL01 \ref KFL01
472 * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
473 * "Factor Graphs and the Sum-Product Algorithm",
474 * <em>IEEE Transactions on Information Theory</em> 47(2):498-519.
475 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
476 *
477 * \anchor MiQ04 \ref MiQ04
478 * T. Minka and Y. Qi (2004):
479 * "Tree-structured Approximations by Expectation Propagation",
480 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.
481 * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
482 *
483 * \anchor MoR05 \ref MoR05
484 * A. Montanari and T. Rizzo (2005):
485 * "How to Compute Loop Corrections to the Bethe Approximation",
486 * <em>Journal of Statistical Mechanics: Theory and Experiment</em>
487 * 2005(10)-P10011.
488 * http://stacks.iop.org/1742-5468/2005/P10011
489 *
490 * \anchor YFW05 \ref YFW05
491 * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
492 * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
493 * <em>IEEE Transactions on Information Theory</em>
494 * 51(7):2282-2312.
495 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
496 *
497 * \anchor HAK03 \ref HAK03
498 * T. Heskes and C. A. Albers and H. J. Kappen (2003):
499 * "Approximate Inference and Constrained Optimization",
500 * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.
501 * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
502 *
503 * \anchor MoK07 \ref MoK07
504 * J. M. Mooij and H. J. Kappen (2007):
505 * "Loop Corrections for Approximate Inference on Factor Graphs",
506 * <em>Journal of Machine Learning Research</em> 8:1113-1143.
507 * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
508 *
509 * \anchor MoK07b \ref MoK07b
510 * J. M. Mooij and H. J. Kappen (2007):
511 * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
512 * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.
513 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
514 *
515 * \anchor EaG09 \ref EaG09
516 * F. Eaton and Z. Ghahramani (2009):
517 * "Choosing a Variable to Clamp",
518 * <em>Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS 2009)</em> 5:145-152
519 * http://jmlr.csail.mit.edu/proceedings/papers/v5/eaton09a/eaton09a.pdf
520 *
521 * \anchor StW99 \ref StW99
522 * A. Steger and N. C. Wormald (1999):
523 * "Generating Random Regular Graphs Quickly",
524 * <em>Combinatorics, Probability and Computing</em> Vol 8, Issue 4, pp. 377-396
525 * http://www.math.uwaterloo.ca/~nwormald/papers/randgen.pdf
526 *
527 * \anchor EMK06 \ref EMK06
528 * G. Elidan and I. McGraw and D. Koller (2006):
529 * "Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing",
530 * <em>Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)</em>
531 * http://uai.sis.pitt.edu/papers/06/UAI2006_0091.pdf
532 */
533
534
535 /** \page discussion Ideas not worth exploring
536 * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs
537 *
538 * A FactorGraph and a RegionGraph are often equipped with
539 * additional properties for nodes and edges. The code to initialize those
540 * is often quite similar. Maybe one could abstract this, e.g.:
541 * \code
542 * template <typename Node1Properties, typename Node2Properties, typename EdgeProperties>
543 * class ExtFactorGraph : public FactorGraph {
544 * public:
545 * std::vector<Node1Properties> node1Props;
546 * std::vector<Node2Properties> node2Props;
547 * std::vector<std::vector<EdgeProperties> > edgeProps;
548 * // ...
549 * }
550 * \endcode
551 *
552 * Advantages:
553 * - Less code duplication.
554 * - Easier maintainability.
555 * - Easier to write new inference algorithms.
556 *
557 * Disadvantages:
558 * - Cachability may be worse.
559 * - A problem is the case where there are no properties for either type of nodes or for edges.
560 * Maybe this can be solved using specializations, or using variadac template arguments?
561 * Another possible solution would be to define a "class Empty {}", and add some code
562 * that checks for the typeid, comparing it with Empty, and doing something special in that case
563 * (e.g., not allocating memory).
564 * - The main disadvantage of this approach seems to be that it leads to even more entanglement.
565 * Therefore this is probably a bad idea.
566 *
567 * \section discuss_templates Polymorphism by template parameterization
568 *
569 * Instead of polymorphism by inheritance, use polymorphism by template parameterization.
570 * For example, the real reason for introducing the complicated inheritance scheme of dai::InfAlg
571 * was for functions like dai::calcMarginal. Instead, one could use a template function:
572 * \code
573 * template<typename InfAlg>
574 * Factor calcMarginal( const InfAlg &obj, const VarSet &ns, bool reInit );
575 * \endcode
576 * This would assume that the type InfAlg supports certain methods. Ideally, one would use
577 * concepts to define different classes of inference algorithms with different capabilities,
578 * for example the ability to calculate logZ, the ability to calculate marginals, the ability to
579 * calculate bounds, the ability to calculate MAP states, etc. Then, one would use traits
580 * classes in order to be able to query the capabilities of the model. For example, one would be
581 * able to query whether the inference algorithm supports calculation of logZ. Unfortunately,
582 * this is compile-time polymorphism, whereas tests/testdai needs runtime polymorphism.
583 * Therefore this is probably a bad idea.
584 */
585
586