Significant improvement of documentation
authorJoris Mooij <jorism@marvin.jorismooij.nl>
Tue, 30 Sep 2008 20:29:50 +0000 (22:29 +0200)
committerJoris Mooij <jorism@marvin.jorismooij.nl>
Tue, 30 Sep 2008 20:29:50 +0000 (22:29 +0200)
51 files changed:
ChangeLog
Makefile
Makefile.shared [new file with mode: 0644]
Makefile.win
README
STATUS [deleted file]
TODO
doxygen.conf
include/dai/alldai.h
include/dai/bipgraph.h
include/dai/bp.h
include/dai/clustergraph.h
include/dai/daialg.h
include/dai/diffs.h [deleted file]
include/dai/enum.h
include/dai/exactinf.h
include/dai/exceptions.h
include/dai/factor.h
include/dai/factorgraph.h
include/dai/hak.h
include/dai/index.h
include/dai/jtree.h
include/dai/lc.h
include/dai/mf.h
include/dai/mr.h
include/dai/prob.h
include/dai/properties.h
include/dai/regiongraph.h
include/dai/smallset.h [new file with mode: 0644]
include/dai/treeep.h
include/dai/util.h
include/dai/var.h
include/dai/varset.h
include/dai/weightedgraph.h
src/alldai.cpp
src/bp.cpp
src/daialg.cpp
src/factorgraph.cpp
src/hak.cpp
src/jtree.cpp
src/lc.cpp
src/mf.cpp
src/mr.cpp
src/properties.cpp
src/regiongraph.cpp
src/treeep.cpp
src/util.cpp
src/varset.cpp [deleted file]
src/weightedgraph.cpp
utils/createfg.cpp
utils/fginfo.cpp

index 66326a0..467c507 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,14 +1,20 @@
-libDAI-0.2.2 (2008-??-??)
+libDAI-0.2.2 (2008-09-30)
 -------------------------
 
-* Now compiles also under Visual C++ and cygwin.
-* Added Exceptions framework.
+New features:
 * Approximate inference methods now report the number of iterations needed.
 * Added damping to various algorithms to improve convergence properties.
-* Replaced ENUM2,ENUM3,ENUM4,ENUM5,ENUM6 by single DAI_ENUM macro.
-* Removed utils/remove_short_loops and matlab/remove_short_loops.
 * Added more features to utils/createfg for creating factor graphs.
-* Replaced sub_nb class in mr.h by boost::dynamic_bitset.
+* Added ExactInf class for brute force exact inference.
+* [Giuseppe Pasino] Added "logdomain" property to BP, a boolean that controls 
+  whether calculations are done in the log-domain or in the linear domain;
+  doing calculations in the log-domain may help if the numerical range
+  of a double is too small.
+* [Claudio Lima] Added Max-Product functionality to BP.
+* Improved documentation.
+
+Improved architecture:
+* Added Exceptions framework.
 * Pervasive change of BipartiteGraph implementation (based on an idea by
   Giuseppe Passino). BipartiteGraph no longer stores the node properties 
   (former _V1 and _V2), nor does it store a dense adjacency matrix anymore, 
@@ -16,21 +22,44 @@ libDAI-0.2.2 (2008-??-??)
   neighboring nodes. This yields a significant memory/speed improvement for 
   large factor graphs, and is more elegant as well. Iterating over neighbors is
   made easy by using boost::foreach.
-* Improved index.h (merged from SVN head):
+* Added conditional compilation of inference methods.
+* VarSet is now implemented using a std::vector<Var> instead of a
+  std::set<Var>, which yields a significant speed improvement. Furthermore,
+  the implementation has been generalized, resulting in the small_set<T> class
+  which can be used to represent sets of small cardinality; VarSet is the
+  specialization with T = Var.
+* Improved ClusterGraph implementation, yielding significant speedups
+  for the JunctionTree algorithm on large factorgraphs.
+
+Code cleanup:
+* Moved everything into namespace "dai".
+* Renamed DEBUG to DAI_DEBUG to avoid conflicts.
+* Replaced ENUM2,ENUM3,ENUM4,ENUM5,ENUM6 by single DAI_ENUM macro.
+* Removed utils/remove_short_loops and matlab/remove_short_loops.
+* Replaced sub_nb class in mr.h by boost::dynamic_bitset.
+* Improved index.h:
   - Renamed Index -> IndexFor
   - Added some .reserve()'s to IndexFor methods which yields a 
     25% speedup of testregression
   - Replaced multind by Permute
   - Added MultiFor
   - Added State
-* Improved factor.h (merged from SVN head): mainly new functionality.
-* Moved everything into namespace "dai".
-* Added ExactInf class for brute force exact inference.
-* Renamed DEBUG to DAI_DEBUG to avoid conflicts.
-* Added conditional compilation of inference methods.
+* New funcstionality of factor.h.
+* Moved Properties and MaxDiff frameworks from InfAlg to each individual
+  inference algorithm, because the Properties framework was not as 
+  convenient as I hoped, and not every inference algorithm needs a maxdiff
+  variable. Also, replaced some FactorGraph functionality in InfAlg by a
+  function that returns the FactorGraph. The result is cleaner (less 
+  entangled) code.
+* Removed x2x.
+* Replaced Complex with real numbers (negative potentials are just too rare
+  to warrant the additional "complexity" :)).
+
+Miscellaneous improvements:
+* Now compiles also with MS Visual C++ and with GCC under cygwin.
 * Contributions by Peter Gober:
   - Renamed variable _N in mr.* for compatibility with g++ under cygwin.
-* Contributions by Giuseppe Passino:
+* Misc contributions by Giuseppe Passino:
   - removed "using namespace std;" from header files - bad practice;
   - moved header files in include/dai and sources in src;
   - changed #ifndefs to GNU style;
@@ -41,83 +70,60 @@ libDAI-0.2.2 (2008-??-??)
     o added methods takeExp, takeLog, takeLog0 for transformation in-place;
     o explicit constructor (prevents implicit conversion from size_t to TProb);
     o added operator+,+=,-,-=, with argument T (for calculations in log-scale);
-  - Added "logdomain" property to BP, a boolean that controls whether 
-    calculations are done in the log-domain or in the linear domain;
-    doing calculations in the log-domain may help if the numerical range
-    of a double is too small.
-* Contributions by Christian Wojek:
+* Misc contributions by Christian Wojek:
   - New FactorGraph constructor that constructs from given ranges of factors
     and variables;
   - Optimization of FactorGraph constructors using tr1::unordered_map.
-* Contributions by Claudio Lima:
-  - Added Max-Product functinoality to BP.
 * FactorGraph constructors no longer check for short loops (huge speed
   increase for large factor graphs), nor for negative entries. Also, the 
   normtype is now Prob::NORMPROB by default.
-* VarSet is now implemented using a std::vector<Var> instead of a
-  std::set<Var>, which yields a significant speed improvement. Furthermore,
-  the implementation has been generalized, resulting in the small_set<T> class
-  which can be used to represent sets of small cardinality; VarSet is the
-  specialization with T = Var.
 * Improved MaxSpanningTreePrims algorithm (uses boost::graph).
-* Small optimization in Diffs.
-* Replaced Complex with real numbers (negative potentials is just not
-  used enough to warrant the additional "complexity" :)).
-* Moved Properties and MaxDiff frameworks from InfAlg to each individual
-  inference algorithm, because the Properties framework was not as 
-  convenient as I hoped, and not every inference algorithm needs a maxdiff
-  variable. Also, replaced some FactorGraph functionality in InfAlg by a
-  function that returns the FactorGraph. The result is cleaner (less 
-  entangled) code.
-* Improved ClusterGraph implementation, yielding significant speedups
-  for the JunctionTree algorithm on large factorgraphs.
-* Improved documetation.
-* Removed x2x.
-* Interface changes:
-  - VarSet::
-      VarSet::stateSpace() -> nrStates(const VarSet &)
-      VarSet( const std::set<Var> ) -> VarSet( begin, end, sizeHint=0 )
-      VarSet( const std::vector<Var> ) -> VarSet( begin, end, sizeHint=0 )
-      removed bool operator||
-      operator&&(const VarSet&) -> intersects(const VarSet&)
-      operator&&(const Var&) -> contains(const Var&)
-  - FactorGraph::
-      delta(const Var &) -> delta(size_t)
-      Delta(const Var &) -> Delta(size_t)
-      makeCavity(const Var &) -> makeCavity(size_t)
-      vars() -> vars
-      factors() -> factors
-      removed MakeFactorCavity(size_t)
-      removed ExactMarginal(const VarSet &)
-      removed ExactlogZ()
-      removed updatedFactor(size_t)
-      removed _normtype and NormType()
-      removed hasShortLoops(...) and removeShortLoops(...)
-      WriteToDotFile(const char *filename) -> printDot( std::ostream& os )
-      undoProb(size_t) -> restoreFactor(size_t)
-      saveProb(size_t) -> backupFactor(size_t)
-      undoProbs(const VarSet &) -> restoreFactors(const VarSet &)
-      saveProbs(const VarSet &) -> backupFactors(const VarSet &)
-      ReadFromFile(const char*) returns void (throws on error)
-      WriteToFile(const char*) returns void (throws on error)
-      removed hasNegatives()
-  - RegionGraph::
-      nr_ORs() -> nrORs()
-      nr_IRs() -> nrIRs()
-      ORs() -> ORs
-      IRs() -> IRs
-  - *::Regenerate() -> *::construct()
-  - Renamed Index -> IndexFor
-  - Diffs:
-      max() -> maxDiff()
-      max_size() -> maxSize()
-  - Prob::max() -> Prob::maxVal()
-  - Factor::
-      max() -> maxVal()
-      part_sum() -> partSum()
-  - toc() in util.h now returns seconds as a double
-  - VarSet::operator&&
-  - Properties -> PropertySet
+
+Interface changes:
+* VarSet::
+  - VarSet::stateSpace() -> nrStates(const VarSet &)
+  - VarSet( const std::set<Var> ) -> VarSet( begin, end, sizeHint=0 )
+  - VarSet( const std::vector<Var> ) -> VarSet( begin, end, sizeHint=0 )
+  - removed bool operator||
+  - operator&&(const VarSet&) -> intersects(const VarSet&)
+  - operator&&(const Var&) -> contains(const Var&)
+* FactorGraph::
+  - delta(const Var &) -> delta(size_t)
+  - Delta(const Var &) -> Delta(size_t)
+  - makeCavity(const Var &) -> makeCavity(size_t)
+  - vars() -> vars
+  - factors() -> factors
+  - removed MakeFactorCavity(size_t)
+  - removed ExactMarginal(const VarSet &)
+  - removed ExactlogZ()
+  - removed updatedFactor(size_t)
+  - removed _normtype and NormType()
+  - removed hasShortLoops(...) and removeShortLoops(...)
+  - WriteToDotFile(const char *filename) -> printDot( std::ostream& os )
+  - undoProb(size_t) -> restoreFactor(size_t)
+  - saveProb(size_t) -> backupFactor(size_t)
+  - undoProbs(const VarSet &) -> restoreFactors(const VarSet &)
+  - saveProbs(const VarSet &) -> backupFactors(const VarSet &)
+  - ReadFromFile(const char*) returns void (throws on error)
+  - WriteToFile(const char*) returns void (throws on error)
+  - removed hasNegatives()
+* RegionGraph::
+  - nr_ORs() -> nrORs()
+  - nr_IRs() -> nrIRs()
+  - ORs() -> ORs
+  - IRs() -> IRs
+* *::Regenerate() -> *::construct()
+* Renamed Index -> IndexFor
+* Diffs:
+  - max() -> maxDiff()
+  - max_size() -> maxSize()
+* Prob::max() -> Prob::maxVal()
+* Factor::
+  - max() -> maxVal()
+  - part_sum() -> partSum()
+* toc() in util.h now returns seconds as a double
+* VarSet::operator&&
+* Properties -> PropertySet
 
 
 libDAI-0.2.1 (2008-05-26)
index 672d80c..930431f 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -41,10 +41,11 @@ INC=include/dai
 SRC=src
 LIB=lib
 
-# Extensions (library, object, executable extensions)
+# Extensions (library, object, executable, MEX file extensions)
 LE=.a
 OE=.o
 EE=
+ME=.mexglx
 
 # Libraries
 LIBS=-ldai
@@ -69,31 +70,31 @@ endif
 
 OBJECTS:=exactinf$(OE)
 ifdef WITH_BP
-CCFLAGS:=$(CCFLAGS) -DWITH_BP
+CCFLAGS:=$(CCFLAGS) -DDAI_WITH_BP
 OBJECTS:=$(OBJECTS) bp$(OE)
 endif
 ifdef WITH_MF
-CCFLAGS:=$(CCFLAGS) -DWITH_MF
+CCFLAGS:=$(CCFLAGS) -DDAI_WITH_MF
 OBJECTS:=$(OBJECTS) mf$(OE)
 endif
 ifdef WITH_HAK
-CCFLAGS:=$(CCFLAGS) -DWITH_HAK
+CCFLAGS:=$(CCFLAGS) -DDAI_WITH_HAK
 OBJECTS:=$(OBJECTS) hak$(OE)
 endif
 ifdef WITH_LC
-CCFLAGS:=$(CCFLAGS) -DWITH_LC
+CCFLAGS:=$(CCFLAGS) -DDAI_WITH_LC
 OBJECTS:=$(OBJECTS) lc$(OE)
 endif
 ifdef WITH_TREEEP
-CCFLAGS:=$(CCFLAGS) -DWITH_TREEEP
+CCFLAGS:=$(CCFLAGS) -DDAI_WITH_TREEEP
 OBJECTS:=$(OBJECTS) treeep$(OE)
 endif
 ifdef WITH_JTREE
-CCFLAGS:=$(CCFLAGS) -DWITH_JTREE
+CCFLAGS:=$(CCFLAGS) -DDAI_WITH_JTREE
 OBJECTS:=$(OBJECTS) jtree$(OE)
 endif
 ifdef WITH_MR
-CCFLAGS:=$(CCFLAGS) -DWITH_MR
+CCFLAGS:=$(CCFLAGS) -DDAI_WITH_MR
 OBJECTS:=$(OBJECTS) mr$(OE)
 endif
 
@@ -101,7 +102,6 @@ ifdef WITH_MATLAB
 # Replace the following by the directory where Matlab has been installed
 MATLABDIR=/opt/matlab/bin
 # Replace the following with the extension of compiled MEX files on this platform, e.g. .mexglx for x86
-ME=.mexglx
 MEX=$(MATLABDIR)/mex
 MEXFLAGS=-I.
 ifdef DEBUG
@@ -114,7 +114,7 @@ MEXFLAGS:=$(MEXFLAGS) -DSMALLMEM
 endif
 endif
 
-HEADERS=$(INC)/bipgraph.h $(INC)/diffs.h $(INC)/index.h $(INC)/var.h $(INC)/factor.h $(INC)/varset.h $(INC)/prob.h $(INC)/daialg.h $(INC)/properties.h $(INC)/alldai.h $(INC)/enum.h $(INC)/exceptions.h
+HEADERS=$(INC)/bipgraph.h $(INC)/index.h $(INC)/var.h $(INC)/factor.h $(INC)/varset.h $(INC)/smallset.h $(INC)/prob.h $(INC)/daialg.h $(INC)/properties.h $(INC)/alldai.h $(INC)/enum.h $(INC)/exceptions.h
 
 TARGETS=tests utils $(LIB)/libdai$(LE) example$(EE) testregression doc
 ifdef WITH_MATLAB
@@ -123,11 +123,11 @@ endif
 all : $(TARGETS)
        echo -e "\a"
 
-matlabs : matlab/dai.$(ME) matlab/dai_readfg.$(ME) matlab/dai_writefg.$(ME) matlab/dai_potstrength.$(ME)
+matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)
 
-$(LIB)/libdai$(LE) : bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) varset$(OE) $(OBJECTS)
+$(LIB)/libdai$(LE) : bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)
        -mkdir -p lib
-       ar rcus $(LIB)/libdai$(LE) bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) varset$(OE) $(OBJECTS)
+       ar rcus $(LIB)/libdai$(LE) bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)
 
 tests : tests/testdai$(EE)
 
