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( const std::vector
<VarSet
> & cls
) : G(), vars(), clusters() {
36 // construct vars, clusters and edge list
38 foreach( const VarSet
&cl
, cls
) {
39 if( find( clusters
.begin(), clusters
.end(), cl
) == clusters
.end() ) {
41 size_t n2
= clusters
.size();
42 clusters
.push_back( cl
);
43 for( VarSet::const_iterator n
= cl
.begin(); n
!= cl
.end(); n
++ ) {
44 size_t n1
= find( vars
.begin(), vars
.end(), *n
) - vars
.begin();
45 if( n1
== vars
.size() )
48 edges
.push_back( Edge( n1
, n2
) );
50 } // disregard duplicate clusters
53 // Create bipartite graph
54 G
.construct( vars
.size(), clusters
.size(), edges
.begin(), edges
.end() );
58 ClusterGraph
ClusterGraph::VarElim_MinFill() const {
60 ClusterGraph
cl(*this);
65 // Construct set of variable indices
66 set
<size_t> varindices
;
67 for( size_t i
= 0; i
< vars
.size(); ++i
)
68 varindices
.insert( i
);
70 // Do variable elimination
71 while( !varindices
.empty() ) {
72 set
<size_t>::const_iterator lowest
= varindices
.end();
73 size_t lowest_cost
= -1UL;
74 for( set
<size_t>::const_iterator i
= varindices
.begin(); i
!= varindices
.end(); i
++ ) {
75 size_t cost
= cl
.eliminationCost( *i
);
76 if( lowest
== varindices
.end() || lowest_cost
> cost
) {
83 result
.insert( cl
.Delta( i
) );
85 cl
.insert( cl
.delta( i
) );
86 cl
.eraseSubsuming( i
);
88 varindices
.erase( i
);
96 ClusterGraph
ClusterGraph::VarElim( const std::vector
<Var
> & ElimSeq
) const {
98 ClusterGraph
cl(*this);
103 // Do variable elimination
104 for( vector
<Var
>::const_iterator n
= ElimSeq
.begin(); n
!= ElimSeq
.end(); n
++ ) {
105 size_t i
= cl
.findVar( *n
);
106 assert( i
!= cl
.vars
.size() );
108 result
.insert( cl
.Delta(i
) );
110 cl
.insert( cl
.delta(i
) );
111 cl
.eraseSubsuming( i
);
112 cl
.eraseNonMaximal();
119 } // end of namespace dai