1 /* This file is part of libDAI - http://www.libdai.org/
2 *
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
9 */
12 #include <algorithm>
13 #include <cmath>
14 #include <boost/dynamic_bitset.hpp>
15 #include <dai/regiongraph.h>
16 #include <dai/factorgraph.h>
17 #include <dai/clustergraph.h>
20 namespace dai {
23 using namespace std;
26 void RegionGraph::construct( const FactorGraph &fg, const std::vector<VarSet> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges ) {
27 // Copy factor graph structure
28 FactorGraph::operator=( fg );
30 // Copy inner regions
31 _IRs = irs;
33 // Construct outer regions (giving them counting number 1.0)
34 _ORs.clear();
35 _ORs.reserve( ors.size() );
36 foreach( const VarSet &alpha, ors )
37 _ORs.push_back( FRegion(Factor(alpha, 1.0), 1.0) );
39 // For each factor, find an outer region that subsumes that factor.
40 // Then, multiply the outer region with that factor.
41 _fac2OR.clear();
42 _fac2OR.reserve( nrFactors() );
43 for( size_t I = 0; I < nrFactors(); I++ ) {
44 size_t alpha;
45 for( alpha = 0; alpha < nrORs(); alpha++ )
46 if( OR(alpha).vars() >> factor(I).vars() ) {
47 _fac2OR.push_back( alpha );
48 break;
49 }
50 DAI_ASSERT( alpha != nrORs() );
51 }
52 recomputeORs();
54 // Create bipartite graph
55 _G.construct( nrORs(), nrIRs(), edges.begin(), edges.end() );
56 }
59 void RegionGraph::constructCVM( const FactorGraph &fg, const std::vector<VarSet> &cl ) {
60 // Retain only maximal clusters
61 ClusterGraph cg( cl );
62 cg.eraseNonMaximal();
64 // Create inner regions - first pass
65 set<VarSet> betas;
66 for( size_t alpha = 0; alpha < cg.nrClusters(); alpha++ )
67 for( size_t alpha2 = alpha; (++alpha2) != cg.nrClusters(); ) {
68 VarSet intersection = cg.cluster(alpha) & cg.cluster(alpha2);
69 if( intersection.size() > 0 )
70 betas.insert( intersection );
71 }
73 // Create inner regions - subsequent passes
74 set<VarSet> new_betas;
75 do {
76 new_betas.clear();
77 for( set<VarSet>::const_iterator gamma = betas.begin(); gamma != betas.end(); gamma++ )
78 for( set<VarSet>::const_iterator gamma2 = gamma; (++gamma2) != betas.end(); ) {
79 VarSet intersection = (*gamma) & (*gamma2);
80 if( (intersection.size() > 0) && (betas.count(intersection) == 0) )
81 new_betas.insert( intersection );
82 }
83 betas.insert(new_betas.begin(), new_betas.end());
84 } while( new_betas.size() );
86 // Create inner regions - final phase
87 vector<Region> irs;
88 irs.reserve( betas.size() );
89 for( set<VarSet>::const_iterator beta = betas.begin(); beta != betas.end(); beta++ )
90 irs.push_back( Region(*beta,0.0) );
92 // Create edges
93 vector<pair<size_t,size_t> > edges;
94 for( size_t beta = 0; beta < irs.size(); beta++ )
95 for( size_t alpha = 0; alpha < cg.nrClusters(); alpha++ )
96 if( cg.cluster(alpha) >> irs[beta] )
97 edges.push_back( pair<size_t,size_t>(alpha,beta) );
99 // Construct region graph
100 construct( fg, cg.clusters(), irs, edges );
102 // Calculate counting numbers
103 calcCVMCountingNumbers();
104 }
107 void RegionGraph::calcCVMCountingNumbers() {
108 // Calculates counting numbers of inner regions based upon counting numbers of outer regions
110 vector<vector<size_t> > ancestors(nrIRs());
111 boost::dynamic_bitset<> assigned(nrIRs());
112 for( size_t beta = 0; beta < nrIRs(); beta++ ) {
113 IR(beta).c() = 0.0;
114 for( size_t beta2 = 0; beta2 < nrIRs(); beta2++ )
115 if( (beta2 != beta) && IR(beta2) >> IR(beta) )
116 ancestors[beta].push_back(beta2);
117 }
119 bool new_counting;
120 do {
121 new_counting = false;
122 for( size_t beta = 0; beta < nrIRs(); beta++ ) {
123 if( !assigned[beta] ) {
124 bool has_unassigned_ancestor = false;
125 for( vector<size_t>::const_iterator beta2 = ancestors[beta].begin(); (beta2 != ancestors[beta].end()) && !has_unassigned_ancestor; beta2++ )
126 if( !assigned[*beta2] )
127 has_unassigned_ancestor = true;
128 if( !has_unassigned_ancestor ) {
129 Real c = 1.0;
130 foreach( const Neighbor &alpha, nbIR(beta) )
131 c -= OR(alpha).c();
132 for( vector<size_t>::const_iterator beta2 = ancestors[beta].begin(); beta2 != ancestors[beta].end(); beta2++ )
133 c -= IR(*beta2).c();
134 IR(beta).c() = c;
135 assigned.set(beta, true);
136 new_counting = true;
137 }
138 }
139 }
140 } while( new_counting );
141 }
144 bool RegionGraph::checkCountingNumbers() const {
145 // Checks whether the counting numbers satisfy the fundamental relation
147 bool all_valid = true;
148 for( vector<Var>::const_iterator n = vars().begin(); n != vars().end(); n++ ) {
149 Real c_n = 0.0;
150 for( size_t alpha = 0; alpha < nrORs(); alpha++ )
151 if( OR(alpha).vars().contains( *n ) )
152 c_n += OR(alpha).c();
153 for( size_t beta = 0; beta < nrIRs(); beta++ )
154 if( IR(beta).contains( *n ) )
155 c_n += IR(beta).c();
156 if( fabs(c_n - 1.0) > 1e-15 ) {
157 all_valid = false;
158 cerr << "WARNING: counting numbers do not satisfy relation for " << *n << "(c_n = " << c_n << ")." << endl;
159 }
160 }
162 return all_valid;
163 }
166 void RegionGraph::recomputeORs() {
167 for( size_t alpha = 0; alpha < nrORs(); alpha++ )
168 OR(alpha).fill( 1.0 );
169 for( size_t I = 0; I < nrFactors(); I++ )
170 if( fac2OR(I) != -1U )
171 OR( fac2OR(I) ) *= factor( I );
172 }
175 void RegionGraph::recomputeORs( const VarSet &ns ) {
176 for( size_t alpha = 0; alpha < nrORs(); alpha++ )
177 if( OR(alpha).vars().intersects( ns ) )
178 OR(alpha).fill( 1.0 );
179 for( size_t I = 0; I < nrFactors(); I++ )
180 if( fac2OR(I) != -1U )
181 if( OR( fac2OR(I) ).vars().intersects( ns ) )
182 OR( fac2OR(I) ) *= factor( I );
183 }
186 void RegionGraph::recomputeOR( size_t I ) {
187 DAI_ASSERT( I < nrFactors() );
188 if( fac2OR(I) != -1U ) {
189 size_t alpha = fac2OR(I);
190 OR(alpha).fill( 1.0 );
191 for( size_t J = 0; J < nrFactors(); J++ )
192 if( fac2OR(J) == alpha )
193 OR(alpha) *= factor( J );
194 }
195 }
198 /// Send RegionGraph to output stream
199 ostream & operator << (ostream & os, const RegionGraph & rg) {
200 os << "digraph RegionGraph {" << endl;
201 os << "node[shape=box];" << endl;
202 for( size_t alpha = 0; alpha < rg.nrORs(); alpha++ )
203 os << "\ta" << alpha << " [label=\"a" << alpha << ": " << rg.OR(alpha).vars() << ", c=" << rg.OR(alpha).c() << "\"];" << endl;
204 os << "node[shape=ellipse];" << endl;
205 for( size_t beta = 0; beta < rg.nrIRs(); beta++ )
206 os << "\tb" << beta << " [label=\"b" << beta << ": " << (VarSet)rg.IR(beta) << ", c=" << rg.IR(beta).c() << "\"];" << endl;
207 for( size_t alpha = 0; alpha < rg.nrORs(); alpha++ )
208 foreach( const RegionGraph::Neighbor &beta, rg.nbOR(alpha) )
209 os << "\ta" << alpha << " -> b" << beta << ";" << endl;
210 os << "}" << endl;
211 return os;
212 }
215 } // end of namespace dai