1 /* This file is part of libDAI - http://www.libdai.org/
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
14 #include <dai/factorgraph.h>
15 #include <dai/jtree.h>
22 void findLoopClusters( const FactorGraph
& fg
, std::set
<VarSet
> &allcl
, VarSet newcl
, const Var
& root
, size_t length
, VarSet vars
) {
23 for( VarSet::const_iterator in
= vars
.begin(); in
!= vars
.end(); in
++ ) {
24 VarSet ind
= fg
.delta( *in
);
25 if( (newcl
.size()) >= 2 && ind
.contains( root
) ) {
26 allcl
.insert( newcl
| *in
);
29 findLoopClusters( fg
, allcl
, newcl
| *in
, root
, length
- 1, ind
/ newcl
);
34 size_t countLoops( const FactorGraph
& fg
, size_t loopdepth
) {
36 for( vector
<Var
>::const_iterator i0
= fg
.vars().begin(); i0
!= fg
.vars().end(); i0
++ ) {
37 VarSet i0d
= fg
.delta(*i0
);
39 findLoopClusters( fg
, loops
, *i0
, *i0
, loopdepth
- 1, i0d
);
45 bool hasShortLoops( const std::vector
<Factor
> &P
) {
47 vector
<Factor
>::const_iterator I
, J
;
48 for( I
= P
.begin(); I
!= P
.end(); I
++ ) {
51 for( ; J
!= P
.end(); J
++ )
52 if( (I
->vars() & J
->vars()).size() >= 2 ) {
63 bool hasNegatives( const std::vector
<Factor
> &P
) {
65 for( size_t I
= 0; I
< P
.size(); I
++ )
66 if( P
[I
].hasNegatives() ) {
74 int main( int argc
, char *argv
[] ) {
76 cout
<< "Usage: " << argv
[0] << " <in.fg> <tw>" << endl
<< endl
;
77 cout
<< "Reports some characteristics of the .fg network." << endl
;
78 cout
<< "Also calculates treewidth (which may take some time) unless <tw> == 0." << endl
;
83 char *infile
= argv
[1];
84 int calc_tw
= atoi(argv
[2]);
85 fg
.ReadFromFile( infile
);
87 cout
<< "Number of variables: " << fg
.nrVars() << endl
;
88 cout
<< "Number of factors: " << fg
.nrFactors() << endl
;
89 cout
<< "Connected: " << fg
.isConnected() << endl
;
90 cout
<< "Tree: " << fg
.isTree() << endl
;
91 cout
<< "Has short loops: " << hasShortLoops(fg
.factors()) << endl
;
92 cout
<< "Has negatives: " << hasNegatives(fg
.factors()) << endl
;
93 cout
<< "Binary variables? " << fg
.isBinary() << endl
;
94 cout
<< "Pairwise interactions? " << fg
.isPairwise() << endl
;
96 std::pair
<size_t,size_t> tw
= boundTreewidth(fg
);
97 cout
<< "Treewidth: " << tw
.first
<< endl
;
98 cout
<< "Largest cluster for JTree has " << tw
.second
<< " states " << endl
;
100 long double stsp
= 1.0;
101 for( size_t i
= 0; i
< fg
.nrVars(); i
++ )
102 stsp
*= fg
.var(i
).states();
103 cout
<< "Total state space: " << stsp
<< endl
;
105 long double cavsum_lcbp
= 0.0;
106 long double cavsum_lcbp2
= 0.0;
107 size_t max_Delta_size
= 0;
108 map
<size_t,size_t> cavsizes
;
109 for( size_t i
= 0; i
< fg
.nrVars(); i
++ ) {
110 VarSet di
= fg
.delta(i
);
111 if( cavsizes
.count(di
.size()) )
112 cavsizes
[di
.size()]++;
114 cavsizes
[di
.size()] = 1;
115 size_t Ds
= fg
.Delta(i
).nrStates();
116 if( Ds
> max_Delta_size
)
118 cavsum_lcbp
+= di
.nrStates();
119 for( VarSet::const_iterator j
= di
.begin(); j
!= di
.end(); j
++ )
120 cavsum_lcbp2
+= j
->states();
122 cout
<< "Maximum pancake has " << max_Delta_size
<< " states" << endl
;
123 cout
<< "LCBP with full cavities needs " << cavsum_lcbp
<< " BP runs" << endl
;
124 cout
<< "LCBP with only pairinteractions needs " << cavsum_lcbp2
<< " BP runs" << endl
;
125 cout
<< "Cavity sizes: ";
126 for( map
<size_t,size_t>::const_iterator it
= cavsizes
.begin(); it
!= cavsizes
.end(); it
++ )
127 cout
<< it
->first
<< "(" << it
->second
<< ") ";
130 cout
<< "Type: " << (fg
.isPairwise() ? "pairwise" : "higher order") << " interactions, " << (fg
.isBinary() ? "binary" : "nonbinary") << " variables" << endl
;
132 if( fg
.isPairwise() ) {
133 bool girth_reached
= false;
135 for( loopdepth
= 2; loopdepth
<= fg
.nrVars() && !girth_reached
; loopdepth
++ ) {
136 size_t nr_loops
= countLoops( fg
, loopdepth
);
137 cout
<< "Loops up to " << loopdepth
<< " variables: " << nr_loops
<< endl
;
139 girth_reached
= true;
142 cout
<< "Girth: " << loopdepth
-1 << endl
;
144 cout
<< "Girth: infinity" << endl
;
147 map
<size_t,size_t> facsizes
;
148 for( size_t I
= 0; I
< fg
.nrFactors(); I
++ ) {
149 size_t Isize
= fg
.factor(I
).vars().size();
150 if( facsizes
.count( Isize
) )
155 cout
<< "Factor sizes: ";
156 for( map
<size_t,size_t>::const_iterator it
= facsizes
.begin(); it
!= facsizes
.end(); it
++ )
157 cout
<< it
->first
<< "(" << it
->second
<< ") ";