1 /* This file is part of libDAI - http://www.libdai.org/
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
11 #include <dai/factorgraph.h>
12 #include <dai/jtree.h>
19 void findLoopClusters( const FactorGraph
& fg
, std::set
<VarSet
> &allcl
, VarSet newcl
, const Var
& root
, size_t length
, VarSet vars
) {
20 for( VarSet::const_iterator in
= vars
.begin(); in
!= vars
.end(); in
++ ) {
21 VarSet ind
= fg
.delta( *in
);
22 if( (newcl
.size()) >= 2 && ind
.contains( root
) ) {
23 allcl
.insert( newcl
| *in
);
26 findLoopClusters( fg
, allcl
, newcl
| *in
, root
, length
- 1, ind
/ newcl
);
31 size_t countLoops( const FactorGraph
& fg
, size_t loopdepth
) {
33 for( vector
<Var
>::const_iterator i0
= fg
.vars().begin(); i0
!= fg
.vars().end(); i0
++ ) {
34 VarSet i0d
= fg
.delta(*i0
);
36 findLoopClusters( fg
, loops
, *i0
, *i0
, loopdepth
- 1, i0d
);
42 bool hasShortLoops( const std::vector
<Factor
> &P
) {
44 vector
<Factor
>::const_iterator I
, J
;
45 for( I
= P
.begin(); I
!= P
.end(); I
++ ) {
48 for( ; J
!= P
.end(); J
++ )
49 if( (I
->vars() & J
->vars()).size() >= 2 ) {
60 bool hasNegatives( const std::vector
<Factor
> &P
) {
62 for( size_t I
= 0; I
< P
.size(); I
++ )
63 if( P
[I
].hasNegatives() ) {
71 int main( int argc
, char *argv
[] ) {
73 // Display help message if number of command line arguments is incorrect
74 cout
<< "This program is part of libDAI - http://www.libdai.org/" << endl
<< endl
;
75 cout
<< "Usage: ./fginfo <in.fg> <maxstates>" << endl
<< endl
;
76 cout
<< "Reports some detailed information about the factor graph <in.fg>." << endl
;
77 cout
<< "Also calculates treewidth, with maximum total number of states" << endl
;
78 cout
<< "given by <maxstates>, where 0 means unlimited." << endl
<< endl
;
83 char *infile
= argv
[1];
84 size_t maxstates
= fromString
<size_t>( argv
[2] );
85 fg
.ReadFromFile( infile
);
87 // Output various statistics
88 cout
<< "Number of variables: " << fg
.nrVars() << endl
;
89 cout
<< "Number of factors: " << fg
.nrFactors() << endl
;
90 cout
<< "Connected: " << fg
.isConnected() << endl
;
91 cout
<< "Tree: " << fg
.isTree() << endl
;
92 cout
<< "Has short loops: " << hasShortLoops(fg
.factors()) << endl
;
93 cout
<< "Has negatives: " << hasNegatives(fg
.factors()) << endl
;
94 cout
<< "Binary variables? " << fg
.isBinary() << endl
;
95 cout
<< "Pairwise interactions? " << fg
.isPairwise() << endl
;
97 // Calculate treewidth using various heuristics
99 std::pair
<size_t,BigInt
> tw
;
100 cout
<< "Treewidth (MinNeighbors): ";
102 tw
= boundTreewidth(fg
, &eliminationCost_MinNeighbors
, maxstates
);
103 cout
<< tw
.first
<< " (" << tw
.second
<< " states)" << endl
;
104 } catch( Exception
&e
) {
105 if( e
.getCode() == Exception::OUT_OF_MEMORY
)
106 cout
<< "> " << maxstates
<< endl
;
108 cout
<< "an exception occurred" << endl
;
111 cout
<< "Treewidth (MinWeight): ";
113 tw
= boundTreewidth(fg
, &eliminationCost_MinWeight
, maxstates
);
114 cout
<< tw
.first
<< " (" << tw
.second
<< " states)" << endl
;
115 } catch( Exception
&e
) {
116 if( e
.getCode() == Exception::OUT_OF_MEMORY
)
117 cout
<< "> " << maxstates
<< endl
;
119 cout
<< "an exception occurred" << endl
;
122 cout
<< "Treewidth (MinFill): ";
124 tw
= boundTreewidth(fg
, &eliminationCost_MinFill
, maxstates
);
125 cout
<< tw
.first
<< " (" << tw
.second
<< " states)" << endl
;
126 } catch( Exception
&e
) {
127 if( e
.getCode() == Exception::OUT_OF_MEMORY
)
128 cout
<< "> " << maxstates
<< endl
;
130 cout
<< "an exception occurred" << endl
;
133 cout
<< "Treewidth (WeightedMinFill): ";
135 tw
= boundTreewidth(fg
, &eliminationCost_WeightedMinFill
, maxstates
);
136 cout
<< tw
.first
<< " (" << tw
.second
<< " states)" << endl
;
137 } catch( Exception
&e
) {
138 if( e
.getCode() == Exception::OUT_OF_MEMORY
)
139 cout
<< "> " << maxstates
<< endl
;
141 cout
<< "an exception occurred" << endl
;
145 // Calculate total state space
147 for( size_t i
= 0; i
< fg
.nrVars(); i
++ )
148 stsp
*= fg
.var(i
).states();
149 cout
<< "Total state space: " << stsp
<< endl
;
150 // Output type of factor graph
151 cout
<< "Type: " << (fg
.isPairwise() ? "pairwise" : "higher order") << " interactions, " << (fg
.isBinary() ? "binary" : "nonbinary") << " variables" << endl
;
153 // Calculate complexity for LCBP
154 BigInt cavsum_lcbp
= 0;
155 BigInt cavsum_lcbp2
= 0;
156 BigInt max_Delta_size
= 0;
157 map
<size_t,size_t> cavsizes
;
158 for( size_t i
= 0; i
< fg
.nrVars(); i
++ ) {
159 VarSet di
= fg
.delta(i
);
160 if( cavsizes
.count(di
.size()) )
161 cavsizes
[di
.size()]++;
163 cavsizes
[di
.size()] = 1;
164 BigInt Ds
= fg
.Delta(i
).nrStates();
165 if( Ds
> max_Delta_size
)
167 cavsum_lcbp
+= di
.nrStates();
168 for( VarSet::const_iterator j
= di
.begin(); j
!= di
.end(); j
++ )
169 cavsum_lcbp2
+= j
->states();
171 cout
<< "Maximum pancake has " << max_Delta_size
<< " states" << endl
;
172 cout
<< "LCBP with full cavities needs " << cavsum_lcbp
<< " BP runs" << endl
;
173 cout
<< "LCBP with only pairinteractions needs " << cavsum_lcbp2
<< " BP runs" << endl
;
174 cout
<< "Cavity sizes: ";
175 for( map
<size_t,size_t>::const_iterator it
= cavsizes
.begin(); it
!= cavsizes
.end(); it
++ )
176 cout
<< it
->first
<< "(" << it
->second
<< ") ";
179 // Calculate girth and length of loops
180 if( fg
.isPairwise() ) {
181 bool girth_reached
= false;
183 for( loopdepth
= 2; loopdepth
<= fg
.nrVars() && !girth_reached
; loopdepth
++ ) {
184 size_t nr_loops
= countLoops( fg
, loopdepth
);
185 cout
<< "Loops up to " << loopdepth
<< " variables: " << nr_loops
<< endl
;
187 girth_reached
= true;
190 cout
<< "Girth: " << loopdepth
-1 << endl
;
192 cout
<< "Girth: infinity" << endl
;
195 // Output factor state spaces
196 map
<size_t,size_t> facsizes
;
197 for( size_t I
= 0; I
< fg
.nrFactors(); I
++ ) {
198 size_t Isize
= fg
.factor(I
).vars().size();
199 if( facsizes
.count( Isize
) )
204 cout
<< "Factor sizes: ";
205 for( map
<size_t,size_t>::const_iterator it
= facsizes
.begin(); it
!= facsizes
.end(); it
++ )
206 cout
<< it
->first
<< "(" << it
->second
<< ") ";