Fixed bug in MaxSpanningTree
[libdai.git] / ChangeLog
index d5c9cbc..a056d74 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,11 +1,92 @@
-libDAI-0.2.2 (2008-??-??)
+* Added work-around for bug in Boost Graph Library
+* [Frederik Eaton] Added Gibbs::state() accessors/mutators
+* [Frederik Eaton] Fixed Gibbs::getVarDist(size_t) to return uniform 
+  distribution if no state is allowed
+* [Frederik Eaton] Improved parsing code in tests/testdai to allow recursive
+  alias substitutions
+* Interface changes:
+    TProb<T>::minVal()     -> TProb<T>::min()
+    TFactor<T>::minVal()   -> TFactor<T>::min()
+    TProb<T>::maxVal()     -> TProb<T>::max()
+    TFactor<T>::maxVal()   -> TFactor<T>::max()
+    TProb<T>::totalSum()   -> TProb<T>sum()
+    TFactor<T>::totalSum() -> TFactor<T>::sum()
+* [Frederik Eaton] Added methods setUniform (), sumAbs(), argmax() to TProb<T>
+* [Frederik Eaton] Added TAGS, lib targets to Makefile
+* [Frederik Eaton] Add useful aliases to aliases.conf
+* [Frederik Eaton] Removed unnecessary copy constructors and assignment
+  operators
+* [Frederik Eaton] Change cout to cerr in warnings and error messages
+* [Giuseppe Passino] Optimised maximum-residual BP by using a reversed ordered
+  set instead of the linear search (which can yield enormous speedups - a 
+  factor 500 has been measured on a binary Ising grid with 128x128 variables!)
+* Added debug assertions to Var which check for inconsistent dimensions of 
+  variables with the same labels
+* [Giuseppe Passino] Added prefix ++ operator to State (State::operator++())
+* [Giuseppe Passino] Added iterators to FactorGraph (FactorGraph::begin, 
+  FactorGraph::end)
+* [Giuseppe Passino] Added iterators to TFactor (TFactor::begin, TFactor::end)
+* [Giuseppe Passino] Added iterators to TProb (TProb::begin, TProb::end)
+* [Giuseppe Passino] Added BP::findMaximum(), which can be used after running
+  max-product BP to construct a global state with maximum probability
+* Improved Makefile (libDAI now also builds out-of-the-box on MacOSX, 
+  thanks to Dan Preston; merged Makefile.win and Makefile.shared into Makefile)
+* Fixed bug in calcMarginal, calcPairBeliefs, calcPairBeliefsNew where
+  states with zero probability mass were clamped, leading to NaNs or assertion
+  errors (thanks to Dan Preston for reporting this)
+* toc() now returns POSIX system time with maximum accuracy of microseconds
+* Exception objects now remember their error code
+* Added examples/example_sprinkler.cpp
+
+
+git 065eae35cbfcc36f1a945ae3053c80c23f366306
+--------------------------------------------
+* [Peter Gober] Made libDAI build out-of-the-box on Cygwin.
+* [Frederik Eaton] Added Gibbs sampler to algorithms
+* Improved documentation of include/dai/{bipgraph.h, prob.h, smallset.h,
+  var.h, varset.h, factor.h, enum.h} and of examples/example.cpp
+  Merged TODO and FILEFORMAT into doxygen documentation
+* examples/
+  - Moved example.cpp to examples/ 
+  - Added examples/example_bipgraph.cpp
+  - Added examples/example_varset.cpp
+* Interface changes:
+  - Replaced TProb<T>::log0() by TProb<T>::log(true)
+  - Replaced TProb<T>::takeLog0() by TProb<T>::takeLog(true)
+  - Replaced TFactor<T>::log0() by TFactor<T>::log(true)
+  - Removed TProb<T>::hasNonPositives()
+  - Renamed smallSet<T> to SmallSet<T>
+  - Removed TFactor<T>::divided_by, use operator/ instead
+  - Removed TFactor<T>::divide, use operator/= instead
+  - Removed TFactor<T>::partSum(const VarSet&), use marginal(const VarSet&,true) instead
+  - Improved constructors of TProb and TFactor to use iterators instead of pointers
+* Miscellaneous small changes and cleanups:
+  - Changed regression test so that it also works under Windows
+  - Changed output stream operator<< for Var and VarSet
+  - Added TProb::draw() function, which draws a random index
+  - Cleanup of matlab interface code
+  - Small improvement of utils/fginfo
+  - Small cleanup of BP code
+  - Switched Makefile.win to GNU Make syntax
+
+
+libDAI-0.2.2 (2008-09-30)
 -------------------------
 
-* Now compiles also under Visual C++.
-* Added Exceptions framework.
-* Replaced ENUM2,ENUM3,ENUM4,ENUM5,ENUM6 by single DAI_ENUM macro.
-* Removed utils/remove_short_loops and matlab/remove_short_loops.
+New features:
+* Approximate inference methods now report the number of iterations needed.
+* Added damping to various algorithms to improve convergence properties.
 * Added more features to utils/createfg for creating factor graphs.
+* 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, 
@@ -13,102 +94,109 @@ 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++ (thanks to Jiuxiang Hu) and with 
+  GCC under cygwin.
 * Contributions by Peter Gober:
-  - Renamed variable _N in mr.* for compatibility with g++ under cygwin
-* 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
-  - added extra warning checks (-W -Wextra) and fixed resulting warnings
+  - Renamed variable _N in mr.* for compatibility with g++ under cygwin.
+* 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;
+  - added extra warning checks (-W -Wextra) and fixed resulting warnings;
   - dai::TProb: 
-    o removed copy constructor and assignment operators (redundant)
-    o implementation of some methods via STL algorithms
-    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:
+    o removed copy constructor and assignment operators (redundant);
+    o implementation of some methods via STL algorithms;
+    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);
+* Misc contributions by Christian Wojek:
   - New FactorGraph constructor that constructs from given ranges of factors
-    and variables
+    and variables;
   - Optimization of FactorGraph constructors using tr1::unordered_map.
 * 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.
-* 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
-* Interface changes:
-  - VarSet::
-      stateSpace() -> states()
-      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
+* Improved MaxSpanningTreePrims algorithm (uses boost::graph).
+
+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)