@@ -144,7 +144,7 @@ doc : $(INC)/*.h $(SRC)/*.cpp doxygen.conf
 .PHONY : clean
 clean :
        -rm *$(OE) 
-       -rm matlab/*.$(ME) matlab/*$(OE) 
+       -rm matlab/*$(ME) matlab/*$(OE) 
        -rm example$(EE) tests/testdai$(EE) utils/fg2dot$(EE) utils/createfg$(EE) utils/fginfo$(EE)
        -rm -R doc
        -rm -R lib
diff --git a/Makefile.shared b/Makefile.shared
new file mode 100644 (file)
index 0000000..a131922
--- /dev/null
@@ -0,0 +1,120 @@
+#   Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
+#   Radboud University Nijmegen, The Netherlands /
+#   Max Planck Institute for Biological Cybernetics, Germany
+#   
+#   This file is part of libDAI.
+#
+#   libDAI is free software; you can redistribute it and/or modify
+#   it under the terms of the GNU General Public License as published by
+#   the Free Software Foundation; either version 2 of the License, or
+#   (at your option) any later version.
+#
+#   libDAI is distributed in the hope that it will be useful,
+#   but WITHOUT ANY WARRANTY; without even the implied warranty of
+#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+#   GNU General Public License for more details.
+#
+#   You should have received a copy of the GNU General Public License
+#   along with libDAI; if not, write to the Free Software
+#   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+
+bipgraph$(OE) : $(SRC)/bipgraph.cpp $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/bipgraph.cpp
+
+daialg$(OE) : $(SRC)/daialg.cpp $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/daialg.cpp
+
+exactinf$(OE) : $(SRC)/exactinf.cpp $(INC)/exactinf.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/exactinf.cpp
+
+bp$(OE) : $(SRC)/bp.cpp $(INC)/bp.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/bp.cpp
+
+lc$(OE) : $(SRC)/lc.cpp $(INC)/lc.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/lc.cpp
+
+mf$(OE) : $(SRC)/mf.cpp $(INC)/mf.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/mf.cpp
+
+factorgraph$(OE) : $(SRC)/factorgraph.cpp $(INC)/factorgraph.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/factorgraph.cpp
+
+util$(OE) : $(SRC)/util.cpp $(INC)/util.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/util.cpp
+
+regiongraph$(OE) : $(SRC)/regiongraph.cpp $(INC)/regiongraph.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/regiongraph.cpp
+
+hak$(OE) : $(SRC)/hak.cpp $(INC)/hak.h $(HEADERS) $(INC)/regiongraph.h
+       $(CC) $(CCFLAGS) -c $(SRC)/hak.cpp
+
+clustergraph$(OE) : $(SRC)/clustergraph.cpp $(INC)/clustergraph.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/clustergraph.cpp
+
+jtree$(OE) : $(SRC)/jtree.cpp $(INC)/jtree.h $(HEADERS) $(INC)/weightedgraph.h $(INC)/clustergraph.h $(INC)/regiongraph.h
+       $(CC) $(CCFLAGS) -c $(SRC)/jtree.cpp
+
+treeep$(OE) : $(SRC)/treeep.cpp $(INC)/treeep.h $(HEADERS) $(INC)/weightedgraph.h $(INC)/clustergraph.h $(INC)/regiongraph.h $(INC)/jtree.h
+       $(CC) $(CCFLAGS) -c $(SRC)/treeep.cpp
+
+weightedgraph$(OE) : $(SRC)/weightedgraph.cpp $(INC)/weightedgraph.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/weightedgraph.cpp
+
+mr$(OE) : $(SRC)/mr.cpp $(INC)/mr.h $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/mr.cpp
+
+properties$(OE) : $(SRC)/properties.cpp $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/properties.cpp
+
+exceptions$(OE) : $(SRC)/exceptions.cpp $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/exceptions.cpp
+
+alldai$(OE) : $(SRC)/alldai.cpp $(HEADERS)
+       $(CC) $(CCFLAGS) -c $(SRC)/alldai.cpp
+
+
+# EXAMPLE
+##########
+
+example$(EE) : example.cpp $(HEADERS) $(LIB)/libdai$(LE)
+       $(CC) $(CCFLAGS) $(CCO) example$(EE) example.cpp $(LIBS)
+
+
+# TESTS
+########
+
+tests/testdai$(EE) : tests/testdai.cpp $(HEADERS) $(LIB)/libdai$(LE)
+       $(CC) $(CCFLAGS) $(CCO) tests/testdai$(EE) tests/testdai.cpp $(LIBS) $(BOOSTLIBS)
+
+
+# MATLAB INTERFACE
+###################
+
+matlab/dai.$(ME) : matlab/dai.cpp $(HEADERS) matlab/matlab$(OE) $(LIB)/libdai$(LE)
+       $(MEX) $(MEXFLAGS) -o matlab/dai matlab/dai.cpp matlab/matlab$(OE) $(LIB)/libdai$(LE)
+
+matlab/dai_readfg.$(ME) : matlab/dai_readfg.cpp $(HEADERS) factorgraph$(OE) matlab/matlab$(OE) exceptions$(OE)
+       $(MEX) $(MEXFLAGS) -o matlab/dai_readfg matlab/dai_readfg.cpp factorgraph$(OE) matlab/matlab$(OE) exceptions$(OE)
+
+matlab/dai_writefg.$(ME) : matlab/dai_writefg.cpp $(HEADERS) factorgraph$(OE) matlab/matlab$(OE) exceptions$(OE)
+       $(MEX) $(MEXFLAGS) -o matlab/dai_writefg matlab/dai_writefg.cpp factorgraph$(OE) matlab/matlab$(OE) exceptions$(OE)
+
+matlab/dai_potstrength.$(ME) : matlab/dai_potstrength.cpp $(HEADERS) matlab/matlab$(OE) exceptions$(OE)
+       $(MEX) $(MEXFLAGS) -o matlab/dai_potstrength matlab/dai_potstrength.cpp matlab/matlab$(OE) exceptions$(OE)
+
+matlab/matlab$(OE) : matlab/matlab.cpp matlab/matlab.h $(HEADERS)
+       $(MEX) $(MEXFLAGS) -outdir matlab -c matlab/matlab.cpp
+
+
+# UTILS
+########
+
+utils/createfg$(EE) : utils/createfg.cpp $(HEADERS) $(LIB)/libdai$(LE)
+       $(CC) $(CCFLAGS) $(CCO) utils/createfg$(EE) utils/createfg.cpp $(LIBS) $(BOOSTLIBS)
+
+utils/fg2dot$(EE) : utils/fg2dot.cpp $(HEADERS) $(LIB)/libdai$(LE)
+       $(CC) $(CCFLAGS) $(CCO) utils/fg2dot$(EE) utils/fg2dot.cpp $(LIBS)
+
+utils/fginfo$(EE) : utils/fginfo.cpp $(HEADERS) $(LIB)/libdai$(LE)
+       $(CC) $(CCFLAGS) $(CCO) utils/fginfo$(EE) utils/fginfo.cpp $(LIBS)
index b0a1754..e275be4 100755 (executable)
@@ -41,10 +41,11 @@ INC=include/dai
 SRC=src\r
 LIB=lib\r
 \r
-# Extensions (library, object, executable extensions)\r
+# Extensions (library, object, executable, MEX file extensions)\r
 LE=.lib\r
 OE=.obj\r
 EE=.exe\r
+ME=.mexglx\r
 \r
 # Libraries (for some reason, we have to add the VC library path, although it is in the environment)\r
 LIBS=/link $(LIB)/libdai$(LE) /LIBPATH:"C:\Program Files\Microsoft Visual Studio 9.0\VC\ATLMFC\LIB" /LIBPATH:"C:\Program Files\Microsoft Visual Studio 9.0\VC\LIB" /LIBPATH:"C:\Program Files\Microsoft SDKs\Windows\v6.0A\lib"\r
@@ -69,31 +70,31 @@ CCFLAGS=$(CCFLAGS) /DWINDOWS
 \r
 OBJECTS=exactinf$(OE)\r
 !IFDEF WITH_BP\r
-CCFLAGS=$(CCFLAGS) /DWITH_BP\r
+CCFLAGS=$(CCFLAGS) /DDAI_WITH_BP\r
 OBJECTS=$(OBJECTS) bp$(OE)\r
 !ENDIF\r
 !IFDEF WITH_MF\r
-CCFLAGS=$(CCFLAGS) /DWITH_MF\r
+CCFLAGS=$(CCFLAGS) /DDAI_WITH_MF\r
 OBJECTS=$(OBJECTS) mf$(OE)\r
 !ENDIF\r
 !IFDEF WITH_HAK\r
-CCFLAGS=$(CCFLAGS) /DWITH_HAK\r
+CCFLAGS=$(CCFLAGS) /DDAI_WITH_HAK\r
 OBJECTS=$(OBJECTS) hak$(OE)\r
 !ENDIF\r
 !IFDEF WITH_LC\r
-CCFLAGS=$(CCFLAGS) /DWITH_LC\r
+CCFLAGS=$(CCFLAGS) /DDAI_WITH_LC\r
 OBJECTS=$(OBJECTS) lc$(OE)\r
 !ENDIF\r
 !IFDEF WITH_TREEEP\r
-CCFLAGS=$(CCFLAGS) /DWITH_TREEEP\r
+CCFLAGS=$(CCFLAGS) /DDAI_WITH_TREEEP\r
 OBJECTS=$(OBJECTS) treeep$(OE)\r
 !ENDIF\r
 !IFDEF WITH_JTREE\r
-CCFLAGS=$(CCFLAGS) /DWITH_JTREE\r
+CCFLAGS=$(CCFLAGS) /DDAI_WITH_JTREE\r
 OBJECTS=$(OBJECTS) jtree$(OE)\r
 !ENDIF\r
 !IFDEF WITH_MR\r
-CCFLAGS=$(CCFLAGS) /DWITH_MR\r
+CCFLAGS=$(CCFLAGS) /DDAI_WITH_MR\r
 OBJECTS=$(OBJECTS) mr$(OE)\r
 !ENDIF\r
 \r
@@ -101,7 +102,6 @@ OBJECTS=$(OBJECTS) mr$(OE)
 # Replace the following by the directory where Matlab has been installed\r
 MATLABDIR=/opt/matlab/bin\r
 # Replace the following with the extension of compiled MEX files on this platform, e.g. .mexglx for x86\r
-ME=.mexglx\r
 MEX=$(MATLABDIR)/mex\r
 MEXFLAGS=-I.\r
 !IFDEF DEBUG\r
@@ -114,7 +114,7 @@ MEXFLAGS=$(MEXFLAGS) /DSMALLMEM
 !ENDIF\r
 !ENDIF\r
 \r
-HEADERS=$(INC)/bipgraph.h $(INC)/diffs.h $(INC)/index.h $(INC)/var.h $(INC)/factor.h $(INC)/varset.h $(INC)/prob.h $(INC)/daialg.h $(INC)/properties.h $(INC)/alldai.h $(INC)/enum.h $(INC)/exceptions.h\r
+HEADERS=$(INC)/bipgraph.h $(INC)/index.h $(INC)/var.h $(INC)/factor.h $(INC)/varset.h $(INC)/smallset.h $(INC)/prob.h $(INC)/daialg.h $(INC)/properties.h $(INC)/alldai.h $(INC)/enum.h $(INC)/exceptions.h\r
 \r
 TARGETS=tests utils $(LIB)/libdai$(LE) example$(EE)\r
 # testregression disabled, it uses diff\r
@@ -124,10 +124,10 @@ TARGETS = $(TARGETS) matlabs
 !ENDIF\r
 all : $(TARGETS)\r
 \r
-matlabs : matlab/dai.$(ME) matlab/dai_readfg.$(ME) matlab/dai_writefg.$(ME) matlab/dai_potstrength.$(ME)\r
+matlabs : matlab/dai$(ME) matlab/dai_readfg$(ME) matlab/dai_writefg$(ME) matlab/dai_potstrength$(ME)\r
 \r
-$(LIB)/libdai$(LE) : bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) varset$(OE) $(OBJECTS)\r
-       lib /out:$(LIB)/libdai$(LE) bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) varset$(OE) $(OBJECTS)\r
+$(LIB)/libdai$(LE) : bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)\r
+       lib /out:$(LIB)/libdai$(LE) bipgraph$(OE) daialg$(OE) alldai$(OE) clustergraph$(OE) factorgraph$(OE) properties$(OE) regiongraph$(OE) util$(OE) weightedgraph$(OE) exceptions$(OE) $(OBJECTS)\r
 \r
 tests : tests/testdai$(EE)\r
 \r
@@ -141,6 +141,6 @@ doc : $(INC)/*.h $(SRC)/*.cpp doxygen.conf
        doxygen doxygen.conf\r
 \r
 clean :\r
-       del *$(OE) *.ilk *.pdb *$(EE) matlab\*.$(ME) matlab\*$(OE) tests\testdai$(EE) tests\*.pdb tests\*.ilk utils\*$(EE) utils\*.pdb utils\*.ilk $(LIB)\libdai$(LE)\r
+       del *$(OE) *.ilk *.pdb *$(EE) matlab\*$(ME) matlab\*$(OE) tests\testdai$(EE) tests\*.pdb tests\*.ilk utils\*$(EE) utils\*.pdb utils\*.ilk $(LIB)\libdai$(LE)\r
 \r
 !INCLUDE Makefile.shared\r
diff --git a/README b/README
index 954f794..7b642da 100644 (file)
--- a/README
+++ b/README
@@ -1,13 +1,21 @@
 libDAI - A free/open source C++ library for Discrete Approximate Inference methods
 ==================================================================================
 
-v 0.2.2 - May 26, 2008
+v 0.2.2 - September 30, 2008
 
 
 Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
 Radboud University Nijmegen, The Netherlands /
 Max Planck Institute for Biological Cybernetics, Germany
-    
+
+with contributions from:
+
+Martijn Leisink
+Giuseppe Passino
+Christian Wojek
+Claudio Lima
+Bastian Wemmenhove
+
 
 ----------------------------------------------------------------------------------
 This file is part of libDAI.
@@ -35,142 +43,107 @@ that made substantive use of this program, it is your moral obligation as a
 scientist to (a) mention the fashion in which this software was used, including
 the version number, with a citation to the literature, to allow replication;
 (b) mention this software in the Acknowledgements section.  The appropriate
-citation is: J. M. Mooij (2008) libDAI: A free/open source C++ library for
-Discrete Approximate Inference methods, http://mloss.org/software/view/77/.
+citation is: 
+
+J. M. Mooij (2008) "libDAI 0.2.2: A free/open source C++ library for Discrete 
+Approximate Inference methods", http://mloss.org/software/view/77/.
+
 Moreover, as a personal note, I would appreciate it if you would email me with
 citations of papers referencing this work so I can mention them to my funding
 agent and tenure committee.
 
-What is libDAI?
----------------
-libDAI is a free/open source C++ library (licensed under GPL, see the file
-COPYING for more details) that provides implementations of various
-(deterministic) approximate inference methods for discrete graphical models.
-libDAI supports arbitrary factor graphs with discrete variables (this includes
-discrete Markov Random Fields and Bayesian Networks).
 
+About libDAI
+------------
+libDAI is a free/open source C++ library (licensed under GPL) that provides
+implementations of various (approximate) inference methods for discrete
+graphical models. libDAI supports arbitrary factor graphs with discrete
+variables; this includes discrete Markov Random Fields and Bayesian Networks.
+
+The library is targeted at researchers; to be able to use the library, a good
+understanding of graphical models is needed.
+
+
+Limitations
+-----------
 libDAI is not intended to be a complete package for approximate inference.
 Instead, it should be considered as an "inference engine", providing various
 inference methods. In particular, it contains no GUI, currently only supports
 its own file format for input and output (although support for standard file
-formats may be added), and provides no visualization.
-
-Because libDAI is implemented in C++, it is very fast compared with e.g. MatLab
-implementations. libDAI does provide a MatLab interface for easy integration
-with MatLab. Currently, libDAI supports the following deterministic approximate
-inference methods:
-
-    * Mean Field
-    * (Loopy) Belief Propagation
-    * Tree Expectation Propagation
-    * Generalized Belief Propagation
-    * Double-loop GBP
-    * Loop Corrected Approximate Inference
+formats may be added later), and provides very limited visualization
+functionalities.
 
-Exact inference by JunctionTree is also provided.
 
-Many of these algorithms are not yet available in similar open source software,
-to the best of the author's knowledge (open source packages supporting both
-directed and undirected graphical models are Murphy's BNT, Intel's PNL and gR).
+Features
+--------
+Currently, libDAI supports the following (approximate) inference methods:
 
-The library is targeted at researchers; to be able to use the library, a good
-understanding of graphical models is needed. However, the code will hopefully
-find its way into real-world applications as well. 
+    * Exact inference by brute force enumeration;
+    * Exact inference by junction-tree methods;
+    * Mean Field;
+    * Loopy Belief Propagation [KFL01];
+    * Tree Expectation Propagation [MiQ04];
+    * Generalized Belief Propagation [YFW05];
+    * Double-loop GBP [HAK03];
+    * Various variants of Loop Corrected Belief Propagation [MoK07, MoR05].
 
 
-Rationale
----------
-In my opinion, the lack of open source reference implementations hampers
-progress in research on approximate inference. Methods differ widely in terms
-of quality and performance characteristics, which also depend in different ways
-on various properties of the graphical models. Finding the best approximate
-inference method for a particular application therefore often requires
-empirical comparisons. However, implementing and debugging these methods takes
-a lot of time which could otherwise be spent on research. I hope that this code
-will aid researchers to be able to easily compare various (existing as well as
-new) approximate inference methods, in this way accelerating research and
-stimulating real-world applications of approximate inference.  
+Why C++?
+--------
+Because libDAI is implemented in C++, it is very fast compared with
+implementations in MatLab (a factor 1000 faster is not uncommon). libDAI does
+provide a MatLab interface for easy integration with MatLab.
 
 
 Releases
 --------
-Releases can be obtained from http://www.mbfys.ru.nl/~jorism/libDAI.
+Releases can be obtained from http://mloss.org/software/view/77/
 License: GNU Public License v2 (or higher).
 
 libDAI-0.2      December 1, 2006
 libDAI-0.2.1    May 26, 2008
+libDAI-0.2.2   September 30, 2008
 
 
 Acknowledgments
 ---------------
-The development reported here is part of the Interactive Collaborative
-Information Systems (ICIS) project, supported by the Dutch Ministry of Economic
-Affairs, grant BSIK03024. I would like to thank Martijn Leisink for providing
-the basis on which libDAI has been built.
+This work is part of the Interactive Collaborative Information Systems (ICIS) 
+project, supported by the Dutch Ministry of Economic Affairs, grant BSIK03024. 
+I would like to thank Martijn Leisink for providing the basis on which libDAI has been built.
 
 
-Known issues
-------------
-Due to a bug in GCC 3.3.x and earlier (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20358) 
-it doesn't compile with these versions (it does compile with GCC version 3.4 and higher).
-Workaround: replace the two NAN's in factor.h causing the error messages by -1.
+Documentation
+-------------
+Some doxygen documentation is available. Install doxygen and use "make doc" to build the
+documentation. If the documentation is not clear enough, feel free to send me an email 
+(or even better, to improve the documentation!).
 
+A description of the factor graph (.fg) file format can be found in the file FILEFORMAT.
 
-Documentation
+
+Compatibility
 -------------
-Almost nonexistant. But I'm working on it. In the meantime, I'll provide limited support
-by email. The following gives an overview of different methods and their properties
-(can be slightly obsolete):
-
-BP
-    updates     UpdateType SEQFIX,SEQRND,SEQMAX,PARALL
-    tol         double
-    maxiter     size_t
-    verbose     size_t
-MF
-    tol         double
-    maxiter     size_t
-    verbose     size_t
-HAK
-    clusters    MIN,DELTA,LOOP
-    loopdepth
-    doubleloop  bool
-    tol         double
-    maxiter     size_t
-    verbose     size_t
-JTREE
-    updates     UpdateType  HUGIN,SHSH
-    verbose     size_t
-MR
-    updates     UpdateType  FULL,LINEAR
-    inits       InitType    RESPPROP,CLAMPING,EXACT
-    verbose     size_t
-TREEEP
-    type        TypeType    ORG,ALT
-    tol         double
-    maxiter     size_t
-    verbose     size_t
-LC
-    cavity      CavityType  FULL,PAIR,PAIR2,UNIFORM
-    updates     UpdateType  SEQFIX,SEQRND(,NONE)
-    reinit      bool
-    cavainame   string
-    cavaiopts   Properties
-    tol         double
-    maxiter     size_t
-    verbose     size_t
-
-
-
-Quick start
------------
+The code has been developed under Debian GNU/Linux with the GCC compiler suite.
+libDAI compiles successfully with g++ versions 4.1, 4.2 and 4.3.
+
+libDAI has also been successfully compiled with MS Visual Studio 2008 under Windows
+(but not all build targets are supported yet).
+
+
+Quick start (linux/cygwin)
+--------------------------
 You need:
-- a recent version of gcc (version 3.4 at least)
-- the Boost C++ libraries (under Debian/Ubuntu you can install them using
-  "apt-get install libboost-dev libboost-program-options-dev")
+- a recent version of gcc (at least version 3.4)
 - GNU make
+- doxygen
+- graphviz
+- recent boost C++ libraries (at least version 1.34)
 
-To build the source, edit the Makefile and then run
+On Debian/Ubuntu, you can easily install all these packages with a single command:
+"apt-get install g++ make doxygen libboost-dev libboost-graph-dev libboost-program-options-dev"
+(root permissions needed).
+
+To build the source, edit the Makefile and adapt it to your local setup. Then, run
     
     make
 
@@ -180,6 +153,23 @@ If the build was successful, you can test the example program:
 
 or the more elaborate test program:
 
-    tests/test --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX
+    tests/testdai --aliases tests/aliases.conf --filename tests/alarm.fg --methods JTREE_HUGIN BP_SEQMAX
 
-A description of the factor graph (.fg) file format can be found in the file FILEFORMAT.
+
+Quick start (windows)
+---------------------
+You need:
+- A recent version of MicroSoft Visual Studio (2008 works)
+- recent boost C++ libraries (version 1.34 or higher)
+
+To build the source, edit the Makefile and adapt it to your local setup. Then, run (from the command line)
+    
+    nmake -f Makefile.win
+
+If the build was successful, you can test the example program:
+
+    example tests\alarm.fg
+
+or the more elaborate test program:
+
+    tests\testdai --aliases tests\aliases.conf --filename tests\alarm.fg --methods JTREE_HUGIN BP_SEQMAX
diff --git a/STATUS b/STATUS
deleted file mode 100644 (file)
index 010714f..0000000
--- a/STATUS
+++ /dev/null
@@ -1,10 +0,0 @@
-TODO FOR RELEASE:
-- Test {Visual C++, cygwin, gcc various version} compatibility; state tested compilers/build environments in README
-- Figure out which libraries are required and document in README
-  boost headers, boost::program_options library, boost::graph library,
-  boost::math library (under Windows)
-- Complete doxygen documentation
-
-DOCUMENTATION READY:
-- bipgraph.h, bipgraph.cpp
-- var.h
diff --git a/TODO b/TODO
index bc83a2f..d389239 100644 (file)
--- a/TODO
+++ b/TODO
-- Add comments in example.cpp, add documentation.
-- Write documentation.
-- Improve error handling.
-- http://www.boost.org/development/requirements.html#Design_and_Programming
+TODO:
 
-OPTIMIZATION:
-- BipartiteGraph::isConnected should be optimized using boost::graph
-- Can the FactorGraph constructors be optimized further?
-- Cache second-order neighborhoods (delta's) in BipGraph?
-- Replace VarSets by small_set<size_t> if appropriate, in order to minimize the use of findVar().
-- A DAIAlg<T> should not inherit from a FactorGraph/RegionGraph, but should store a reference to it
-
-IDEAS:
-- Use "gcc -MM" to generate dependencies for targets.
-
-- Use a PropertySet as output of a DAIAlg, instead of functions like maxDiff and Iterations().
-
-- A FactorGraph and a RegionGraph are often equipped with
-additional properties for nodes and edges. The code to initialize those
-is often quite similar; maybe this can be abstracted to classes
-like ExtFactorGraph and ExtRegionGraph (Ext stands for Extended), e.g.
-template <typename NodeProperties, typename EdgeProperties>
-class ExtFactorGraph : public FactorGraph {
-       public:
-               std::vector<NodeProperties>               nodeProps;
-               std::vector<std::vector<EdgeProperties> > edgeProps;
-       // blabla
-}
-A disadvantage of this approach may be worse cachability.
-A problem is if there are nog properties for nodes (type 1), nodes (type 2)
-or edges. Maybe this can be solved using specializations, or using variadac
-template arguments or something similar?
-Idea: you could define a "class Empty {}", and add some code that checks for
-the typeid, comparing it with Empty, and doing something special in that case 
-(e.g., not allocating memory).
-The main disadvantage of this approach seems to be that it leads to even more
-entanglement.
-
-- Instead of polymorphism by inheritance,
-use polymorphism by template parameterization. For example, the real reason
-you introduced the complicated inheritance scheme was for functions like
-    Factor calcMarginal( const InferenceAlgorithm & obj, const VarSet & ns, bool reInit );
-Now instead, you could use a template function:
-template<typename InferenceAlgorithm>
-    Factor calcMarginal( const InferenceAlgorithm &obj, const VarSet &ns, bool reInit );
-This would assume that InferenceAlgorithm supports certain methods, like
-clone(), grm(), ......
-Ideally, you would use concepts to define different classes of inference
-algorithms with different capabilities, for example the ability to calculate logZ,
-the ability to calculate marginals, the ability to calculate bounds, the ability
-to calculate MAP states, etcetera. Then, use traits classes in order to be able to
-query the capabilities of the model. For example, you would be able to query whether
-the inference algorithm supports calculation of logZ.
-Unfortunately, this is compile-time polymorphism, whereas tests/test needs runtime polymorphism.
-
-- If you ever do a rewrite, make sure that the graphical properties are
-not entangled with the probabilistic properties. E.g., a factor graph
-really should be represented as a bipartite graph, with a separate array
-of variable labels and dimensions, and a seperate array of (pointers to)
-factor tables. In this way, each factor could be implemented differently,
-e.g., we could have some sparse factors, some noisy-OR factors, some dense
-factors, some arbitrary precision factors, etc. Or we could make more use
-of templates to have a more generic factor graph. Maybe in the end, 
-HasA relations are better than IsA relations...
-Also, the current setup is stupid: I wrote a new function that works
-on FactorGraphs, and I had to write boiler plate code for it in graphicalmodel.h
-and in regiongraph.h (which is stupid).
-
-- Use Boost::uBLAS framework to deal with matrices, especially, with
-2D sparse matrices. See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
-and tests/errorbounds/errorbounds3
-
-- Introduce naming scheme:
-all Vars and VarSets should be named v_..., e.g. v_i instead of i
-all Factors should be named f_..., e.g. f_I instead of I
-all indices should be named _..., e.g. _k instead of k
-all iterators should be named i_, e.g. i_i is an iterator to i
-all const_iterators should be named ci_, e.g. ci_i is an iterator to i
-
-- Improve weightedgraph or use Boost::Graph
-
-- Iterations and maxDiff are only interesting for iterative inference
-algorithms. Yet, tests/test wants to know these values in a generic
-way. Maybe we have to think of some way (e.g. using a Properties object)
-to return these values from run(). Then we can simply look whether a
-InferenceAlgorithm supports these fields. What other results could
-we return? Time. MaxDiff during initialization for LC methods.
-Or maybe we could use some traits mechanism which we can ask whether the
-object has _iterations and _maxdiff variables.
+- Improve documentation.
 
-- Think about whether the cavity initialization belongs to init() or to run().
+- Adapt http://www.boost.org/development/requirements.html#Design_and_Programming
 
-- Fix LCLin.
+- Use "gcc -MM" to generate dependencies for targets.
+  Maybe even better: switch to cmake (see http://lwn.net/Articles/188693/)
+  cross-platform build system.
 
-- setFactor and setFactors should only change Probs, not Factors.
 
-- Simplify Properties framework: each Property should be a std::string.
-Each DAIAlg should have its own _properties struct and handle conversion.
+OPTIMIZATION:
 
-- Forwardport the Bart patch
+- BipartiteGraph::isConnected should be optimized using boost::graph
 
-- Another design question that needs to be answered: should a BP object own a
-  FactorGraph, or only store a reference to a FactorGraph (which can optimize
-  memory), or should it be a FactorGraph with additional variables and functions?
-  Probably, the first or second option would be the best. Since FactorGraphs are
-  assumed to be rather static, it would make sense to store *references* to
-  FactorGraphs inside AIAlgs. Or maybe some smart_ptr? It would make sense to 
-  prevent unnecessary copying of FactorGraphs. Also, general marginalization 
-  functions now copy a complete object. Instead, it would make more sense that
-  they construct a new object without copying the FactorGraph. Or they can be made
-  simply methods of the general InfAlg class.
+- Replace VarSets by smallSet<size_t> where appropriate, in order to minimize the use of findVar().
 
+- A DAIAlg<T> should not inherit from a FactorGraph/RegionGraph, but should
+  store a reference to it.  This prevents needless copying of (possibly large)
+  data structures. Disadvantage: the caller must not change the data structure
+  between calls. (Maybe a smart_ptr would help here?)
+  Also, general marginalization functions now copy a complete object. Instead, it
+  would make more sense that they construct a new object without copying the
+  FactorGraph. Or they can simply be made methods of the general InfAlg class.
 
 
-DIFFICULT
+IDEAS WORTH EXPLORING:
 
-- What to do in case of NANs?
+- Use a PropertySet as output of a DAIAlg, instead of functions like maxDiff and Iterations().
 
-- Bug: TreeEP::logZ() seems to be wrong (?).
+- Cache second-order neighborhoods (delta's) in BipGraph?
 
-- Kees' trick for preventing NANs in GBP updates:  if quantity smaller than epsilon, replace by epsilon.
+- If you ever do a rewrite, make sure that the graphical properties are not
+  entangled with the probabilistic properties. E.g., a factor graph really
+  should be represented as a bipartite graph, with a separate array of variable
+  labels and dimensions, and a seperate array of (pointers to) factor tables. In
+  this way, each factor could be implemented differently, e.g., we could have
+  some sparse factors, some noisy-OR factors, some dense factors, some arbitrary
+  precision factors, etc. Or we could make more use of templates to have a more
+  generic factor graph. 
 
+- Use Boost::uBLAS framework to deal with matrices, especially, with
+  2D sparse matrices. 
+  See http://www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
+  and tests/errorbounds/errorbounds3
 
-OPTIONAL
+- Introduce naming scheme:
+  all Vars and VarSets should be named v_..., e.g. v_i instead of i
+  all Factors should be named f_..., e.g. f_I instead of I
+  all indices should be named _..., e.g. _k instead of k
+  all iterators should be named i_, e.g. i_i is an iterator to i
+  all const_iterators should be named ci_, e.g. ci_i is an iterator to i
 
 - Define a better fileformat for .fg files (maybe using XML)?
 
-- Find a good multi-platform build system (GNU autotool? Boost JAM?)
-
-- Another design question that needs to be answered: should a BP object own a
-  FactorGraph, or only store a reference to a FactorGraph (which can optimize
-  memory), or should it be a FactorGraph with additional variables and functions?
-  Probably, the first or second option would be the best. Since FactorGraphs are
-  assumed to be rather static, it would make sense to store *references* to
-  FactorGraphs inside AIAlgs. Or maybe some smart_ptr? It would make sense to 
-  prevent unnecessary copying of FactorGraphs. Also, general marginalization 
-  functions now copy a complete object. Instead, it would make more sense that
-  they construct a new object without copying the FactorGraph. Or they can be made
-  simply methods of the general InfAlg class.
-
-- Forwardport the Bart/Max patch.
-
 - Alternative implementation of undo factor changes: the only things that have to be
-undone are setting a factor to all ones and setting a factor to a Kronecker delta. This
-could also be implemented in the factor itself, which could maintain its state 
-(one/delta/full) and act accordingly.
+  undone are setting a factor to all ones and setting a factor to a Kronecker delta. This
+  could also be implemented in the factor itself, which could maintain its state 
+  (one/delta/full) and act accordingly.
 
-- Think about the _fac2ind variable: a better implementation of this feature is
-probably possible.
+- Think about the RegionGraph::fac2OR variable: a better implementation of this feature is
+  probably possible.
 
 - Optimize GBP with precalculated indices.
 
 - Optimize all indices as follows: keep a cache of all indices that have been
-computed (use a hash). Then, instead of computing on the fly, use the precomputed
-ones.
+  computed (use a hash). Then, instead of computing on the fly, use the precomputed ones.
 
 - Variable elimination should be implemented generically using a function
   object that tells you which variable to delete.
@@ -162,3 +74,44 @@ ones.
 - Add support for sparse potentials.
 
 - Optimize BP_SEQMAX (it should use a better data structure than a vector for the residuals).
+
+
+BAD IDEAS:
+
+- A FactorGraph and a RegionGraph are often equipped with
+  additional properties for nodes and edges. The code to initialize those
+  is often quite similar; maybe this can be abstracted to classes
+  like ExtFactorGraph and ExtRegionGraph (Ext stands for Extended), e.g.
+  template <typename NodeProperties, typename EdgeProperties>
+  class ExtFactorGraph : public FactorGraph {
+       public:
+               std::vector<NodeProperties>               nodeProps;
+               std::vector<std::vector<EdgeProperties> > edgeProps;
+       // blabla
+  }
+  A disadvantage of this approach may be worse cachability.
+  A problem is if there are nog properties for nodes (type 1), nodes (type 2)
+  or edges. Maybe this can be solved using specializations, or using variadac
+  template arguments or something similar?
+  Idea: you could define a "class Empty {}", and add some code that checks for
+  the typeid, comparing it with Empty, and doing something special in that case 
+  (e.g., not allocating memory).
+  The main disadvantage of this approach seems to be that it leads to even more
+  entanglement.
+
+- Instead of polymorphism by inheritance, use polymorphism by template
+  parameterization. For example, the real reason you introduced the complicated
+  inheritance scheme was for functions like
+      Factor calcMarginal( const InferenceAlgorithm & obj, const VarSet & ns, bool reInit );
+  Now instead, you could use a template function:
+      template<typename InferenceAlgorithm>
+      Factor calcMarginal( const InferenceAlgorithm &obj, const VarSet &ns, bool reInit );
+  This would assume that InferenceAlgorithm supports certain methods, like
+  clone(), grm(), ......  Ideally, you would use concepts to define different
+  classes of inference algorithms with different capabilities, for example the
+  ability to calculate logZ, the ability to calculate marginals, the ability to
+  calculate bounds, the ability to calculate MAP states, etcetera. Then, use
+  traits classes in order to be able to query the capabilities of the model. For
+  example, you would be able to query whether the inference algorithm supports
+  calculation of logZ.  Unfortunately, this is compile-time polymorphism, whereas
+  tests/test needs runtime polymorphism.
index febd3e1..4c9bf8e 100644 (file)
@@ -99,7 +99,7 @@ ALWAYS_DETAILED_SEC    = NO
 # members were ordinary class members. Constructors, destructors and assignment 
 # operators of the base classes will not be shown.
 
-INLINE_INHERITED_MEMB  = NO
+INLINE_INHERITED_MEMB  = YES
 
 # If the FULL_PATH_NAMES tag is set to YES then Doxygen will prepend the full 
 # path before files name in the file list and in the header files. If set 
@@ -268,7 +268,7 @@ TYPEDEF_HIDES_STRUCT   = NO
 # Private class members and static file members will be hidden unless 
 # the EXTRACT_PRIVATE and EXTRACT_STATIC tags are set to YES
 
-EXTRACT_ALL            = YES
+EXTRACT_ALL            = NO
 
 # If the EXTRACT_PRIVATE tag is set to YES all private members of a class 
 # will be included in the documentation.
@@ -278,7 +278,7 @@ EXTRACT_PRIVATE        = NO
 # If the EXTRACT_STATIC tag is set to YES all static members of a file 
 # will be included in the documentation.
 
-EXTRACT_STATIC         = NO
+EXTRACT_STATIC         = YES
 
 # If the EXTRACT_LOCAL_CLASSES tag is set to YES classes (and structs) 
 # defined locally in source files will be included in the documentation. 
@@ -1116,7 +1116,7 @@ INCLUDE_FILE_PATTERNS  =
 # undefined via #undef or recursively expanded use the := operator 
 # instead of the = operator.
 
-PREDEFINED             = 
+PREDEFINED             = DAI_WITH_BP DAI_WITH_MF DAI_WITH_HAK DAI_WITH_LC DAI_WITH_TREEEP DAI_WITH_JTREE DAI_WITH_MR
 
 # If the MACRO_EXPANSION and EXPAND_ONLY_PREDEF tags are set to YES then 
 # this tag can be used to specify a list of macro names that should be expanded. 
index 7772657..3bf9b2d 100644 (file)
 */
 
 
+/// \file
+/// \brief Main libDAI header file
+
+
 #ifndef __defined_libdai_alldai_h
 #define __defined_libdai_alldai_h
 
 #include <dai/daialg.h>
 #include <dai/properties.h>
 #include <dai/exactinf.h>
-#ifdef WITH_BP
+#ifdef DAI_WITH_BP
     #include <dai/bp.h>
 #endif
-#ifdef WITH_MF
+#ifdef DAI_WITH_MF
     #include <dai/mf.h>
 #endif
-#ifdef WITH_HAK
+#ifdef DAI_WITH_HAK
     #include <dai/hak.h>
 #endif
-#ifdef WITH_LC
+#ifdef DAI_WITH_LC
     #include <dai/lc.h>
 #endif
-#ifdef WITH_TREEEP
+#ifdef DAI_WITH_TREEEP
     #include <dai/treeep.h>
 #endif
-#ifdef WITH_JTREE
+#ifdef DAI_WITH_JTREE
     #include <dai/jtree.h>
 #endif
-#ifdef WITH_MR
+#ifdef DAI_WITH_MR
     #include <dai/mr.h>
 #endif
 
 
