Merge branch 'pletscher'
[libdai.git] / src / clustergraph.cpp
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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.
6 *
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 #include <set>
13 #include <vector>
14 #include <iostream>
15 #include <dai/varset.h>
16 #include <dai/clustergraph.h>
17
18
19 namespace dai {
20
21
22 using namespace std;
23
24
25 ClusterGraph::ClusterGraph( const std::vector<VarSet> & cls ) : G(), vars(), clusters() {
26 // construct vars, clusters and edge list
27 vector<Edge> edges;
28 foreach( const VarSet &cl, cls ) {
29 if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
30 // add cluster
31 size_t n2 = clusters.size();
32 clusters.push_back( cl );
33 for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
34 size_t n1 = find( vars.begin(), vars.end(), *n ) - vars.begin();
35 if( n1 == vars.size() )
36 // add variable
37 vars.push_back( *n );
38 edges.push_back( Edge( n1, n2 ) );
39 }
40 } // disregard duplicate clusters
41 }
42
43 // Create bipartite graph
44 G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() );
45 }
46
47
48 ClusterGraph ClusterGraph::VarElim_MinFill() const {
49 // Make a copy
50 ClusterGraph cl(*this);
51 cl.eraseNonMaximal();
52
53 ClusterGraph result;
54
55 // Construct set of variable indices
56 set<size_t> varindices;
57 for( size_t i = 0; i < vars.size(); ++i )
58 varindices.insert( i );
59
60 // Do variable elimination
61 while( !varindices.empty() ) {
62 set<size_t>::const_iterator lowest = varindices.end();
63 size_t lowest_cost = -1UL;
64 for( set<size_t>::const_iterator i = varindices.begin(); i != varindices.end(); i++ ) {
65 size_t cost = cl.eliminationCost( *i );
66 if( lowest == varindices.end() || lowest_cost > cost ) {
67 lowest = i;
68 lowest_cost = cost;
69 }
70 }
71 size_t i = *lowest;
72
73 result.insert( cl.Delta( i ) );
74
75 cl.insert( cl.delta( i ) );
76 cl.eraseSubsuming( i );
77 cl.eraseNonMaximal();
78 varindices.erase( i );
79 }
80
81 return result;
82 }
83
84
85
86 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
87 // Make a copy
88 ClusterGraph cl(*this);
89 cl.eraseNonMaximal();
90
91 ClusterGraph result;
92
93 // Do variable elimination
94 for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
95 size_t i = cl.findVar( *n );
96 DAI_ASSERT( i != cl.vars.size() );
97
98 result.insert( cl.Delta(i) );
99
100 cl.insert( cl.delta(i) );
101 cl.eraseSubsuming( i );
102 cl.eraseNonMaximal();
103 }
104
105 return result;
106 }
107
108
109 } // end of namespace dai