Generalized VarSet to "template<typename T> small_set<T>"
[libdai.git] / src / clustergraph.cpp
1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
3
4 This file is part of libDAI.
5
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.
10
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.
15
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
19 */
20
21
22 #include <set>
23 #include <vector>
24 #include <iostream>
25 #include <dai/varset.h>
26 #include <dai/clustergraph.h>
27
28
29 namespace dai {
30
31
32 using namespace std;
33
34
35 ClusterGraph::ClusterGraph( const std::vector<VarSet> & cls ) : G(), vars(), clusters() {
36 // construct vars, clusters and edge list
37 vector<Edge> edges;
38 foreach( const VarSet &cl, cls ) {
39 if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
40 // add cluster
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() )
46 // add variable
47 vars.push_back( *n );
48 edges.push_back( Edge( n1, n2 ) );
49 }
50 } // disregard duplicate clusters
51 }
52
53 // Create bipartite graph
54 G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() );
55 }
56
57
58 ClusterGraph ClusterGraph::VarElim_MinFill() const {
59 // Make a copy
60 ClusterGraph cl(*this);
61 cl.eraseNonMaximal();
62
63 ClusterGraph result;
64
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 );
69
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 ) {
77 lowest = i;
78 lowest_cost = cost;
79 }
80 }
81 size_t i = *lowest;
82
83 result.insert( cl.Delta( i ) );
84
85 cl.insert( cl.delta( i ) );
86 cl.eraseSubsuming( i );
87 cl.eraseNonMaximal();
88 varindices.erase( i );
89 }
90
91 return result;
92 }
93
94
95
96 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
97 // Make a copy
98 ClusterGraph cl(*this);
99 cl.eraseNonMaximal();
100
101 ClusterGraph result;
102
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() );
107
108 result.insert( cl.Delta(i) );
109
110 cl.insert( cl.delta(i) );
111 cl.eraseSubsuming( i );
112 cl.eraseNonMaximal();
113 }
114
115 return result;
116 }
117
118
119 } // end of namespace dai