libDAI
|
00001 /* This file is part of libDAI - http://www.libdai.org/ 00002 * 00003 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved. 00004 * 00005 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file. 00006 */ 00007 00008 00011 00012 00013 #ifndef __defined_libdai_jtree_h 00014 #define __defined_libdai_jtree_h 00015 00016 00017 #include <vector> 00018 #include <string> 00019 #include <dai/daialg.h> 00020 #include <dai/varset.h> 00021 #include <dai/regiongraph.h> 00022 #include <dai/factorgraph.h> 00023 #include <dai/clustergraph.h> 00024 #include <dai/weightedgraph.h> 00025 #include <dai/enum.h> 00026 #include <dai/properties.h> 00027 00028 00029 namespace dai { 00030 00031 00033 00041 class JTree : public DAIAlgRG { 00042 private: 00044 std::vector<std::vector<Factor> > _mes; 00045 00047 Real _logZ; 00048 00049 public: 00051 RootedTree RTree; 00052 00054 std::vector<Factor> Qa; 00055 00057 std::vector<Factor> Qb; 00058 00060 struct Properties { 00062 00066 DAI_ENUM(UpdateType,HUGIN,SHSH); 00067 00069 00073 DAI_ENUM(InfType,SUMPROD,MAXPROD); 00074 00076 00085 DAI_ENUM(HeuristicType,MINNEIGHBORS,MINWEIGHT,MINFILL,WEIGHTEDMINFILL); 00086 00088 size_t verbose; 00089 00091 UpdateType updates; 00092 00094 InfType inference; 00095 00097 HeuristicType heuristic; 00098 00100 size_t maxmem; 00101 } props; 00102 00103 public: 00105 00106 00107 JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {} 00108 00110 00114 JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true ); 00116 00117 00119 00120 virtual JTree* clone() const { return new JTree(*this); } 00121 virtual JTree* construct( const FactorGraph &fg, const PropertySet &opts ) const { return new JTree( fg, opts ); } 00122 virtual std::string name() const { return "JTREE"; } 00123 virtual Factor belief( const VarSet &vs ) const; 00124 virtual std::vector<Factor> beliefs() const; 00125 virtual Real logZ() const; 00128 std::vector<std::size_t> findMaximum() const; 00129 virtual void init() {} 00130 virtual void init( const VarSet &/*ns*/ ) {} 00131 virtual Real run(); 00132 virtual Real maxDiff() const { return 0.0; } 00133 virtual size_t Iterations() const { return 1UL; } 00134 virtual void setProperties( const PropertySet &opts ); 00135 virtual PropertySet getProperties() const; 00136 virtual std::string printProperties() const; 00138 00139 00141 00142 00143 00156 void construct( const FactorGraph &fg, const std::vector<VarSet> &cl, bool verify=false ); 00157 00159 00162 void GenerateJT( const FactorGraph &fg, const std::vector<VarSet> &cl ); 00163 00165 const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; } 00167 Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; } 00168 00170 00172 void runHUGIN(); 00173 00175 00177 void runShaferShenoy(); 00178 00180 00187 size_t findEfficientTree( const VarSet& vs, RootedTree &Tree, size_t PreviousRoot=(size_t)-1 ) const; 00188 00190 00192 Factor calcMarginal( const VarSet& vs ); 00194 }; 00195 00196 00198 00205 std::pair<size_t,BigInt> boundTreewidth( const FactorGraph &fg, greedyVariableElimination::eliminationCostFunction fn, size_t maxStates=0 ); 00206 00207 00208 } // end of namespace dai 00209 00210 00211 #endif