1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
4 This file is part of libDAI.
6 libDAI is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 libDAI is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with libDAI; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25 #include <dai/varset.h>
26 #include <dai/clustergraph.h>
35 ClusterGraph
ClusterGraph::VarElim( const std::vector
<Var
> & ElimSeq
) const {
36 const long verbose
= 0;
39 ClusterGraph
_Cl(*this);
42 _Cl
.eraseNonMaximal();
44 // Do variable elimination
45 for( vector
<Var
>::const_iterator n
= ElimSeq
.begin(); n
!= ElimSeq
.end(); n
++ ) {
46 assert( _Cl
.vars() && *n
);
49 cout
<< "Cost of eliminating " << *n
<< ": " << _Cl
.eliminationCost( *n
) << " new edges" << endl
;
51 result
.insert( _Cl
.Delta(*n
) );
54 cout
<< "_Cl = " << _Cl
<< endl
;
57 cout
<< "After inserting " << _Cl
.delta(*n
) << ", _Cl = ";
58 _Cl
.insert( _Cl
.delta(*n
) );
63 cout
<< "After erasing clusters that contain " << *n
<< ", _Cl = ";
64 _Cl
.eraseSubsuming( *n
);
69 cout
<< "After erasing nonmaximal clusters, _Cl = ";
70 _Cl
.eraseNonMaximal();
79 ClusterGraph
ClusterGraph::VarElim_MinFill() const {
80 const long verbose
= 0;
83 ClusterGraph
_Cl(*this);
84 VarSet
_vars( vars() );
87 _Cl
.eraseNonMaximal();
89 // Do variable elimination
90 while( !_vars
.empty() ) {
92 cout
<< "Var Eliminiation cost" << endl
;
93 VarSet::const_iterator lowest
= _vars
.end();
94 size_t lowest_cost
= -1UL;
95 for( VarSet::const_iterator n
= _vars
.begin(); n
!= _vars
.end(); n
++ ) {
96 size_t cost
= _Cl
.eliminationCost( *n
);
98 cout
<< *n
<< " " << cost
<< endl
;
99 if( lowest
== _vars
.end() || lowest_cost
> cost
) {
107 cout
<< "Lowest: " << n
<< " (" << lowest_cost
<< ")" << endl
;
109 result
.insert( _Cl
.Delta(n
) );
111 _Cl
.insert( _Cl
.delta(n
) );
112 _Cl
.eraseSubsuming( n
);
113 _Cl
.eraseNonMaximal();
122 } // end of namespace dai