1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
5 This file is part of libDAI.
7 libDAI is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 libDAI is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with libDAI; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
26 #include <dai/varset.h>
27 #include <dai/clustergraph.h>
36 ClusterGraph::ClusterGraph( const std::vector
<VarSet
> & cls
) : G(), vars(), clusters() {
37 // construct vars, clusters and edge list
39 foreach( const VarSet
&cl
, cls
) {
40 if( find( clusters
.begin(), clusters
.end(), cl
) == clusters
.end() ) {
42 size_t n2
= clusters
.size();
43 clusters
.push_back( cl
);
44 for( VarSet::const_iterator n
= cl
.begin(); n
!= cl
.end(); n
++ ) {
45 size_t n1
= find( vars
.begin(), vars
.end(), *n
) - vars
.begin();
46 if( n1
== vars
.size() )
49 edges
.push_back( Edge( n1
, n2
) );
51 } // disregard duplicate clusters
54 // Create bipartite graph
55 G
.construct( vars
.size(), clusters
.size(), edges
.begin(), edges
.end() );
59 ClusterGraph
ClusterGraph::VarElim_MinFill() const {
61 ClusterGraph
cl(*this);
66 // Construct set of variable indices
67 set
<size_t> varindices
;
68 for( size_t i
= 0; i
< vars
.size(); ++i
)
69 varindices
.insert( i
);
71 // Do variable elimination
72 while( !varindices
.empty() ) {
73 set
<size_t>::const_iterator lowest
= varindices
.end();
74 size_t lowest_cost
= -1UL;
75 for( set
<size_t>::const_iterator i
= varindices
.begin(); i
!= varindices
.end(); i
++ ) {
76 size_t cost
= cl
.eliminationCost( *i
);
77 if( lowest
== varindices
.end() || lowest_cost
> cost
) {
84 result
.insert( cl
.Delta( i
) );
86 cl
.insert( cl
.delta( i
) );
87 cl
.eraseSubsuming( i
);
89 varindices
.erase( i
);
97 ClusterGraph
ClusterGraph::VarElim( const std::vector
<Var
> & ElimSeq
) const {
99 ClusterGraph
cl(*this);
100 cl
.eraseNonMaximal();
104 // Do variable elimination
105 for( vector
<Var
>::const_iterator n
= ElimSeq
.begin(); n
!= ElimSeq
.end(); n
++ ) {
106 size_t i
= cl
.findVar( *n
);
107 assert( i
!= cl
.vars
.size() );
109 result
.insert( cl
.Delta(i
) );
111 cl
.insert( cl
.delta(i
) );
112 cl
.eraseSubsuming( i
);
113 cl
.eraseNonMaximal();
120 } // end of namespace dai