3
* Christian Schulte <schulte@gecode.org>
4
* Guido Tack <tack@gecode.org>
7
* Christian Schulte, 2005
11
* $Date: 2005-11-29 13:35:41 +0100 (Tue, 29 Nov 2005) $ by $Author: schulte $
14
* This file is part of Gecode, the generic constraint
15
* development environment:
16
* http://www.gecode.org
18
* See the file "LICENSE" for information on usage and
19
* redistribution of this file, and for a
20
* DISCLAIMER OF ALL WARRANTIES.
25
* No code, just contains the group definitions of the
26
* Doxygen-generated documentation
31
* \defgroup Task Functionality by programming task
35
* \defgroup TaskInt Interfacing to Gecode
40
* \defgroup TaskIntScript Setting up scripts
42
* Scripts (or models) are programmed by inheriting from the class
43
* Gecode::Space. For many examples see \ref Example.
49
* \defgroup TaskIntInt Using finite domain integers
54
* \defgroup TaskIntIntVars Integer variables
59
* \defgroup TaskIntSearch Search engines
61
* Defines search engines. All search engines (but Gecode::LDS, where
62
* it is not needed) support recomputation. The behaviour of recomputation
63
* can be controlled by two parameters:
64
* - \a c_d as minimal recomputation distance: this guarantees that
65
* a path between two nodes in the search tree for which copies are
66
* stored has at least length \a c_d. That is, in order to recompute
67
* a node in the search tree, \a c_d recomputation steps are needed.
68
* The minimal recomputation distance yields a guarantee on saving
69
* memory compared to full copying: it stores \a c_d times less nodes
71
* - \a a_d as adaptive recomputation distance: when a node needs to be
72
* recomputed and the path is longer than \a a_d, an intermediate copy
73
* is created (approximately in the middle of the path) to speed up
74
* future recomputation. Note that small values of \a a_d can increase
75
* the memory consumption considerably.
77
* Full copying corresponds to a maximal recomputation distance \a c_d of 1.
79
* All recomputation performed is based on batch recomputation: batch
80
* recomputation performs propagation only once for an entire path
81
* used in recomputation.
83
* Requires \code #include "search.hh" \endcode
88
* \defgroup TaskIntSet Using finite integer sets
93
* \defgroup TaskIntSetVars Set variables
98
* \defgroup TaskMiniModel Direct modelling
103
* \defgroup TaskSearch Programming search engines
108
* \defgroup TaskActor Programming actors
113
* \defgroup TaskActorInt Programming integer actors
118
* \defgroup TaskActorSet Programming set actors
123
* \defgroup TaskVar Programming variables
128
* \defgroup TaskVarView Programming views for variables
133
* \defgroup Func Common functionality
137
* \defgroup FuncMem Memory management
142
* \defgroup FuncThrow Gecode exceptions
147
* \defgroup FuncSupport Support algorithms and datastructures
149
* These are some common datastructures used in the implementation of
150
* %Gecode. Maybe they can be also useful to others.
152
* In order to use them, one needs to include the appropriate header-file
153
* as described in the class and function documentation.
158
* \defgroup FuncIter Range and value iterators
160
* Both range and value iterators have a rather simple interface
161
* for controlling iteration (which deviates what you might be
162
* used to from other iterators).
164
* The application operator (if \c i is an iterator, it is invoked by \c i() )
165
* tests whether an iterator has not yet reached
166
* its end (in this case, \c true is returned). The prefix
167
* increment operator (if \c i is an iterator, this is invoked as \c ++i)
168
* moves the iterator to the next element (either next value or next range).
170
* Value iterators provide access to the value by the member function
171
* \c val(). Range iterators provide access to the smallest, largest, and
172
* width of the current range by \c min(), \c max(), and \c width()
175
* Requires \code #include "iter.hh" \endcode
180
* \defgroup FuncIterRanges Range iterators
182
* A range iterator provides incremental access to a sequence of increasing
185
* Requires \code #include "iter.hh" \endcode
190
* \defgroup FuncIterValues Value iterators
192
* A value iterator provides incremental access to a sequence of increasing
195
* Requires \code #include "iter.hh" \endcode
200
* \defgroup Other Other available functionality
205
* \defgroup FuncIntProp Integer propagators
207
* This module contains a description of all predefined integer
208
* propagators. They can be reused, for example, for rewriting
209
* newly defined integer propagators into already available
215
* \defgroup FuncIntSelView Integer view selection for branching
217
* Contains a description of view selection strategies on integer
218
* views that can be used together with the generic view/value
219
* branching class Gecode::ViewValBranching (argument \a ViewSel).
221
* All view selection classes require
222
* \code #include "int/branch.hh" \endcode
227
* \defgroup FuncIntSelVal Integer value selection for branching
229
* Contains a description of value selection strategies on integer
230
* views that can be used together with the generic view/value
231
* branching class Gecode::ViewValBranching (argument \a ValSel).
233
* All value selection classes require
234
* \code #include "int/branch.hh" \endcode
239
* \defgroup FuncSetProp Set propagators
241
* This module contains a description of all predefined finite set
242
* propagators. They can be reused, for example, for rewriting
243
* newly defined finite set propagators into already available
249
* \defgroup FuncSetSelView Set view selection for branching
251
* Contains a description of view selection strategies on set
252
* views that can be used together with the generic view/value
253
* branching class Gecode::ViewValBranching (argument \a ViewSel).
255
* All view selection classes require
256
* \code #include "set/branch.hh" \endcode
261
* \defgroup FuncSetSelVal Set value selection for branching
263
* Contains a description of value selection strategies on set
264
* views that can be used together with the generic view/value
265
* branching class Gecode::ViewValBranching (argument \a ValSel).
267
* All value selection classes require
268
* \code #include "set/branch.hh" \endcode
273
* \defgroup Example Example scripts (models)
275
* All scripts are compiled into simple standalone programs. These
276
* programs understand the following options given on the
278
* - <code>-mode (solution, time, stat)</code>
279
* - <code>solution</code>: print solutions.
280
* - <code>time</code>: measure time.
281
* - <code>stat</code>: print statistics.
282
* - <code>-naive</code>, <code>-smart</code>: if there is a naive and
283
* a smart model of the problem, select which to use
284
* - <code>-solutions</code>: give the maximum number of solutions after which
285
* the search stops. 0 means all solutions.
286
* - <code>-icl (def, val, bnd, dom)</code>: give the consistency level of
287
* integer constraints such as <code>distinct</code>.
288
* - <code>-c_d</code>, <code>-a_c</code>: copying and adaptive recomputation
289
* distance to be used by the search engine.
290
* - <code>-samples</code>, <code>-iterations</code>: how many samples and
291
* iterations per sample to compute in time mode.
292
* - <code>-help</code>: print usage information and default values for
295
* Many scripts can be given the problem size as an extra argument.
299
* Collect some definitions for which no reasonable place exists
304
* \namespace Gecode::Support
305
* \brief %Support algorithms and datastructures
309
* \mainpage Gecode Reference Documentation
311
* This document provides reference information about
312
* <A HREF="http://www.gecode.org">%Gecode</A>.
313
* The documentation is structured into three major groups:
314
* common programming tasks, common functionality, and other
315
* available functionality.
317
* This document corresponds to %Gecode version @VERSION@.
319
* \section SecByTask Programming tasks
321
* Documentation is available for the following tasks:
323
* - \ref TaskMiniModel
325
* - \ref TaskActor "Programming propagators and branchings"
328
* \section SecByFunc Common functionality
330
* The most important functionality is:
334
* The complete functionality can be found \ref Func "here".
336
* \section SecByOther Other available functionality
338
* The part \ref Other documents existing propagators, variable
339
* implementations, and so on which serves as documentation of examples.
341
* \section SecMore More content
343
* Additionally, the documentation also features the following parts:
344
* - \ref PageNotation
345
* - \ref PageGlossary
352
* \section SecIndex List and index content
354
* The following lists and indices are available
355
* - \ref PageCodeStat
356
* - <a class="el" href="modules.html">List of all modules</a>
357
* - <a class="el" href="annotated.html">List of all classes including brief documentation</a>
358
* - <a class="el" href="namespaces.html">List of all namespaces including brief documentation</a>
359
* - <a class="el" href="files.html">List of all files</a>
360
* - <a class="el" href="hierarchy.html">Class hierarchy</a>
361
* - <a class="el" href="classes.html">Alphabetical class index</a>
362
* - <a class="el" href="namespacemembers.html">Namespace members</a>
363
* - <a class="el" href="functions.html">Class members</a>
364
* - <a class="el" href="globals.html">File members</a>
368
* \page PageNotation Notational conventions
370
* Throughout this reference documentation we use some notational conventions
371
* designed to keep the documentation concise yet understandable. Please
372
* read the following carefully.
374
* \section NotationArray Array notation
376
* We allow ourselves to refer to the \f$i\f$-th element of an array \f$x\f$
377
* by \f$x_i\f$. The size of an array \f$x\f$ (either provided by a member
378
* function \c %size() or clear from context) is denoted \f$|x|\f$.
380
* \section NotationHome The home space
382
* Many functions and member functions take an argument \a home of
383
* type \c Space*. The home space serves as manager to many
384
* operations used by variables, views, propagators, spaces, and so
386
* services such as failure management, propagation control,
387
* memory management, and so on. To keep the documentation concise
388
* the home space is not documented for functions
389
* and member functions.
391
* \section NotationShare Sharing in update and copy
393
* In member functions that either copy or update an object during
394
* cloning, an argument \a share of type \c bool is available. This
395
* Boolean value controls whether during cloning the data structure at
396
* hand will be shared among the newly created cloned space and the original
397
* or whether two independent copies are created. Some functions (such
398
* as \c copy for spaces (Gecode::Space) or \c copy for propagators
399
* (Gecode::Propagator) also feature this argument. Here it is used
400
* to pass on the Boolean value to other datastructures used inside spaces
403
* The actual value the \a share argument has is defined by the search
404
* engine: when a search engine uses the \a clone member function of
405
* a space it decides whether sharing is to be used in the cloning of
406
* the space or not. If the search engine is single-threaded, it will
407
* use full sharing (\a share will be true). Only if the search engine
408
* uses concurrency or parallelism with more than a single thread,
409
* it will pass false as value. This means that by not sharing data structures
410
* among spaces which are to be used in different threads, all parts of
411
* %Gecode but the actual search engine do not need to provide concurrency
414
* As examples for data structures which are sensitive to sharing, consider
415
* Gecode::Support::SharedArray, Gecode::DomSpec, and Gecode::DFA.
419
\page PageGlossary Brief glossary
421
This page gives brief explanations about some of the most
422
frequently occurring terms (currently limited to important
423
entities manifest in the implementation) used in the %Gecode
424
reference documentation.
426
\section GlossaryActor Actor
428
An actor is either a branching (\ref GlossaryBranching) or a
429
propagator (\ref GlossaryPropagator). Actors provide the
430
functionality that is common for propagators and branchings such
431
as member functions for copying during cloning, memory
432
allocation, and so on. Actors are implemented by the class
433
Gecode::Actor. More on programming actors can be found in the
434
module \ref TaskActor.
436
\section GlossaryBranching Branching
438
A branching defines the shape of the search tree. Branchings are
439
also known as labelings or distributors, and a branching creates
440
a series of choice points. Branchings are implemented by the
441
class Gecode::Branching. A common abstraction for defining
442
branchings based on view and value selection is provided by the
443
class Gecode::ViewValBranching.
445
\section GlossaryBranchingDesc Branching description
447
A branching description speeds up recomputation by providing
448
batch recomputation. It is created by a branching (\ref
449
GlossaryBranching) and allows to replay the effect of that
450
branching without the need to first perform constraint
451
propagation. The base-class for branching descriptions is
452
Gecode::BranchingDesc. An example for a branching description
453
that works together with branchings based on view and value
454
selection is Gecode::PosValDesc.
456
\section GlossarySpace Computation space
458
A computation space (space for short) comprises all entities for
459
a constraint problem to be solved, including all actors (\ref
460
GlossaryActor) and variables (\ref GlossaryVariable). A space can
461
be seen as corresponding to a node in the search tree. It
462
organizes constraint propagation, the branching process,
463
exploration, and memory management. Spaces are implemented by the
464
class Gecode::Space. They provide functionality for \ref
465
TaskIntScript, \ref TaskSearch, and \ref FuncMemSpace.
467
\section GlossaryME Modification event
469
A modification event describes how a view (\ref GlossaryView) or
470
variable implementation (\ref GlossaryVarImp) is changed by an
471
update operation performed on the view or variable. Each variable
472
domain defines its own modification events (see \ref
473
TaskActorIntMEPC and \ref TaskActorSetMEPC). However modification
474
events that describe generic events such as failure, no
475
modification, or assignment to a single value are predefined (see
478
\section GlossaryPropCond Propagation condition
480
A propagation condition defines when a propagator requires to be
481
re-executed. Re-execution is controlled by the modification events
482
that occur on the variables the propagator depends on (see \ref
483
GlossaryPropagator). Propagation conditions and the relation
484
between propagation conditions and modification events depends on
485
the variable domain (see \ref TaskActorIntMEPC and \ref
486
TaskActorSetMEPC). However, the propagation conditions that
487
states re-execution when a variable becomes assigned is generic
488
(see \ref TaskVarMEPC).
490
\section GlossaryPropagator Propagator
492
A propagator implements a constraint (actually, a constraint can
493
be implemented by a collection of propagators). Execution by a
494
propagator is defined by its dependencies: the views (referring to
495
some variables) together with their propagation conditions. A
496
propagator is implemented by inheriting from the class
497
Gecode::Propagator. Common abstractions for propagators are also
498
available (see \ref TaskPropPat, \ref TaskPropRePat, and \ref
501
\section GlossaryPME Propagator modification event
503
A propagator maintains as propagator modification event for each
504
variable domain a modification event. These modification events
505
describe which modification events occurred on all views
506
(variables) the propagator depends on (see \ref
507
GlossaryPropagator). A propagator modification event is available
508
through a view or variable implementation (see for example \ref
509
TaskActorIntView or \ref TaskActorSetView).
511
\section GlossaryVariable Variable
513
A variable is used for modeling problems, be it for direct
514
modeling or for modeling through some interface. A variable
515
provides only those operations useful for modeling and excludes
516
in particular operations that can modify the variable domain
517
directly. A variable is implemented by a variable implementation
520
\section GlossaryVarImp Variable implementation
522
A variable implementation is implemented by inheriting from
523
Gecode::Variable. It implements the variable domain and provides
524
operations to access and modify the domain. Examples of variable
525
implementations are Gecode::Int::IntVarImp and
526
Gecode::Set::SetVarImp.
528
\section GlossaryView View
530
A view offers essentially the same interface as a variable
531
implementation and allows both domain access and
532
modification. Typically, several views exist for the same
533
variable implementation to obtain several constraints from the
534
same propagator. Examples of views are \ref TaskActorIntView and
535
\ref TaskActorSetView.
540
* \page PageUsage Using Gecode
542
* \section SecUsageInclude Including header files
544
* Deciding which header files must be included when using %Gecode is
545
* quite straightforward. There are the following header files for inclusion:
546
* - kernel.hh must always be included (the header files below
547
* also always include kernel.hh).
548
* - search.hh must be included, if search engines are used
549
* (see for example \ref TaskIntSearch).
550
* - int.hh must be included, if any integer functionality is used
551
* (see for example \ref TaskIntInt and \ref TaskActorInt).
552
* - set.hh must be included, if any finite set functionality is used
553
* (see for example \ref TaskIntSet and \ref TaskActorSet).
554
* - minimodel.hh must be included, if direct modelling support
555
* is used (see for example \ref TaskMiniModel).
557
* Other functionality is available through a set of header files. For example
558
* to access the implementation of particular propagators, a particular header
559
* file must be included. The header file to be included is always mentioned
560
* in the documentation of the class or function.
562
* \section SecUsageLink Linking libraries
564
* Setting the exact name for a library on a particular platform aside,
565
* inclusion of header files basically coincides with against which
566
* library must be linked. That is:
567
* - If kernel.hh is included, linking against the kernel library is required.
568
* - If search.hh is included, linking against the search library is required.
569
* - If int.hh is included, linking against the integer library is required.
570
* - If set.hh is included, linking against the set library is required.
571
* - If minimodel.hh is included, linking against the minimodel library
574
* The functionality in \ref FuncSupport and \ref FuncIter require no
575
* library for linking. Reusing integer or set propagators of course
576
* require the integer or set library.
578
* If there is a difference between library and DLL (such as on Windows)
579
* linking must be done against the appropriate library and the
580
* corresponding DLL must be available for execution (such as in the
581
* PATH environment variable).
583
* \section SecUsageLibraries Library names
585
* \subsection SULA Windows with Visual Studio
587
* - Kernel library and DLL: GecodeKernel.lib and GecodeKernel.dll
588
* - Search library and DLL: GecodeSearch.lib and GecodeSearch.dll
589
* - Integer library and DLL: GecodeInt.lib and GecodeInt.dll
590
* - Set library and DLL: GecodeSet.lib and GecodeSet.dll
591
* - Minimodel library and DLL: GecodeMiniModel.lib and GecodeMiniModel.dll
593
* \subsection SULB Unix (Linux, MacOS X)
595
* Depending on whether %Gecode was compiled as a static or as a dynamic
596
* library, different filename suffixes are used on different Unix platforms.
597
* All library names follow the following scheme:
599
* - Kernel library: libgecodekernel.<EXT>
600
* - Search library: libgecodesearch.<EXT>
601
* - Integer library: libgecodeint.<EXT>
602
* - Set library: libgecodeset.<EXT>
603
* - Minimodel library: libgecodeminimodel.<EXT>
605
* where <EXT> depends on the library type and platform:
607
* - libgecode[...].a for static libaries on all Unix flavors
608
* - libgecode[...].so for shared libraries on Linux
609
* - libgecode[...].dylib for shared libraries on MacOS X
611
* You can use for example
613
* <code>gcc -L$GPREFIX/lib -lgecodekernel</code>
615
* to link the kernel library, if the libraries are found in
616
* <code>$GPREFIX/lib</code>.
620
* \page PageInst Installation
622
* After a successful compilation, you can install the %Gecode library
623
* and all header files necessary for compiling against it by invoking
625
* <code>make install</code>
627
* in the build directory.
632
* \page PageComp Compiling Gecode
634
* The %Gecode library, including examples and documentation, can be built
635
* on all recent versions of Windows, Linux, and MacOS X. Porting to other
636
* Unix flavors should be easy, if any change is necessary at all.
638
* \section Prerequisites
640
* In order to compile %Gecode, you need a standard Unix toolchain including
641
* the following programs:
643
* - a bash-compatible shell
649
* These are available in all standard installations of Linux. On MacOS X,
650
* you need to install the Apple developer tools. For
651
* Windows, we require the
652
* <a href="http://www.cygwin.com/">Cygwin environment</a> that provides
653
* all necessary tools.
655
* We currently support
656
* - the Microsoft Visual C++ compilers for Windows. The Microsoft
657
* Visual C++ toolkit is available free of charge from
658
* <a href="http://msdn.microsoft.com/visualc/vctoolkit2003/">the MSDN
660
* - the GNU Compiler Collection (gcc) for Windows and Unix flavors such as
661
* Linux and MacOS X. The GNU gcc is open source software and available
662
* from <a href="http://gcc.gnu.org/">the GCC home page</a>. It is included
663
* in all Linux distributions and the Apple MacOS X developer tools.
664
* %Gecode requires at least version 3.4 of gcc. We recommend using version
665
* 4.0 or higher. Very unfortunately, the parser used in versions of gcc
666
* before 3.4 is broken and hence cannot compile %Gecode.
667
* - The Intel C++ compiler for Windows and Linux. Please note that this
668
* compiler was only tested using the evaluation license available from
669
* Intel. If you encounter problems or have suggestions for improvements,
670
* please let us know.
672
* \section CompConf Configuring the sources
674
* %Gecode uses GNU autoconf to acquire information about the system it is
675
* compiled on. Typically, you need to run the <code>configure</code>
676
* script in the toplevel directory.
678
* To setup %Gecode for your particular system, you may need to add one or
679
* more of the following options to <code>configure</code>:
681
* - When using the Microsoft Visual C++ compiler, add
682
* <code>CC=cl CXX=cl</code> to your
683
* invocation of <code>configure</code>
684
* - When using the Intel C++ compiler under Windows, add
685
* <code>CC=icl CXX=icl</code> to your
686
* invokation of configure.
687
* - When using the Intel C++ compiler under Linux, add
688
* <code>CC=icc CXX=icpc</code> to your
689
* invokation of configure.
690
* - To install %Gecode somewhere else than the default
691
* <code>/usr/local</code>, use the <code>--prefix=[...]</code> switch
692
* - You can enable and disable the individual modules %Gecode consists of
693
* using <code>--enable-[MODULE]</code> and <code>--disable-[MODULE]</code>
695
* You can get a list of all supported configuration options by calling
696
* <code>configure</code> with the <code>--help</code> switch.
698
* \subsection CompConfExamples Example configurations
700
* To compile %Gecode on a Windows machine using the Microsoft compiler, use
702
* <code>./configure CC=cl CXX=cl</code>
704
* To compile only the %Gecode library without examples on a Unix machine, use
706
* <code>./configure --disable-examples</code>
708
* To compile on a Unix machine using a different than the default
709
* <code>gcc</code> compiler, and install under <code>/opt/gecode</code>, use
711
* <code>./configure --prefix=/opt/gecode CC=gcc-4.0 CXX=g++-4.0</code>
713
* To compile a debug build on Unix, turning on all assertions and not
714
* inlining anything, use
716
* <code>./configure --enable-debug</code>
718
* To compile on Cygwin, but linking against the Windows libraries instead
719
* of the Cygwin libraries, use
721
* <code>./configure CC="gcc -mno-cygwin" CXX="g++ -mno-cygwin"</code>
723
* \subsection CompConfUsr Passing options for compilation
725
* Additional options for compilation can be passed to the compiler
726
* from the make commandline via the variable <code>CXXUSR</code>. For
727
* example, to pass to gcc the additional option "-mtune=i686" the following
730
* <code>make CXXUSR="-mtune=i686"</code>
732
* \subsection CompConfSepDir Compiling in a separate directory
734
* The %Gecode library can be built in a separate directory. This is useful
735
* if you do not want to clutter the source tree with all the object files
738
* Configuring %Gecode in a separate directory is easy. Assume that the
739
* sources can be found in directory <code>$GSOURCEDIR</code>, change to
740
* the directory where you want to compile %Gecode and call
742
* <code>$GSOURCEDIR/configure [options]</code>
744
* This will generate all necessary files in the new build directory.
746
* \section CompComp Compiling the sources
748
* After successful configuration, simply invoking
752
* in the toplevel %Gecode directory will compile the whole library.
754
* \section CompExamples Running the examples
756
* After compiling the examples, they can be run directly from the command
757
* line. For instance, try the %Golomb Rulers Problem:
759
* <code>./examples/golomb</code>
761
* or (when running Windows):
763
* <code>./examples/golomb.exe</code>
765
* For more information on example scripts see \ref Example.
767
* \section DepMngmt Dependency management
769
* The dependencies between source files are not handled automatically. If you
770
* are using a Gecode version from our subversion repository or if you
771
* modified any of the source files, you will have to call
772
* <code>make depend</code> before compilation in order to determine the
773
* source dependencies.
775
* Dependency management is only needed for recompiling Gecode after changing
776
* something. In an unmodified version (or after a <code>make clean</code>)
777
* all files are compiled anyway.
779
* \section UnsupPlatfrms Compiling for unsupported platforms
781
* If you want to try compiling Gecode on a platform that we do not support
782
* officially, you can override the platform tests during
783
* <code>configure</code>. There are two options to specify the type of
786
* - <code>--with-host-os=[linux|darwin|windows]</code>
787
* - <code>--with-compiler-vendor=[gnu|microsoft|intel]</code>
789
* Using the first option, you can state that your platform should behave like
790
* Linux, Darwin (which is actually BSD), or Windows. This affects mainly
791
* the filenames and the tools used to generate shared and static libraries.
793
* The second option says
794
* that your compiler can be used very much like the gnu compiler
795
* <code>gcc</code>, the Microsoft compiler <code>cl</code>, or the Intel
796
* compiler <code>icl</code>. Please let us know of any successfull attempt at
797
* compiling Gecode on other platforms.
801
* \page PageChange Changelog
803
* A changelog will only be available after the first release.
added
removed
doxygen.hh.in
