Merge branch 'no-edges2'
[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::VarElim( const vector<Var> & ElimSeq ) const {
36 const long verbose = 0;
37
38 // Make a copy
39 ClusterGraph _Cl(*this);
40
41 ClusterGraph result;
42 _Cl.eraseNonMaximal();
43
44 // Do variable elimination
45 for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
46 assert( _Cl.vars() && *n );
47
48 if( verbose >= 1 )
49 cout << "Cost of eliminating " << *n << ": " << _Cl.eliminationCost( *n ) << " new edges" << endl;
50
51 result.insert( _Cl.Delta(*n) );
52
53 if( verbose >= 1 )
54 cout << "_Cl = " << _Cl << endl;
55
56 if( verbose >= 1 )
57 cout << "After inserting " << _Cl.delta(*n) << ", _Cl = ";
58 _Cl.insert( _Cl.delta(*n) );
59 if( verbose >= 1 )
60 cout << _Cl << endl;
61
62 if( verbose >= 1 )
63 cout << "After erasing clusters that contain " << *n << ", _Cl = ";
64 _Cl.eraseSubsuming( *n );
65 if( verbose >= 1 )
66 cout << _Cl << endl;
67
68 if( verbose >= 1 )
69 cout << "After erasing nonmaximal clusters, _Cl = ";
70 _Cl.eraseNonMaximal();
71 if( verbose >= 1 )
72 cout << _Cl << endl;
73 }
74
75 return result;
76 }
77
78
79 ClusterGraph ClusterGraph::VarElim_MinFill() const {
80 const long verbose = 0;
81
82 // Make a copy
83 ClusterGraph _Cl(*this);
84 VarSet _vars( vars() );
85
86 ClusterGraph result;
87 _Cl.eraseNonMaximal();
88
89 // Do variable elimination
90 while( !_vars.empty() ) {
91 if( verbose >= 1 )
92 cout << "Var Eliminiation cost" << endl;
93 VarSet::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 );
97 if( verbose >= 1 )
98 cout << *n << " " << cost << endl;
99 if( lowest == _vars.end() || lowest_cost > cost ) {
100 lowest = n;
101 lowest_cost = cost;
102 }
103 }
104 Var n = *lowest;
105
106 if( verbose >= 1 )
107 cout << "Lowest: " << n << " (" << lowest_cost << ")" << endl;
108
109 result.insert( _Cl.Delta(n) );
110
111 _Cl.insert( _Cl.delta(n) );
112 _Cl.eraseSubsuming( n );
113 _Cl.eraseNonMaximal();
114 _vars /= n;
115
116 }
117
118 return result;
119 }
120
121
122 } // end of namespace dai