Improved documentation of include/dai/cbp.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 fileformat libDAI factorgraph file format
225 *
226 * This page describes the .fg fileformat used in libDAI to store factor graphs.
227 * Markov Random Fields are special cases of factor graphs, as are Bayesian
228 * networks. A factor graph can be specified as follows: for each factor, one has
229 * to specify which variables occur in the factor, what their respective
230 * cardinalities (i.e., number of possible values) are, and a table listing all
231 * the values of that factor for all possible configurations of these variables.
232 * A .fg file is not much more than that. It starts with a line containing the
233 * number of factors in that graph, followed by an empty line. Then all factors
234 * are specified, one block for each factor, where the blocks are seperated by
235 * empty lines. Each variable occurring in the factor graph has a unique
236 * identifier, its index (which should be a nonnegative integer). Comment lines
237 * start with #.
238 *
239 * Each block starts with a line containing the number of variables in that
240 * factor. The second line contains the indices of these variables, seperated by
241 * spaces (indices are nonnegative integers and to avoid confusion, it is
242 * suggested to start counting at 0). The third line contains the number of
243 * possible values of each of these variables, also seperated by spaces. Note that
244 * there is some redundancy here, since if a variable appears in more than one
245 * factor, the cardinality of that variable appears several times in the .fg file.
246 * The fourth line contains the number of nonzero entries in the factor table.
247 * The rest of the lines contain these nonzero entries; each entry consists of a
248 * table index, followed by white-space, followed by the value corresponding to
249 * that table index. The most difficult part is getting the indexing right. The
250 * convention that is used is that the left-most variables cycle through their
251 * values the fastest (similar to MATLAB indexing of multidimensional arrays). An
252 * example block describing one factor is:
253 *
254 * 3\n
255 * 4 8 7\n
256 * 3 2 2\n
257 * 11\n
258 * 0 0.1\n
259 * 1 3.5\n
260 * 2 2.8\n
261 * 3 6.3\n
262 * 4 8.4\n
263 * 6 7.4\n
264 * 7 2.4\n
265 * 8 8.9\n
266 * 9 1.3\n
267 * 10 1.6\n
268 * 12 6.4\n
269 * 11 2.6\n
270 *
271 * which corresponds to the following factor:
272 *
273 * \f[
274 * \begin{array}{ccc|c}
275 * x_4 & x_8 & x_7 & \mbox{value}\\
276 * \hline
277 * 0 & 0 & 0 & 0.1\\
278 * 1 & 0 & 0 & 3.5\\
279 * 2 & 0 & 0 & 2.8\\
280 * 0 & 1 & 0 & 6.3\\
281 * 1 & 1 & 0 & 8.4\\
282 * 2 & 1 & 0 & 0.0\\
283 * 0 & 0 & 1 & 7.4\\
284 * 1 & 0 & 1 & 2.4\\
285 * 2 & 0 & 1 & 8.9\\
286 * 0 & 1 & 1 & 1.3\\
287 * 1 & 1 & 1 & 1.6\\
288 * 2 & 1 & 1 & 2.6
289 * \end{array}
290 * \f]
291 *
292 * Note that the value of x_4 changes fastest, followed by that of x_8, and x_7
293 * varies the slowest, corresponding to the second line of the block ("4 8 7").
294 * Further, x_4 can take on three values, and x_8 and x_7 each have two possible
295 * values, as described in the third line of the block ("3 2 2"). The table
296 * contains 11 non-zero entries (all except for the fifth entry). Note that the
297 * eleventh and twelveth entries are interchanged.
298 *
299 * A final note: the internal representation in libDAI of the factor above is
300 * different, because the variables are ordered according to their indices
301 * (i.e., the ordering would be x_4 x_7 x_8) and the values of the table are
302 * stored accordingly, with the variable having the smallest index changing
303 * fastest:
304 *
305 * \f[
306 * \begin{array}{ccc|c}
307 * x_4 & x_7 & x_8 & \mbox{value}\\
308 * \hline
309 * 0 & 0 & 0 & 0.1\\
310 * 1 & 0 & 0 & 3.5\\
311 * 2 & 0 & 0 & 2.8\\
312 * 0 & 1 & 0 & 7.4\\
313 * 1 & 1 & 0 & 2.4\\
314 * 2 & 1 & 0 & 8.9\\
315 * 0 & 0 & 1 & 6.3\\
316 * 1 & 0 & 1 & 8.4\\
317 * 2 & 0 & 1 & 0.0\\
318 * 0 & 1 & 1 & 1.3\\
319 * 1 & 1 & 1 & 1.6\\
320 * 2 & 1 & 1 & 2.6
321 * \end{array}
322 * \f]
323 */
324
325
326 /** \page license License
327
328 <b>libDAI is licensed under the GNU General Public License version 2, or
329 (at your option) any later version. The complete license text is
330 included below.</b>
331
332 \htmlonly
333 <pre>
334 GNU GENERAL PUBLIC LICENSE
335 Version 2, June 1991
336
337 Copyright (C) 1989, 1991 Free Software Foundation, Inc.
338 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
339 Everyone is permitted to copy and distribute verbatim copies
340 of this license document, but changing it is not allowed.
341
342 Preamble
343
344 The licenses for most software are designed to take away your
345 freedom to share and change it. By contrast, the GNU General Public
346 License is intended to guarantee your freedom to share and change free
347 software--to make sure the software is free for all its users. This
348 General Public License applies to most of the Free Software
349 Foundation's software and to any other program whose authors commit to
350 using it. (Some other Free Software Foundation software is covered by
351 the GNU Library General Public License instead.) You can apply it to
352 your programs, too.
353
354 When we speak of free software, we are referring to freedom, not
355 price. Our General Public Licenses are designed to make sure that you
356 have the freedom to distribute copies of free software (and charge for
357 this service if you wish), that you receive source code or can get it
358 if you want it, that you can change the software or use pieces of it
359 in new free programs; and that you know you can do these things.
360
361 To protect your rights, we need to make restrictions that forbid
362 anyone to deny you these rights or to ask you to surrender the rights.
363 These restrictions translate to certain responsibilities for you if you
364 distribute copies of the software, or if you modify it.
365
366 For example, if you distribute copies of such a program, whether
367 gratis or for a fee, you must give the recipients all the rights that
368 you have. You must make sure that they, too, receive or can get the
369 source code. And you must show them these terms so they know their
370 rights.
371
372 We protect your rights with two steps: (1) copyright the software, and
373 (2) offer you this license which gives you legal permission to copy,
374 distribute and/or modify the software.
375
376 Also, for each author's protection and ours, we want to make certain
377 that everyone understands that there is no warranty for this free
378 software. If the software is modified by someone else and passed on, we
379 want its recipients to know that what they have is not the original, so
380 that any problems introduced by others will not reflect on the original
381 authors' reputations.
382
383 Finally, any free program is threatened constantly by software
384 patents. We wish to avoid the danger that redistributors of a free
385 program will individually obtain patent licenses, in effect making the
386 program proprietary. To prevent this, we have made it clear that any
387 patent must be licensed for everyone's free use or not licensed at all.
388
389 The precise terms and conditions for copying, distribution and
390 modification follow.
391
392 GNU GENERAL PUBLIC LICENSE
393 TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
394
395 0. This License applies to any program or other work which contains
396 a notice placed by the copyright holder saying it may be distributed
397 under the terms of this General Public License. The "Program", below,
398 refers to any such program or work, and a "work based on the Program"
399 means either the Program or any derivative work under copyright law:
400 that is to say, a work containing the Program or a portion of it,
401 either verbatim or with modifications and/or translated into another
402 language. (Hereinafter, translation is included without limitation in
403 the term "modification".) Each licensee is addressed as "you".
404
405 Activities other than copying, distribution and modification are not
406 covered by this License; they are outside its scope. The act of
407 running the Program is not restricted, and the output from the Program
408 is covered only if its contents constitute a work based on the
409 Program (independent of having been made by running the Program).
410 Whether that is true depends on what the Program does.
411
412 1. You may copy and distribute verbatim copies of the Program's
413 source code as you receive it, in any medium, provided that you
414 conspicuously and appropriately publish on each copy an appropriate
415 copyright notice and disclaimer of warranty; keep intact all the
416 notices that refer to this License and to the absence of any warranty;
417 and give any other recipients of the Program a copy of this License
418 along with the Program.
419
420 You may charge a fee for the physical act of transferring a copy, and
421 you may at your option offer warranty protection in exchange for a fee.
422
423 2. You may modify your copy or copies of the Program or any portion
424 of it, thus forming a work based on the Program, and copy and
425 distribute such modifications or work under the terms of Section 1
426 above, provided that you also meet all of these conditions:
427
428 a) You must cause the modified files to carry prominent notices
429 stating that you changed the files and the date of any change.
430
431 b) You must cause any work that you distribute or publish, that in
432 whole or in part contains or is derived from the Program or any
433 part thereof, to be licensed as a whole at no charge to all third
434 parties under the terms of this License.
435
436 c) If the modified program normally reads commands interactively
437 when run, you must cause it, when started running for such
438 interactive use in the most ordinary way, to print or display an
439 announcement including an appropriate copyright notice and a
440 notice that there is no warranty (or else, saying that you provide
441 a warranty) and that users may redistribute the program under
442 these conditions, and telling the user how to view a copy of this
443 License. (Exception: if the Program itself is interactive but
444 does not normally print such an announcement, your work based on
445 the Program is not required to print an announcement.)
446
447 These requirements apply to the modified work as a whole. If
448 identifiable sections of that work are not derived from the Program,
449 and can be reasonably considered independent and separate works in
450 themselves, then this License, and its terms, do not apply to those
451 sections when you distribute them as separate works. But when you
452 distribute the same sections as part of a whole which is a work based
453 on the Program, the distribution of the whole must be on the terms of
454 this License, whose permissions for other licensees extend to the
455 entire whole, and thus to each and every part regardless of who wrote it.
456
457 Thus, it is not the intent of this section to claim rights or contest
458 your rights to work written entirely by you; rather, the intent is to
459 exercise the right to control the distribution of derivative or
460 collective works based on the Program.
461
462 In addition, mere aggregation of another work not based on the Program
463 with the Program (or with a work based on the Program) on a volume of
464 a storage or distribution medium does not bring the other work under
465 the scope of this License.
466
467 3. You may copy and distribute the Program (or a work based on it,
468 under Section 2) in object code or executable form under the terms of
469 Sections 1 and 2 above provided that you also do one of the following:
470
471 a) Accompany it with the complete corresponding machine-readable
472 source code, which must be distributed under the terms of Sections
473 1 and 2 above on a medium customarily used for software interchange; or,
474
475 b) Accompany it with a written offer, valid for at least three
476 years, to give any third party, for a charge no more than your
477 cost of physically performing source distribution, a complete
478 machine-readable copy of the corresponding source code, to be
479 distributed under the terms of Sections 1 and 2 above on a medium
480 customarily used for software interchange; or,
481
482 c) Accompany it with the information you received as to the offer
483 to distribute corresponding source code. (This alternative is
484 allowed only for noncommercial distribution and only if you
485 received the program in object code or executable form with such
486 an offer, in accord with Subsection b above.)
487
488 The source code for a work means the preferred form of the work for
489 making modifications to it. For an executable work, complete source
490 code means all the source code for all modules it contains, plus any
491 associated interface definition files, plus the scripts used to
492 control compilation and installation of the executable. However, as a
493 special exception, the source code distributed need not include
494 anything that is normally distributed (in either source or binary
495 form) with the major components (compiler, kernel, and so on) of the
496 operating system on which the executable runs, unless that component
497 itself accompanies the executable.
498
499 If distribution of executable or object code is made by offering
500 access to copy from a designated place, then offering equivalent
501 access to copy the source code from the same place counts as
502 distribution of the source code, even though third parties are not
503 compelled to copy the source along with the object code.
504
505 4. You may not copy, modify, sublicense, or distribute the Program
506 except as expressly provided under this License. Any attempt
507 otherwise to copy, modify, sublicense or distribute the Program is
508 void, and will automatically terminate your rights under this License.
509 However, parties who have received copies, or rights, from you under
510 this License will not have their licenses terminated so long as such
511 parties remain in full compliance.
512
513 5. You are not required to accept this License, since you have not
514 signed it. However, nothing else grants you permission to modify or
515 distribute the Program or its derivative works. These actions are
516 prohibited by law if you do not accept this License. Therefore, by
517 modifying or distributing the Program (or any work based on the
518 Program), you indicate your acceptance of this License to do so, and
519 all its terms and conditions for copying, distributing or modifying
520 the Program or works based on it.
521
522 6. Each time you redistribute the Program (or any work based on the
523 Program), the recipient automatically receives a license from the
524 original licensor to copy, distribute or modify the Program subject to
525 these terms and conditions. You may not impose any further
526 restrictions on the recipients' exercise of the rights granted herein.
527 You are not responsible for enforcing compliance by third parties to
528 this License.
529
530 7. If, as a consequence of a court judgment or allegation of patent
531 infringement or for any other reason (not limited to patent issues),
532 conditions are imposed on you (whether by court order, agreement or
533 otherwise) that contradict the conditions of this License, they do not
534 excuse you from the conditions of this License. If you cannot
535 distribute so as to satisfy simultaneously your obligations under this
536 License and any other pertinent obligations, then as a consequence you
537 may not distribute the Program at all. For example, if a patent
538 license would not permit royalty-free redistribution of the Program by
539 all those who receive copies directly or indirectly through you, then
540 the only way you could satisfy both it and this License would be to
541 refrain entirely from distribution of the Program.
542
543 If any portion of this section is held invalid or unenforceable under
544 any particular circumstance, the balance of the section is intended to
545 apply and the section as a whole is intended to apply in other
546 circumstances.
547
548 It is not the purpose of this section to induce you to infringe any
549 patents or other property right claims or to contest validity of any
550 such claims; this section has the sole purpose of protecting the
551 integrity of the free software distribution system, which is
552 implemented by public license practices. Many people have made
553 generous contributions to the wide range of software distributed
554 through that system in reliance on consistent application of that
555 system; it is up to the author/donor to decide if he or she is willing
556 to distribute software through any other system and a licensee cannot
557 impose that choice.
558
559 This section is intended to make thoroughly clear what is believed to
560 be a consequence of the rest of this License.
561
562 8. If the distribution and/or use of the Program is restricted in
563 certain countries either by patents or by copyrighted interfaces, the
564 original copyright holder who places the Program under this License
565 may add an explicit geographical distribution limitation excluding
566 those countries, so that distribution is permitted only in or among
567 countries not thus excluded. In such case, this License incorporates
568 the limitation as if written in the body of this License.
569
570 9. The Free Software Foundation may publish revised and/or new versions
571 of the General Public License from time to time. Such new versions will
572 be similar in spirit to the present version, but may differ in detail to
573 address new problems or concerns.
574
575 Each version is given a distinguishing version number. If the Program
576 specifies a version number of this License which applies to it and "any
577 later version", you have the option of following the terms and conditions
578 either of that version or of any later version published by the Free
579 Software Foundation. If the Program does not specify a version number of
580 this License, you may choose any version ever published by the Free Software
581 Foundation.
582
583 10. If you wish to incorporate parts of the Program into other free
584 programs whose distribution conditions are different, write to the author
585 to ask for permission. For software which is copyrighted by the Free
586 Software Foundation, write to the Free Software Foundation; we sometimes
587 make exceptions for this. Our decision will be guided by the two goals
588 of preserving the free status of all derivatives of our free software and
589 of promoting the sharing and reuse of software generally.
590
591 NO WARRANTY
592
593 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
594 FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
595 OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
596 PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
597 OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
598 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
599 TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
600 PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
601 REPAIR OR CORRECTION.
602
603 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
604 WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
605 REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
606 INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
607 OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
608 TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
609 YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
610 PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
611 POSSIBILITY OF SUCH DAMAGES.
612
613 END OF TERMS AND CONDITIONS
614
615 How to Apply These Terms to Your New Programs
616
617 If you develop a new program, and you want it to be of the greatest
618 possible use to the public, the best way to achieve this is to make it
619 free software which everyone can redistribute and change under these terms.
620
621 To do so, attach the following notices to the program. It is safest
622 to attach them to the start of each source file to most effectively
623 convey the exclusion of warranty; and each file should have at least
624 the "copyright" line and a pointer to where the full notice is found.
625
626 &lt;one line to give the program's name and a brief idea of what it does.&gt;
627 Copyright (C) &lt;year&gt; &lt;name of author&gt;
628
629 This program is free software; you can redistribute it and/or modify
630 it under the terms of the GNU General Public License as published by
631 the Free Software Foundation; either version 2 of the License, or
632 (at your option) any later version.
633
634 This program is distributed in the hope that it will be useful,
635 but WITHOUT ANY WARRANTY; without even the implied warranty of
636 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
637 GNU General Public License for more details.
638
639 You should have received a copy of the GNU General Public License
640 along with this program; if not, write to the Free Software
641 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
642
643
644 Also add information on how to contact you by electronic and paper mail.
645
646 If the program is interactive, make it output a short notice like this
647 when it starts in an interactive mode:
648
649 Gnomovision version 69, Copyright (C) year name of author
650 Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
651 This is free software, and you are welcome to redistribute it
652 under certain conditions; type `show c' for details.
653
654 The hypothetical commands `show w' and `show c' should show the appropriate
655 parts of the General Public License. Of course, the commands you use may
656 be called something other than `show w' and `show c'; they could even be
657 mouse-clicks or menu items--whatever suits your program.
658
659 You should also get your employer (if you work as a programmer) or your
660 school, if any, to sign a "copyright disclaimer" for the program, if
661 necessary. Here is a sample; alter the names:
662
663 Yoyodyne, Inc., hereby disclaims all copyright interest in the program
664 `Gnomovision' (which makes passes at compilers) written by James Hacker.
665
666 &lt;signature of Ty Coon&gt;, 1 April 1989
667 Ty Coon, President of Vice
668
669 This General Public License does not permit incorporating your program into
670 proprietary programs. If your program is a subroutine library, you may
671 consider it more useful to permit linking proprietary applications with the
672 library. If this is what you want to do, use the GNU Library General
673 Public License instead of this License.</pre>
674 \endhtmlonly
675 */