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