Improved documentation of include/dai/evidence.h
[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 Improve documentation
15 *
16 * \todo Merge README into doxygen documentation
17 * \todo Document examples, tests and utils
18 *
19 * \todo Adapt (part of the) guidelines in http://www.boost.org/development/requirements.html#Design_and_Programming
20 *
21 * \todo Use "gcc -MM" to generate dependencies for targets: http://make.paulandlesley.org/autodep.html
22 * \todo Investigate whether switching to cmake as cross-platform build system would be a good idea.
23 *
24 * \todo Replace VarSets by SmallSet<size_t> where appropriate, in order to minimize the use of FactorGraph::findVar().
25 *
26 * \idea Disentangle structures. In particular, ensure that graphical properties are not
27 * entangled with probabilistic properties. For example, a FactorGraph contains several
28 * components:
29 * - a BipartiteGraph
30 * - an array of variable labels
31 * - an array of variable state space sizes
32 * - an array of pointers to factor value vectors
33 * In this way, each factor could be implemented differently, e.g., we could have
34 * some sparse factors, some noisy-OR factors, some dense factors, some arbitrary
35 * precision factors, etc.
36 *
37 * \idea Use Boost::uBLAS framework to deal with matrices, especially, with 2D sparse matrices.
38 * See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
39 * I read somewhere that boost::uBLAS concentrates more on correct implementation than on performance.
40 *
41 * \idea Introduce naming scheme:
42 * - all Vars should be named v_..., e.g. v_i instead of i
43 * - all VarSets should be named vs_..., e.g. v_i instead of i
44 * - all Factors should be named f_..., e.g. f_I instead of I
45 * - all indices should be named _..., e.g. _k instead of k
46 * - all iterators should be named i_, e.g. i_i is an iterator to i
47 * - all const_iterators should be named ci_, e.g. ci_i is an iterator to i
48 **/
49
50
51 /** \page discussion Discussion of possible improvements
52 * \section discuss_extendedgraphs Extended factorgraphs/regiongraphs
53 *
54 * A FactorGraph and a RegionGraph are often equipped with
55 * additional properties for nodes and edges. The code to initialize those
56 * is often quite similar. Maybe one could abstract this, e.g.:
57 * \code
58 * template <typename Node1Properties, typename Node2Properties, typename EdgeProperties>
59 * class ExtFactorGraph : public FactorGraph {
60 * public:
61 * std::vector<Node1Properties> node1Props;
62 * std::vector<Node2Properties> node2Props;
63 * std::vector<std::vector<EdgeProperties> > edgeProps;
64 * // ...
65 * }
66 * \endcode
67 *
68 * Advantages:
69 * - Less code duplication.
70 * - Easier maintainability.
71 * - Easier to write new inference algorithms.
72 *
73 * Disadvantages:
74 * - Cachability may be worse.
75 * - A problem is the case where there are no properties for either type of nodes or for edges.
76 * Maybe this can be solved using specializations, or using variadac template arguments?
77 * Another possible solution would be to define a "class Empty {}", and add some code
78 * that checks for the typeid, comparing it with Empty, and doing something special in that case
79 * (e.g., not allocating memory).
80 * - The main disadvantage of this approach seems to be that it leads to even more entanglement.
81 * Therefore this is probably a bad idea.
82 *
83 * \section discuss_templates Polymorphism by template parameterization
84 * Instead of polymorphism by inheritance, use polymorphism by template parameterization.
85 * For example, the real reason for introducing the complicated inheritance scheme of dai::InfAlg
86 * was for functions like dai::calcMarginal. Instead, one could use a template function:
87 * \code
88 * template<typename InfAlg>
89 * Factor calcMarginal( const InfAlg &obj, const VarSet &ns, bool reInit );
90 * \endcode
91 * This would assume that the type InfAlg supports certain methods. Ideally, one would use
92 * concepts to define different classes of inference algorithms with different capabilities,
93 * for example the ability to calculate logZ, the ability to calculate marginals, the ability to
94 * calculate bounds, the ability to calculate MAP states, etc. Then, one would use traits
95 * classes in order to be able to query the capabilities of the model. For example, one would be
96 * able to query whether the inference algorithm supports calculation of logZ. Unfortunately,
97 * this is compile-time polymorphism, whereas tests/testdai needs runtime polymorphism.
98 * Therefore this is probably a bad idea.
99 */
100
101
102 /** \mainpage libDAI reference manual
103 * \author Joris Mooij
104 * \version git HEAD
105 * \date October 10, 2008
106 *
107 * \section about About libDAI
108 * libDAI is a free/open source C++ library (licensed under GPLv2+) that provides
109 * implementations of various (approximate) inference methods for discrete
110 * graphical models. libDAI supports arbitrary factor graphs with discrete
111 * variables; this includes discrete Markov Random Fields and Bayesian
112 * Networks.
113 *
114 * The library is targeted at researchers. To be able to use the library, a
115 * good understanding of graphical models is needed.
116 *
117 * \section limitations Limitations
118 * libDAI is not intended to be a complete package for approximate inference.
119 * Instead, it should be considered as an "inference engine", providing
120 * various inference methods. In particular, it contains no GUI, currently
121 * only supports its own file format for input and output (although support
122 * for standard file formats may be added later), and provides very limited
123 * visualization functionalities. The only learning method supported currently
124 * is EM for learning factor parameters.
125 *
126 * \section features Features
127 * Currently, libDAI supports the following (approximate) inference methods:
128 * - Exact inference by brute force enumeration;
129 * - Exact inference by junction-tree methods;
130 * - Mean Field;
131 * - Loopy Belief Propagation [\ref KFL01];
132 * - Tree Expectation Propagation [\ref MiQ04];
133 * - Generalized Belief Propagation [\ref YFW05];
134 * - Double-loop GBP [\ref HAK03];
135 * - Various variants of Loop Corrected Belief Propagation
136 * [\ref MoK07, \ref MoR05];
137 * - Gibbs sampler;
138 * - Conditioned BP [\ref EaG09];
139 *
140 * In addition, libDAI supports parameter learning of conditional probability
141 * tables by Expectation Maximization.
142 *
143 * \section language Why C++?
144 * Because libDAI is implemented in C++, it is very fast compared with
145 * implementations in MatLab (a factor 1000 faster is not uncommon).
146 * libDAI does provide a MatLab interface for easy integration with MatLab.
147 */
148
149
150 /** \example example.cpp
151 */
152
153
154 /** \page quickstart Quick start
155 * An example program illustrating basic usage of libDAI is given in examples/example.cpp.
156 */
157
158
159 /** \page bibliography Bibliography
160 * \anchor KFL01 \ref KFL01
161 * F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
162 * "Factor Graphs and the Sum-Product Algorithm",
163 * <em>IEEE Transactions on Information Theory</em> 47(2):498-519.
164 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
165 *
166 * \anchor MiQ04 \ref MiQ04
167 * T. Minka and Y. Qi (2004):
168 * "Tree-structured Approximations by Expectation Propagation",
169 * <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.
170 * http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
171 *
172 * \anchor MoR05 \ref MoR05
173 * A. Montanari and T. Rizzo (2005):
174 * "How to Compute Loop Corrections to the Bethe Approximation",
175 * <em>Journal of Statistical Mechanics: Theory and Experiment</em>
176 * 2005(10)-P10011.
177 * http://stacks.iop.org/1742-5468/2005/P10011
178 *
179 * \anchor YFW05 \ref YFW05
180 * J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
181 * "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
182 * <em>IEEE Transactions on Information Theory</em>
183 * 51(7):2282-2312.
184 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
185 *
186 * \anchor HAK03 \ref HAK03
187 * T. Heskes and C. A. Albers and H. J. Kappen (2003):
188 * "Approximate Inference and Constrained Optimization",
189 * <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.
190 * http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
191 *
192 * \anchor MoK07 \ref MoK07
193 * J. M. Mooij and H. J. Kappen (2007):
194 * "Loop Corrections for Approximate Inference on Factor Graphs",
195 * <em>Journal of Machine Learning Research</em> 8:1113-1143.
196 * http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
197 *
198 * \anchor MoK07b \ref MoK07b
199 * J. M. Mooij and H. J. Kappen (2007):
200 * "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
201 * <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.
202 * http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
203 *
204 * \anchor EaG09 \ref EaG09
205 * F. Eaton and Z. Ghahramani (2009):
206 * "Choosing a Variable to Clamp",
207 * <em>Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS 2009)</em> 5:145-152
208 * http://jmlr.csail.mit.edu/proceedings/papers/v5/eaton09a/eaton09a.pdf
209 *
210 * \anchor StW99 \ref StW99
211 * A. Steger and N. C. Wormald (1999):
212 * "Generating Random Regular Graphs Quickly",
213 * <em>Combinatorics, Probability and Computing</em> Vol 8, Issue 4, pp. 377-396
214 * http://www.math.uwaterloo.ca/~nwormald/papers/randgen.pdf
215 *
216 * \anchor EMK06 \ref EMK06
217 * G. Elidan and I. McGraw and D. Koller (2006):
218 * "Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing",
219 * <em>Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)</em>
220 * http://uai.sis.pitt.edu/papers/06/UAI2006_0091.pdf
221 */
222
223
224 /** \page fileformats libDAI file formats
225 *
226 * \section fileformats-factorgraph Factor graph (.fg) file format
227 *
228 * This section describes the .fg file format used in libDAI to store factor graphs.
229 * Markov Random Fields are special cases of factor graphs, as are Bayesian
230 * networks. A factor graph can be specified as follows: for each factor, one has
231 * to specify which variables occur in the factor, what their respective
232 * cardinalities (i.e., number of possible values) are, and a table listing all
233 * the values of that factor for all possible configurations of these variables.
234 * A .fg file is not much more than that. It starts with a line containing the
235 * number of factors in that graph, followed by an empty line. Then all factors
236 * are specified, one block for each factor, where the blocks are seperated by
237 * empty lines. Each variable occurring in the factor graph has a unique
238 * identifier, its index (which should be a nonnegative integer). Comment lines
239 * start with #.
240 *
241 * Each block starts with a line containing the number of variables in that
242 * factor. The second line contains the indices of these variables, seperated by
243 * spaces (indices are nonnegative integers and to avoid confusion, it is
244 * suggested to start counting at 0). The third line contains the number of
245 * possible values of each of these variables, also seperated by spaces. Note that
246 * there is some redundancy here, since if a variable appears in more than one
247 * factor, the cardinality of that variable appears several times in the .fg file.
248 * The fourth line contains the number of nonzero entries in the factor table.
249 * The rest of the lines contain these nonzero entries; each entry consists of a
250 * table index, followed by white-space, followed by the value corresponding to
251 * that table index. The most difficult part is getting the indexing right. The
252 * convention that is used is that the left-most variables cycle through their
253 * values the fastest (similar to MATLAB indexing of multidimensional arrays). An
254 * example block describing one factor is:
255 *
256 * <pre>
257 * 3
258 * 4 8 7
259 * 3 2 2
260 * 11
261 * 0 0.1
262 * 1 3.5
263 * 2 2.8
264 * 3 6.3
265 * 4 8.4
266 * 6 7.4
267 * 7 2.4
268 * 8 8.9
269 * 9 1.3
270 * 10 1.6
271 * 12 6.4
272 * 11 2.6
273 * </pre>
274 *
275 * which corresponds to the following factor:
276 *
277 * \f[
278 * \begin{array}{ccc|c}
279 * x_4 & x_8 & x_7 & \mbox{value}\\
280 * \hline
281 * 0 & 0 & 0 & 0.1\\
282 * 1 & 0 & 0 & 3.5\\
283 * 2 & 0 & 0 & 2.8\\
284 * 0 & 1 & 0 & 6.3\\
285 * 1 & 1 & 0 & 8.4\\
286 * 2 & 1 & 0 & 0.0\\
287 * 0 & 0 & 1 & 7.4\\
288 * 1 & 0 & 1 & 2.4\\
289 * 2 & 0 & 1 & 8.9\\
290 * 0 & 1 & 1 & 1.3\\
291 * 1 & 1 & 1 & 1.6\\
292 * 2 & 1 & 1 & 2.6
293 * \end{array}
294 * \f]
295 *
296 * Note that the value of \f$x_4\f$ changes fastest, followed by that of \f$x_8\f$, and \f$x_7\f$
297 * varies the slowest, corresponding to the second line of the block ("4 8 7").
298 * Further, \f$x_4\f$ can take on three values, and \f$x_8\f$ and \f$x_7\f$ each have two possible
299 * values, as described in the third line of the block ("3 2 2"). The table
300 * contains 11 non-zero entries (all except for the fifth entry). Note that the
301 * eleventh and twelveth entries are interchanged.
302 *
303 * A final note: the internal representation in libDAI of the factor above is
304 * different, because the variables are ordered according to their indices
305 * (i.e., the ordering would be \f$x_4 x_7 x_8\f$) and the values of the table are
306 * stored accordingly, with the variable having the smallest index changing
307 * fastest:
308 *
309 * \f[
310 * \begin{array}{ccc|c}
311 * x_4 & x_7 & x_8 & \mbox{value}\\
312 * \hline
313 * 0 & 0 & 0 & 0.1\\
314 * 1 & 0 & 0 & 3.5\\
315 * 2 & 0 & 0 & 2.8\\
316 * 0 & 1 & 0 & 7.4\\
317 * 1 & 1 & 0 & 2.4\\
318 * 2 & 1 & 0 & 8.9\\
319 * 0 & 0 & 1 & 6.3\\
320 * 1 & 0 & 1 & 8.4\\
321 * 2 & 0 & 1 & 0.0\\
322 * 0 & 1 & 1 & 1.3\\
323 * 1 & 1 & 1 & 1.6\\
324 * 2 & 1 & 1 & 2.6
325 * \end{array}
326 * \f]
327 *
328 *
329 * \section fileformats-evidence Evidence (.tab) file format
330 *
331 * This page describes the .tab fileformat used in libDAI to store "evidence",
332 * i.e., a data set consisting of multiple samples, where each sample is the
333 * observed joint state of some variables.
334 *
335 * A .tab file is a tabular data file, consisting of a header line followed by
336 * one line for each data sample. Each line should have the same number of columns,
337 * where columns are separated by one tab character. Each column corresponds to
338 * a variable. The header line consists of the variable labels (corresponding to
339 * Var::label()). The other lines are observed joint states of the variables, i.e.,
340 * each line corresponds to a joint observation of the variables, and each column
341 * of a line contains the state of the variable associated with that column.
342 * Missing data is handled simply by having two consecutive tab characters,
343 * without any characters in between.
344 *
345 * \par Example:
346 *
347 * <pre>
348 * 1 3 2
349 * 0 0 1
350 * 1 0 1
351 * 1 1
352 * </pre>
353 *
354 * This would correspond to a data set consisting of three observations concerning
355 * the variables with labels 1, 3 and 2; the first observation being
356 * \f$x_1 = 0, x_3 = 0, x_2 = 1\f$, the second observation being
357 * \f$x_1 = 1, x_3 = 0, x_2 = 1\f$, and the third observation being
358 * \f$x_1 = 1, x_2 = 1\f$ (where the state of \f$x_3\f$ is missing).
359 */
360
361 /** \page license License
362
363 <b>libDAI is licensed under the GNU General Public License version 2, or
364 (at your option) any later version. The complete license text is
365 included below.</b>
366
367 \htmlonly
368 <pre>
369 GNU GENERAL PUBLIC LICENSE
370 Version 2, June 1991
371
372 Copyright (C) 1989, 1991 Free Software Foundation, Inc.
373 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
374 Everyone is permitted to copy and distribute verbatim copies
375 of this license document, but changing it is not allowed.
376
377 Preamble
378
379 The licenses for most software are designed to take away your
380 freedom to share and change it. By contrast, the GNU General Public
381 License is intended to guarantee your freedom to share and change free
382 software--to make sure the software is free for all its users. This
383 General Public License applies to most of the Free Software
384 Foundation's software and to any other program whose authors commit to
385 using it. (Some other Free Software Foundation software is covered by
386 the GNU Library General Public License instead.) You can apply it to
387 your programs, too.
388
389 When we speak of free software, we are referring to freedom, not
390 price. Our General Public Licenses are designed to make sure that you
391 have the freedom to distribute copies of free software (and charge for
392 this service if you wish), that you receive source code or can get it
393 if you want it, that you can change the software or use pieces of it
394 in new free programs; and that you know you can do these things.
395
396 To protect your rights, we need to make restrictions that forbid
397 anyone to deny you these rights or to ask you to surrender the rights.
398 These restrictions translate to certain responsibilities for you if you
399 distribute copies of the software, or if you modify it.
400
401 For example, if you distribute copies of such a program, whether
402 gratis or for a fee, you must give the recipients all the rights that
403 you have. You must make sure that they, too, receive or can get the
404 source code. And you must show them these terms so they know their
405 rights.
406
407 We protect your rights with two steps: (1) copyright the software, and
408 (2) offer you this license which gives you legal permission to copy,
409 distribute and/or modify the software.
410
411 Also, for each author's protection and ours, we want to make certain
412 that everyone understands that there is no warranty for this free
413 software. If the software is modified by someone else and passed on, we
414 want its recipients to know that what they have is not the original, so
415 that any problems introduced by others will not reflect on the original
416 authors' reputations.
417
418 Finally, any free program is threatened constantly by software
419 patents. We wish to avoid the danger that redistributors of a free
420 program will individually obtain patent licenses, in effect making the
421 program proprietary. To prevent this, we have made it clear that any
422 patent must be licensed for everyone's free use or not licensed at all.
423
424 The precise terms and conditions for copying, distribution and
425 modification follow.
426
427 GNU GENERAL PUBLIC LICENSE
428 TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
429
430 0. This License applies to any program or other work which contains
431 a notice placed by the copyright holder saying it may be distributed
432 under the terms of this General Public License. The "Program", below,
433 refers to any such program or work, and a "work based on the Program"
434 means either the Program or any derivative work under copyright law:
435 that is to say, a work containing the Program or a portion of it,
436 either verbatim or with modifications and/or translated into another
437 language. (Hereinafter, translation is included without limitation in
438 the term "modification".) Each licensee is addressed as "you".
439
440 Activities other than copying, distribution and modification are not
441 covered by this License; they are outside its scope. The act of
442 running the Program is not restricted, and the output from the Program
443 is covered only if its contents constitute a work based on the
444 Program (independent of having been made by running the Program).
445 Whether that is true depends on what the Program does.
446
447 1. You may copy and distribute verbatim copies of the Program's
448 source code as you receive it, in any medium, provided that you
449 conspicuously and appropriately publish on each copy an appropriate
450 copyright notice and disclaimer of warranty; keep intact all the
451 notices that refer to this License and to the absence of any warranty;
452 and give any other recipients of the Program a copy of this License
453 along with the Program.
454
455 You may charge a fee for the physical act of transferring a copy, and
456 you may at your option offer warranty protection in exchange for a fee.
457
458 2. You may modify your copy or copies of the Program or any portion
459 of it, thus forming a work based on the Program, and copy and
460 distribute such modifications or work under the terms of Section 1
461 above, provided that you also meet all of these conditions:
462
463 a) You must cause the modified files to carry prominent notices
464 stating that you changed the files and the date of any change.
465
466 b) You must cause any work that you distribute or publish, that in
467 whole or in part contains or is derived from the Program or any
468 part thereof, to be licensed as a whole at no charge to all third
469 parties under the terms of this License.
470
471 c) If the modified program normally reads commands interactively
472 when run, you must cause it, when started running for such
473 interactive use in the most ordinary way, to print or display an
474 announcement including an appropriate copyright notice and a
475 notice that there is no warranty (or else, saying that you provide
476 a warranty) and that users may redistribute the program under
477 these conditions, and telling the user how to view a copy of this
478 License. (Exception: if the Program itself is interactive but
479 does not normally print such an announcement, your work based on
480 the Program is not required to print an announcement.)
481
482 These requirements apply to the modified work as a whole. If
483 identifiable sections of that work are not derived from the Program,
484 and can be reasonably considered independent and separate works in
485 themselves, then this License, and its terms, do not apply to those
486 sections when you distribute them as separate works. But when you
487 distribute the same sections as part of a whole which is a work based
488 on the Program, the distribution of the whole must be on the terms of
489 this License, whose permissions for other licensees extend to the
490 entire whole, and thus to each and every part regardless of who wrote it.
491
492 Thus, it is not the intent of this section to claim rights or contest
493 your rights to work written entirely by you; rather, the intent is to
494 exercise the right to control the distribution of derivative or
495 collective works based on the Program.
496
497 In addition, mere aggregation of another work not based on the Program
498 with the Program (or with a work based on the Program) on a volume of
499 a storage or distribution medium does not bring the other work under
500 the scope of this License.
501
502 3. You may copy and distribute the Program (or a work based on it,
503 under Section 2) in object code or executable form under the terms of
504 Sections 1 and 2 above provided that you also do one of the following:
505
506 a) Accompany it with the complete corresponding machine-readable
507 source code, which must be distributed under the terms of Sections
508 1 and 2 above on a medium customarily used for software interchange; or,
509
510 b) Accompany it with a written offer, valid for at least three
511 years, to give any third party, for a charge no more than your
512 cost of physically performing source distribution, a complete
513 machine-readable copy of the corresponding source code, to be
514 distributed under the terms of Sections 1 and 2 above on a medium
515 customarily used for software interchange; or,
516
517 c) Accompany it with the information you received as to the offer
518 to distribute corresponding source code. (This alternative is
519 allowed only for noncommercial distribution and only if you
520 received the program in object code or executable form with such
521 an offer, in accord with Subsection b above.)
522
523 The source code for a work means the preferred form of the work for
524 making modifications to it. For an executable work, complete source
525 code means all the source code for all modules it contains, plus any
526 associated interface definition files, plus the scripts used to
527 control compilation and installation of the executable. However, as a
528 special exception, the source code distributed need not include
529 anything that is normally distributed (in either source or binary
530 form) with the major components (compiler, kernel, and so on) of the
531 operating system on which the executable runs, unless that component
532 itself accompanies the executable.
533
534 If distribution of executable or object code is made by offering
535 access to copy from a designated place, then offering equivalent
536 access to copy the source code from the same place counts as
537 distribution of the source code, even though third parties are not
538 compelled to copy the source along with the object code.
539
540 4. You may not copy, modify, sublicense, or distribute the Program
541 except as expressly provided under this License. Any attempt
542 otherwise to copy, modify, sublicense or distribute the Program is
543 void, and will automatically terminate your rights under this License.
544 However, parties who have received copies, or rights, from you under
545 this License will not have their licenses terminated so long as such
546 parties remain in full compliance.
547
548 5. You are not required to accept this License, since you have not
549 signed it. However, nothing else grants you permission to modify or
550 distribute the Program or its derivative works. These actions are
551 prohibited by law if you do not accept this License. Therefore, by
552 modifying or distributing the Program (or any work based on the
553 Program), you indicate your acceptance of this License to do so, and
554 all its terms and conditions for copying, distributing or modifying
555 the Program or works based on it.
556
557 6. Each time you redistribute the Program (or any work based on the
558 Program), the recipient automatically receives a license from the
559 original licensor to copy, distribute or modify the Program subject to
560 these terms and conditions. You may not impose any further
561 restrictions on the recipients' exercise of the rights granted herein.
562 You are not responsible for enforcing compliance by third parties to
563 this License.
564
565 7. If, as a consequence of a court judgment or allegation of patent
566 infringement or for any other reason (not limited to patent issues),
567 conditions are imposed on you (whether by court order, agreement or
568 otherwise) that contradict the conditions of this License, they do not
569 excuse you from the conditions of this License. If you cannot
570 distribute so as to satisfy simultaneously your obligations under this
571 License and any other pertinent obligations, then as a consequence you
572 may not distribute the Program at all. For example, if a patent
573 license would not permit royalty-free redistribution of the Program by
574 all those who receive copies directly or indirectly through you, then
575 the only way you could satisfy both it and this License would be to
576 refrain entirely from distribution of the Program.
577
578 If any portion of this section is held invalid or unenforceable under
579 any particular circumstance, the balance of the section is intended to
580 apply and the section as a whole is intended to apply in other
581 circumstances.
582
583 It is not the purpose of this section to induce you to infringe any
584 patents or other property right claims or to contest validity of any
585 such claims; this section has the sole purpose of protecting the
586 integrity of the free software distribution system, which is
587 implemented by public license practices. Many people have made
588 generous contributions to the wide range of software distributed
589 through that system in reliance on consistent application of that
590 system; it is up to the author/donor to decide if he or she is willing
591 to distribute software through any other system and a licensee cannot
592 impose that choice.
593
594 This section is intended to make thoroughly clear what is believed to
595 be a consequence of the rest of this License.
596
597 8. If the distribution and/or use of the Program is restricted in
598 certain countries either by patents or by copyrighted interfaces, the
599 original copyright holder who places the Program under this License
600 may add an explicit geographical distribution limitation excluding
601 those countries, so that distribution is permitted only in or among
602 countries not thus excluded. In such case, this License incorporates
603 the limitation as if written in the body of this License.
604
605 9. The Free Software Foundation may publish revised and/or new versions
606 of the General Public License from time to time. Such new versions will
607 be similar in spirit to the present version, but may differ in detail to
608 address new problems or concerns.
609
610 Each version is given a distinguishing version number. If the Program
611 specifies a version number of this License which applies to it and "any
612 later version", you have the option of following the terms and conditions
613 either of that version or of any later version published by the Free
614 Software Foundation. If the Program does not specify a version number of
615 this License, you may choose any version ever published by the Free Software
616 Foundation.
617
618 10. If you wish to incorporate parts of the Program into other free
619 programs whose distribution conditions are different, write to the author
620 to ask for permission. For software which is copyrighted by the Free
621 Software Foundation, write to the Free Software Foundation; we sometimes
622 make exceptions for this. Our decision will be guided by the two goals
623 of preserving the free status of all derivatives of our free software and
624 of promoting the sharing and reuse of software generally.
625
626 NO WARRANTY
627
628 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
629 FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
630 OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
631 PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
632 OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
633 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
634 TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
635 PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
636 REPAIR OR CORRECTION.
637
638 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
639 WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
640 REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
641 INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
642 OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
643 TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
644 YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
645 PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
646 POSSIBILITY OF SUCH DAMAGES.
647
648 END OF TERMS AND CONDITIONS
649
650 How to Apply These Terms to Your New Programs
651
652 If you develop a new program, and you want it to be of the greatest
653 possible use to the public, the best way to achieve this is to make it
654 free software which everyone can redistribute and change under these terms.
655
656 To do so, attach the following notices to the program. It is safest
657 to attach them to the start of each source file to most effectively
658 convey the exclusion of warranty; and each file should have at least
659 the "copyright" line and a pointer to where the full notice is found.
660
661 &lt;one line to give the program's name and a brief idea of what it does.&gt;
662 Copyright (C) &lt;year&gt; &lt;name of author&gt;
663
664 This program is free software; you can redistribute it and/or modify
665 it under the terms of the GNU General Public License as published by
666 the Free Software Foundation; either version 2 of the License, or
667 (at your option) any later version.
668
669 This program is distributed in the hope that it will be useful,
670 but WITHOUT ANY WARRANTY; without even the implied warranty of
671 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
672 GNU General Public License for more details.
673
674 You should have received a copy of the GNU General Public License
675 along with this program; if not, write to the Free Software
676 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
677
678
679 Also add information on how to contact you by electronic and paper mail.
680
681 If the program is interactive, make it output a short notice like this
682 when it starts in an interactive mode:
683
684 Gnomovision version 69, Copyright (C) year name of author
685 Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
686 This is free software, and you are welcome to redistribute it
687 under certain conditions; type `show c' for details.
688
689 The hypothetical commands `show w' and `show c' should show the appropriate
690 parts of the General Public License. Of course, the commands you use may
691 be called something other than `show w' and `show c'; they could even be
692 mouse-clicks or menu items--whatever suits your program.
693
694 You should also get your employer (if you work as a programmer) or your
695 school, if any, to sign a "copyright disclaimer" for the program, if
696 necessary. Here is a sample; alter the names:
697
698 Yoyodyne, Inc., hereby disclaims all copyright interest in the program
699 `Gnomovision' (which makes passes at compilers) written by James Hacker.
700
701 &lt;signature of Ty Coon&gt;, 1 April 1989
702 Ty Coon, President of Vice
703
704 This General Public License does not permit incorporating your program into
705 proprietary programs. If your program is a subroutine library, you may
706 consider it more useful to permit linking proprietary applications with the
707 library. If this is what you want to do, use the GNU Library General
708 Public License instead of this License.</pre>
709 \endhtmlonly
710 */