Documented all exceptions and did some general cleanups
[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 * \section fileformats-emalg Expectation Maximization (.em) file format
361 *
362 * This section describes the file format of .em files, which are used
363 * to specify a particular EM algorithm. The .em files are complementary
364 * to .fg files; in other words, an .em file without a corresponding .fg
365 * file is useless. Furthermore, one also needs a corresponding .tab file
366 * containing the data used for parameter learning.
367 *
368 * An .em file starts with a line specifying the number of maximization steps.
369 * Then, for each maximization step, its description follows in the format
370 * described in the next section.
371 *
372 * \subsection fileformats-emalg-maximizationstep Maximization Step section in EM file
373 *
374 * A maximization step section of an .em file starts with a single line
375 * describing the number of shared parameters sections that will follow.
376 * Then, precisely that number of shared parameters sections follow,
377 * where each of those sections follows the format described in the next
378 * subsection.
379 *
380 * \subsection fileformats-emalg-sharedparameters Shared parameters section in EM file
381 *
382 * A shared parameters section of an .em file starts with a single line
383 * consisting of the name of a ParameterEstimation subclass
384 * and its parameters in the format of a PropertySet. For example:
385 *
386 * <pre>
387 * ConditionalProbEstimation [target_dim=2,total_dim=4,pseudo_count=1]
388 * </pre>
389 *
390 * The next line contains the number of factors that share their parameters.
391 * Then, each of these factors is specified on separate lines (possibly
392 * seperated by empty lines), where each line consists of several fields
393 * seperated by a space or a tab character. The first field contains
394 * the index of the factor in the factor graph. The following fields should
395 * contain the variable labels of the variables on which that factor depends,
396 * in a specific ordering. This ordering can be different from the canonical
397 * ordering of the variables used internally in libDAI (which would be sorted
398 * ascendingly according to the variable labels). The odering of the variables
399 * specifies the implicit ordering of the shared parameters: when iterating
400 * over all shared parameters, the corresponding index of the first variable
401 * changes fastest (in the inner loop), and the corresponding index of the
402 * last variable changes slowest (in the outer loop). By choosing the right
403 * ordering, it is possible to let different factors (depending on different
404 * variables) share parameters in parameter learning using EM.
405 */
406
407 /** \page license License
408
409 <b>libDAI is licensed under the GNU General Public License version 2, or
410 (at your option) any later version. The complete license text is
411 included below.</b>
412
413 \htmlonly
414 <pre>
415 GNU GENERAL PUBLIC LICENSE
416 Version 2, June 1991
417
418 Copyright (C) 1989, 1991 Free Software Foundation, Inc.
419 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
420 Everyone is permitted to copy and distribute verbatim copies
421 of this license document, but changing it is not allowed.
422
423 Preamble
424
425 The licenses for most software are designed to take away your
426 freedom to share and change it. By contrast, the GNU General Public
427 License is intended to guarantee your freedom to share and change free
428 software--to make sure the software is free for all its users. This
429 General Public License applies to most of the Free Software
430 Foundation's software and to any other program whose authors commit to
431 using it. (Some other Free Software Foundation software is covered by
432 the GNU Library General Public License instead.) You can apply it to
433 your programs, too.
434
435 When we speak of free software, we are referring to freedom, not
436 price. Our General Public Licenses are designed to make sure that you
437 have the freedom to distribute copies of free software (and charge for
438 this service if you wish), that you receive source code or can get it
439 if you want it, that you can change the software or use pieces of it
440 in new free programs; and that you know you can do these things.
441
442 To protect your rights, we need to make restrictions that forbid
443 anyone to deny you these rights or to ask you to surrender the rights.
444 These restrictions translate to certain responsibilities for you if you
445 distribute copies of the software, or if you modify it.
446
447 For example, if you distribute copies of such a program, whether
448 gratis or for a fee, you must give the recipients all the rights that
449 you have. You must make sure that they, too, receive or can get the
450 source code. And you must show them these terms so they know their
451 rights.
452
453 We protect your rights with two steps: (1) copyright the software, and
454 (2) offer you this license which gives you legal permission to copy,
455 distribute and/or modify the software.
456
457 Also, for each author's protection and ours, we want to make certain
458 that everyone understands that there is no warranty for this free
459 software. If the software is modified by someone else and passed on, we
460 want its recipients to know that what they have is not the original, so
461 that any problems introduced by others will not reflect on the original
462 authors' reputations.
463
464 Finally, any free program is threatened constantly by software
465 patents. We wish to avoid the danger that redistributors of a free
466 program will individually obtain patent licenses, in effect making the
467 program proprietary. To prevent this, we have made it clear that any
468 patent must be licensed for everyone's free use or not licensed at all.
469
470 The precise terms and conditions for copying, distribution and
471 modification follow.
472
473 GNU GENERAL PUBLIC LICENSE
474 TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
475
476 0. This License applies to any program or other work which contains
477 a notice placed by the copyright holder saying it may be distributed
478 under the terms of this General Public License. The "Program", below,
479 refers to any such program or work, and a "work based on the Program"
480 means either the Program or any derivative work under copyright law:
481 that is to say, a work containing the Program or a portion of it,
482 either verbatim or with modifications and/or translated into another
483 language. (Hereinafter, translation is included without limitation in
484 the term "modification".) Each licensee is addressed as "you".
485
486 Activities other than copying, distribution and modification are not
487 covered by this License; they are outside its scope. The act of
488 running the Program is not restricted, and the output from the Program
489 is covered only if its contents constitute a work based on the
490 Program (independent of having been made by running the Program).
491 Whether that is true depends on what the Program does.
492
493 1. You may copy and distribute verbatim copies of the Program's
494 source code as you receive it, in any medium, provided that you
495 conspicuously and appropriately publish on each copy an appropriate
496 copyright notice and disclaimer of warranty; keep intact all the
497 notices that refer to this License and to the absence of any warranty;
498 and give any other recipients of the Program a copy of this License
499 along with the Program.
500
501 You may charge a fee for the physical act of transferring a copy, and
502 you may at your option offer warranty protection in exchange for a fee.
503
504 2. You may modify your copy or copies of the Program or any portion
505 of it, thus forming a work based on the Program, and copy and
506 distribute such modifications or work under the terms of Section 1
507 above, provided that you also meet all of these conditions:
508
509 a) You must cause the modified files to carry prominent notices
510 stating that you changed the files and the date of any change.
511
512 b) You must cause any work that you distribute or publish, that in
513 whole or in part contains or is derived from the Program or any
514 part thereof, to be licensed as a whole at no charge to all third
515 parties under the terms of this License.
516
517 c) If the modified program normally reads commands interactively
518 when run, you must cause it, when started running for such
519 interactive use in the most ordinary way, to print or display an
520 announcement including an appropriate copyright notice and a
521 notice that there is no warranty (or else, saying that you provide
522 a warranty) and that users may redistribute the program under
523 these conditions, and telling the user how to view a copy of this
524 License. (Exception: if the Program itself is interactive but
525 does not normally print such an announcement, your work based on
526 the Program is not required to print an announcement.)
527
528 These requirements apply to the modified work as a whole. If
529 identifiable sections of that work are not derived from the Program,
530 and can be reasonably considered independent and separate works in
531 themselves, then this License, and its terms, do not apply to those
532 sections when you distribute them as separate works. But when you
533 distribute the same sections as part of a whole which is a work based
534 on the Program, the distribution of the whole must be on the terms of
535 this License, whose permissions for other licensees extend to the
536 entire whole, and thus to each and every part regardless of who wrote it.
537
538 Thus, it is not the intent of this section to claim rights or contest
539 your rights to work written entirely by you; rather, the intent is to
540 exercise the right to control the distribution of derivative or
541 collective works based on the Program.
542
543 In addition, mere aggregation of another work not based on the Program
544 with the Program (or with a work based on the Program) on a volume of
545 a storage or distribution medium does not bring the other work under
546 the scope of this License.
547
548 3. You may copy and distribute the Program (or a work based on it,
549 under Section 2) in object code or executable form under the terms of
550 Sections 1 and 2 above provided that you also do one of the following:
551
552 a) Accompany it with the complete corresponding machine-readable
553 source code, which must be distributed under the terms of Sections
554 1 and 2 above on a medium customarily used for software interchange; or,
555
556 b) Accompany it with a written offer, valid for at least three
557 years, to give any third party, for a charge no more than your
558 cost of physically performing source distribution, a complete
559 machine-readable copy of the corresponding source code, to be
560 distributed under the terms of Sections 1 and 2 above on a medium
561 customarily used for software interchange; or,
562
563 c) Accompany it with the information you received as to the offer
564 to distribute corresponding source code. (This alternative is
565 allowed only for noncommercial distribution and only if you
566 received the program in object code or executable form with such
567 an offer, in accord with Subsection b above.)
568
569 The source code for a work means the preferred form of the work for
570 making modifications to it. For an executable work, complete source
571 code means all the source code for all modules it contains, plus any
572 associated interface definition files, plus the scripts used to
573 control compilation and installation of the executable. However, as a
574 special exception, the source code distributed need not include
575 anything that is normally distributed (in either source or binary
576 form) with the major components (compiler, kernel, and so on) of the
577 operating system on which the executable runs, unless that component
578 itself accompanies the executable.
579
580 If distribution of executable or object code is made by offering
581 access to copy from a designated place, then offering equivalent
582 access to copy the source code from the same place counts as
583 distribution of the source code, even though third parties are not
584 compelled to copy the source along with the object code.
585
586 4. You may not copy, modify, sublicense, or distribute the Program
587 except as expressly provided under this License. Any attempt
588 otherwise to copy, modify, sublicense or distribute the Program is
589 void, and will automatically terminate your rights under this License.
590 However, parties who have received copies, or rights, from you under
591 this License will not have their licenses terminated so long as such
592 parties remain in full compliance.
593
594 5. You are not required to accept this License, since you have not
595 signed it. However, nothing else grants you permission to modify or
596 distribute the Program or its derivative works. These actions are
597 prohibited by law if you do not accept this License. Therefore, by
598 modifying or distributing the Program (or any work based on the
599 Program), you indicate your acceptance of this License to do so, and
600 all its terms and conditions for copying, distributing or modifying
601 the Program or works based on it.
602
603 6. Each time you redistribute the Program (or any work based on the
604 Program), the recipient automatically receives a license from the
605 original licensor to copy, distribute or modify the Program subject to
606 these terms and conditions. You may not impose any further
607 restrictions on the recipients' exercise of the rights granted herein.
608 You are not responsible for enforcing compliance by third parties to
609 this License.
610
611 7. If, as a consequence of a court judgment or allegation of patent
612 infringement or for any other reason (not limited to patent issues),
613 conditions are imposed on you (whether by court order, agreement or
614 otherwise) that contradict the conditions of this License, they do not
615 excuse you from the conditions of this License. If you cannot
616 distribute so as to satisfy simultaneously your obligations under this
617 License and any other pertinent obligations, then as a consequence you
618 may not distribute the Program at all. For example, if a patent
619 license would not permit royalty-free redistribution of the Program by
620 all those who receive copies directly or indirectly through you, then
621 the only way you could satisfy both it and this License would be to
622 refrain entirely from distribution of the Program.
623
624 If any portion of this section is held invalid or unenforceable under
625 any particular circumstance, the balance of the section is intended to
626 apply and the section as a whole is intended to apply in other
627 circumstances.
628
629 It is not the purpose of this section to induce you to infringe any
630 patents or other property right claims or to contest validity of any
631 such claims; this section has the sole purpose of protecting the
632 integrity of the free software distribution system, which is
633 implemented by public license practices. Many people have made
634 generous contributions to the wide range of software distributed
635 through that system in reliance on consistent application of that
636 system; it is up to the author/donor to decide if he or she is willing
637 to distribute software through any other system and a licensee cannot
638 impose that choice.
639
640 This section is intended to make thoroughly clear what is believed to
641 be a consequence of the rest of this License.
642
643 8. If the distribution and/or use of the Program is restricted in
644 certain countries either by patents or by copyrighted interfaces, the
645 original copyright holder who places the Program under this License
646 may add an explicit geographical distribution limitation excluding
647 those countries, so that distribution is permitted only in or among
648 countries not thus excluded. In such case, this License incorporates
649 the limitation as if written in the body of this License.
650
651 9. The Free Software Foundation may publish revised and/or new versions
652 of the General Public License from time to time. Such new versions will
653 be similar in spirit to the present version, but may differ in detail to
654 address new problems or concerns.
655
656 Each version is given a distinguishing version number. If the Program
657 specifies a version number of this License which applies to it and "any
658 later version", you have the option of following the terms and conditions
659 either of that version or of any later version published by the Free
660 Software Foundation. If the Program does not specify a version number of
661 this License, you may choose any version ever published by the Free Software
662 Foundation.
663
664 10. If you wish to incorporate parts of the Program into other free
665 programs whose distribution conditions are different, write to the author
666 to ask for permission. For software which is copyrighted by the Free
667 Software Foundation, write to the Free Software Foundation; we sometimes
668 make exceptions for this. Our decision will be guided by the two goals
669 of preserving the free status of all derivatives of our free software and
670 of promoting the sharing and reuse of software generally.
671
672 NO WARRANTY
673
674 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
675 FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
676 OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
677 PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
678 OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
679 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
680 TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
681 PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
682 REPAIR OR CORRECTION.
683
684 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
685 WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
686 REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
687 INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
688 OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
689 TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
690 YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
691 PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
692 POSSIBILITY OF SUCH DAMAGES.
693
694 END OF TERMS AND CONDITIONS
695
696 How to Apply These Terms to Your New Programs
697
698 If you develop a new program, and you want it to be of the greatest
699 possible use to the public, the best way to achieve this is to make it
700 free software which everyone can redistribute and change under these terms.
701
702 To do so, attach the following notices to the program. It is safest
703 to attach them to the start of each source file to most effectively
704 convey the exclusion of warranty; and each file should have at least
705 the "copyright" line and a pointer to where the full notice is found.
706
707 &lt;one line to give the program's name and a brief idea of what it does.&gt;
708 Copyright (C) &lt;year&gt; &lt;name of author&gt;
709
710 This program is free software; you can redistribute it and/or modify
711 it under the terms of the GNU General Public License as published by
712 the Free Software Foundation; either version 2 of the License, or
713 (at your option) any later version.
714
715 This program is distributed in the hope that it will be useful,
716 but WITHOUT ANY WARRANTY; without even the implied warranty of
717 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
718 GNU General Public License for more details.
719
720 You should have received a copy of the GNU General Public License
721 along with this program; if not, write to the Free Software
722 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
723
724
725 Also add information on how to contact you by electronic and paper mail.
726
727 If the program is interactive, make it output a short notice like this
728 when it starts in an interactive mode:
729
730 Gnomovision version 69, Copyright (C) year name of author
731 Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
732 This is free software, and you are welcome to redistribute it
733 under certain conditions; type `show c' for details.
734
735 The hypothetical commands `show w' and `show c' should show the appropriate
736 parts of the General Public License. Of course, the commands you use may
737 be called something other than `show w' and `show c'; they could even be
738 mouse-clicks or menu items--whatever suits your program.
739
740 You should also get your employer (if you work as a programmer) or your
741 school, if any, to sign a "copyright disclaimer" for the program, if
742 necessary. Here is a sample; alter the names:
743
744 Yoyodyne, Inc., hereby disclaims all copyright interest in the program
745 `Gnomovision' (which makes passes at compilers) written by James Hacker.
746
747 &lt;signature of Ty Coon&gt;, 1 April 1989
748 Ty Coon, President of Vice
749
750 This General Public License does not permit incorporating your program into
751 proprietary programs. If your program is a subroutine library, you may
752 consider it more useful to permit linking proprietary applications with the
753 library. If this is what you want to do, use the GNU Library General
754 Public License instead of this License.</pre>
755 \endhtmlonly
756 */