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