+/// Namespace for libDAI
 namespace dai {
 
 
-/// newInfAlg constructs a new approximate inference algorithm named name for the
-/// FactorGraph fg with optionts opts and returns a pointer to the new object.
-/// The caller needs to delete it (maybe some sort of smart_ptr might be useful here).
+/// Constructs a new approximate inference algorithm.
+/** \param name The name of the approximate inference algorithm (should be one of the names in DAINames).
+ *  \param fg The FactorGraph that the algorithm should be applied to.
+ *  \param opts A PropertySet specifying the options for the algorithm.
+ *  \return Returns a pointer to the new InfAlg object; it is the responsibility of the caller to delete it later.
+ */
 InfAlg *newInfAlg( const std::string &name, const FactorGraph &fg, const PropertySet &opts );
 
 
-/// DAINames contains the names of all approximate inference algorithms
-
+/// Contains the names of all approximate inference algorithms compiled into libDAI.
 static const char* DAINames[] = {
     ExactInf::Name,
-#ifdef WITH_BP
+#ifdef DAI_WITH_BP
     BP::Name, 
 #endif
-#ifdef WITH_MF
+#ifdef DAI_WITH_MF
     MF::Name,
 #endif
-#ifdef WITH_HAK
+#ifdef DAI_WITH_HAK
     HAK::Name,
 #endif
-#ifdef WITH_LC
+#ifdef DAI_WITH_LC
     LC::Name,
 #endif
-#ifdef WITH_TREEEP
+#ifdef DAI_WITH_TREEEP
     TreeEP::Name,
 #endif
-#ifdef WITH_JTREE
+#ifdef DAI_WITH_JTREE
     JTree::Name,
 #endif
-#ifdef WITH_MR
+#ifdef DAI_WITH_MR
     MR::Name,
 #endif
     ""
@@ -92,4 +99,95 @@ static const char* DAINames[] = {
 } // end of namespace dai
 
 
+/** \mainpage libDAI reference manual
+ *  \author Joris Mooij
+ *  \version 0.2.2
+ *  \date 30 September 2008
+ *
+ *  \section about About libDAI
+ *  libDAI is a free/open source C++ library (licensed under GPL) that provides
+ *  implementations of various (approximate) inference methods for discrete 
+ *  graphical models. libDAI supports arbitrary factor graphs with discrete 
+ *  variables; this includes discrete Markov Random Fields and Bayesian 
+ *  Networks.
+ *
+ *  The library is targeted at researchers; to be able to use the library, a 
+ *  good understanding of graphical models is needed. 
+ *
+ *  \section limitations Limitations
+ *  libDAI is not intended to be a complete package for approximate inference. 
+ *  Instead, it should be considered as an "inference engine", providing 
+ *  various inference methods. In particular, it contains no GUI, currently 
+ *  only supports its own file format for input and output (although support 
+ *  for standard file formats may be added later), and provides very limited
+ *  visualization functionalities.
+ *
+ *  \section features Features
+ *  Currently, libDAI supports the following (approximate) inference methods:
+ *  - Exact inference by brute force enumeration;
+ *  - Exact inference by junction-tree methods;
+ *  - Mean Field;
+ *  - Loopy Belief Propagation [\ref KFL01];
+ *  - Tree Expectation Propagation [\ref MiQ04];
+ *  - Generalized Belief Propagation [\ref YFW05];
+ *  - Double-loop GBP [\ref HAK03];
+ *  - Various variants of Loop Corrected Belief Propagation
+ *    [\ref MoK07, \ref MoR05].
+ *
+ *  \section language Why C++?
+ *  Because libDAI is implemented in C++, it is very fast compared with
+ *  implementations in MatLab (a factor 1000 faster is not uncommon).
+ *  libDAI does provide a MatLab interface for easy integration with MatLab. 
+ *
+ */
+
+
+/** \page Bibliography
+ *  \section Bibliograpy
+ *  \anchor KFL01 \ref KFL01
+ *  F. R. Kschischang and B. J. Frey and H.-A. Loeliger (2001):
+ *  "Factor Graphs and the Sum-Product Algorithm",
+ *  <em>IEEE Transactions on Information Theory</em> 47(2):498-519.
+ *  http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=910572
+ *
+ *  \anchor MiQ04 \ref MiQ04
+ *  T. Minka and Y. Qi (2004):
+ *  "Tree-structured Approximations by Expectation Propagation",
+ *  <em>Advances in Neural Information Processing Systems</em> (NIPS) 16.
+ *  http://books.nips.cc/papers/files/nips16/NIPS2003_AA25.pdf
+ *
+ *  \anchor MoR05 \ref MoR05
+ *  A. Montanari and T. Rizzo (2005):
+ *  "How to Compute Loop Corrections to the Bethe Approximation",
+ *  <em>Journal of Statistical Mechanics: Theory and Experiment</em>
+ *  2005(10)-P10011.
+ *  http://stacks.iop.org/1742-5468/2005/P10011
+ *
+ *  \anchor YFW05 \ref YFW05
+ *  J. S. Yedidia and W. T. Freeman and Y. Weiss (2005):
+ *  "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms",
+ *  <em>IEEE Transactions on Information Theory</em>
+ *  51(7):2282-2312.
+ *  http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1459044
+ *
+ *  \anchor HAK03 \ref HAK03
+ *  T. Heskes and C. A. Albers and H. J. Kappen (2003):
+ *  "Approximate Inference and Constrained Optimization",
+ *  <em>Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)</em> pp. 313-320.
+ *  http://www.snn.ru.nl/reports/Heskes.uai2003.ps.gz
+ *
+ *  \anchor MoK07 \ref MoK07
+ *  J. M. Mooij and H. J. Kappen (2007):
+ *  "Loop Corrections for Approximate Inference on Factor Graphs",
+ *  <em>Journal of Machine Learning Research</em> 8:1113-1143.
+ *  http://www.jmlr.org/papers/volume8/mooij07a/mooij07a.pdf
+ *
+ *  \anchor MoK07b \ref MoK07b
+ *  J. M. Mooij and H. J. Kappen (2007):
+ *  "Sufficient Conditions for Convergence of the Sum-Product Algorithm",
+ *  <em>IEEE Transactions on Information Theory</em> 53(12):4422-4437.
+ *  http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4385778
+ */
+
+
 #endif
index e11ca0e..341ec58 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines BipartiteGraph class
+
+
 #ifndef __defined_libdai_bipgraph_h
 #define __defined_libdai_bipgraph_h
 
 namespace dai {
 
 
-/// A BipartiteGraph represents the neighborhood structure of nodes in a bipartite graph.
+/// Represents the neighborhood structure of nodes in a bipartite graph.
 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
  *  nodes of different type. Nodes are indexed by an unsigned integer, edges are indexed as
  *  a pair of unsigned integers, where the pair (a,b) means the b'th neighbor of the a'th node.
- *  The BipartiteGraph stores neighborhood structures as vectors of vectors of Neighbor entries:
- *  each node has a vector of Neighbor entries, which is also known as a Neighbors type.
+ *
+ *  The BipartiteGraph stores for each node of type 1 a vector of Neighbor structures, where
+ *  each Neighbor corresponds to a neighboring node of type 2. In addition, each node of type 2
+ *  stores a vector of Neighbor structures describing its neighboring nodes of type 1.
  */
 class BipartiteGraph {
     public:
-        /// A Neighbor describes a neighboring node of some other node in a BipartiteGraph.
-        /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
+        /// Describes a neighboring node of some other node in a BipartiteGraph.
+        /** Iterating over all neighbors of the n1'th node of type 1 can be done in the following way:
          *  \code
+         *      size_t n1 = ...;
          *      foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
          *          size_t _n2 = n2.iter;
          *          size_t _n1 = n2.dual;
-         *          // n2 == n2.node;
-         *          // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
-         *          // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1 
+         *          std::cout << "The " << _n2 << "'th neighbor of the " << n1 << "'th node of type 1 is: the " << n2 << "'th node of type 2" << endl;
+         *
+         *          // The _n2'th neighbor of n1 is n2:
+         *          assert( nb1(n1)[_n2] == n2 );
+         *          // The _n1'th neighbor of n2 is n1:
+         *          assert( nb2(n2)[_n1] == n1 );
+         *          // n2 can be used as an abbreviation of n2.node:
+         *          assert( static_cast<size_t>(n2) == n2.node );
          *      }
          *  \endcode
          */
         struct Neighbor {
             /// Corresponds to the index of this Neighbor entry in the vector of neighbors
-            unsigned iter;
+            size_t iter;
             /// Contains the number of the neighboring node
-            unsigned node;
+            size_t node;
             /// Contains the "dual" iter
-            unsigned dual;
-            /// Cast to unsigned returns node member
-            operator unsigned () const { return node; }
+            size_t dual;
+
             /// Default constructor
             Neighbor() {}
-            /// Constructor
+            /// Constructor that sets the Neighbor members accordingly to the parameters
             Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
+
+            /// Cast to size_t returns member node
+            operator size_t () const { return node; }
         };
 
-        /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
+        /// Describes the neighbors of some node.
         typedef std::vector<Neighbor> Neighbors;
 
-        /// Edge is used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor. It depends on the context whether the first node (with index a) is of type 1 or of type 2.
+        /// Used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor (it depends on the context whether the first node (with index a) is of type 1 or of type 2).
         typedef std::pair<size_t,size_t> Edge;
 
     private:
-        /// _nb1 contains for each node of type 1 a vector of its neighbors
+        /// Contains for each node of type 1 a vector of its neighbors
         std::vector<Neighbors> _nb1;
-        /// _nb2 contains for each node of type 2 a vector of its neighbors
+
+        /// Contains for each node of type 2 a vector of its neighbors
         std::vector<Neighbors> _nb2;
 
         /// Used internally by isTree()
         struct levelType {
-            std::vector<size_t> ind1;       // indices of vertices of type 1
-            std::vector<size_t> ind2;       // indices of vertices of type 2
+            std::vector<size_t> ind1;       // indices of nodes of type 1
+            std::vector<size_t> ind2;       // indices of nodes of type 2
         };
 
     public:
@@ -104,22 +119,28 @@ class BipartiteGraph {
             return *this;
         }
 
-        /// Create bipartite graph from a range of edges. 
-        /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2. 
-         *  The value_type of an EdgeInputIterator should be Edge.
-         */
-        template<typename EdgeInputIterator>
-        void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
-
-        /// Construct bipartite graph from a range of edges. 
-        /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2. 
-         *  The value_type of an EdgeInputIterator should be Edge.
+        /// Constructs BipartiteGraph from a range of edges. 
+        /** \tparam EdgeInputIterator Iterator with value_type Edge.
+         *  \param nr1 The number of nodes of type 1.
+         *  \param nr2 The number of nodes of type 2. 
+         *  \param begin Points to the first Edge.
+         *  \param end Points just beyond the last Edge.
          */
         template<typename EdgeInputIterator>
         BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
             construct( nr1, nr2, begin, end );
         }
 
+        /// (Re)constructs BipartiteGraph from a range of edges. 
+        /** \tparam EdgeInputIterator Iterator with value_type Edge.
+         *  \param nr1 The number of nodes of type 1.
+         *  \param nr2 The number of nodes of type 2. 
+         *  \param begin Points to the first Edge.
+         *  \param end Points just beyond the last Edge.
+         */
+        template<typename EdgeInputIterator>
+        void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
+
         /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
         const Neighbor & nb1( size_t i1, size_t _i2 ) const { 
 #ifdef DAI_DEBUG
@@ -197,16 +218,18 @@ class BipartiteGraph {
             return sum;
         }
         
-        /// Add node of type 1 without neighbors.
+        /// Adds a node of type 1 without neighbors.
         void add1() { _nb1.push_back( Neighbors() ); }
         
-        /// Add node of type 2 without neighbors.
+        /// Adds a node of type 2 without neighbors.
         void add2() { _nb2.push_back( Neighbors() ); }
 
-        /// Add node of type 1 with neighbors specified by a range.
-        /** The value_type of an NodeInputIterator should be a size_t, corresponding to
+        /// Adds a node of type 1, with neighbors specified by a range of indices of nodes of type 2.
+        /** \tparam NodeInputIterator Iterator with value_type size_t, corresponding to
          *  the indices of nodes of type 2 that should become neighbors of the added node.
-         *  For improved efficiency, the size of the range may be specified by sizeHint.
+         *  \param begin Points to the index of the first neighbor.
+         *  \param end Points just beyond the index of the last neighbor.
+         *  \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
          */
         template <typename NodeInputIterator>
         void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
@@ -223,10 +246,12 @@ class BipartiteGraph {
             _nb1.push_back( nbs1new );
         }
 
-        /// Add node of type 2 with neighbors specified by a range.
-        /** The value_type of an NodeInputIterator should be a size_t, corresponding to
+        /// Adds a node of type 2, with neighbors specified by a range of indices of nodes of type 1.
+        /** \tparam NodeInputIterator Iterator with value_type size_t, corresponding to
          *  the indices of nodes of type 1 that should become neighbors of the added node.
-         *  For improved efficiency, the size of the range may be specified by sizeHint.
+         *  \param begin Points to the index of the first neighbor.
+         *  \param end Points just beyond the index of the last neighbor.
+         *  \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
          */
         template <typename NodeInputIterator>
         void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
@@ -243,13 +268,13 @@ class BipartiteGraph {
             _nb2.push_back( nbs2new );
         }
 
-        /// Remove node n1 of type 1 and all incident edges.
+        /// Removes node n1 of type 1 and all incident edges.
         void erase1( size_t n1 );
 
-        /// Remove node n2 of type 2 and all incident edges.
+        /// Removes node n2 of type 2 and all incident edges.
         void erase2( size_t n2 );
 
-        /// Add edge between node n1 of type 1 and node n2 of type 2.
+        /// Adds an edge between node n1 of type 1 and node n2 of type 2.
         /** If check == true, only adds the edge if it does not exist already.
          */
         void addEdge( size_t n1, size_t n2, bool check = true ) {
@@ -272,13 +297,13 @@ class BipartiteGraph {
             }
         }
 
-        /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
-        /** If include == true, include n1 itself, otherwise exclude n1.
+        /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
+        /** If include == true, includes n1 itself, otherwise excludes n1.
          */
         std::vector<size_t> delta1( size_t n1, bool include = false ) const;
 
-        /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
-        /** If include == true, include n2 itself, otherwise exclude n2.
+        /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
+        /** If include == true, includes n2 itself, otherwise excludes n2.
          */
         std::vector<size_t> delta2( size_t n2, bool include = false ) const;
 
@@ -286,14 +311,15 @@ class BipartiteGraph {
         bool isConnected() const;
 
         /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
-        /** This is equivalent to whether for each pair of vertices in the graph, there exists
-         *  a unique path in the graph that starts at the first and ends at the second vertex.
+        /** This is equivalent to whether for each pair of nodes in the graph, there exists
+         *  a unique path in the graph that starts at the first and ends at the second node.
          */
         bool isTree() const;
 
-        /// Stream to output stream os in graphviz .dot syntax
+        /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
         void printDot( std::ostream& os ) const;
 
+    private:
         /// Checks internal consistency
         void check() const;
 };
index ba53c8e..c762d7e 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class BP
+
+
 #ifndef __defined_libdai_bp_h
 #define __defined_libdai_bp_h
 
@@ -34,6 +38,7 @@
 namespace dai {
 
 
+/// Approximate inference algorithm "(Loopy) Belief Propagation"
 class BP : public DAIAlgFG {
     private:
         typedef std::vector<size_t> ind_t;
@@ -50,38 +55,46 @@ class BP : public DAIAlgFG {
         size_t _iters;
     
     public:
+        /// Parameters of this inference algorithm
         struct Properties {
+            /// Enumeration of possible update schedules
+            DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL)
+
+            /// Enumeration of inference variants
+            DAI_ENUM(InfType,SUMPROD,MAXPROD)
+        
+            /// Verbosity
             size_t verbose;
+
+            /// Maximum number of iterations
             size_t maxiter;
+
+            /// Tolerance
             double tol;
+
+            /// Do updates in logarithmic domain?
             bool logdomain;
+
+            /// Damping constant
             double damping;
-            DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL)
+
+            /// Update schedule
             UpdateType updates;
-            DAI_ENUM(InfType,SUMPROD,MAXPROD)
+
+            /// Type of inference: sum-product or max-product?
             InfType inference;
         } props;
+
+        /// Name of this inference algorithm
         static const char *Name;
 
     public:
         /// Default constructor
         BP() : DAIAlgFG(), _edges(), _maxdiff(0.0), _iters(0U), props() {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), props() {
-            setProperties( opts );
-            construct();
-        }
-
         /// Copy constructor
         BP( const BP &x ) : DAIAlgFG(x), _edges(x._edges), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
 
-        /// Clone *this (virtual copy constructor)
-        virtual BP* clone() const { return new BP(*this); }
-
-        /// Create (virtual default constructor)
-        virtual BP* create() const { return new BP(); }
-
         /// Assignment operator
         BP& operator=( const BP &x ) {
             if( this != &x ) {
@@ -94,39 +107,35 @@ class BP : public DAIAlgFG {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
+        /// Construct from FactorGraph fg and PropertySet opts
+        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), props() {
+            setProperties( opts );
+            construct();
+        }
 
-        /// Get single node belief
-        virtual Factor belief( const Var &n ) const;
 
-        /// Get general belief
+        /// @name General InfAlg interface
+        //@{
+        virtual BP* clone() const { return new BP(*this); }
+        virtual BP* create() const { return new BP(); }
+        virtual std::string identify() const;
+        virtual Factor belief( const Var &n ) const;
         virtual Factor belief( const VarSet &ns ) const;
-
-        /// Get all beliefs
         virtual std::vector<Factor> beliefs() const;
-
-        /// Get log partition sum
         virtual Real logZ() const;
-
-        /// Clear messages and beliefs
         virtual void init();
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
         virtual void init( const VarSet &ns );
-
-        /// The actual approximate inference algorithm
         virtual double run();
-
-        /// Return maximum difference between single node beliefs in the last pass
         virtual double maxDiff() const { return _maxdiff; }
-
-        /// Return number of passes over the factorgraph
         virtual size_t Iterations() const { return _iters; }
+        //@}
 
 
+        /// @name Additional interface specific for BP
+        //@{
         Factor beliefV( size_t i ) const;
         Factor beliefF( size_t I ) const;
+        //@}
 
     private:
         const Prob & message(size_t i, size_t _I) const { return _edges[i][_I].message; }
index 211f636..249128a 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class ClusterGraph
+
+
 #ifndef __defined_libdai_clustergraph_h
 #define __defined_libdai_clustergraph_h
 
@@ -34,17 +38,24 @@ namespace dai {
 
 
     /// A ClusterGraph is a hypergraph with VarSets as nodes.
-    /// It is implemented as bipartite graph with variable nodes
-    /// and cluster (VarSet) nodes. The additional
-    /// functionality compared to a simple set<VarSet> is
-    /// finding maximal clusters, finding cliques, etc...
+    /** It is implemented as bipartite graph with variable (Var) nodes
+     *  and cluster (VarSet) nodes. 
+     */
     class ClusterGraph {
         public:
+            /// Stores the neighborhood structure
             BipartiteGraph       G;
+
+            /// Stores the variables corresponding to the nodes
             std::vector<Var>     vars;
+
+            /// Stores the clusters corresponding to the hyperedges
             std::vector<VarSet>  clusters;
 
+            /// Shorthand for BipartiteGraph::Neighbor
             typedef BipartiteGraph::Neighbor Neighbor;
+
+            /// Shorthand for BipartiteGraph::Edge
             typedef BipartiteGraph::Edge     Edge;
 
         public:
@@ -87,7 +98,7 @@ namespace dai {
                 return maximal;
             }
 
-            /// Erase all VarSets that are not maximal
+            /// Erases all VarSets that are not maximal
             ClusterGraph& eraseNonMaximal() {
                 for( size_t I = 0; I < G.nr2(); ) {
                     if( !isMaximal(I) ) {
@@ -99,12 +110,12 @@ namespace dai {
                 return *this;
             }
 
-            /// Return number of clusters
+            /// Returns number of clusters
             size_t size() const {
                 return G.nr2();
             }
 
-            /// Return index of variable n
+            /// Returns index of variable n
             size_t findVar( const Var &n ) const {
                 return find( vars.begin(), vars.end(), n ) - vars.begin();
             }
@@ -160,13 +171,14 @@ namespace dai {
                 return *this;
             }
             
-            /// Provide read access to clusters
+            /// Returns a const reference to the clusters
             const std::vector<VarSet> & toVector() const { return clusters; }
 
-            /// Calculate cost of eliminating the variable with index i,
-            /// using as a measure "number of added edges in the adjacency graph"
-            /// where the adjacency graph has the variables as its nodes and
-            /// connects nodes i1 and i2 iff i1 and i2 occur in some common cluster
+            /// Calculates cost of eliminating the variable with index i.
+            /** The cost is measured as "number of added edges in the adjacency graph",
+             *  where the adjacency graph has the variables as its nodes and
+             *  connects nodes i1 and i2 iff i1 and i2 occur in some common cluster.
+             */
             size_t eliminationCost( size_t i ) {
                 std::vector<size_t> id_n = G.delta1( i );
 
@@ -183,16 +195,17 @@ namespace dai {
                 return cost;
             }
 
-            /// Perform Variable Elimination without Probs, i.e. only keeping track of
-            /// the interactions that are created along the way.
-            /// Input:  a set of outer clusters and an elimination sequence
-            /// Output: a set of elimination "cliques"
+            /// Performs Variable Elimination without Probs, i.e. only keeping track of
+            /*  the interactions that are created along the way.
+             *  \param ElimSeq A set of outer clusters and an elimination sequence
+             *  \return A set of elimination "cliques"
+             */
             ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
 
-            /// Perform Variable Eliminiation using the MinFill heuristic
+            /// Performs Variable Eliminiation using the MinFill heuristic
             ClusterGraph VarElim_MinFill() const;
 
-            /// Send to output stream
+            /// Writes a ClusterGraph to an output stream
             friend std::ostream & operator << ( std::ostream & os, const ClusterGraph & cl ) {
                 os << cl.toVector();
                 return os;
index b4e0419..92d875f 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines abstract base class InfAlg, its descendants DAIAlg<T>, the specializations DAIAlgFG and DAIAlgRG and some generic inference methods.
+
+
 #ifndef __defined_libdai_daialg_h
 #define __defined_libdai_daialg_h
 
 namespace dai {
 
 
-/// The InfAlg class is the common denominator of the various approximate inference algorithms.
-/// A InfAlg object represents a discrete factorized probability distribution over multiple variables 
-/// together with an inference algorithm.
+/// InfAlg is an abstract base class, defining the common interface of all inference algorithms in libDAI.
 class InfAlg {
     public:
-        /// Clone *this (virtual copy constructor)
+        /// Virtual desctructor (needed because this class contains virtual functions)
+        virtual ~InfAlg() {}
+
+    public:
+        /// Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor)
         virtual InfAlg* clone() const = 0;
 
-        /// Create (virtual default constructor)
+        /// Returns a pointer to a newly constructed object *this (i.e., virtual default constructor)
         virtual InfAlg* create() const = 0;
         
-        /// Virtual desctructor (needed because this class contains virtual functions)
-        virtual ~InfAlg() {}
-        
         /// Identifies itself for logging purposes
         virtual std::string identify() const = 0;
 
-        /// Get single node belief
+        /// Returns the "belief" (i.e., approximate marginal probability distribution) of a variable
         virtual Factor belief( const Var &n ) const = 0;
 
-        /// Get general belief
+        /// Returns the "belief" (i.e., approximate marginal probability distribution) of a set of variables
         virtual Factor belief( const VarSet &n ) const = 0;
 
-        /// Get all beliefs
+        /// Returns all "beliefs" (i.e., approximate marginal probability distribution) calculated by the algorithm
         virtual std::vector<Factor> beliefs() const = 0;
 
-        /// Get log partition sum
+        /// Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph)
         virtual Real logZ() const = 0;
 
-        /// Clear messages and beliefs
+        /// Initializes all data structures of the approximate inference algorithm
+        /** This method should be called at least once before run() is called
+         */
         virtual void init() = 0;
 
-        /// Clear messages and beliefs corresponding to the nodes in ns
+        /// Initializes all data structures corresponding to some set of variables
+        /** This method can be used to do a partial initialization after a part of the factor graph has changed.
+         *  Instead of initializing all data structures, it only initializes those involving the variables in ns.
+         */
         virtual void init( const VarSet &ns ) = 0;
 
-        /// The actual approximate inference algorithm
+        /// Runs the approximate inference algorithm
+        /*  Before run() is called the first time, init() should be called.
+         *  If run() returns successfully, the results can be queried using the methods belief(), beliefs() and logZ().
+         */
         virtual double run() = 0;
 
-        /// Save factor I
-        virtual void backupFactor( size_t I ) = 0;
-        /// Save Factors involving ns
-        virtual void backupFactors( const VarSet &ns ) = 0;
-
-        /// Restore factor I
-        virtual void restoreFactor( size_t I ) = 0;
-        /// Restore Factors involving ns
-        virtual void restoreFactors( const VarSet &ns ) = 0;
-
         /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
         virtual void clamp( const Var & n, size_t i, bool backup = false ) = 0;
 
         /// Set all factors interacting with var(i) to 1
         virtual void makeCavity( size_t i, bool backup = false ) = 0;
 
+        /// Return maximum difference between single node beliefs in the last pass
+        /// \throw Exception if not implemented/supported
+        virtual double maxDiff() const = 0;
+
+        /// Return number of passes over the factorgraph
+        /// \throw Exception if not implemented/supported
+        virtual size_t Iterations() const = 0;
+
+
         /// Get reference to underlying FactorGraph
         virtual FactorGraph &fg() = 0;
 
         /// Get const reference to underlying FactorGraph
         virtual const FactorGraph &fg() const = 0;
 
-        /// Return maximum difference between single node beliefs in the last pass
-        virtual double maxDiff() const = 0;
+        /// Save factor I
+        virtual void backupFactor( size_t I ) = 0;
+        /// Save Factors involving ns
+        virtual void backupFactors( const VarSet &ns ) = 0;
 
-        /// Return number of passes over the factorgraph
-        virtual size_t Iterations() const = 0;
+        /// Restore factor I
+        virtual void restoreFactor( size_t I ) = 0;
+        /// Restore Factors involving ns
+        virtual void restoreFactors( const VarSet &ns ) = 0;
 };
 
 
-template <class T>
-class DAIAlg : public InfAlg, public T {
+/// Combines an InfAlg and a graphical model, e.g., a FactorGraph or RegionGraph
+/** \tparam GRM Should be castable to FactorGraph
+ */
+template <class GRM>
+class DAIAlg : public InfAlg, public GRM {
     public:
         /// Default constructor
-        DAIAlg() : InfAlg(), T() {}
+        DAIAlg() : InfAlg(), GRM() {}
         
-        /// Construct from T
-        DAIAlg( const T &t ) : InfAlg(), T(t) {}
+        /// Construct from GRM 
+        DAIAlg( const GRM &grm ) : InfAlg(), GRM(grm) {}
 
         /// Copy constructor
-        DAIAlg( const DAIAlg & x ) : InfAlg(x), T(x) {}
+        DAIAlg( const DAIAlg & x ) : InfAlg(x), GRM(x) {}
 
         /// Assignment operator
         DAIAlg & operator=( const DAIAlg &x ) {
             if( this != &x ) {
                 InfAlg::operator=(x);
-                T::operator=(x);
+                GRM::operator=(x);
             }
             return *this;
         }
 
-        /// Save factor I (using T::backupFactor)
-        void backupFactor( size_t I ) { T::backupFactor( I ); }
-        /// Save Factors involving ns (using T::backupFactors)
-        void backupFactors( const VarSet &ns ) { T::backupFactors( ns ); }
+        /// Save factor I
+        void backupFactor( size_t I ) { GRM::backupFactor( I ); }
+        /// Save Factors involving ns
+        void backupFactors( const VarSet &ns ) { GRM::backupFactors( ns ); }
 
-        /// Restore factor I (using T::restoreFactor)
-        void restoreFactor( size_t I ) { T::restoreFactor( I ); }
-        /// Restore Factors involving ns (using T::restoreFactors)
-        void restoreFactors( const VarSet &ns ) { T::restoreFactors( ns ); }
+        /// Restore factor I
+        void restoreFactor( size_t I ) { GRM::restoreFactor( I ); }
+        /// Restore Factors involving ns
+        void restoreFactors( const VarSet &ns ) { GRM::restoreFactors( ns ); }
 
-        /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$) (using T::clamp)
-        void clamp( const Var & n, size_t i, bool backup = false ) { T::clamp( n, i, backup ); }
+        /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
+        void clamp( const Var & n, size_t i, bool backup = false ) { GRM::clamp( n, i, backup ); }
 
-        /// Set all factors interacting with var(i) to 1 (using T::makeCavity)
-        void makeCavity( size_t i, bool backup = false ) { T::makeCavity( i, backup ); }
+        /// Set all factors interacting with var(i) to 1
+        void makeCavity( size_t i, bool backup = false ) { GRM::makeCavity( i, backup ); }
 
         /// Get reference to underlying FactorGraph
         FactorGraph &fg() { return (FactorGraph &)(*this); }
@@ -147,26 +164,16 @@ class DAIAlg : public InfAlg, public T {
 };
 
 
+/// Base class for inference algorithms that operate on a FactorGraph
 typedef DAIAlg<FactorGraph> DAIAlgFG;
+
+/// Base class for inference algorithms that operate on a RegionGraph
 typedef DAIAlg<RegionGraph> DAIAlgRG;
 
 
-/// Calculate the marginal of obj on ns by clamping 
-/// all variables in ns and calculating logZ for each joined state
 Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit );
-
-
-/// Calculate beliefs of all pairs in ns (by clamping
-/// nodes in ns and calculating logZ and the beliefs for each state)
 std::vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reInit );
-
-
-/// Calculate beliefs of all pairs in ns (by clamping
-/// pairs in ns and calculating logZ for each joined state)
 std::vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool reInit );
-
-
-/// Calculate 2nd order interactions of the marginal of obj on ns
 Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit );
 
 
diff --git a/include/dai/diffs.h b/include/dai/diffs.h
deleted file mode 100644 (file)
index cf06f09..0000000
+++ /dev/null
@@ -1,84 +0,0 @@
-/*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
-    Radboud University Nijmegen, The Netherlands /
-    Max Planck Institute for Biological Cybernetics, Germany
-
-    This file is part of libDAI.
-
-    libDAI is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
-
-    libDAI is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
-
-    You should have received a copy of the GNU General Public License
-    along with libDAI; if not, write to the Free Software
-    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-*/
-
-
-#ifndef __defined_libdai_diffs_h
-#define __defined_libdai_diffs_h
-
-
-#include <vector>
-
-
-namespace dai {
-
-
-class Diffs : public std::vector<double> {
-    private:
-        size_t _maxsize;
-        double _def;
-        std::vector<double>::iterator _pos;
-        std::vector<double>::iterator _maxpos;
-    public:
-        Diffs(long maxsize, double def) : std::vector<double>(), _maxsize(maxsize), _def(def) { 
-            this->reserve(_maxsize); 
-            _pos = begin(); 
-            _maxpos = begin(); 
-        };
-        double maxDiff() { 
-            if( size() < _maxsize )
-                return _def;
-            else
-                return( *_maxpos ); 
-        }
-        void push(double x) {
-            if( size() < _maxsize ) {
-                push_back(x);
-                _pos = end();
-                if( size() > 1 ) {
-                    if( *_maxpos < back() ) {
-                        _maxpos = end();
-                        _maxpos--;
-                    }
-                } else {
-                    _maxpos = begin();
-                }
-            }
-            else {
-                if( _pos == end() )
-                    _pos = begin();
-                if( _maxpos == _pos ) {
-                    *_pos++ = x; 
-                    _maxpos = max_element(begin(),end());
-                } else {
-                    if( x > *_maxpos )
-                        _maxpos = _pos;
-                    *_pos++ = x;
-                }
-            }
-        }
-        size_t maxSize() { return _maxsize; }
-};
-
-
-} // end of namespace dai
-
-
-#endif
index e6b926a..f73d090 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines the DAI_ENUM macro
+
+
 #ifndef __defined_libdai_enum_h
 #define __defined_libdai_enum_h
 
 #include <dai/exceptions.h>
 
 
-/// Extends the C++ enum type by supporting io streaming and conversion to and from const char* (using anonymous variadic macros)
-
-
+/// Extends the C++ enum type by supporting input/output streaming and conversion to and from const char*
+/** Example of usage:
+ *  \code
+ *      DAI_ENUM(colors,RED,GREEN,BLUE)
+ *  \endcode
+ *  defines a class encapsulating an
+ *  \code
+ *      enum colors {RED, GREEN, BLUE};
+ *  \endcode
+ *  It offers additional functionality over the plain "enum" keyword.
+ */
 #define DAI_ENUM(x,val0,...) class x {\
     public:\
         enum value {val0,__VA_ARGS__};\
index 7d69c68..549269b 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines ExactInf class
+
+
 #ifndef __defined_libdai_exactinf_h
 #define __defined_libdai_exactinf_h
 
 namespace dai {
 
 
+/// Exact inference algorithm using brute force enumeration (mainly useful for testing purposes)
 class ExactInf : public DAIAlgFG {
     public:
+        /// Parameters of this inference algorithm
         struct Properties {
+            /// Verbosity
             size_t verbose;
         } props;
-        /// Name of this inference method
+
+        /// Name of this inference algorithm
         static const char *Name;
 
     private:
@@ -50,21 +58,9 @@ class ExactInf : public DAIAlgFG {
         /// Default constructor
         ExactInf() : DAIAlgFG(), props(), _beliefsV(), _beliefsF(), _logZ(0) {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        ExactInf( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), props(), _beliefsV(), _beliefsF(), _logZ() {
-            setProperties( opts );
-            construct();
-        }
-        
         /// Copy constructor
         ExactInf( const ExactInf &x ) : DAIAlgFG(x), props(x.props), _beliefsV(x._beliefsV), _beliefsF(x._beliefsF), _logZ(x._logZ) {}
 
-        /// Clone *this (virtual copy constructor)
-        virtual ExactInf* clone() const { return new ExactInf(*this); }
-
-        /// Create (virtual default constructor)
-        virtual ExactInf* create() const { return new ExactInf(); }
-
         /// Assignment operator
         ExactInf& operator=( const ExactInf &x ) {
             if( this != &x ) {
@@ -77,51 +73,41 @@ class ExactInf : public DAIAlgFG {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
+        /// Construct from FactorGraph fg and PropertySet opts
+        ExactInf( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), props(), _beliefsV(), _beliefsF(), _logZ() {
+            setProperties( opts );
+            construct();
+        }
 
-        /// Get single node belief
+        
+        /// @name General InfAlg interface
+        //@{
+        virtual ExactInf* clone() const { return new ExactInf(*this); }
+        virtual ExactInf* create() const { return new ExactInf(); }
+        virtual std::string identify() const;
         virtual Factor belief( const Var &n ) const { return beliefV( findVar( n ) ); }
-
-        /// Get general belief
         virtual Factor belief( const VarSet &ns ) const;
-
-        /// Get all beliefs
         virtual std::vector<Factor> beliefs() const;
-
-        /// Get log partition sum
         virtual Real logZ() const { return _logZ; }
-
-        /// Clear messages and beliefs
         virtual void init();
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
-        virtual void init( const VarSet &/*ns*/ ) {
-            DAI_THROW(NOT_IMPLEMENTED);
-        }
-
-        /// The actual approximate inference algorithm
+        virtual void init( const VarSet &/*ns*/ ) { DAI_THROW(NOT_IMPLEMENTED); }
         virtual double run();
+        virtual double maxDiff() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
+        virtual size_t Iterations() const { DAI_THROW(NOT_IMPLEMENTED); return 0; }
+        //@}
+        
 
-        /// Return maximum difference between single node beliefs in the last pass
-        virtual double maxDiff() const {
-            DAI_THROW(NOT_IMPLEMENTED);
-            return 0.0;
-        }
+        /// @name Additional interface specific for ExactInf
+        //@{ 
+        Factor beliefV( size_t i ) const { return _beliefsV[i]; }
+        Factor beliefF( size_t I ) const { return _beliefsF[I]; }
+        //@}
 
-        /// Return number of passes over the factorgraph
-        virtual size_t Iterations() const { 
-            DAI_THROW(NOT_IMPLEMENTED);
-            return 0; 
-        }
-        
+    private:
         void construct();
         void setProperties( const PropertySet &opts );
         PropertySet getProperties() const;
         std::string printProperties() const;
-
-        Factor beliefV( size_t i ) const { return _beliefsV[i]; }
-        Factor beliefF( size_t I ) const { return _beliefsF[I]; }
 };
 
 
index dc46756..0f5c420 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines Exception class and the DAI_THROW macro
+
+
 #ifndef __defined_libdai_exceptions_h
 #define __defined_libdai_exceptions_h
 
 #include <string>
 
 
+/// Used by DAI_THROW
 #define DAI_QUOTE(x) #x
+
+/// Used by DAI_THROW
 #define DAI_TOSTRING(x) DAI_QUOTE(x)
 
+/// Macro that simplifies throwing an exceptions with a useful error message
+/** \param cod Corresponds to one of the enum values in dai::Exception::codes
+ *
+ * Example:
+ *  \code
+ *  DAI_THROW(NOT_IMPLEMENTED);
+ *  \endcode
+ */
 #define DAI_THROW(cod) throw dai::Exception(dai::Exception::cod, std::string(__FILE__ ", line " DAI_TOSTRING(__LINE__)))
 
 
 namespace dai {
 
 
-    class Exception : public std::runtime_error {
-        public:
+/// Represents an exception (based on std::runtime_error)
+class Exception : public std::runtime_error {
+    public:
+        /// Constructor
             Exception(size_t code, const std::string& msg = "") : std::runtime_error(ErrorStrings[code] + " [" +  msg + "]") {}
 
-        enum {NOT_IMPLEMENTED,
-              UNKNOWN_DAI_ALGORITHM,
-              UNKNOWN_PROPERTY_TYPE,
-              MALFORMED_PROPERTY,
-              UNKNOWN_ENUM_VALUE,
-              CANNOT_READ_FILE,
-              CANNOT_WRITE_FILE,
-              INVALID_FACTORGRAPH_FILE,
-              NOT_ALL_PROPERTIES_SPECIFIED,
-              MULTIPLE_UNDO,
-              FACTORGRAPH_NOT_CONNECTED,
-              IMPOSSIBLE_TYPECAST,
-              INTERNAL_ERROR,
-              NUM_ERRORS};  // NUM_ERRORS should be the last entry
-
-        private:
-            static std::string ErrorStrings[NUM_ERRORS];
-    };
+        /// Enumeration of exceptions used in libDAI
+        enum codes {NOT_IMPLEMENTED,
+                    UNKNOWN_DAI_ALGORITHM,
+                    UNKNOWN_PROPERTY_TYPE,
+                    MALFORMED_PROPERTY,
+                    UNKNOWN_ENUM_VALUE,
+                    CANNOT_READ_FILE,
+                    CANNOT_WRITE_FILE,
+                    INVALID_FACTORGRAPH_FILE,
+                    NOT_ALL_PROPERTIES_SPECIFIED,
+                    MULTIPLE_UNDO,
+                    FACTORGRAPH_NOT_CONNECTED,
+                    IMPOSSIBLE_TYPECAST,
+                    INTERNAL_ERROR,
+                    NUM_ERRORS};  // NUM_ERRORS should be the last entry
+
+    private:
+        /// Error messages corresponding to the exceptions enumerated above
+        static std::string ErrorStrings[NUM_ERRORS];
+};
 
 
 }
index 9801546..d65937a 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines TFactor<T> and Factor classes
+
+
 #ifndef __defined_libdai_factor_h
 #define __defined_libdai_factor_h
 
 namespace dai {
 
 
+// predefine TFactor<T> class
 template<typename T> class      TFactor;
-typedef TFactor<Real>           Factor;
 
 
-// predefine friends
-template<typename T> Real           dist( const TFactor<T> & x, const TFactor<T> & y, Prob::DistType dt );
-template<typename T> Real           KL_dist( const TFactor<T> & p, const TFactor<T> & q );
-template<typename T> Real           MutualInfo( const TFactor<T> & p );
-template<typename T> TFactor<T>     max( const TFactor<T> & P, const TFactor<T> & Q );
-template<typename T> TFactor<T>     min( const TFactor<T> & P, const TFactor<T> & Q );
-template<typename T> std::ostream&  operator<< (std::ostream& os, const TFactor<T>& P);
+/// Represents a factor with probability entries represented as Real
+typedef TFactor<Real>           Factor;
 
-        
-// T should be castable from and to double
+
+/// Represents a probability factor.
+/** A \e factor is a function of the Cartesian product of the state
+ *  spaces of some set of variables to the nonnegative real numbers.
+ *  More formally, if \f$x_i \in X_i\f$ for all \f$i\f$, then a factor
+ *  depending on the variables \f$\{x_i\}\f$ is a function defined
+ *  on \f$\prod_i X_i\f$ with values in \f$[0,\infty)\f$.
+ *  
+ *  A Factor has two components: a VarSet, defining the set of variables
+ *  that the factor depends on, and a TProb<T>, containing the values of
+ *  the factor for all possible joint states of the variables.
+ *
+ *  \tparam T Should be castable from and to double.
+ */
 template <typename T> class TFactor {
     private:
         VarSet      _vs;
         TProb<T>    _p;
 
     public:
-        // Construct Factor with empty VarSet but nonempty _p
+        /// Construct Factor with empty VarSet
         TFactor ( Real p = 1.0 ) : _vs(), _p(1,p) {}
 
-        // Construct Factor from VarSet
-        TFactor( const VarSet& ns ) : _vs(ns), _p(nrStates(_vs)) {}
+        /// Construct Factor from VarSet
+        TFactor( const VarSet& ns ) : _vs(ns), _p(_vs.nrStates()) {}
         
-        // Construct Factor from VarSet and initial value
-        TFactor( const VarSet& ns, Real p ) : _vs(ns), _p(nrStates(_vs),p) {}
+        /// Construct Factor from VarSet and initial value
+        TFactor( const VarSet& ns, Real p ) : _vs(ns), _p(_vs.nrStates(),p) {}
         
-        // Construct Factor from VarSet and initial array
-        TFactor( const VarSet& ns, const Real* p ) : _vs(ns), _p(nrStates(_vs),p) {}
+        /// Construct Factor from VarSet and initial array
+        TFactor( const VarSet& ns, const Real *p ) : _vs(ns), _p(_vs.nrStates(),p) {}
 
-        // Construct Factor from VarSet and TProb<T>
+        /// Construct Factor from VarSet and TProb<T>
         TFactor( const VarSet& ns, const TProb<T>& p ) : _vs(ns), _p(p) {
 #ifdef DAI_DEBUG
-            assert( nrStates(_vs) == _p.size() );
+            assert( _vs.nrStates() == _p.size() );
 #endif
         }
         
-        // Construct Factor from Var
+        /// Construct Factor from Var
         TFactor( const Var& n ) : _vs(n), _p(n.states()) {}
 
-        // Copy constructor
+        /// Copy constructor
         TFactor( const TFactor<T> &x ) : _vs(x._vs), _p(x._p) {}
         
-        // Assignment operator
+        /// Assignment operator
         TFactor<T> & operator= (const TFactor<T> &x) {
             if( this != &x ) {
                 _vs = x._vs;
@@ -91,39 +102,68 @@ template <typename T> class TFactor {
             return *this;
         }
 
+        /// Returns const reference to probability entries
         const TProb<T> & p() const { return _p; }
+        /// Returns reference to probability entries
         TProb<T> & p() { return _p; }
+
+        /// Returns const reference to variables
         const VarSet & vars() const { return _vs; }
+
+        /// Returns the number of possible joint states of the variables
         size_t states() const { return _p.size(); }
 
+        /// Returns a copy of the i'th probability value
         T operator[] (size_t i) const { return _p[i]; }
+
+        /// Returns a reference to the i'th probability value
         T& operator[] (size_t i) { return _p[i]; }
-        TFactor<T> & fill (T p)
-            { _p.fill( p ); return(*this); }
-        TFactor<T> & randomize ()
-            { _p.randomize(); return(*this); }
+
+        /// Sets all probability entries to p
+        TFactor<T> & fill (T p) { _p.fill( p ); return(*this); }
+
+        /// Fills all probability entries with random values
+        TFactor<T> & randomize () { _p.randomize(); return(*this); }
+
+        /// Returns product of *this with x
         TFactor<T> operator* (T x) const {
             Factor result = *this;
             result.p() *= x;
             return result;
         }
+
+        /// Multiplies each probability entry with x
         TFactor<T>& operator*= (T x) {
             _p *= x;
             return *this;
         }
+
+        /// Returns quotient of *this with x
         TFactor<T> operator/ (T x) const {
             Factor result = *this;
             result.p() /= x;
             return result;
         }
+
+        /// Divides each probability entry by x
         TFactor<T>& operator/= (T x) {
             _p /= x;
             return *this;
         }
+
+        /// Returns product of *this with another Factor
         TFactor<T> operator* (const TFactor<T>& Q) const;
+
+        /// Returns quotient of *this with another Factor
         TFactor<T> operator/ (const TFactor<T>& Q) const;
+
+        /// Multiplies *this with another Factor
         TFactor<T>& operator*= (const TFactor<T>& Q) { return( *this = (*this * Q) ); }
+
+        /// Divides *this by another Factor
         TFactor<T>& operator/= (const TFactor<T>& Q) { return( *this = (*this / Q) ); }
+
+        /// Returns sum of *this and another Factor (their vars() should be identical)
         TFactor<T> operator+ (const TFactor<T>& Q) const {
 #ifdef DAI_DEBUG
             assert( Q._vs == _vs );
@@ -132,6 +172,8 @@ template <typename T> class TFactor {
             sum._p += Q._p; 
             return sum; 
         }
+
+        /// Returns difference of *this and another Factor (their vars() should be identical)
         TFactor<T> operator- (const TFactor<T>& Q) const {
 #ifdef DAI_DEBUG
             assert( Q._vs == _vs );
@@ -140,6 +182,8 @@ template <typename T> class TFactor {
             sum._p -= Q._p; 
             return sum; 
         }
+
+        /// Adds another Factor to *this (their vars() should be identical)
         TFactor<T>& operator+= (const TFactor<T>& Q) { 
 #ifdef DAI_DEBUG
             assert( Q._vs == _vs );
@@ -147,6 +191,8 @@ template <typename T> class TFactor {
             _p += Q._p;
             return *this;
         }
+
+        /// Subtracts another Factor from *this (their vars() should be identical)
         TFactor<T>& operator-= (const TFactor<T>& Q) { 
 #ifdef DAI_DEBUG
             assert( Q._vs == _vs );
@@ -154,38 +200,52 @@ template <typename T> class TFactor {
             _p -= Q._p;
             return *this;
         }
+
+        /// Adds scalar to *this
         TFactor<T>& operator+= (T q) { 
             _p += q;
             return *this;
         }
+
+        /// Subtracts scalar from *this
         TFactor<T>& operator-= (T q) { 
             _p -= q;
             return *this;
         }
+
+        /// Returns sum of *this and a scalar
         TFactor<T> operator+ (T q) const {
             TFactor<T> result(*this); 
             result._p += q; 
             return result; 
         }
+
+        /// Returns difference of *this with a scalar
         TFactor<T> operator- (T q) const {
             TFactor<T> result(*this); 
             result._p -= q; 
             return result; 
         }
 
+        /// Returns *this raised to some power
         TFactor<T> operator^ (Real a) const { TFactor<T> x; x._vs = _vs; x._p = _p^a; return x; }
+
+        /// Raises *this to some power
         TFactor<T>& operator^= (Real a) { _p ^= a; return *this; }
 
+        /// Sets all entries that are smaller than epsilon to zero
         TFactor<T>& makeZero( Real epsilon ) {
             _p.makeZero( epsilon );
             return *this;
         }
 
+        /// Sets all entries that are smaller than epsilon to epsilon
         TFactor<T>& makePositive( Real epsilon ) {
             _p.makePositive( epsilon );
             return *this;
         }
             
+        /// Returns inverse of *this
         TFactor<T> inverse() const { 
             TFactor<T> inv; 
             inv._vs = _vs; 
@@ -193,6 +253,7 @@ template <typename T> class TFactor {
             return inv; 
         }
 
+        /// Returns *this divided by another Factor
         TFactor<T> divided_by( const TFactor<T>& denom ) const { 
 #ifdef DAI_DEBUG
             assert( denom._vs == _vs );
@@ -202,6 +263,7 @@ template <typename T> class TFactor {
             return quot; 
         }
 
+        /// Divides *this by another Factor
         TFactor<T>& divide( const TFactor<T>& denom ) {
 #ifdef DAI_DEBUG
             assert( denom._vs == _vs );
@@ -210,6 +272,7 @@ template <typename T> class TFactor {
             return *this;
         }
 
+        /// Returns exp of *this
         TFactor<T> exp() const { 
             TFactor<T> e; 
             e._vs = _vs; 
@@ -217,6 +280,7 @@ template <typename T> class TFactor {
             return e; 
         }
 
+        /// Returns absolute value of *this
         TFactor<T> abs() const { 
             TFactor<T> e; 
             e._vs = _vs; 
@@ -224,6 +288,7 @@ template <typename T> class TFactor {
             return e; 
         }
 
+        /// Returns logarithm of *this
         TFactor<T> log() const {
             TFactor<T> l; 
             l._vs = _vs; 
@@ -231,6 +296,7 @@ template <typename T> class TFactor {
             return l; 
         }
 
+        /// Returns logarithm of *this (defining log(0)=0)
         TFactor<T> log0() const {
             TFactor<T> l0; 
             l0._vs = _vs; 
@@ -238,7 +304,10 @@ template <typename T> class TFactor {
             return l0; 
         }
 
+        /// Normalizes *this Factor
         T normalize( typename Prob::NormType norm = Prob::NORMPROB ) { return _p.normalize( norm ); }
+
+        /// Returns a normalized copy of *this
         TFactor<T> normalized( typename Prob::NormType norm = Prob::NORMPROB ) const { 
             TFactor<T> result;
             result._vs = _vs;
@@ -246,7 +315,7 @@ template <typename T> class TFactor {
             return result;
         }
 
-        // returns slice of this factor where the subset ns is in state ns_state
+        /// Returns a slice of this factor, where the subset ns is in state ns_state
         Factor slice( const VarSet & ns, size_t ns_state ) const {
             assert( ns << _vs );
             VarSet nsrem = _vs / ns;
@@ -262,14 +331,16 @@ template <typename T> class TFactor {
             return result;
         }
 
-        // returns unnormalized marginal; ns should be a subset of vars()
+        /// Returns unnormalized marginal; ns should be a subset of vars()
         TFactor<T> partSum(const VarSet & ns) const;
-        // returns (normalized by default) marginal; ns should be a subset of vars()
+
+        /// Returns (normalized by default) marginal; ns should be a subset of vars()
         TFactor<T> marginal(const VarSet & ns, bool normed = true) const { if(normed) return partSum(ns).normalized(); else return partSum(ns); }
-        // sums out all variables except those in ns
+
+        /// Sums out all variables except those in ns
         TFactor<T> notSum(const VarSet & ns) const { return partSum(vars() ^ ns); }
 
-        // embeds this factor in larger varset ns
+        /// Embeds this factor in a larger VarSet
         TFactor<T> embed(const VarSet & ns) const { 
             VarSet vs = vars();
             assert( ns >> vs );
@@ -279,28 +350,29 @@ template <typename T> class TFactor {
                 return (*this) * Factor(ns / vs, 1.0);
         }
 
+        /// Returns true if *this has NANs
         bool hasNaNs() const { return _p.hasNaNs(); }
+
+        /// Returns true if *this has negative entries
         bool hasNegatives() const { return _p.hasNegatives(); }
+
+        /// Returns total sum of probability entries
         T totalSum() const { return _p.totalSum(); }
+
+        /// Returns maximum absolute value of probability entries
         T maxAbs() const { return _p.maxAbs(); }
+
+        /// Returns maximum value of probability entries
         T maxVal() const { return _p.maxVal(); }
+
+        /// Returns minimum value of probability entries
         T minVal() const { return _p.minVal(); }
+
+        /// Returns entropy of *this
         Real entropy() const { return _p.entropy(); }
-        T strength( const Var &i, const Var &j ) const;
 
-        friend Real dist( const TFactor<T> & x, const TFactor<T> & y, Prob::DistType dt ) {
-            if( x._vs.empty() || y._vs.empty() )
-                return -1;
-            else {
-#ifdef DAI_DEBUG
-                assert( x._vs == y._vs );
-#endif
-                return dist( x._p, y._p, dt );
-            }
-        }
-        friend Real KL_dist <> (const TFactor<T> & p, const TFactor<T> & q);
-        friend Real MutualInfo <> ( const TFactor<T> & P );
-        template<class U> friend std::ostream& operator<< (std::ostream& os, const TFactor<U>& P);
+        /// Returns strength of *this, between variables i and j, using (52) of [\ref MoK07b]
+        T strength( const Var &i, const Var &j ) const;
 };
 
 
@@ -319,15 +391,6 @@ template<typename T> TFactor<T> TFactor<T>::partSum(const VarSet & ns) const {
 }
 
 
-template<typename T> std::ostream& operator<< (std::ostream& os, const TFactor<T>& P) {
-    os << "(" << P.vars() << " <";
-    for( size_t i = 0; i < P._p.size(); i++ )
-        os << P._p[i] << " ";
-    os << ">)";
-    return os;
-}
-
-
 template<typename T> TFactor<T> TFactor<T>::operator* (const TFactor<T>& Q) const {
     TFactor<T> prod( _vs | Q._vs, 0.0 );
 
@@ -354,39 +417,6 @@ template<typename T> TFactor<T> TFactor<T>::operator/ (const TFactor<T>& Q) cons
 }
 
 
-template<typename T> Real KL_dist(const TFactor<T> & P, const TFactor<T> & Q) {
-    if( P._vs.empty() || Q._vs.empty() )
-        return -1;
-    else {
-#ifdef DAI_DEBUG
-        assert( P._vs == Q._vs );
-#endif
-        return KL_dist( P._p, Q._p );
-    }
-}
-
-
-// calculate mutual information of x_i and x_j where P.vars() = \{x_i,x_j\}
-template<typename T> Real MutualInfo(const TFactor<T> & P) {
-    assert( P._vs.size() == 2 );
-    VarSet::const_iterator it = P._vs.begin();
-    Var i = *it; it++; Var j = *it;
-    TFactor<T> projection = P.marginal(i) * P.marginal(j);
-    return real( KL_dist( P.normalized(), projection ) );
-}
-
-
-template<typename T> TFactor<T> max( const TFactor<T> & P, const TFactor<T> & Q ) {
-    assert( P._vs == Q._vs );
-    return TFactor<T>( P._vs, min( P.p(), Q.p() ) );
-}
-
-template<typename T> TFactor<T> min( const TFactor<T> & P, const TFactor<T> & Q ) {
-    assert( P._vs == Q._vs );
-    return TFactor<T>( P._vs, max( P.p(), Q.p() ) );
-}
-
-// calculate N(psi, i, j)
 template<typename T> T TFactor<T>::strength( const Var &i, const Var &j ) const {
 #ifdef DAI_DEBUG
     assert( _vs.contains( i ) );
@@ -418,17 +448,50 @@ template<typename T> T TFactor<T>::strength( const Var &i, const Var &j ) const
 }
 
 
-template<typename T> TFactor<T> RemoveFirstOrderInteractions( const TFactor<T> & psi ) {
-    TFactor<T> result = psi;
+/// Writes a Factor to an output stream
+template<typename T> std::ostream& operator<< (std::ostream& os, const TFactor<T>& P) {
+    os << "(" << P.vars() << " <";
+    for( size_t i = 0; i < P.states(); i++ )
+        os << P[i] << " ";
+    os << ">)";
+    return os;
+}
+
 
-    VarSet vars = psi.vars();
-    for( size_t iter = 0; iter < 100; iter++ ) {
-        for( VarSet::const_iterator n = vars.begin(); n != vars.end(); n++ )
-            result = result * result.partSum(*n).inverse();
-        result.normalize();
+/// Returns distance between two Factors (with identical vars())
+template<typename T> Real dist( const TFactor<T> & x, const TFactor<T> & y, Prob::DistType dt ) {
+    if( x.vars().empty() || y.vars().empty() )
+        return -1;
+    else {
+#ifdef DAI_DEBUG
+        assert( x.vars() == y.vars() );
+#endif
+        return dist( x.p(), y.p(), dt );
     }
+}
+
 
-    return result;
+/// Returns the pointwise maximum of two Factors
+template<typename T> TFactor<T> max( const TFactor<T> & P, const TFactor<T> & Q ) {
+    assert( P._vs == Q._vs );
+    return TFactor<T>( P._vs, min( P.p(), Q.p() ) );
+}
+
+
+/// Returns the pointwise minimum of two Factors
+template<typename T> TFactor<T> min( const TFactor<T> & P, const TFactor<T> & Q ) {
+    assert( P._vs == Q._vs );
+    return TFactor<T>( P._vs, max( P.p(), Q.p() ) );
+}
+
+
+/// Calculates the mutual information between the two variables in P
+template<typename T> Real MutualInfo(const TFactor<T> & P) {
+    assert( P.vars().size() == 2 );
+    VarSet::const_iterator it = P.vars().begin();
+    Var i = *it; it++; Var j = *it;
+    TFactor<T> projection = P.marginal(i) * P.marginal(j);
+    return real( dist( P.normalized(), projection, Prob::DISTKL ) );
 }
 
 
index ffb5315..11d8215 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines the FactorGraph class
+
+
 #ifndef __defined_libdai_factorgraph_h
 #define __defined_libdai_factorgraph_h
 
 namespace dai {
 
 
+/// Represents a factor graph.
+/** Both Bayesian Networks and Markov random fields can be represented in a 
+ *  unifying representation, called <em>factor graph</em> [\ref KFL01], 
+ *  implemented in libDAI by the FactorGraph class.
+ *  
+ *  Consider a probability distribution over \f$N\f$ discrete random variables 
+ *  \f$x_0,x_1,\dots,x_N\f$ that factorizes as a product of factors, each of
+ *  which depends on some subset of the variables:
+ *  \f[
+ *    P(x_0,x_1,\dots,x_N) = \frac{1}{Z} \prod_{I=0}^M f_I(x_I), \qquad
+ *    Z = \sum_{x_0}\dots\sum_{x_N} \prod_{I=0}^M f_I(X_I).
+ *  \f]
+ *  Each factor \f$f_I\f$ is a function from an associated subset
+ *  of variables \f$X_I \subset \{x_0,x_1,\dots,x_N\}\f$ to the nonnegative
+ *  real numbers.
+ * 
+ *  For a Bayesian network, each factor corresponds to a (conditional) 
+ *  probability table, whereas for a Markov random field, each factor 
+ *  corresponds to a maximal clique of the undirected graph.
+ *
+ *  Factor graphs explicitly express the factorization structure of the
+ *  corresponding probability distribution.
+ */ 
 class FactorGraph {
     public:
-        BipartiteGraph         G;
-        std::vector<Var>       vars;
+        /// Stores the neighborhood structure
+        BipartiteGraph                    G;
+
+        /// Shorthand for BipartiteGraph::Neighbor
         typedef BipartiteGraph::Neighbor  Neighbor;
+
+        /// Shorthand for BipartiteGraph::Neighbors
         typedef BipartiteGraph::Neighbors Neighbors;
+
+        /// Shorthand for BipartiteGraph::Edge
         typedef BipartiteGraph::Edge      Edge;
 
     private:
+        std::vector<Var>         _vars;
         std::vector<Factor>      _factors;
         std::map<size_t,Factor>  _backup;
 
     public:
         /// Default constructor
-        FactorGraph() : G(), vars(), _factors(), _backup() {}
+        FactorGraph() : G(), _vars(), _factors(), _backup() {}
+
         /// Copy constructor
-        FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), _factors(x._factors), _backup(x._backup) {}
-        /// Construct FactorGraph from vector of Factors
-        FactorGraph(const std::vector<Factor> &P);
-        // Construct a FactorGraph from given factor and variable iterators
-        template<typename FactorInputIterator, typename VarInputIterator>
-        FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint = 0, size_t nr_var_hint = 0 );
-        
+        FactorGraph(const FactorGraph & x) : G(x.G), _vars(x._vars), _factors(x._factors), _backup(x._backup) {}
+
         /// Assignment operator
         FactorGraph & operator=(const FactorGraph & x) {
             if( this != &x ) {
                 G          = x.G;
-                vars       = x.vars;
+                _vars      = x._vars;
                 _factors   = x._factors;
                 _backup    = x._backup;
             }
             return *this;
         }
+
+        /// Constructs a FactorGraph from a vector of factors
+        FactorGraph(const std::vector<Factor> &P);
+
+        /// Constructs a FactorGraph from given factor and variable iterators
+        /** \tparam FactorInputIterator Iterator with value_type Factor
+         *  \tparam VarInputIterator Iterator with value_type Var
+         *  \pre Assumes that the set of variables in [var_begin,var_end) is the union of the variables in the factors in [fact_begin, fact_end)
+         */
+        template<typename FactorInputIterator, typename VarInputIterator>
+        FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint = 0, size_t nr_var_hint = 0 );
+
+        /// Destructor        
         virtual ~FactorGraph() {}
 
         /// Clone *this (virtual copy constructor)
@@ -74,21 +117,22 @@ class FactorGraph {
         /// Create (virtual default constructor)
         virtual FactorGraph* create() const { return new FactorGraph(*this); }
 
-        // aliases
-        Var & var(size_t i) { return vars[i]; }
-        /// Get const reference to i'th variable
-        const Var & var(size_t i) const { return vars[i]; }
-        /// Get const reference to I'th factor
+        /// Returns const reference to i'th variable
+        const Var & var(size_t i) const { return _vars[i]; }
+        /// Returns const reference to all factors
+        const std::vector<Var> & vars() const { return _vars; }
+        /// Returns reference to I'th factor
         Factor & factor(size_t I) { return _factors[I]; }
-        /// Get const reference to I'th factor
+        /// Returns const reference to I'th factor
         const Factor & factor(size_t I) const { return _factors[I]; }
-        /// Get const reference to all factors
+        /// Returns const reference to all factors
         const std::vector<Factor> & factors() const { return _factors; }
 
-        /// Get number of variables
-        size_t nrVars() const { return vars.size(); }
-        /// Get number of factors
-        size_t nrFactors() const { return _factors.size(); }
+        /// Returns number of variables
+        size_t nrVars() const { return vars().size(); }
+        /// Returns number of factors
+        size_t nrFactors() const { return factors().size(); }
+        /// Calculates number of edges
         size_t nrEdges() const { return G.nrEdges(); }
 
         /// Provides read access to neighbors of variable
@@ -108,14 +152,14 @@ class FactorGraph {
         /// Provides full access to neighbor of factor
         Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
 
-        /// Get index of variable n
+        /// Returns the index of a particular variable
         size_t findVar( const Var & n ) const {
-            size_t i = find( vars.begin(), vars.end(), n ) - vars.begin();
+            size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
             assert( i != nrVars() );
             return i;
         }
 
-        /// Get set of indexes for set of variables
+        /// Returns a set of indexes corresponding to a set of variables
         std::set<size_t> findVars( VarSet &ns ) const {
             std::set<size_t> indexes;
             for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
@@ -123,7 +167,7 @@ class FactorGraph {
             return indexes;
         }
 
-        /// Get index of first factor involving ns
+        /// Returns index of the first factor that depends on the variables
         size_t findFactor(const VarSet &ns) const {
             size_t I;
             for( I = 0; I < nrFactors(); I++ )
@@ -177,38 +221,60 @@ class FactorGraph {
         /// Restore all factors to the backup copies
         virtual void restoreFactors();
 
+        /// Returns true if the FactorGraph is connected
         bool isConnected() const { return G.isConnected(); }
+
+        /// Returns true if the FactorGraph is a tree
         bool isTree() const { return G.isTree(); }
 
-        friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
-        friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
+        /// Returns true if each factor depends on at most two variables
+        bool isPairwise() const;
 
+        /// Returns true if each variable has only two possible values
+        bool isBinary() const;
+
+        /// Reads a FactorGraph from a file
         void ReadFromFile(const char *filename);
+
+        /// Writes a FactorGraph to a file
         void WriteToFile(const char *filename) const;
+
+        /// Writes a FactorGraph to a GraphViz .dot file
         void printDot( std::ostream& os ) const;
         
+        /// Returns the cliques in this FactorGraph
         std::vector<VarSet> Cliques() const;
 
-        // Clamp variable v_i to value state (i.e. multiply with a Kronecker delta \f$\delta_{x_{v_i},x}\f$);
-        // This version changes the factor graph structure and thus returns a newly constructed FactorGraph
-        // and keeps the current one constant, contrary to clamp()
+        /// Clamp variable v_i to value state (i.e. multiply with a Kronecker delta \f$\delta_{x_{v_i},x}\f$);
+        /** This version changes the factor graph structure and thus returns a newly constructed FactorGraph
+         *  and keeps the current one constant, contrary to clamp()
+         */
         FactorGraph clamped( const Var & v_i, size_t x ) const;
 
+        /// Returns a copy of *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
         FactorGraph maximalFactors() const;
 
-        bool isPairwise() const;
-        bool isBinary() const;
-
+        /// Makes a backup of the I'th Factor
         void restoreFactor( size_t I );
+
+        /// Restores the I'th Factor from the backup (it should be backed up first)
         void backupFactor( size_t I );
-        void restoreFactors( const VarSet &ns );
+
+        /// Makes a backup of all factors connected to a set of variables
         void backupFactors( const VarSet &ns );
+        /// Restores all factors connected to a set of variables from their backups
+        void restoreFactors( const VarSet &ns );
+
+        // Friends
+        friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
+        friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
+
+    private:
         /// Part of constructors (creates edges, neighbors and adjacency matrix)
         void constructGraph( size_t nrEdges );
 };
 
 
-// assumes that the set of variables in [var_begin,var_end) is the union of the variables in the factors in [fact_begin, fact_end)
 template<typename FactorInputIterator, typename VarInputIterator>
 FactorGraph::FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint, size_t nr_var_hint ) : G(), _backup() {
     // add factors
@@ -220,9 +286,9 @@ FactorGraph::FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fac
     }
 
     // add variables
-    vars.reserve( nr_var_hint );
+    _vars.reserve( nr_var_hint );
     for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
-        vars.push_back( *p1 );
+        _vars.push_back( *p1 );
 
     // create graph structure
     constructGraph( nrEdges );
index 7401e46..a21ea7c 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class HAK.
+
+
 #ifndef __defined_libdai_hak_h
 #define __defined_libdai_hak_h
 
@@ -34,7 +38,7 @@
 namespace dai {
 
 
-/// HAK provides an implementation of the single and double-loop algorithms by Heskes, Albers and Kappen
+/// Approximate inference algorithm: implementation of single-loop ("Generalized Belief Propagation") and double-loop algorithms by Heskes, Albers and Kappen
 class HAK : public DAIAlgRG {
     private:
         std::vector<Factor>                _Qa;
@@ -47,38 +51,43 @@ class HAK : public DAIAlgRG {
         size_t _iters;
 
     public:
+        /// Parameters of this inference algorithm
         struct Properties {
+            /// Enumeration of possible cluster choices
+            DAI_ENUM(ClustersType,MIN,DELTA,LOOP)
+
+            /// Verbosity
             size_t verbose;
+
+            /// Maximum number of iterations
             size_t maxiter;
+
+            /// Tolerance
             double tol;
+
+            /// Damping constant
             double damping;
-            DAI_ENUM(ClustersType,MIN,DELTA,LOOP)
+
+            /// How to choose the clusters
             ClustersType clusters;
+
+            /// Use single-loop (GBP) or double-loop (HAK)
             bool doubleloop;
+
+            /// Depth of loops (only relevant for clusters == ClustersType::LOOP)
             size_t loopdepth;
         } props;
-        /// Name of this inference method
+
+        /// Name of this inference algorithm
         static const char *Name;
 
     public:
         /// Default constructor
         HAK() : DAIAlgRG(), _Qa(), _Qb(), _muab(), _muba(), _maxdiff(0.0), _iters(0U), props() {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        HAK( const FactorGraph &fg, const PropertySet &opts );
-
-        /// Construct from RegionGraph rg and PropertySet opts
-        HAK( const RegionGraph &rg, const PropertySet &opts );
-
         /// Copy constructor
         HAK( const HAK &x ) : DAIAlgRG(x), _Qa(x._Qa), _Qb(x._Qb), _muab(x._muab), _muba(x._muba), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
 
-        /// Clone *this (virtual copy constructor)
-        virtual HAK* clone() const { return new HAK(*this); }
-
-        /// Create (virtual default constructor)
-        virtual HAK* create() const { return new HAK(); }
-
         /// Assignment operator
         HAK& operator=( const HAK &x ) {
             if( this != &x ) {
@@ -94,37 +103,32 @@ class HAK : public DAIAlgRG {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
+        /// Construct from FactorGraph fg and PropertySet opts
+        HAK( const FactorGraph &fg, const PropertySet &opts );
 
-        /// Get single node belief
-        virtual Factor belief( const Var &n ) const;
+        /// Construct from RegionGraph rg and PropertySet opts
+        HAK( const RegionGraph &rg, const PropertySet &opts );
 
-        /// Get general belief
-        virtual Factor belief( const VarSet &ns ) const;
 
-        /// Get all beliefs
+        /// @name General InfAlg interface
+        //@{
+        virtual HAK* clone() const { return new HAK(*this); }
+        virtual HAK* create() const { return new HAK(); }
+        virtual std::string identify() const;
+        virtual Factor belief( const Var &n ) const;
+        virtual Factor belief( const VarSet &ns ) const;
         virtual std::vector<Factor> beliefs() const;
-
-        /// Get log partition sum
         virtual Real logZ() const;
-
-        /// Clear messages and beliefs
         virtual void init();
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
         virtual void init( const VarSet &ns );
-
-        /// The actual approximate inference algorithm
         virtual double run();
-
-        /// Return maximum difference between single node beliefs in the last pass
         virtual double maxDiff() const { return _maxdiff; }
-
-        /// Return number of passes over the factorgraph
         virtual size_t Iterations() const { return _iters; }
+        //@}
 
 
+        /// @name Additional interface specific for HAK
+        //@{ 
         Factor & muab( size_t alpha, size_t _beta ) { return _muab[alpha][_beta]; }
         Factor & muba( size_t alpha, size_t _beta ) { return _muba[alpha][_beta]; }
         const Factor& Qa( size_t alpha ) const { return _Qa[alpha]; };
@@ -132,14 +136,15 @@ class HAK : public DAIAlgRG {
 
         double doGBP();
         double doDoubleLoop();
-
-        void setProperties( const PropertySet &opts );
-        PropertySet getProperties() const;
-        std::string printProperties() const;
+        //@}
 
     private:
         void constructMessages();
         void findLoopClusters( const FactorGraph &fg, std::set<VarSet> &allcl, VarSet newcl, const Var & root, size_t length, VarSet vars );
+
+        void setProperties( const PropertySet &opts );
+        PropertySet getProperties() const;
+        std::string printProperties() const;
 };
 
 
index 9193d5b..8665a6a 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines the IndexFor, MultiFor, Permute and State classes
+
+
 #ifndef __defined_libdai_index_h
 #define __defined_libdai_index_h
 
 namespace dai {
 
 
-    /// Tool for looping over the states of several variables.
-    /** The class IndexFor is an important tool for indexing of Factors.
-     *  Its usage can best be explained by an example.
-     *  Assume indexVars, forVars are two VarSets.
-     *  Then the following code:
-     *  \code
-     *      IndexFor i( indexVars, forVars );
-     *      for( ; i >= 0; ++i ) {
-     *          // use long(i)
-     *      }
-     *  \endcode
-     *  loops over all joint states of the variables in forVars,
-     *  and (long)i is equal to the linear index of the corresponding
-     *  state of indexVars, where the variables in indexVars that are
-     *  not in forVars assume their zero'th value.
-     */
-    class IndexFor {
-        private:
-            /// The current linear index corresponding to the state of indexVars
-            long                _index;
-
-            /// For each variable in forVars, the amount of change in _index
-            std::vector<long>   _sum;
-
-            /// For each variable in forVars, the current state
-            std::vector<size_t> _count;
-            
-            /// For each variable in forVars, its number of possible values
-            std::vector<size_t> _dims;
-
-        public:
-            /// Default constructor
-            IndexFor() { 
-                _index = -1; 
-            }
+/// Tool for looping over the states of several variables.
+/** The class IndexFor is an important tool for indexing Factor entries.
+ *  Its usage can best be explained by an example.
+ *  Assume indexVars, forVars are both VarSets.
+ *  Then the following code:
+ *  \code
+ *      IndexFor i( indexVars, forVars );
+ *      for( ; i >= 0; ++i ) {
+ *          // use long(i)
+ *      }
+ *  \endcode
+ *  loops over all joint states of the variables in forVars,
+ *  and (long)i is equal to the linear index of the corresponding
+ *  state of indexVars, where the variables in indexVars that are
+ *  not in forVars assume their zero'th value.
+ */
+class IndexFor {
+    private:
+        /// The current linear index corresponding to the state of indexVars
+        long                _index;
+
+        /// For each variable in forVars, the amount of change in _index
+        std::vector<long>   _sum;
 
-            /// Constructor
-            IndexFor( const VarSet& indexVars, const VarSet& forVars ) : _count( forVars.size(), 0 ) {
-                long sum = 1;
+        /// For each variable in forVars, the current state
+        std::vector<size_t> _count;
+        
+        /// For each variable in forVars, its number of possible values
+        std::vector<size_t> _dims;
+
+    public:
+        /// Default constructor
+        IndexFor() { 
+            _index = -1; 
+        }
 
-                _dims.reserve( forVars.size() );
-                _sum.reserve( forVars.size() );
+        /// Constructor
+        IndexFor( const VarSet& indexVars, const VarSet& forVars ) : _count( forVars.size(), 0 ) {
+            long sum = 1;
 
-                VarSet::const_iterator j = forVars.begin();
-                for( VarSet::const_iterator i = indexVars.begin(); i != indexVars.end(); ++i ) {
-                    for( ; j != forVars.end() && *j <= *i; ++j ) {
-                        _dims.push_back( j->states() );
-                        _sum.push_back( (*i == *j) ? sum : 0 );
-                    }
-                    sum *= i->states();
-                }
-                for( ; j != forVars.end(); ++j ) {
+            _dims.reserve( forVars.size() );
+            _sum.reserve( forVars.size() );
+
+            VarSet::const_iterator j = forVars.begin();
+            for( VarSet::const_iterator i = indexVars.begin(); i != indexVars.end(); ++i ) {
+                for( ; j != forVars.end() && *j <= *i; ++j ) {
                     _dims.push_back( j->states() );
-                    _sum.push_back( 0 );
+                    _sum.push_back( (*i == *j) ? sum : 0 );
                 }
-                _index = 0;
+                sum *= i->states();
+            }
+            for( ; j != forVars.end(); ++j ) {
+                _dims.push_back( j->states() );
+                _sum.push_back( 0 );
             }
+            _index = 0;
+        }
 
-            /// Copy constructor
-            IndexFor( const IndexFor & ind ) : _index(ind._index), _sum(ind._sum), _count(ind._count), _dims(ind._dims) {}
+        /// Copy constructor
+        IndexFor( const IndexFor & ind ) : _index(ind._index), _sum(ind._sum), _count(ind._count), _dims(ind._dims) {}
 
-            /// Assignment operator
-            IndexFor& operator=( const IndexFor &ind ) {
-                if( this != &ind ) {
-                    _index = ind._index;
-                    _sum = ind._sum;
-                    _count = ind._count;
-                    _dims = ind._dims;
-                }
-                return *this;
+        /// Assignment operator
+        IndexFor& operator=( const IndexFor &ind ) {
+            if( this != &ind ) {
+                _index = ind._index;
+                _sum = ind._sum;
+                _count = ind._count;
+                _dims = ind._dims;
             }
+            return *this;
+        }
 
-            /// Sets the index back to zero
-            IndexFor& clear() {
-                fill( _count.begin(), _count.end(), 0 );
-                _index = 0;
-                return( *this );
-            }
+        /// Sets the index back to zero
+        IndexFor& clear() {
+            fill( _count.begin(), _count.end(), 0 );
+            _index = 0;
+            return( *this );
+        }
 
-            /// Conversion to long
-            operator long () const { 
-                return( _index ); 
-            }
+        /// Conversion to long
+        operator long () const { 
+            return( _index ); 
+        }
 
-            /// Pre-increment operator
-            IndexFor& operator++ () {
-                if( _index >= 0 ) {
-                    size_t i = 0;
-
-                    while( i < _count.size() ) {
-                        _index += _sum[i];
-                        if( ++_count[i] < _dims[i] )
-                            break;
-                        _index -= _sum[i] * _dims[i];
-                        _count[i] = 0;
-                        i++;
-                    }
-
-                    if( i == _count.size() ) 
-                        _index = -1;
+        /// Pre-increment operator
+        IndexFor& operator++ () {
+            if( _index >= 0 ) {
+                size_t i = 0;
+
+                while( i < _count.size() ) {
+                    _index += _sum[i];
+                    if( ++_count[i] < _dims[i] )
+                        break;
+                    _index -= _sum[i] * _dims[i];
+                    _count[i] = 0;
+                    i++;
                 }
-                return( *this );
+
+                if( i == _count.size() ) 
+                    _index = -1;
             }
-    };
+            return( *this );
+        }
+};
 
 
 /// MultiFor makes it easy to perform a dynamic number of nested for loops.
 /** An example of the usage is as follows:
  *  \code
- *      std::vector<size_t> dims;
- *      dims.push_back( 3 );
- *      dims.push_back( 4 );
- *      dims.push_back( 5 );
- *      for( MultiFor s(dims); s.valid(); ++s )
- *          cout << "linear index: " << (size_t)s << " corresponds with indices " << s[0] << ", " << s[1] << ", " << s[2] << endl;
+ *  std::vector<size_t> dims;
+ *  dims.push_back( 3 );
+ *  dims.push_back( 4 );
+ *  dims.push_back( 5 );
+ *  for( MultiFor s(dims); s.valid(); ++s )
+ *      cout << "linear index: " << (size_t)s << " corresponds to indices " << s[0] << ", " << s[1] << ", " << s[2] << endl;
  *  \endcode
  *  which would be equivalent to:
  *  \code
@@ -159,7 +163,7 @@ namespace dai {
  *  for( size_t s0 = 0; s0 < 3; s0++ )
  *      for( size_t s1 = 0; s1 < 4; s1++ )
  *          for( size_t s2 = 0; s2 < 5; s++, s2++ )
- *              cout << "linear index: " << (size_t)s << " corresponds with indices " << s0 << ", " << s1 << ", " << s2 << endl;
+ *              cout << "linear index: " << (size_t)s << " corresponds to indices " << s0 << ", " << s1 << ", " << s2 << endl;
  *  \endcode
  */
 class MultiFor {
@@ -287,8 +291,9 @@ class Permute {
 };
 
 
-/// Contains the state of variables within a VarSet and useful things to do with this information.
-/// This is very similar to a MultiFor, but tailored for Vars and Varsets.
+/// Contains the joint state of variables within a VarSet and useful things to do with this information.
+/** This is very similar to a MultiFor, but tailored for Vars and Varsets.
+ */
 class State {
     private:
         typedef std::map<Var, size_t> states_type;
index db1ddd1..48a2c29 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class JTree
+
+
 #ifndef __defined_libdai_jtree_h
 #define __defined_libdai_jtree_h
 
 namespace dai {
 
 
+/// Exact inference algorithm using junction tree
 class JTree : public DAIAlgRG {
     private:
         std::vector<std::vector<Factor> >  _mes;
         double               _logZ;
 
     public:
-        DEdgeVec             RTree;     // rooted tree
+        /// Rooted tree
+        DEdgeVec             RTree;
+        
+        /// Outer region beliefs
         std::vector<Factor>  Qa;
+        
+        /// Inner region beliefs
         std::vector<Factor>  Qb;
+
+        /// Parameters of this inference algorithm
         struct Properties {
-            size_t verbose;
+            /// Enumeration of possible JTree updates
             DAI_ENUM(UpdateType,HUGIN,SHSH)
+
+            /// Verbosity
+            size_t verbose;
+
+            /// Type of updates
             UpdateType updates;
         } props;
-        /// Name of this inference method
+
+        /// Name of this inference algorithm
         static const char *Name;
 
     public:
         /// Default constructor
         JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
-
         /// Copy constructor
         JTree( const JTree &x ) : DAIAlgRG(x), _mes(x._mes), _logZ(x._logZ), RTree(x.RTree), Qa(x.Qa), Qb(x.Qb), props(x.props) {}
 
-        /// Clone *this (virtual copy constructor)
-        virtual JTree* clone() const { return new JTree(*this); }
-
-        /// Create (virtual default constructor)
-        virtual JTree* create() const { return new JTree(); }
-
         /// Assignment operator
         JTree& operator=( const JTree &x ) {
             if( this != &x ) {
@@ -86,53 +95,60 @@ class JTree : public DAIAlgRG {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
+        /// Construct from FactorGraph fg and PropertySet opts
+        JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
 
-        /// Get single node belief
-        virtual Factor belief( const Var &n ) const;
 
-        /// Get general belief
+        /// @name General InfAlg interface
+        //@{
+        virtual JTree* clone() const { return new JTree(*this); }
+        virtual JTree* create() const { return new JTree(); }
+        virtual std::string identify() const;
+        virtual Factor belief( const Var &n ) const;
         virtual Factor belief( const VarSet &ns ) const;
-
-        /// Get all beliefs
         virtual std::vector<Factor> beliefs() const;
-
-        /// Get log partition sum
         virtual Real logZ() const;
-
-        /// Clear messages and beliefs
         virtual void init() {}
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
         virtual void init( const VarSet &/*ns*/ ) {}
-
-        /// The actual approximate inference algorithm
         virtual double run();
-
-        /// Return maximum difference between single node beliefs in the last pass
         virtual double maxDiff() const { return 0.0; }
-
-        /// Return number of passes over the factorgraph
         virtual size_t Iterations() const { return 1UL; }
+        //@}
 
 
+        /// @name Additional interface specific for JTree
+        //@{ 
         void GenerateJT( const std::vector<VarSet> &Cliques );
 
+        /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }   
+        /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }   
 
+        /// Runs junction-tree with HUGIN updates
         void runHUGIN();
+
+        /// Runs junction-tree with Shafer-Shenoy updates
         void runShaferShenoy();
+
+        /// Finds an efficient tree for calculating the marginal of some variables
         size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
+
+        /// Calculates the marginal of a set of variables
         Factor calcMarginal( const VarSet& ns );
+        //@}
 
+    private:
         void setProperties( const PropertySet &opts );
         PropertySet getProperties() const;
         std::string printProperties() const;
 };
 
 
+/// Calculates upper bound to the treewidth of a FactorGraph
+/** \relates JTree
+ *  \return a pair (number of variables in largest clique, number of states in largest clique)
+ */
 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 
 
index 70f7c69..b160709 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class LC
+
+
 #ifndef __defined_libdai_lc_h
 #define __defined_libdai_lc_h
 
@@ -35,6 +39,7 @@
 namespace dai {
 
 
+/// Approximate inference algorithm "Loop Corrected Belief Propagation" by Mooij and Kappen
 class LC : public DAIAlgFG {
     private:
         std::vector<Factor>      _pancakes;      // used by all LC types (psi_I is stored in the pancake)
@@ -51,38 +56,52 @@ class LC : public DAIAlgFG {
         size_t                  _iters;
 
     public:
+        /// Parameters of this inference algorithm
         struct Properties {
+            /// Enumeration of possible ways to initialize the cavities
+            DAI_ENUM(CavityType,FULL,PAIR,PAIR2,UNIFORM)
+
+            /// Enumeration of different update schedules
+            DAI_ENUM(UpdateType,SEQFIX,SEQRND,NONE)
+
+            /// Verbosity
             size_t verbose;
+
+            /// Maximum number of iterations
             size_t maxiter;
+
+            /// Tolerance
             double tol;
+
+            /// Complete or partial reinit of cavity graphs?
             bool reinit;
+
+            /// Damping constant
             double damping;
-            DAI_ENUM(CavityType,FULL,PAIR,PAIR2,UNIFORM)
+
+            /// How to initialize the cavities
             CavityType cavity;
-            DAI_ENUM(UpdateType,SEQFIX,SEQRND,NONE)
+
+            /// What update schedule to use
             UpdateType updates;
+
+            /// Name of the algorithm used to initialize the cavity distributions
             std::string cavainame;      // FIXME: needs assignment operator?
+
+            /// Parameters for the algorithm used to initialize the cavity distributions
             PropertySet cavaiopts;      // FIXME: needs assignment operator?
         } props;
-        /// Name of this inference method
+
+        /// Name of this inference algorithm
         static const char *Name;
 
     public:
         /// Default constructor
         LC() : DAIAlgFG(), _pancakes(), _cavitydists(), _phis(), _beliefs(), _maxdiff(), _iters(), props() {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        LC( const FactorGraph &fg, const PropertySet &opts );
-
         /// Copy constructor
         LC( const LC &x ) : DAIAlgFG(x), _pancakes(x._pancakes), _cavitydists(x._cavitydists), _phis(x._phis), _beliefs(x._beliefs), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
 
-        /// Clone *this (virtual copy constructor)
-        virtual LC* clone() const { return new LC(*this); }
-
-        /// Create (virtual default constructor)
-        virtual LC* create() const { return new LC(); }
-
         /// Assignment operator
         LC& operator=( const LC &x ) {
             if( this != &x ) {
@@ -98,42 +117,29 @@ class LC : public DAIAlgFG {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
-
-        /// Get single node belief
-        virtual Factor belief( const Var &n ) const { return( _beliefs[findVar(n)] ); }
+        /// Construct from FactorGraph fg and PropertySet opts
+        LC( const FactorGraph &fg, const PropertySet &opts );
 
-        /// Get general belief
-        virtual Factor belief( const VarSet &/*ns*/ ) const {
-            DAI_THROW(NOT_IMPLEMENTED);
-            return Factor(); 
-        }
 
-        /// Get all beliefs
+        /// @name General InfAlg interface
+        //@{
+        virtual LC* clone() const { return new LC(*this); }
+        virtual LC* create() const { return new LC(); }
+        virtual std::string identify() const;
+        virtual Factor belief( const Var &n ) const { return( _beliefs[findVar(n)] ); }
+        virtual Factor belief( const VarSet &/*ns*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
         virtual std::vector<Factor> beliefs() const { return _beliefs; }
-
-        /// Get log partition sum
-        virtual Real logZ() const { 
-            DAI_THROW(NOT_IMPLEMENTED);
-            return 0.0; 
-        }
-
-        /// Clear messages and beliefs
+        virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
         virtual void init();
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
         virtual void init( const VarSet &/*ns*/ ) { init(); }
-
-        /// The actual approximate inference algorithm
         virtual double run();
-
-        /// Return maximum difference between single node beliefs in the last pass
         virtual double maxDiff() const { return _maxdiff; }
-
-        /// Return number of passes over the factorgraph
         virtual size_t Iterations() const { return _iters; }
+        //@}
 
+
+        /// @name Additional interface specific for LC
+        //@{ 
         double CalcCavityDist( size_t i, const std::string &name, const PropertySet &opts );
         double InitCavityDists( const std::string &name, const PropertySet &opts );
         long SetCavityDists( std::vector<Factor> &Q );
@@ -144,7 +150,9 @@ class LC : public DAIAlgFG {
         const Factor &belief (size_t i) const { return _beliefs[i]; };
         const Factor &pancake (size_t i) const { return _pancakes[i]; };
         const Factor &cavitydist (size_t i) const { return _cavitydists[i]; };
+        //@}
 
+    private:
         void setProperties( const PropertySet &opts );
         PropertySet getProperties() const;
         std::string printProperties() const;
index 185e80b..653204c 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class MF
+
+
 #ifndef __defined_libdai_mf_h
 #define __defined_libdai_mf_h
 
@@ -33,6 +37,7 @@
 namespace dai {
 
 
+/// Approximate inference algorithm "Mean Field"
 class MF : public DAIAlgFG {
     private:
         std::vector<Factor>  _beliefs;
@@ -42,33 +47,31 @@ class MF : public DAIAlgFG {
         size_t _iters;
 
     public:
+        /// Parameters of this inference algorithm
         struct Properties {
+            /// Verbosity
             size_t verbose;
+
+            /// Maximum number of iterations
             size_t maxiter;
+
+            /// Tolerance
             double tol;
+
+            /// Damping constant
             double damping;
         } props;
+
+        /// Name of this inference algorithm
         static const char *Name;
 
     public:
         /// Default constructor
         MF() : DAIAlgFG(), _beliefs(), _maxdiff(0.0), _iters(0U), props() {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        MF( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), _beliefs(), _maxdiff(0.0), _iters(0U), props() {
-            setProperties( opts );
-            construct();
-        }
-
         /// Copy constructor
         MF( const MF &x ) : DAIAlgFG(x), _beliefs(x._beliefs), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
 
-        /// Clone *this (virtual copy constructor)
-        virtual MF* clone() const { return new MF(*this); }
-
-        /// Create (virtual default constructor)
-        virtual MF* create() const { return new MF(); }
-
         /// Assignment operator
         MF& operator=( const MF &x ) {
             if( this != &x ) {
@@ -81,44 +84,40 @@ class MF : public DAIAlgFG {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
+        /// Construct from FactorGraph fg and PropertySet opts
+        MF( const FactorGraph &fg, const PropertySet &opts ) : DAIAlgFG(fg), _beliefs(), _maxdiff(0.0), _iters(0U), props() {
+            setProperties( opts );
+            construct();
+        }
 
-        /// Get single node belief
-        virtual Factor belief( const Var &n ) const;
 
-        /// Get general belief
+        /// @name General InfAlg interface
+        //@{
+        virtual MF* clone() const { return new MF(*this); }
+        virtual MF* create() const { return new MF(); }
+        virtual std::string identify() const;
+        virtual Factor belief( const Var &n ) const;
         virtual Factor belief( const VarSet &ns ) const;
-
-        /// Get all beliefs
         virtual std::vector<Factor> beliefs() const;
-
-        /// Get log partition sum
         virtual Real logZ() const;
-
-        /// Clear messages and beliefs
         virtual void init();
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
         virtual void init( const VarSet &ns );
-
-        /// The actual approximate inference algorithm
         virtual double run();
-
-        /// Return maximum difference between single node beliefs in the last pass
         virtual double maxDiff() const { return _maxdiff; }
-
-        /// Return number of passes over the factorgraph
         virtual size_t Iterations() const { return _iters; }
+        //@}
 
 
+        /// @name Additional interface specific for MF
+        //@{ 
+        Factor beliefV( size_t i ) const;
+        //@}
+        
+    private:
         void construct();
-
         void setProperties( const PropertySet &opts );
         PropertySet getProperties() const;
         std::string printProperties() const;
-
-        Factor beliefV( size_t i ) const;
 };
 
 
index a15b7b3..24a8354 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class MR
+
+
 #ifndef __defined_libdai_mr_h
 #define __defined_libdai_mr_h
 
@@ -37,6 +41,7 @@
 namespace dai {
 
 
+/// Approximate inference algorithm by Montanari and Rizzo
 class MR : public DAIAlgFG {
     private:
         bool supported;                                            // is the underlying factor graph supported?
@@ -60,32 +65,37 @@ class MR : public DAIAlgFG {
         size_t _iters;
 
     public:
+        /// Parameters of this inference algorithm
         struct Properties {
-            size_t verbose;
-            double tol;
+            /// Enumeration of different types of update equations
             DAI_ENUM(UpdateType,FULL,LINEAR)
+
+            /// Enumeration of different ways of initializing the cavity correlations
             DAI_ENUM(InitType,RESPPROP,CLAMPING,EXACT)
+
+            /// Verbosity
+            size_t verbose;
+
+            /// Tolerance
+            double tol;
+
+            /// Update equations
             UpdateType updates;
+
+            /// How to initialize the cavity correlations
             InitType inits;
         } props;
+
+        /// Name of this inference method
         static const char *Name;
 
     public:
         /// Default constructor
         MR() : DAIAlgFG(), supported(), con(), nb(), tJ(), theta(), M(), kindex(), cors(), N(), Mag(), _maxdiff(), _iters(), props() {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        MR( const FactorGraph &fg, const PropertySet &opts );
-
         /// Copy constructor
         MR( const MR &x ) : DAIAlgFG(x), supported(x.supported), con(x.con), nb(x.nb), tJ(x.tJ), theta(x.theta), M(x.M), kindex(x.kindex), cors(x.cors), N(x.N), Mag(x.Mag), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {}
 
-        /// Clone *this (virtual copy constructor)
-        virtual MR* clone() const { return new MR(*this); }
-
-        /// Create (virtual default constructor)
-        virtual MR* create() const { return new MR(); }
-
         /// Assignment operator
         MR& operator=( const MR &x ) {
             if( this != &x ) {
@@ -107,45 +117,32 @@ class MR : public DAIAlgFG {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
-
-        /// Get single node belief
-        virtual Factor belief( const Var &n ) const;
+        /// Construct from FactorGraph fg and PropertySet opts
+        MR( const FactorGraph &fg, const PropertySet &opts );
 
-        /// Get general belief
-        virtual Factor belief( const VarSet &/*ns*/ ) const { 
-            DAI_THROW(NOT_IMPLEMENTED);
-            return Factor(); 
-        }
 
-        /// Get all beliefs
+        /// @name General InfAlg interface
+        //@{
+        virtual MR* clone() const { return new MR(*this); }
+        virtual MR* create() const { return new MR(); }
+        virtual std::string identify() const;
+        virtual Factor belief( const Var &n ) const;
+        virtual Factor belief( const VarSet &/*ns*/ ) const { DAI_THROW(NOT_IMPLEMENTED); return Factor(); }
         virtual std::vector<Factor> beliefs() const;
-
-        /// Get log partition sum
-        virtual Real logZ() const { 
-            DAI_THROW(NOT_IMPLEMENTED);
-            return 0.0; 
-        }
-
-        /// Clear messages and beliefs
+        virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
         virtual void init() {}
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
-        virtual void init( const VarSet &/*ns*/ ) {
-            DAI_THROW(NOT_IMPLEMENTED);
-        }
-
-        /// The actual approximate inference algorithm
+        virtual void init( const VarSet &/*ns*/ ) { DAI_THROW(NOT_IMPLEMENTED); }
         virtual double run();
-
-        /// Return maximum difference between single node beliefs in the last pass
         virtual double maxDiff() const { return _maxdiff; }
-
-        /// Return number of passes over the factorgraph
         virtual size_t Iterations() const { return _iters; }
+        //@}
 
 
+        /// @name Additional interface specific for MR
+        //@{ 
+        //@}
+        
+    private:
         void init(size_t Nin, double *_w, double *_th);
         void makekindex();
         void init_cor();
index 7e3d62f..dbd434b 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines TProb<T> and Prob classes
+
+
 #ifndef __defined_libdai_prob_h
 #define __defined_libdai_prob_h
 
 namespace dai {
 
 
+/// Real number (alias for double, could be changed to long double if necessary)
 typedef double                  Real;
 
 template<typename T> class      TProb;
-typedef TProb<Real>             Prob;
 
-
-// predefine friends
-template<typename T> TProb<T> min( const TProb<T> &a, const TProb<T> &b );
-template<typename T> TProb<T> max( const TProb<T> &a, const TProb<T> &b );
+/// Represents a probability measure, with entries of type Real.
+typedef TProb<Real>             Prob;
 
 
-/// TProb<T> implements a probability vector of type T.
-/// T should be castable from and to double.
+/// Represents a probability measure on a finite outcome space (i.e., corresponding to a discrete random variable).
+/** It is implemented as a std::vector<T> but adds a convenient interface.
+ *  It is not necessarily normalized at all times.
+ *  \tparam T Should be castable from and to double.
+ */
 template <typename T> class TProb {
     private:
-        /// The entries
+        /// The probability measure
         std::vector<T> _p;
 
-    private:
-        /// Calculate x times log(x), or 0 if x == 0
-        Real xlogx( Real x ) const { return( x == 0.0 ? 0.0 : x * std::log(x)); }
-
     public:
-        /// NORMPROB means that the sum of all entries should be 1
-        /// NORMLINF means that the maximum absolute value of all entries should be 1
+        /// Enumerates different ways of normalizing a probability measure.
+        /** 
+         *  - NORMPROB means that the sum of all entries should be 1;
+         *  - NORMLINF means that the maximum absolute value of all entries should be 1.
+         */
         typedef enum { NORMPROB, NORMLINF } NormType;
-        /// DISTL1 is the L-1 distance (sum of absolute values of pointwise difference)
-        /// DISTLINF is the L-inf distance (maximum absolute value of pointwise difference)
-        /// DISTTV is the Total Variation distance
-        typedef enum { DISTL1, DISTLINF, DISTTV } DistType;
+        /// Enumerates different distance measures between probability measures.
+        /** 
+         *  - DISTL1 is the L-1 distance (sum of absolute values of pointwise difference);
+         *  - DISTLINF is the L-inf distance (maximum absolute value of pointwise difference);
+         *  - DISTTV is the Total Variation distance;
+         *  - DISTKL is the Kullback-Leibler distance.
+         */
+        typedef enum { DISTL1, DISTLINF, DISTTV, DISTKL } DistType;
         
         /// Default constructor
         TProb() : _p() {}
@@ -74,19 +82,19 @@ template <typename T> class TProb {
         /// Construct uniform distribution of given length
         explicit TProb( size_t n ) : _p(std::vector<T>(n, 1.0 / n)) {}
         
-        /// Construct with given length and initial value
+        /// Construct from given length and initial value
         TProb( size_t n, Real p ) : _p(n, (T)p) {}
         
-        /// Construct with given length and initial array
+        /// Construct from given length and initial array
         TProb( size_t n, const Real* p ) : _p(p, p + n ) {}
         
-        /// Provide read access to _p
+        /// Returns a const reference to the probability vector
         const std::vector<T> & p() const { return _p; }
 
-        /// Provide full access to _p
+        /// Returns a reference to the probability vector
         std::vector<T> & p() { return _p; }
         
-        /// Provide read access to ith element of _p
+        /// Returns a copy of the i'th probability entry
         T operator[]( size_t i ) const { 
 #ifdef DAI_DEBUG
             return _p.at(i);
@@ -95,36 +103,35 @@ template <typename T> class TProb {
 #endif
         }
         
-        /// Provide full access to ith element of _p
+        /// Returns a reference to the i'th probability entry
         T& operator[]( size_t i ) { return _p[i]; }
 
-        /// Set all elements to x
+        /// Sets all elements to x
         TProb<T> & fill(T x) { 
             std::fill( _p.begin(), _p.end(), x );
             return *this;
         }
 
-        /// Set all elements to iid random numbers from uniform(0,1) distribution
+        /// Sets all elements to i.i.d. random numbers from a uniform[0,1) distribution
         TProb<T> & randomize() { 
             std::generate(_p.begin(), _p.end(), rnd_uniform);
             return *this;
         }
 
-        /// Return size
+        /// Returns number of elements
         size_t size() const {
             return _p.size();
         }
 
-        /// Make entries zero if (Real) absolute value smaller than epsilon
-        TProb<T>& makeZero (Real epsilon) {
+        /// Sets entries that are smaller than epsilon to zero
+        TProb<T>& makeZero( Real epsilon ) {
             for( size_t i = 0; i < size(); i++ )
-                if( fabs((Real)_p[i]) < epsilon )
+                if( fabs(_p[i]) < epsilon )
                     _p[i] = 0;
-//            std::replace_if( _p.begin(), _p.end(), fabs((Real)boost::lambda::_1) < epsilon, 0.0 );
             return *this;
         }
 
-        /// Make entries epsilon if they are smaller than epsilon
+        /// Sets entries that are smaller than epsilon to epsilon
         TProb<T>& makePositive (Real epsilon) {
             for( size_t i = 0; i < size(); i++ )
                 if( (0 < (Real)_p[i]) && ((Real)_p[i] < epsilon) )
@@ -132,20 +139,20 @@ template <typename T> class TProb {
             return *this;
         }
 
-        /// Multiplication with T x
+        /// Multiplies each entry with x
         TProb<T>& operator*= (T x) {
             std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::multiplies<T>(), x) );
             return *this;
         }
 
-        /// Return product of *this with T x
+        /// Returns product of *this with x
         TProb<T> operator* (T x) const {
             TProb<T> prod( *this );
             prod *= x;
             return prod;
         }
 
-        /// Division by T x
+        /// Divides each entry by x
         TProb<T>& operator/= (T x) {
 #ifdef DAI_DEBUG
             assert( x != 0.0 );
@@ -154,33 +161,33 @@ template <typename T> class TProb {
             return *this;
         }
 
-        /// Return quotient of *this and T x
+        /// Returns quotient of *this and x
         TProb<T> operator/ (T x) const {
             TProb<T> quot( *this );
             quot /= x;
             return quot;
         }
 
-        /// addition of x
+        /// Adds x to each entry
         TProb<T>& operator+= (T x) {
             std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::plus<T>(), x ) );
             return *this;
         }
 
-        /// Return sum of *this with T x
+        /// Returns sum of *this and x
         TProb<T> operator+ (T x) const {
             TProb<T> sum( *this );
             sum += x;
             return sum;
         }
 
-        /// Difference by T x 
+        /// Subtracts x from each entry
         TProb<T>& operator-= (T x) {
             std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::minus<T>(), x ) );
             return *this;
         }
 
-        /// Return difference of *this and T x
+        /// Returns difference of *this and x
         TProb<T> operator- (T x) const {
             TProb<T> diff( *this );
             diff -= x;
@@ -226,15 +233,6 @@ template <typename T> class TProb {
             return *this;
         }
         
-        /// Pointwise subtraction of q
-        TProb<T>& operator-= (const TProb<T> & q) {
-#ifdef DAI_DEBUG
-            assert( size() == q.size() );
-#endif
-            std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::minus<T>() );
-            return *this;
-        }
-        
         /// Return sum of *this and q
         TProb<T> operator+ (const TProb<T> & q) const {
 #ifdef DAI_DEBUG
@@ -245,6 +243,15 @@ template <typename T> class TProb {
             return sum;
         }
         
+        /// Pointwise subtraction of q
+        TProb<T>& operator-= (const TProb<T> & q) {
+#ifdef DAI_DEBUG
+            assert( size() == q.size() );
+#endif
+            std::transform( _p.begin(), _p.end(), q._p.begin(), _p.begin(), std::minus<T>() );
+            return *this;
+        }
+        
         /// Return *this minus q
         TProb<T> operator- (const TProb<T> & q) const {
 #ifdef DAI_DEBUG
@@ -255,7 +262,7 @@ template <typename T> class TProb {
             return diff;
         }
 
-        /// Pointwise division by q (division by zero yields zero)
+        /// Pointwise division by q, where division by zero yields zero
         TProb<T>& operator/= (const TProb<T> & q) {
 #ifdef DAI_DEBUG
             assert( size() == q.size() );
@@ -269,7 +276,7 @@ template <typename T> class TProb {
             return *this;
         }
         
-        /// Pointwise division by q (division by zero yields infinity)
+        /// Pointwise division by q, where division by zero yields infinity
         TProb<T>& divide (const TProb<T> & q) {
 #ifdef DAI_DEBUG
             assert( size() == q.size() );
@@ -278,7 +285,7 @@ template <typename T> class TProb {
             return *this;
         }
         
-        /// Return quotient of *this with q
+        /// Returns quotient of *this with q
         TProb<T> operator/ (const TProb<T> & q) const {
 #ifdef DAI_DEBUG
             assert( size() == q.size() );
@@ -288,7 +295,7 @@ template <typename T> class TProb {
             return quot;
         }
 
-        /// Return pointwise inverse
+        /// Returns pointwise inverse
         TProb<T> inverse(bool zero = false) const {
             TProb<T> inv;
             inv._p.reserve( size() );
@@ -305,21 +312,21 @@ template <typename T> class TProb {
             return inv;
         }
 
-        /// Return *this to the power of a (pointwise)
+        /// Raises elements to the power a
         TProb<T>& operator^= (Real a) {
             if( a != 1.0 )
                 std::transform( _p.begin(), _p.end(), _p.begin(), std::bind2nd( std::ptr_fun<T, Real, T>(std::pow), a) );
             return *this;
         }
 
-        /// Pointwise power of a
+        /// Returns *this raised to the power a
         TProb<T> operator^ (Real a) const {
             TProb<T> power(*this);
             power ^= a;
             return power;
         }
 
-        /// Pointwise signum
+        /// Returns pointwise signum
         TProb<T> sgn() const {
             TProb<T> x;
             x._p.reserve( size() );
@@ -334,7 +341,7 @@ template <typename T> class TProb {
             return x;
         }
 
-        /// Pointwise absolute value
+        /// Returns pointwise absolute value
         TProb<T> abs() const {
             TProb<T> x;
             x._p.reserve( size() );
@@ -343,48 +350,48 @@ template <typename T> class TProb {
             return x;
         }
 
-        /// Pointwise exp
+        /// Applies exp pointwise
         const TProb<T>& takeExp() {
             std::transform( _p.begin(), _p.end(), _p.begin(),  std::ptr_fun<T, T>(std::exp) );
             return *this;
         }
 
-        /// Pointwise log
+        /// Applies log pointwise
         const TProb<T>& takeLog() {
             std::transform( _p.begin(), _p.end(), _p.begin(),  std::ptr_fun<T, T>(std::log) );
             return *this;
         }
 
-        /// Pointwise log (or 0 if == 0)
+        /// Applies log pointwise (defining log(0)=0)
         const TProb<T>& takeLog0()  {
             for( size_t i = 0; i < size(); i++ )
                _p[i] = ( (_p[i] == 0.0) ? 0.0 : std::log( _p[i] ) );
             return *this;
         }
 
-        /// Pointwise exp
+        /// Returns pointwise exp
         TProb<T> exp() const {
             TProb<T> e(*this);
             e.takeExp();
             return e;
         }
 
-        /// Pointwise log
+        /// Returns pointwise log
         TProb<T> log() const {
             TProb<T> l(*this);
             l.takeLog();
             return l;
         }
 
-        /// Pointwise log (or 0 if == 0)
+        /// Returns pointwise log (defining log(0)=0)
         TProb<T> log0() const {
             TProb<T> l0(*this);
             l0.takeLog0();
             return l0;
         }
 
-        /// Return distance of p and q
-        friend Real dist( const TProb<T> & p, const TProb<T> & q, DistType dt ) {
+        /// Returns distance of p and q, measured using dt
+        friend Real dist( const TProb<T> &p, const TProb<T> &q, DistType dt ) {
 #ifdef DAI_DEBUG
             assert( p.size() == q.size() );
 #endif
@@ -408,33 +415,23 @@ template <typename T> class TProb {
                         result += fabs((Real)p[i] - (Real)q[i]);
                     result *= 0.5;
                     break;
-            }
-            return result;
-        }
 
-        /// Return Kullback-Leibler distance with q
-        friend Real KL_dist( const TProb<T> & p, const TProb<T> & q ) {
-#ifdef DAI_DEBUG
-            assert( p.size() == q.size() );
-#endif
-            Real result = 0.0;
-            for( size_t i = 0; i < p.size(); i++ ) {
-                if( (Real) p[i] != 0.0 ) {
-                    Real p_i = p[i];
-                    Real q_i = q[i];
-                    result += p_i * (std::log(p_i) - std::log(q_i));
-                }
+                case DISTKL:
+                    for( size_t i = 0; i < p.size(); i++ ) {
+                        if( p[i] != 0.0 )
+                            result += p[i] * (std::log(p[i]) - std::log(q[i]));
+                    }
             }
             return result;
         }
 
-        /// Return sum of all entries
+        /// Returns sum of all entries
         T totalSum() const {
             T Z = std::accumulate( _p.begin(),  _p.end(), (T)0 );
             return Z;
         }
 
-        /// Converts entries to Real and returns maximum absolute value
+        /// Returns maximum absolute value of entries
         T maxAbs() const {
             T Z = 0;
             for( size_t i = 0; i < size(); i++ ) {
@@ -445,19 +442,19 @@ template <typename T> class TProb {
             return Z;
         }
 
-        /// Returns maximum value
+        /// Returns maximum value of entries
         T maxVal() const {
             T Z = *std::max_element( _p.begin(), _p.end() );
             return Z;
         }
 
-        /// Returns minimum value
+        /// Returns minimum value of entries
         T minVal() const {
             T Z = *std::min_element( _p.begin(), _p.end() );
             return Z;
         }
 
-        /// Normalize, using the specified norm
+        /// Normalizes using the specified norm
         T normalize( NormType norm = NORMPROB ) {
             T Z = 0.0;
             if( norm == NORMPROB )
@@ -471,7 +468,7 @@ template <typename T> class TProb {
             return Z;
         }
 
-        /// Return normalized copy of *this, using the specified norm
+        /// Returns normalized copy of *this, using the specified norm
         TProb<T> normalized( NormType norm = NORMPROB ) const {
             TProb<T> result(*this);
             result.normalize( norm );
@@ -501,21 +498,21 @@ template <typename T> class TProb {
             return S;
         }
 
-        /// Returns TProb<T> containing the pointwise minimum of a and b (which should have equal size)
-        friend TProb<T> min <> ( const TProb<T> &a, const TProb<T> &b );
-
-        /// Returns TProb<T> containing the pointwise maximum of a and b (which should have equal size)
-        friend TProb<T> max <> ( const TProb<T> &a, const TProb<T> &b );
-
+        /// Writes a TProb<T> to an output stream
         friend std::ostream& operator<< (std::ostream& os, const TProb<T>& P) {
             os << "[";
             std::copy( P._p.begin(), P._p.end(), std::ostream_iterator<T>(os, " ") );
             os << "]";
             return os;
         }
+
+    private:
+        /// Returns x*log(x), or 0 if x == 0
+        Real xlogx( Real x ) const { return( x == 0.0 ? 0.0 : x * std::log(x)); }
 };
 
 
+/// Returns TProb<T> containing the pointwise minimum of a and b (which should have equal size)
 template<typename T> TProb<T> min( const TProb<T> &a, const TProb<T> &b ) {
     assert( a.size() == b.size() );
     TProb<T> result( a.size() );
@@ -528,6 +525,7 @@ template<typename T> TProb<T> min( const TProb<T> &a, const TProb<T> &b ) {
 }
 
 
+/// Returns TProb<T> containing the pointwise maximum of a and b (which should have equal size)
 template<typename T> TProb<T> max( const TProb<T> &a, const TProb<T> &b ) {
     assert( a.size() == b.size() );
     TProb<T> result( a.size() );
index f77dc53..91698d4 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines the Property and PropertySet classes
+
+
 #ifndef __defined_libdai_properties_h
 #define __defined_libdai_properties_h
 
 namespace dai {
 
 
+/// Type of the key of a Property
 typedef std::string PropertyKey;
+
+/// Type of the value of a Property
 typedef boost::any  PropertyValue;
+
+/// A Property is a pair of a key and a corresponding value
 typedef std::pair<PropertyKey, PropertyValue> Property;
 
 
-/// Sends a Property object to an output stream
+/// Writes a Property object to an output stream
 std::ostream& operator<< (std::ostream & os, const Property & p);
 
 
-/// The PropertySet class represents a set of properties
-class PropertySet : public std::map<PropertyKey, PropertyValue> {
+/// Represents a set of properties, mapping keys (of type PropertyKey) to values (of type PropertyValue)
+class PropertySet : private std::map<PropertyKey, PropertyValue> {
     public:
         /// Gets a property
         const PropertyValue & Get(const PropertyKey &key) const { 
@@ -59,7 +68,7 @@ class PropertySet : public std::map<PropertyKey, PropertyValue> {
             return x->second; 
         }
 
-        /// Sets a property 
+        /// Sets a property
         PropertySet & Set(const PropertyKey &key, const PropertyValue &val) { this->operator[](key) = val; return *this; }
 
         /// Gets a property, casted as ValueType
@@ -74,7 +83,7 @@ class PropertySet : public std::map<PropertyKey, PropertyValue> {
             }
         }
 
-        /// Converts a property from string to ValueType, if necessary
+        /// Converts a property from string to ValueType (if necessary)
         template<typename ValueType>
         void ConvertTo(const PropertyKey &key) { 
             PropertyValue val = Get(key);
@@ -123,14 +132,12 @@ class PropertySet : public std::map<PropertyKey, PropertyValue> {
         /// Shorthand for (temporarily) adding properties, e.g. PropertySet p()("method","BP")("verbose",1)("tol",1e-9)
         PropertySet operator()(const PropertyKey &key, const PropertyValue &val) const { PropertySet copy = *this; return copy.Set(key,val); }
 
-        /// Check if a property with given key exists
+        /// Check if a property with the given key exists
         bool hasKey(const PropertyKey &key) const { PropertySet::const_iterator x = find(key); return (x != this->end()); }
 
-        /// Sends a PropertySet object to an output stream
+        // Friends
         friend std::ostream& operator<< (std::ostream & os, const PropertySet & ps);
-
-        /// Reads a PropertySet object from an input stream
-        friend std::istream& operator >> (std::istream& is, PropertySet & ps);
+        friend std::istream& operator>> (std::istream& is, PropertySet & ps);
 };
 
 
index aa4829f..7ab8d4b 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines classes Region, FRegion and RegionGraph
+
+
 #ifndef __defined_libdai_regiongraph_h
 #define __defined_libdai_regiongraph_h
 
@@ -100,11 +104,16 @@ class FRegion : public Factor {
 /// A RegionGraph is a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region)
 class RegionGraph : public FactorGraph {
     public:
+        /// Stores the neighborhood structure
         BipartiteGraph          G;
+
+        /// The outer regions (corresponding to nodes of type 1)
         std::vector<FRegion>    ORs;
+
+        /// The inner regions (corresponding to nodes of type 2)
         std::vector<Region>     IRs;
 
-        /// Give back the OR index that corresponds to a factor index
+        /// Stores for each factor index the index of the outer region it belongs to
         std::vector<size_t>     fac2OR;
 
 
@@ -199,7 +208,7 @@ class RegionGraph : public FactorGraph {
         /// Recompute all outer regions involving factor I
         void RecomputeOR( size_t I );
 
-        /// Send RegionGraph to output stream
+        // Friends
         friend std::ostream & operator << ( std::ostream & os, const RegionGraph & rg );
 };
 
diff --git a/include/dai/smallset.h b/include/dai/smallset.h
new file mode 100644 (file)
index 0000000..b5e4121
--- /dev/null
@@ -0,0 +1,227 @@
+/*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
+    Radboud University Nijmegen, The Netherlands /
+    Max Planck Institute for Biological Cybernetics, Germany
+
+    Copyright (C) 2002  Martijn Leisink  [martijn@mbfys.kun.nl]
+    Radboud University Nijmegen, The Netherlands
+
+    This file is part of libDAI.
+
+    libDAI is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    libDAI is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with libDAI; if not, write to the Free Software
+    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+*/
+
+
+/// \file
+/// \brief Defines smallSet<T> class
+
+
+#ifndef __defined_libdai_smallset_h
+#define __defined_libdai_smallset_h
+
+
+#include <vector>
+#include <algorithm>
+
+
+namespace dai {
+
+
+/// Represents a set (optimized for a small number of elements).
+/** For sets consisting of a small number of elements, an implementation using
+ *  an ordered std::vector<T> is faster than an implementation using std::set<T>.
+ *  The elements should be less-than-comparable.
+ */
+template <typename T>
+class smallSet {
+    private:
+        /// The elements in this set
+        std::vector<T> _elements;
+
+    public:
+        /// Default constructor
+        smallSet() : _elements() {}
+
+        /// Construct a smallSet with one element
+        smallSet( const T &n ) : _elements() { 
+            _elements.push_back( n );
+        }
+
+        /// Construct a smallSet with two elements
+        smallSet( const T &n1, const T &n2 ) { 
+            if( n1 < n2 ) {
+                _elements.push_back( n1 );
+                _elements.push_back( n2 );
+            } else if( n2 < n1 ) {
+                _elements.push_back( n2 );
+                _elements.push_back( n1 );
+            } else
+                _elements.push_back( n1 );
+        }
+
+        /// Construct a smallSet from a range of iterators.
+        /** \tparam Iterator Iterator with value_type T.
+         *  \param begin Points to first element to be added.
+         *  \param end Points just beyond last element to be added.
+         *  \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
+         */
+        template <typename Iterator>
+        smallSet( Iterator begin, Iterator end, size_t sizeHint=0 ) {
+            _elements.reserve( sizeHint );
+            _elements.insert( _elements.begin(), begin, end );
+            std::sort( _elements.begin(), _elements.end() );
+            typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
+            _elements.erase( new_end, _elements.end() );
+        }
+
+        /// Copy constructor
+        smallSet( const smallSet &x ) : _elements( x._elements ) {}
+
+        /// Assignment operator
+        smallSet & operator=( const smallSet &x ) {
+            if( this != &x ) {
+                _elements = x._elements;
+            }
+            return *this;
+        }
+        
+        /// Setminus operator: returns all elements in *this, except those in ns
+        smallSet operator/ ( const smallSet& ns ) const {
+            smallSet res;
+            std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
+            return res;
+        }
+
+        /// Set-union operator: returns all elements in *this, plus those in ns
+        smallSet operator| ( const smallSet& ns ) const {
+            smallSet res;
+            std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
+            return res;
+        }
+
+        /// Set-intersection operator: returns all elements in *this that are also contained in ns
+        smallSet operator& ( const smallSet& ns ) const {
+            smallSet res;
+            std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
+            return res;
+        }
+        
+        /// Erases from *this all elements in ns
+        smallSet& operator/= ( const smallSet& ns ) {
+            return (*this = (*this / ns));
+        }
+
+        /// Erases one element
+        smallSet& operator/= ( const T& n ) { 
+            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
+            if( pos != _elements.end() )
+                if( *pos == n ) // found element, delete it
+                    _elements.erase( pos ); 
+            return *this; 
+        }
+
+        /// Adds to *this all elements in ns
+        smallSet& operator|= ( const smallSet& ns ) {
+            return( *this = (*this | ns) );
+        }
+
+        /// Adds one element
+        smallSet& operator|= ( const T& n ) {
+            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
+            if( pos == _elements.end() || *pos != n ) // insert it
+                _elements.insert( pos, n );
+            return *this;
+        }
+
+        /// Erases from *this all elements not in ns
+        smallSet& operator&= ( const smallSet& ns ) { 
+            return (*this = (*this & ns));
+        }
+
+        /// Returns true if *this is a subset of ns
+        bool operator<< ( const smallSet& ns ) const { 
+            return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
+        }
+
+        /// Returns true if ns is a subset of *this
+        bool operator>> ( const smallSet& ns ) const { 
+            return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
+        }
+
+        /// Returns true if *this and ns contain common elements
+        bool intersects( const smallSet& ns ) const { 
+            return( (*this & ns).size() > 0 ); 
+        }
+
+        /// Returns true if *this contains the element n
+        bool contains( const T& n ) const { 
+            return std::binary_search( _elements.begin(), _elements.end(), n );
+        }
+
+        /// Constant iterator over the elements
+        typedef typename std::vector<T>::const_iterator const_iterator;
+        /// Iterator over the elements
+        typedef typename std::vector<T>::iterator iterator;
+        /// Constant reverse iterator over the elements
+        typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
+        /// Reverse iterator over the elements
+        typedef typename std::vector<T>::reverse_iterator reverse_iterator;
+        
+        /// Returns iterator that points to the first element
+        iterator begin() { return _elements.begin(); }
+        /// Returns constant iterator that points to the first element
+        const_iterator begin() const { return _elements.begin(); }
+
+        /// Returns iterator that points beyond the last element
+        iterator end() { return _elements.end(); }
+        /// Returns constant iterator that points beyond the last element
+        const_iterator end() const { return _elements.end(); }
+
+        /// Returns reverse iterator that points to the last element
+        reverse_iterator rbegin() { return _elements.rbegin(); }
+        /// Returns constant reverse iterator that points to the last element
+        const_reverse_iterator rbegin() const { return _elements.rbegin(); }
+
+        /// Returns reverse iterator that points beyond the first element
+        reverse_iterator rend() { return _elements.rend(); }
+        /// Returns constant reverse iterator that points beyond the first element
+        const_reverse_iterator rend() const { return _elements.rend(); }
+
+        /// Returns number of elements
+        typename std::vector<T>::size_type size() const { return _elements.size(); }
+
+        /// Returns whether the smallSet is empty
+        bool empty() const { return _elements.size() == 0; }
+
+        /// Returns true if the two sets are identical
+        friend bool operator==( const smallSet &a, const smallSet &b ) {
+            return (a._elements == b._elements);
+        }
+
+        /// Returns true if the two sets are not identical
+        friend bool operator!=( const smallSet &a, const smallSet &b ) {
+            return !(a._elements == b._elements);
+        }
+
+        /// Lexicographical comparison of elements
+        friend bool operator<( const smallSet &a, const smallSet &b ) {
+            return a._elements < b._elements;
+        }
+};
+
+
+} // end of namespace dai
+
+
+#endif
index 9ec2045..cfa7c6e 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class TreeEP
+
+
 #ifndef __defined_libdai_treeep_h
 #define __defined_libdai_treeep_h
 
@@ -40,6 +44,7 @@
 namespace dai {
 
 
+/// Approximate inference algorithm "TreeEP" by Minka and Qi
 class TreeEP : public JTree {
     private:
         /// Maximum difference encountered so far
@@ -48,13 +53,24 @@ class TreeEP : public JTree {
         size_t                  _iters;
 
     public:
+        /// Parameters of this inference algorithm
         struct Properties {
+            /// Enumeration of possible choices for the tree
+            DAI_ENUM(TypeType,ORG,ALT)
+
+            /// Verbosity
             size_t verbose;
+
+            /// Maximum number of iterations
             size_t maxiter;
+
+            /// Tolerance
             double tol;
-            DAI_ENUM(TypeType,ORG,ALT)
+
+            /// How to choose the tree
             TypeType type;
         } props; // FIXME: should be props2 because of conflict with JTree::props?
+
         /// Name of this inference method
         static const char *Name;
 
@@ -105,9 +121,6 @@ class TreeEP : public JTree {
         /// Default constructor
         TreeEP() : JTree(), _maxdiff(0.0), _iters(0), props(), _Q() {}
 
-        /// Construct from FactorGraph fg and PropertySet opts
-        TreeEP( const FactorGraph &fg, const PropertySet &opts );
-
         /// Copy constructor
         TreeEP( const TreeEP &x ) : JTree(x), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props), _Q(x._Q) {
             for( size_t I = 0; I < nrFactors(); I++ )
@@ -115,12 +128,6 @@ class TreeEP : public JTree {
                     _Q[I].I() = &factor(I);
         }
 
-        /// Clone *this (virtual copy constructor)
-        virtual TreeEP* clone() const { return new TreeEP(*this); }
-
-        /// Create (virtual default constructor)
-        virtual TreeEP* create() const { return new TreeEP(); }
-
         /// Assignment operator
         TreeEP& operator=( const TreeEP &x ) {
             if( this != &x ) {
@@ -136,28 +143,29 @@ class TreeEP : public JTree {
             return *this;
         }
 
-        /// Identifies itself for logging purposes
-        virtual std::string identify() const;
+        /// Construct from FactorGraph fg and PropertySet opts
+        TreeEP( const FactorGraph &fg, const PropertySet &opts );
 
-        /// Get log partition sum
-        virtual Real logZ() const;
 
-        /// Clear messages and beliefs
+        /// @name General InfAlg interface
+        //@{
+        virtual TreeEP* clone() const { return new TreeEP(*this); }
+        virtual TreeEP* create() const { return new TreeEP(); }
+        virtual std::string identify() const;
+        virtual Real logZ() const;
         virtual void init();
-
-        /// Clear messages and beliefs corresponding to the nodes in ns
         virtual void init( const VarSet &/*ns*/ ) { init(); }
-
-        /// The actual approximate inference algorithm
         virtual double run();
-
-        /// Return maximum difference between single node beliefs in the last pass
         virtual double maxDiff() const { return _maxdiff; }
-
-        /// Return number of passes over the factorgraph
         virtual size_t Iterations() const { return _iters; }
+        //@}
+
 
+        /// @name Additional interface specific for TreeEP
+        //@{ 
+        //@}
 
+    private:
         void ConstructRG( const DEdgeVec &tree );
         bool offtree( size_t I ) const { return (fac2OR[I] == -1U); }
 
index 670fef9..fdaf396 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines general utility functions and adds an abstraction layer for platform-dependent functionality
+
+
 #ifndef __defined_libdai_util_h
 #define __defined_libdai_util_h
 
@@ -30,6 +34,7 @@
 #include <iostream>
 #include <cstdio>
 #include <boost/foreach.hpp>
+#include <algorithm>
 
 
 #ifdef WINDOWS
 #endif
 
 
+/// An alias to the BOOST_FOREACH macro from the boost::foreach library
 #define foreach BOOST_FOREACH
 
 
 #ifdef WINDOWS
+    /// Returns true if argument is NAN (Not A Number)
     bool isnan( double x );
+
+    /// Returns inverse hyperbolic tangent of argument
     double atanh( double x );
+
+    /// Returns log(1+x)
     double log1p( double x );
 #endif
 
@@ -53,22 +64,38 @@ namespace dai {
 
 
 #ifdef WINDOWS
+    /// hash_map is an alias for std::map.
+    /** Since there is no TR1 unordered_map implementation available yet, we fall back on std::map.
+     */
     template <typename T, typename U>
         class hash_map : public std::map<T,U> {};
 #else
+    /// hash_map is an alias for std::tr1::unordered_map.
+    /** We use the (experimental) TR1 unordered_map implementation included in modern GCC distributions.
+     */
     template <typename T, typename U>
         class hash_map : public std::tr1::unordered_map<T,U> {};
 #endif
 
 
+/// Returns the time in seconds
 double toc();
+
+
+/// Sets the random seed
 void rnd_seed( size_t seed );
+
+/// Returns a real number, distributed uniformly on [0,1)
 double rnd_uniform();
+
+/// Returns a real number from a standard-normal distribution
 double rnd_stdnormal();
+
+/// Returns a random integer in interval [min, max]
 int rnd_int( int min, int max );
 
 
-// Output a std::vector
+/// Writes a std::vector to a std::ostream
 template<class T> 
 std::ostream& operator << (std::ostream& os, const std::vector<T> & x) {
     os << "(";
@@ -78,8 +105,7 @@ std::ostream& operator << (std::ostream& os, const std::vector<T> & x) {
     return os;
 }
 
-
-// Output a std::set
+/// Writes a std::set to a std::ostream
 template<class T> 
 std::ostream& operator << (std::ostream& os, const std::set<T> & x) {
     os << "{";
@@ -89,8 +115,7 @@ std::ostream& operator << (std::ostream& os, const std::set<T> & x) {
     return os;
 }
 
-
-/// Output a std::map
+/// Writes a std::map to a std::ostream
 template<class T1, class T2>
 std::ostream& operator << (std::ostream& os, const std::map<T1,T2> & x) {
     os << "{";
@@ -100,8 +125,7 @@ std::ostream& operator << (std::ostream& os, const std::map<T1,T2> & x) {
     return os;
 }
 
-
-/// Output a std::pair
+/// Writes a std::pair to a std::ostream
 template<class T1, class T2>
 std::ostream& operator << (std::ostream& os, const std::pair<T1,T2> & x) {
     os << "(" << x.first << ", " << x.second << ")";
@@ -109,6 +133,59 @@ std::ostream& operator << (std::ostream& os, const std::pair<T1,T2> & x) {
 }
 
 
+/// Used to keep track of the progress made by iterative algorithms
+class Diffs : public std::vector<double> {
+    private:
+        size_t _maxsize;
+        double _def;
+        std::vector<double>::iterator _pos;
+        std::vector<double>::iterator _maxpos;
+    public:
+        /// Constructor
+        Diffs(long maxsize, double def) : std::vector<double>(), _maxsize(maxsize), _def(def) { 
+            this->reserve(_maxsize); 
+            _pos = begin(); 
+            _maxpos = begin(); 
+        }
+        /// Returns maximum difference encountered
+        double maxDiff() { 
+            if( size() < _maxsize )
+                return _def;
+            else
+                return( *_maxpos ); 
+        }
+        /// Register new difference x
+        void push(double x) {
+            if( size() < _maxsize ) {
+                push_back(x);
+                _pos = end();
+                if( size() > 1 ) {
+                    if( *_maxpos < back() ) {
+                        _maxpos = end();
+                        _maxpos--;
+                    }
+                } else {
+                    _maxpos = begin();
+                }
+            }
+            else {
+                if( _pos == end() )
+                    _pos = begin();
+                if( _maxpos == _pos ) {
+                    *_pos++ = x; 
+                    _maxpos = max_element(begin(),end());
+                } else {
+                    if( x > *_maxpos )
+                        _maxpos = _pos;
+                    *_pos++ = x;
+                }
+            }
+        }
+        /// Return maximum number of differences stored
+        size_t maxSize() { return _maxsize; }
+};
+
+
 } // end of namespace dai
 
 
index 5deb3ff..fbb6e72 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines class Var
+
+
 #ifndef __defined_libdai_var_h
 #define __defined_libdai_var_h
 
 namespace dai {
 
 
-/// Represents a discrete variable.
-/**  It contains the label of the variable, an integer-valued
- *  unique ID for that variable, and the number of possible 
- *  values ("states") of the variable.
+/// Represents a discrete random variable.
+/** It contains the \a label of the variable (an integer-valued unique ID) 
+ *  and the number of possible values (\a states) of the variable.
  */
 class Var {
     private:
@@ -75,7 +78,7 @@ class Var {
         /// Equal-to operator (only compares labels)
         bool operator == ( const Var& n ) const { return( _label == n._label ); }
 
-        /// Write a Var to output stream
+        /// Writes a Var to an output stream
         friend std::ostream& operator << ( std::ostream& os, const Var& n ) {
             return( os << "[" << n.label() << "]" );
         }
index fc41e52..4d3f5b8 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines VarSet class
+
+
 #ifndef __defined_libdai_varset_h
 #define __defined_libdai_varset_h
 
 
 #include <vector>
 #include <map>
-#include <algorithm>
-#include <iostream>
-#include <cassert>
+#include <ostream>
 #include <dai/var.h>
 #include <dai/util.h>
+#include <dai/smallset.h>
 
 
 namespace dai {
 
 
-/// A small_set<T> represents a set, optimized for a small number of elements.
-/** For sets consisting of a small number of elements, an implementation using
- *  an ordered std::vector<T> is faster than an implementation using std::set<T>.
- *  The elements should be less-than-comparable.
+/// Represents a set of variables.
+/** \note A VarSet is implemented using a std::vector<Var> instead
+ *  of the more natural std::set<Var> because of efficiency reasons.
  */
-template <typename T>
-class small_set {
-    private:
-        /// The elements in this set
-        std::vector<T> _elements;
-
+class VarSet : public smallSet<Var> {
     public:
         /// Default constructor
-        small_set() : _elements() {}
-
-        /// Construct a small_set with one element
-        small_set( const T &n ) : _elements() { 
-            _elements.push_back( n );
-        }
-
-        /// Construct a small_set with two elements
-        small_set( const T &n1, const T &n2 ) { 
-            if( n1 < n2 ) {
-                _elements.push_back( n1 );
-                _elements.push_back( n2 );
-            } else if( n2 < n1 ) {
-                _elements.push_back( n2 );
-                _elements.push_back( n1 );
-            } else
-                _elements.push_back( n1 );
-        }
-
-        /// Construct a small_set from a range of iterators.
-        /** The value_type of the Iterator should be T.
-         *  For efficiency, the number of elements can be
-         *  speficied by sizeHint.
-         */
-        template <typename Iterator>
-        small_set( Iterator begin, Iterator end, size_t sizeHint=0 ) {
-            _elements.reserve( sizeHint );
-            _elements.insert( _elements.begin(), begin, end );
-            std::sort( _elements.begin(), _elements.end() );
-            typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
-            _elements.erase( new_end, _elements.end() );
-        }
+        VarSet() : smallSet<Var>() {}
 
         /// Copy constructor
-        small_set( const small_set &x ) : _elements( x._elements ) {}
+        VarSet( const VarSet &x ) : smallSet<Var>(x) {}
 
         /// Assignment operator
-        small_set & operator=( const small_set &x ) {
+        VarSet& operator=( const VarSet &x ) {
             if( this != &x ) {
-                _elements = x._elements;
+                smallSet<Var>::operator=( x );
             }
             return *this;
         }
         
-        /// Setminus operator (result contains all elements in *this, except those in ns)
-        small_set operator/ ( const small_set& ns ) const {
-            small_set res;
-            std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
-            return res;
-        }
+        /// Construct from smallSet<Var>
+        VarSet( const smallSet<Var> &x ) : smallSet<Var>(x) {}
 
-        /// Set-union operator (result contains all elements in *this, plus those in ns)
-        small_set operator| ( const small_set& ns ) const {
-            small_set res;
-            std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
-            return res;
+        /// Calculates the product of the number of states of all variables in this VarSet.
+        size_t nrStates() {
+            size_t states = 1;
+            for( VarSet::const_iterator n = begin(); n != end(); n++ )
+                states *= n->states();
+            return states;
         }
 
-        /// Set-intersection operator (result contains all elements in *this that are also contained in ns)
-        small_set operator& ( const small_set& ns ) const {
-            small_set res;
-            std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
-            return res;
-        }
-        
-        /// Erases from *this all elements in ns
-        small_set& operator/= ( const small_set& ns ) {
-            return (*this = (*this / ns));
-        }
+        /// Construct a VarSet with one element
+        VarSet( const Var &n ) : smallSet<Var>(n) {}
 
-        /// Erase one element
-        small_set& operator/= ( const T& n ) { 
-            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
-            if( pos != _elements.end() )
-                if( *pos == n ) // found element, delete it
-                    _elements.erase( pos ); 
-            return *this; 
-        }
-
-        /// Adds to *this all elements in ns
-        small_set& operator|= ( const small_set& ns ) {
-            return( *this = (*this | ns) );
-        }
+        /// Construct a VarSet with two elements
+        VarSet( const Var &n1, const Var &n2 ) : smallSet<Var>(n1,n2) {} 
 
-        /// Add one element
-        small_set& operator|= ( const T& n ) {
-            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
-            if( pos == _elements.end() || *pos != n ) // insert it
-                _elements.insert( pos, n );
-            return *this;
-        }
-
-        /// Erases from *this all elements not in ns
-        small_set& operator&= ( const small_set& ns ) { 
-            return (*this = (*this & ns));
-        }
-
-        /// Returns true if *this is a subset of ns
-        bool operator<< ( const small_set& ns ) const { 
-            return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
-        }
-
-        /// Returns true if ns is a subset of *this
-        bool operator>> ( const small_set& ns ) const { 
-            return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
-        }
-
-        /// Returns true if *this and ns contain common elements
-        bool intersects( const small_set& ns ) const { 
-            return( (*this & ns).size() > 0 ); 
-        }
-
-        /// Returns true if *this contains the element n
-        bool contains( const T& n ) const { 
-            return std::binary_search( _elements.begin(), _elements.end(), n );
-        }
-
-        /// Constant iterator over the elements
-        typedef typename std::vector<T>::const_iterator const_iterator;
-        /// Iterator over the elements
-        typedef typename std::vector<T>::iterator iterator;
-        /// Constant reverse iterator over the elements
-        typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
-        /// Reverse iterator over the elements
-        typedef typename std::vector<T>::reverse_iterator reverse_iterator;
-        
-        /// Returns iterator that points to the first element
-        iterator begin() { return _elements.begin(); }
-        /// Returns constant iterator that points to the first element
-        const_iterator begin() const { return _elements.begin(); }
-
-        /// Returns iterator that points beyond the last element
-        iterator end() { return _elements.end(); }
-        /// Returns constant iterator that points beyond the last element
-        const_iterator end() const { return _elements.end(); }
-
-        /// Returns reverse iterator that points to the last element
-        reverse_iterator rbegin() { return _elements.rbegin(); }
-        /// Returns constant reverse iterator that points to the last element
-        const_reverse_iterator rbegin() const { return _elements.rbegin(); }
-
-        /// Returns reverse iterator that points beyond the first element
-        reverse_iterator rend() { return _elements.rend(); }
-        /// Returns constant reverse iterator that points beyond the first element
-        const_reverse_iterator rend() const { return _elements.rend(); }
-
-        /// Returns number of elements
-        typename std::vector<T>::size_type size() const { return _elements.size(); }
-
-        /// Returns whether the small_set is empty
-        bool empty() const { return _elements.size() == 0; }
-
-        /// Test for equality of element labels
-        friend bool operator==( const small_set &a, const small_set &b ) {
-            return (a._elements == b._elements);
-        }
-
-        /// Test for inequality of element labels
-        friend bool operator!=( const small_set &a, const small_set &b ) {
-            return !(a._elements == b._elements);
+        /// Construct a VarSet from a range of iterators.
+        /** \tparam VarIterator Iterator with value_type Var.
+         *  \param begin Points to first Var to be added.
+         *  \param end Points just beyond last Var to be added.
+         *  \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
+         */
+        template <typename VarIterator>
+        VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : smallSet<Var>(begin,end,sizeHint) {}
+
+        /// Calculates the linear index in the cartesian product of the variables in *this, which corresponds to a particular joint assignment of the variables.
+        /** \param states Specifies the states of some variables.
+         *  \return The linear index in the cartesian product of the variables in *this
+         *  corresponding with the joint assignment specified by \c states (where it is
+         *  assumed that states[m] == 0 for all m in vars which are not in states).
+         */
+        size_t calcState( const std::map<Var, size_t> &states ) {
+            size_t prod = 1;
+            size_t state = 0;
+            for( VarSet::const_iterator n = begin(); n != end(); n++ ) {
+                std::map<Var, size_t>::const_iterator m = states.find( *n );
+                if( m != states.end() )
+                    state += prod * m->second;
+                prod *= n->states();
+            }
+            return state;
         }
 
-        /// Lexicographical comparison of element labels
-        friend bool operator<( const small_set &a, const small_set &b ) {
-            return a._elements < b._elements;
+        /// Writes a VarSet to an output stream
+        friend std::ostream& operator<< (std::ostream &os, const VarSet& ns)  {
+            for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
+                os << *n;
+            return( os );
         }
 };
 
 
-/// A VarSet represents a set of variables.
-/**
- *  It is implemented as an ordered std::vector<Var> for efficiency reasons
- *  (indeed, it was found that a std::set<Var> usually has more overhead). 
- *  In addition, it provides an interface for common set-theoretic operations.
- */
-typedef small_set<Var> VarSet;
-
-
-/// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
-inline VarSet operator| (const Var& n1, const Var& n2) {
-    return( VarSet(n1, n2) );
-}
-
-
-/// Calculates the product of number of states of all variables in vars
-size_t nrStates( const VarSet &vars );
-
-
-/// calcState calculates the linear index of vars that corresponds
-/// to the states of the variables given in states, implicitly assuming
-/// states[m] = 0 for all m in this VarSet which are not in states.
-size_t calcState( const VarSet &vars, const std::map<Var, size_t> &states );
-
-
-/// Sends a VarSet to an output stream
-std::ostream& operator<< (std::ostream &os, const VarSet& ns);
-
-
 } // end of namespace dai
 
 
index 6560119..4891a4d 100644 (file)
 */
 
 
+/// \file
+/// \brief Defines some utility functions for weighted graphs
+
+
 #ifndef __defined_libdai_weightedgraph_h
 #define __defined_libdai_weightedgraph_h
 
 #include <boost/graph/prim_minimum_spanning_tree.hpp>
 
 
-
 namespace dai {
 
 
-/// Directed edge
+/// Represents a directed edge pointing from n1 to n2
 class DEdge {
     public:
-        size_t  n1, n2;
+        size_t n1;  ///< First node index
+        size_t n2;  ///< Second node index
     
+        /// Default constructor
         DEdge() {}
+
+        /// Constructor
         DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
-        bool operator==( const DEdge &x ) const {
-            return ((n1 == x.n1) && (n2 == x.n2));
-        }
-        bool operator!=( const DEdge &x ) const {
-            return !(*this == x);
-        }
+
+        /// Tests for equality
+        bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
+
+        /// Tests for inequality
+        bool operator!=( const DEdge &x ) const { return !(*this == x); }
+
+        /// Smaller-than operator (performs lexicographical comparison)
         bool operator<( const DEdge &x ) const {
             return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
         }
+
+        /// Writes a DEdge to an output stream
         friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
             os << "(" << e.n1 << "," << e.n2 << ")";
             return os;
@@ -62,17 +73,27 @@ class DEdge {
 };
 
 
-/// Undirected edge
+/// Undirected edge between nodes n1 and n2
 class UEdge {
     public:
-        size_t  n1, n2;
+        size_t  n1;  ///< First node index
+        size_t  n2;  ///< Second node index
     
+        /// Default constructor
         UEdge() {}
+
+        /// Constructor
         UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
+
+        /// Construct from DEdge
         UEdge( const DEdge & e ) : n1(e.n1), n2(e.n2) {}
+
+        /// Tests for inequality (disregarding the ordering of n1 and n2)
         bool operator==( const UEdge &x ) {
             return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
         }
+
+        /// Smaller-than operator
         bool operator<( const UEdge &x ) const {
             size_t s = n1, l = n2;
             if( s > l )
@@ -82,6 +103,8 @@ class UEdge {
                 std::swap( xs, xl );
             return( (s < xs) || ((s == xs) && (l < xl)) );
         }
+
+        /// Writes a UEdge to an output stream
         friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
             if( e.n1 < e.n2 )
                 os << "{" << e.n1 << "," << e.n2 << "}";
@@ -92,17 +115,25 @@ class UEdge {
 };
 
 
+/// Vector of UEdge
 typedef std::vector<UEdge>  UEdgeVec;
+
+/// Vector of DEdge
 typedef std::vector<DEdge>  DEdgeVec;
+
+/// Represents an undirected weighted graph, with weights of type T
 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
+
+/// Represents an undirected graph
 typedef std::set<UEdge>     Graph;
 
 
-/// Use Prim's algorithm to construct a minimal spanning tree from the weighted graph Graph
-/// The weights should be positive. Use implementation in Boost Graph Library.
-template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> & Graph ) {
+/// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
+/** Uses implementation in Boost Graph Library.
+ */
+template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G ) {
     DEdgeVec result;
-    if( Graph.size() > 0 ) {
+    if( G.size() > 0 ) {
         using namespace boost;
         using namespace std;
         typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
@@ -111,9 +142,9 @@ template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> & Gra
         set<size_t> nodes;
         vector<E> edges;
         vector<double> weights;
-        edges.reserve( Graph.size() );
-        weights.reserve( Graph.size() );
-        for( typename WeightedGraph<T>::const_iterator e = Graph.begin(); e != Graph.end(); e++ ) {
+        edges.reserve( G.size() );
+        weights.reserve( G.size() );
+        for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
             weights.push_back( e->second );
             edges.push_back( E( e->first.n1, e->first.n2 ) );
             nodes.insert( e->first.n1 );
@@ -165,8 +196,9 @@ template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> & Gra
 }
 
 
-/// Use Prim's algorithm to construct a maximal spanning tree from the weighted graph Graph
-/// The weights should be positive. Use implementation in Boost Graph Library.
+/// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
+/** Uses implementation in Boost Graph Library.
+ */
 template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Graph ) {
     T maxweight = Graph.begin()->second;
     for( typename WeightedGraph<T>::const_iterator it = Graph.begin(); it != Graph.end(); it++ )
@@ -182,94 +214,14 @@ template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Gra
 }
 
 
-/// Calculate rooted tree from a tree T and a root
+/// Constructs a rooted tree from a tree and a root
 DEdgeVec GrowRootedTree( const Graph & T, size_t Root );
 
 
+/// Constructs a random undirected graph of N nodes, where each node has connectivity d
 UEdgeVec RandomDRegularGraph( size_t N, size_t d );
 
 
-/// Use Dijkstra's algorithm to solve the shortest path problem for the weighted graph Graph and source vertex index s
-template<typename T>
-std::map<size_t,size_t> DijkstraShortestPaths( const WeightedGraph<T> & Graph, size_t s ) {
-/*
- * from wikipedia 
- *
-In the following algorithm, u := Extract_Min(Q) searches for the vertex u in the vertex set Q that has the least d[u] value. That vertex is removed from the set Q and returned to the user.
-
-  function Dijkstra(G, w, s)
-     for each vertex v in V[G]                        // Initializations
-           d[v] := infinity                                 // Unknown distance function from s to v
-           previous[v] := undefined
-     d[s] := 0                                        // Distance from s to s
-     S := empty set                                   // Set of all visited vertices
-     Q := V[G]                                        // Set of all unvisited vertices
-     while Q is not an empty set                      // The algorithm itself
-           u := Extract_Min(Q)                        // Remove best vertex from priority queue
-           S := S union {u}                           // Mark it 'visited'
-           for each edge (u,v) outgoing from u
-                  if d[u] + w(u,v) < d[v]             // Relax (u,v)
-                        d[v] := d[u] + w(u,v) 
-                        previous[v] := u
-
-To find the shortest path from s to t:
-
-u := t
-while defined previous[u]
-      insert u to the beginning of S
-      u := previous[u]
-       
-*/
-
-    // Calculate set of nodes in G
-    std::set<size_t> nodes;
-    for( typename WeightedGraph<T>::const_iterator e = Graph.begin(); e != Graph.end(); e++ ) {
-        nodes.insert( e->n1.n1 );
-        nodes.insert( e->n1.n2 );
-    }
-    if( !nodes.count( s ) )
-        return std::map<size_t, size_t>();
-
-    std::map<size_t, double> d;
-    std::map<size_t, size_t> previous;
-    for( std::set<size_t>::const_iterator n = nodes.begin(); n != nodes.end(); n++ )
-        d[*n] = std::numeric_limits<double>::infinity();
-
-    d[s] = 0;
-    std::set<size_t> S;
-    std::set<size_t> Q = nodes;
-
-    while( Q.size() ) {
-        double least = d[*Q.begin()];
-        std::set<size_t>::iterator u_least = Q.begin();
-        for( std::set<size_t>::iterator _u = Q.begin(); _u != Q.end(); _u++ )
-            if( d[*_u] < least ) {
-                u_least = _u;
-                least = d[*_u];
-            }
-        size_t u = *u_least;
-        Q.erase( u_least );
-            
-        S.insert( u );
-        for( typename WeightedGraph<T>::const_iterator e = Graph.begin(); e != Graph.end(); e++ ) {
-            size_t v;
-            if( e->n1.n1 == u )
-                v = e->n1.n2;
-            else if( e->n1.n2 == u )
-                v = e->n1.n1;
-            else
-                continue;
-            if( d[u] + e->n2 < d[v] ) {
-                d[v] = d[u] + e->n2;
-                previous[v] = u;
-            }
-        }
-    }
-
-    return previous;
-}
-
-
 } // end of namespace dai
 
 
index ee5b7b8..1f8d898 100644 (file)
@@ -35,31 +35,31 @@ using namespace std;
 InfAlg *newInfAlg( const string &name, const FactorGraph &fg, const PropertySet &opts ) {
     if( name == ExactInf::Name )
         return new ExactInf (fg, opts);
-#ifdef WITH_BP
+#ifdef DAI_WITH_BP
     if( name == BP::Name ) 
         return new BP (fg, opts);
 #endif
-#ifdef WITH_MF
+#ifdef DAI_WITH_MF
     if( name == MF::Name ) 
         return new MF (fg, opts);
 #endif
-#ifdef WITH_HAK
+#ifdef DAI_WITH_HAK
     if( name == HAK::Name ) 
         return new HAK (fg, opts);
 #endif
-#ifdef WITH_LC
+#ifdef DAI_WITH_LC
     if( name == LC::Name )
         return new LC (fg, opts);
 #endif
-#ifdef WITH_TREEEP
+#ifdef DAI_WITH_TREEEP
     if( name == TreeEP::Name )
         return new TreeEP (fg, opts);
 #endif
-#ifdef WITH_JTREE
+#ifdef DAI_WITH_JTREE
     if( name == JTree::Name )
         return new JTree (fg, opts);
 #endif
-#ifdef WITH_MR
+#ifdef DAI_WITH_MR
     if( name == MR::Name )
         return new MR (fg, opts);
 #endif
index accb5f7..7c8d81a 100644 (file)
@@ -26,7 +26,6 @@
 #include <set>
 #include <algorithm>
 #include <dai/bp.h>
-#include <dai/diffs.h>
 #include <dai/util.h>
 #include <dai/properties.h>
 
@@ -431,7 +430,7 @@ Real BP::logZ() const {
     for(size_t i = 0; i < nrVars(); ++i )
         sum += (1.0 - nbV(i).size()) * beliefV(i).entropy();
     for( size_t I = 0; I < nrFactors(); ++I )
-        sum -= KL_dist( beliefF(I), factor(I) );
+        sum -= dist( beliefF(I), factor(I), Prob::DISTKL );
     return sum;
 }
 
index 133143c..79f9daa 100644 (file)
@@ -30,6 +30,7 @@ namespace dai {
 using namespace std;
 
 
+/// Calculates the marginal of obj on ns by clamping all variables in ns and calculating logZ for each joined state.
 Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit ) {
     Factor Pns (ns);
     
@@ -74,6 +75,7 @@ Factor calcMarginal( const InfAlg & obj, const VarSet & ns, bool reInit ) {
 }
 
 
+/// Calculates beliefs of all pairs in ns (by clamping nodes in ns and calculating logZ and the beliefs for each state).
 vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reInit ) {
     // convert ns to vector<VarSet>
     size_t N = ns.size();
@@ -89,7 +91,7 @@ vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reIni
             if( j == k )
                 pairbeliefs.push_back( Factor() );
             else
-                pairbeliefs.push_back( Factor( vns[j] | vns[k] ) );
+                pairbeliefs.push_back( Factor( VarSet(vns[j], vns[k]) ) );
 
     InfAlg *clamped = obj.clone();
     if( !reInit )
@@ -144,6 +146,7 @@ vector<Factor> calcPairBeliefs( const InfAlg & obj, const VarSet& ns, bool reIni
 }
 
 
+/// Calculates beliefs of all pairs in ns (by clamping pairs in ns and calculating logZ for each joined state).
 Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit ) {
     // returns a a probability distribution whose 1st order interactions
     // are unspecified, whose 2nd order interactions approximate those of 
@@ -159,6 +162,7 @@ Factor calcMarginal2ndO( const InfAlg & obj, const VarSet& ns, bool reInit ) {
 }
 
 
+/// Calculates 2nd order interactions of the marginal of obj on ns.
 vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool reInit ) {
     vector<Factor> result;
     result.reserve( ns.size() * (ns.size() - 1) / 2 );
@@ -172,7 +176,7 @@ vector<Factor> calcPairBeliefsNew( const InfAlg & obj, const VarSet& ns, bool re
     for( long j = 0; j < (long)ns.size() - 1; j++, nj++ ) {
         size_t k = 0;
         for( VarSet::const_iterator nk = nj; (++nk) != ns.end(); k++ ) {
-            Factor pairbelief( *nj | *nk );
+            Factor pairbelief( VarSet(*nj, *nk) );
 
             // clamp Vars j and k to their possible values
             for( size_t j_val = 0; j_val < nj->states(); j_val++ ) 
index 3851923..f361636 100644 (file)
@@ -41,31 +41,30 @@ using namespace std;
 
 FactorGraph::FactorGraph( const std::vector<Factor> &P ) : G(), _backup() {
     // add factors, obtain variables
-    set<Var> _vars;
+    set<Var> varset;
     _factors.reserve( P.size() );
     size_t nrEdges = 0;
     for( vector<Factor>::const_iterator p2 = P.begin(); p2 != P.end(); p2++ ) {
         _factors.push_back( *p2 );
-        copy( p2->vars().begin(), p2->vars().end(), inserter( _vars, _vars.begin() ) );
+        copy( p2->vars().begin(), p2->vars().end(), inserter( varset, varset.begin() ) );
         nrEdges += p2->vars().size();
     }
 
-    // add _vars
-    vars.reserve( _vars.size() );
-    for( set<Var>::const_iterator p1 = _vars.begin(); p1 != _vars.end(); p1++ )
-        vars.push_back( *p1 );
+    // add vars
+    _vars.reserve( varset.size() );
+    for( set<Var>::const_iterator p1 = varset.begin(); p1 != varset.end(); p1++ )
+        _vars.push_back( *p1 );
 
     // create graph structure
     constructGraph( nrEdges );
 }
 
 
-/// Part of constructors (creates edges, neighbours and adjacency matrix)
 void FactorGraph::constructGraph( size_t nrEdges ) {
     // create a mapping for indices
     hash_map<size_t, size_t> hashmap;
     
-    for( size_t i = 0; i < vars.size(); i++ )
+    for( size_t i = 0; i < vars().size(); i++ )
         hashmap[var(i).label()] = i;
     
     // create edge list
@@ -82,6 +81,7 @@ void FactorGraph::constructGraph( size_t nrEdges ) {
 }
 
 
+/// Writes a FactorGraph to an output stream
 ostream& operator << (ostream& os, const FactorGraph& fg) {
     os << fg.nrFactors() << endl;
 
@@ -111,6 +111,7 @@ ostream& operator << (ostream& os, const FactorGraph& fg) {
 }
 
 
+/// Reads a FactorGraph from an input stream
 istream& operator >> (istream& is, FactorGraph& fg) {
     long verbose = 0;
 
@@ -452,7 +453,7 @@ FactorGraph FactorGraph::maximalFactors() const {
     for( size_t I = 0; I < nrFactors(); I++ )
         facs[newindex[maxfac[I]]] *= factor(I);
 
-    return FactorGraph( facs.begin(), facs.end(), vars.begin(), vars.end(), facs.size(), nrVars() );
+    return FactorGraph( facs.begin(), facs.end(), vars().begin(), vars().end(), facs.size(), nrVars() );
 }
 
 
index 92260ea..e1a33d3 100644 (file)
@@ -23,7 +23,6 @@
 #include <map>
 #include <dai/hak.h>
 #include <dai/util.h>
-#include <dai/diffs.h>
 #include <dai/exceptions.h>
 
 
index 463abb3..16ae300 100644 (file)
@@ -324,7 +324,7 @@ size_t JTree::findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t Previo
     // find new root clique (the one with maximal statespace overlap with ns)
     size_t maxval = 0, maxalpha = 0;
     for( size_t alpha = 0; alpha < nrORs(); alpha++ ) {
-        size_t val = nrStates( ns & OR(alpha).vars() );
+        size_t val = VarSet(ns & OR(alpha).vars()).nrStates();
         if( val > maxval ) {
             maxval = val;
             maxalpha = alpha;
@@ -504,9 +504,11 @@ Factor JTree::calcMarginal( const VarSet& ns ) {
 }
 
 
-// first return value is treewidth
-// second return value is number of states in largest clique
-pair<size_t,size_t> treewidth( const FactorGraph & fg ) {
+/// Calculates upper bound to the treewidth of a FactorGraph
+/** \relates JTree
+ *  \return a pair (number of variables in largest clique, number of states in largest clique)
+ */
+std::pair<size_t,size_t> treewidth( const FactorGraph & fg ) {
     ClusterGraph _cg;
 
     // Copy factors
@@ -525,7 +527,7 @@ pair<size_t,size_t> treewidth( const FactorGraph & fg ) {
     for( size_t i = 0; i < ElimVec.size(); i++ ) {
         if( ElimVec[i].size() > treewidth )
             treewidth = ElimVec[i].size();
-        size_t s = nrStates(ElimVec[i]);
+        size_t s = ElimVec[i].nrStates();
         if( s > nrstates )
             nrstates = s;
     }
index 13f9300..070d5eb 100644 (file)
@@ -25,7 +25,6 @@
 #include <map>
 #include <set>
 #include <dai/lc.h>
-#include <dai/diffs.h>
 #include <dai/util.h>
 #include <dai/alldai.h>
 
@@ -136,7 +135,7 @@ double LC::CalcCavityDist (size_t i, const std::string &name, const PropertySet
     double maxdiff = 0;
 
     if( props.verbose >= 2 )
-        cout << "Initing cavity " << var(i) << "(" << delta(i).size() << " vars, " << nrStates(delta(i)) << " states)" << endl;
+        cout << "Initing cavity " << var(i) << "(" << delta(i).size() << " vars, " << delta(i).nrStates() << " states)" << endl;
 
     if( props.cavity == Properties::CavityType::UNIFORM )
         Bi = Factor(delta(i));
index 9d35b8f..766acc7 100644 (file)
@@ -25,7 +25,6 @@
 #include <map>
 #include <set>
 #include <dai/mf.h>
-#include <dai/diffs.h>
 #include <dai/util.h>
 
 
index 4fe2e31..bc52353 100644 (file)
@@ -28,7 +28,6 @@
 #include <dai/bp.h>
 #include <dai/jtree.h>
 #include <dai/util.h>
-#include <dai/diffs.h>
 
 
 namespace dai {
index 38a8824..bf6d7a0 100644 (file)
@@ -28,7 +28,6 @@
 namespace dai {
 
 
-/// Sends a single Property object to an output stream
 std::ostream& operator<< (std::ostream & os, const Property & p) {
     os << p.first << "=";
     if( p.second.type() == typeid(size_t) )
@@ -47,7 +46,7 @@ std::ostream& operator<< (std::ostream & os, const Property & p) {
 }
 
 
-/// Sends a PropertySet object to an output stream
+/// Writes a PropertySet object to an output stream
 std::ostream& operator<< (std::ostream & os, const PropertySet & ps) {
     os << "[";
     for( PropertySet::const_iterator p = ps.begin(); p != ps.end(); p++ ) {
index 267a4fd..bcd6a98 100644 (file)
@@ -179,7 +179,7 @@ bool RegionGraph::Check_Counting_Numbers() {
     // Checks whether the counting numbers satisfy the fundamental relation
     
     bool all_valid = true;
-    for( vector<Var>::const_iterator n = vars.begin(); n != vars.end(); n++ ) {
+    for( vector<Var>::const_iterator n = vars().begin(); n != vars().end(); n++ ) {
         double c_n = 0.0;
         for( size_t alpha = 0; alpha < nrORs(); alpha++ )
             if( OR(alpha).vars().contains( *n ) )
@@ -229,6 +229,7 @@ void RegionGraph::RecomputeOR( size_t I ) {
 }
 
 
+/// Send RegionGraph to output stream
 ostream & operator << (ostream & os, const RegionGraph & rg) {
     os << "Outer regions" << endl;
     for( size_t alpha = 0; alpha < rg.nrORs(); alpha++ )
index e50be83..a473e9e 100644 (file)
@@ -26,7 +26,6 @@
 #include <dai/jtree.h>
 #include <dai/treeep.h>
 #include <dai/util.h>
-#include <dai/diffs.h>
 
 
 namespace dai {
@@ -236,7 +235,7 @@ TreeEP::TreeEP( const FactorGraph &fg, const PropertySet &opts ) : JTree(fg, opt
                             if( piet.vars() >> ij ) {
                                 piet = piet.marginal( ij );
                                 Factor pietf = piet.marginal(v_i) * piet.marginal(*j);
-                                wg[UEdge(i,findVar(*j))] = KL_dist( piet, pietf );
+                                wg[UEdge(i,findVar(*j))] = dist( piet, pietf, Prob::DISTKL );
                             } else
                                 wg[UEdge(i,findVar(*j))] = 0;
                         } else {
@@ -256,7 +255,7 @@ TreeEP::TreeEP( const FactorGraph &fg, const PropertySet &opts ) : JTree(fg, opt
 void TreeEP::ConstructRG( const DEdgeVec &tree ) {
     vector<VarSet> Cliques;
     for( size_t i = 0; i < tree.size(); i++ )
-        Cliques.push_back( var(tree[i].n1) | var(tree[i].n2) );
+        Cliques.push_back( VarSet( var(tree[i].n1), var(tree[i].n2) ) );
     
     // Construct a weighted graph (each edge is weighted with the cardinality 
     // of the intersection of the nodes, where the nodes are the elements of
index a5d8cc0..e37cb2b 100644 (file)
@@ -95,7 +95,6 @@ double rnd_stdnormal() {
     return _normal_rnd();
 }
 
-// Returns integer in interval [min, max]
 int rnd_int( int min, int max ) {
     return (int)floor(_uni_rnd() * (max + 1 - min) + min);
 }
diff --git a/src/varset.cpp b/src/varset.cpp
deleted file mode 100644 (file)
index d45c4d6..0000000
+++ /dev/null
@@ -1,68 +0,0 @@
-/*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
-    Radboud University Nijmegen, The Netherlands /
-    Max Planck Institute for Biological Cybernetics, Germany
-
-    Copyright (C) 2002  Martijn Leisink  [martijn@mbfys.kun.nl]
-    Radboud University Nijmegen, The Netherlands
-
-    This file is part of libDAI.
-
-    libDAI is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
-
-    libDAI is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
-
-    You should have received a copy of the GNU General Public License
-    along with libDAI; if not, write to the Free Software
-    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-*/
-
-
-#include <dai/varset.h>
-
-
-namespace dai {
-
-
-using namespace std;
-
-
-/// Calculates the product of number of states of all variables in vars
-size_t nrStates( const VarSet &vars ) {
-    size_t states = 1;
-    for( VarSet::const_iterator n = vars.begin(); n != vars.end(); n++ )
-        states *= n->states();
-    return states;
-}
-
-
-/// calcState calculates the linear index of vars that corresponds
-/// to the states of the variables given in states, implicitly assuming
-/// states[m] = 0 for all m in this VarSet which are not in states.
-size_t calcState( const VarSet &vars, const std::map<Var, size_t> &states ) {
-    size_t prod = 1;
-    size_t state = 0;
-    for( VarSet::const_iterator n = vars.begin(); n != vars.end(); n++ ) {
-        map<Var, size_t>::const_iterator m = states.find( *n );
-        if( m != states.end() )
-            state += prod * m->second;
-        prod *= n->states();
-    }
-    return state;
-}
-
-
-/// Sends a VarSet to an output stream
-std::ostream& operator<< (std::ostream &os, const VarSet& ns) {
-    for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
-        os << *n;
-    return( os );
-}
-
-
-} // end of namespace dai
index 78d2069..203d2a1 100644 (file)
@@ -32,7 +32,6 @@ namespace dai {
 using namespace std;
 
 
-/// Calculate rooted tree from a tree T and a root
 DEdgeVec GrowRootedTree( const Graph & T, size_t Root ) {
     DEdgeVec result;
     if( T.size() == 0 )
index 009caec..811714d 100644 (file)
@@ -57,7 +57,7 @@ Factor BinaryFactor( const Var &n1, const Var &n2, double coupling ) {
     double buf[4];
     buf[0] = (buf[3] = exp(coupling));
     buf[1] = (buf[2] = exp(-coupling));
-    return Factor(n1 | n2, &buf[0]);
+    return Factor( VarSet(n1, n2), &buf[0] );
 }
 
 
@@ -70,7 +70,7 @@ Factor RandomFactor( const VarSet &ns, double beta ) {
 
 
 Factor PottsFactor( const Var &n1, const Var &n2, double beta ) {
-    Factor fac( n1 | n2, 1.0 );
+    Factor fac( VarSet( n1, n2 ), 1.0 );
     assert( n1.states() == n2.states() );
     for( size_t s = 0; s < n1.states(); s++ )
         fac[ s * (n1.states() + 1) ] = exp(beta);
@@ -204,9 +204,9 @@ void MakeGridNonbinaryFG( bool periodic, size_t n, size_t states, double beta, F
     for( size_t i = 0; i < n; i++ ) {
         for( size_t j = 0; j < n; j++ ) {
             if( i+1 < n || periodic )
-                factors.push_back( RandomFactor( vars[i*n+j] | vars[((i+1)%n)*n+j], beta ) );
+                factors.push_back( RandomFactor( VarSet( vars[i*n+j], vars[((i+1)%n)*n+j] ), beta ) );
             if( j+1 < n || periodic )
-                factors.push_back( RandomFactor( vars[i*n+j] | vars[i*n+((j+1)%n)], beta ) );
+                factors.push_back( RandomFactor( VarSet( vars[i*n+j], vars[i*n+((j+1)%n)] ), beta ) );
         }
     }
 
@@ -237,7 +237,7 @@ void MakeLoopNonbinaryFG( size_t N, size_t states, double beta, FactorGraph &fg
 
     factors.reserve( N );
     for( size_t i = 0; i < N; i++ ) {
-        factors.push_back( RandomFactor( vars[i] | vars[(i+1)%N], beta ) );
+        factors.push_back( RandomFactor( VarSet( vars[i], vars[(i+1)%N] ), beta ) );
     }
 
     fg = FactorGraph( factors.begin(), factors.end(), vars.begin(), vars.end(), factors.size(), vars.size() );
index df6a942..f31e633 100644 (file)
@@ -44,7 +44,7 @@ void findLoopClusters( const FactorGraph & fg, std::set<VarSet> &allcl, VarSet n
 
 size_t countLoops( const FactorGraph & fg, size_t loopdepth ) {
     set<VarSet> loops;
-    for( vector<Var>::const_iterator i0 = fg.vars.begin(); i0 != fg.vars.end(); i0++ ) {
+    for( vector<Var>::const_iterator i0 = fg.vars().begin(); i0 != fg.vars().end(); i0++ ) {
         VarSet i0d = fg.delta(*i0);
         if( loopdepth > 1 )
             findLoopClusters( fg, loops, *i0, *i0, loopdepth - 1, i0d );
@@ -123,10 +123,10 @@ int main( int argc, char *argv[] ) {
                 cavsizes[di.size()]++;
             else
                 cavsizes[di.size()] = 1;
-            size_t Ds = nrStates( fg.Delta(i) );
+            size_t Ds = fg.Delta(i).nrStates();
             if( Ds > max_Delta_size )
                 max_Delta_size = Ds;
-            cavsum_lcbp += nrStates( di );
+            cavsum_lcbp += di.nrStates();
             for( VarSet::const_iterator j = di.begin(); j != di.end(); j++ )
                 cavsum_lcbp2 += j->states();
         }